New Distance Concept and Graph Theory Approach for Certain Coding Techniques Design and Analysis

Ouahada, Khmaies; Ferreira, Hendrik C.

doi:10.1515/caim-2019-0012

Abstract

A New graph distance concept introduced for certain coding techniques helped in their design and analysis as in the case of distance-preserving mappings and spectral shaping codes. A graph theoretic construction, mapping binary sequences to permutation sequences and inspired from the k-cube graph has reached the upper bound on the sum of the distances for certain values of the length of the permutation sequence. The new introduced distance concept in the k-cube graph helped better understanding and analyzing for the first time the concept of distance-reducing mappings. A combination of distance and the index-permutation graph concepts helped uncover and verify certain properties of spectral null codes, which were previously difficult to analyze.

References

1. N. Deo, Graph Theory with Applications to Engineering and Computer Science. Dover Publications, 2016.
Search in Google Scholar Back to article
2. J. Susymary and R. Lawrance, Graph theory analysis of protein-protein interaction graphs through clustering method, in 2017 IEEE International Conference on Intellignet Techniques in Control, Optimization and Signal Processing, pp. 1–5, Srivilliputhur, India, March 23–25, 2017.10.1109/ITCOSP.2017.8303125
Search in Google Scholar Back to article
3. K. Ouahada and H. Ferreira, A similation and graph theoretical analysis of certain porperties of spectrall null codebooks, SAIEE Africa Research Journal, vol. 103, no. 3, pp. 106–115, 2012.10.23919/SAIEE.2012.8532162
Search in Google Scholar Back to article
4. K. Ouahada and H. C. Ferreira, A graph theoretic approach for spectral null codes, in Proceedings of the Information Theory Workshop, pp. 369–373, Taormina, Sicily, Italy, October 11-16, 2009.10.1109/ITW.2009.5351185
Search in Google Scholar Back to article
5. A. K. Singh, Error detection and correction by hamming codel, in Proceedings of the 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication, pp. 35–37, Bambhori, Jalgoan, India, December 22-24, 2016.10.1109/ICGTSPICC.2016.7955265
Search in Google Scholar Back to article
6. A. Wachter-Zeh, List decoding of insertions and deletions, IEEE Transactions on Information Theory, vol. PP, no. 99, p. 1, 2017.10.1109/ISIT.2017.8006869
Search in Google Scholar Back to article
7. K. Ouahada, T. G. Swart, and H. C. Ferreira, Binary permutation sequences as subsets of levenshtein codes and higher order spectral nulls codes, in 2006 IEEE Information Theory Workshop - ITW ’06 Chengdu, pp. 535–539, Chengdu, China, Oct. 2006.10.1109/ITW2.2006.323690
Search in Google Scholar Back to article
8. A. Viterbi and J. Omura, Principles of Digital Communication and Coding. McGraw-Hill Kogakusha LTD, Tokyo Japan, 1979.
Search in Google Scholar Back to article
9. A. J. H. Vinck and H. C. Ferreira, Permutation trellis codes, in in Proceedings of the International Symposium on Information Theory (ISIT 2001), p. 279, Washington, DC,USA, June 24-29, 2001.
Search in Google Scholar Back to article
10. A. J. H. Vinck, Coded modulation for powerline communications, AEU International Journal of Electronics and Communications, vol. 54, no. 1, pp. 45–49, 2000.
Search in Google Scholar Back to article
11. H. C. Ferreira, A. J. H. Vinck, T. G. Swart, and I. de Beer, Permutation trellis codes, IEEE Trans. Commun., vol. 53, no. 11, pp. 1782–1789, 2005.
Search in Google Scholar Back to article
12. T. G. Swart and H. C. Ferreira, A generalized upper bound and a multilevel construction for distance-preserving mappings, IEEE Trans. Inf. Theory, vol. 52, no. 8, pp. 3685–3695, 2006.
Search in Google Scholar Back to article
13. K. Ouahada and H. C. Ferreira, k-cube construction mappings from binary vectors to permutation sequences, in in proceedings of IEEE International Symposium on Information Theory, p. 279, Seoul, South Korea, June 28–July 3, 2009.10.1109/ISIT.2009.5205703
Search in Google Scholar Back to article
14. W. J. Dally, Express cubes: Improving the performance of k-ary n-cube interconnection networks, IEEE Trans. On Computers, vol. 40, no. 9, pp. 1016–1023, Sept. 1991.
Search in Google Scholar Back to article
15. M. Haynes, Magnetic recording techniques for buried servos, IEEE Transactions on Magnetics, vol. 17, no. 6, pp. 2730–2734, Nov. 198.
Search in Google Scholar Back to article
16. H. C. Ferreira, I. de Beer, and A. J. H. Vinck, Distance preserving mappings onto convolutional codes revisited, in Proceedings of the IEEE Information Theory Workshop, pp. 23–26, Breisach, Germany, Apr. 26–29, 2002.
Search in Google Scholar Back to article
17. E. Gorog, Alphabets with desirable frequency spectrum properties, IBM J. Res. Develop, vol. 12, pp. 234–241, May 1968.10.1147/rd.123.0234
Search in Google Scholar Back to article
18. K. Ouahada, T. G. Swart, and H. C. Ferreira, Spectral shaping permutation distance-preserving mappings codes, in IEEE Proc. ITW’07 Conf. California, USA, pp. 36–41, California, USA, Sept. 2Ö6, 2007.10.1109/ITW.2007.4313046
Search in Google Scholar Back to article
19. K. A. S. Immink, Codes for mass data storage systems. Shannon Foundation Publishers, The Netherlands, 1999.
Search in Google Scholar Back to article
20. K. A. S. Immink, Spectral null codes, IEEE Transactions on Magnetics, vol. 26, no. 2, pp. 1130–1135, Mar. 1990.
Search in Google Scholar Back to article
21. C. Yeh and B. Parhami, ‘parallel algorithms for index-permutation graphs. an extension of cayley graphs for multiple chip-multiprocessors (mcmp), in International Conference on Parallel Processing, pp. 3–12, California, USA, Sept. 2001.10.1109/ICPP.2001.952041
Search in Google Scholar Back to article
22. L.-H. Chang, C. Wang, P.-N. Chen, Y. S. Han, and V. Y. F. Tan, Distance spectrum formula for the largest minimum hamming distance of finite-length binary block codes, in 2017 IEEE Information Theory Workshop - ITW 2017 Kaohsiung, pp. 419–423, Kaohsiung, Taiwan, Nov. 6–10, 2017.10.1109/ITW.2017.8277923
Search in Google Scholar Back to article

New Distance Concept and Graph Theory Approach for Certain Coding Techniques Design and Analysis

Abstract

Paradigm

My account