Ebenezer ESENOGHO, Hendrik FERREIRA, Elie NGOMSEU MAMBOU

Improving the redundancy of Knuth’s balancing scheme for packet transmission systems

A simple scheme was proposed by Knuth to generate binary balanced codewords from any information word.However, this method is limited in the sense that its redundancy is twice that of the full sets of balanced codes. The gapbetween Knuth’s algorithm’s redundancy and that of the full sets of balanced codes is significantly considerable. Thispaper attempts to reduce that gap. Furthermore, many constructions assume that a full balancing can be performedwithout showing the steps. A full balancing refers to the overall balancing of the encoded information together withthe prefix. We propose an efficient way to perform a full balancing scheme that does not make use of lookup tables orenumerative coding.

PDF

___

[1] Immink K. Coding methods for high-density optical recording, Philips Journal of Research 1986; 41 (4): 410-430.
[2] Leiss E. Data integrity in digital optical disks. IEEE Transactions on Computers 1984; 33 (9): 818-827. doi: 10.1109/TC.1984.1676498
[3] Al-Bassam S, Bose B. Design of efficient error-correcting balanced codes. IEEE Transactions on Computers 1993; 42 (10): 1261-1266. doi: 10.1109/12.257712
[4] Weber J, Immink K, Ferreira H. Error-correcting balanced Knuth codes. IEEE Transactions on Information Theory 2012; 58 (1): 82-89. doi: 10.1109/TIT.2011.2167954
[5] Cattermole K. Principles of digital line coding. International Journal of Electronics 1983; 55 (1): 3-33. doi: 10.1080/00207218308961573
[6] Tabor J. Noise Reduction Using Low Weight and Constant Weight Coding Techniques. Cambridge, MA, USA: MIT Computer Science and Artificial Intelligence Lab, 1990.
[7] Knuth D. Efficient balanced codes. IEEE Transactions on Information Theory 1986; 32 (1): 51-53. doi: 10.1109/TIT.1986.1057136
[8] Weber J, Immink K. Knuth’s balanced codes revisited. IEEE Transactions on Information Theory 2010; 56 (4): 1673-1679. doi: 10.1109/TIT.2010.2040868
[9] Al-Rababa’a A, Dubé D, Chouinard J. Using bit recycling to reduce Knuth’s balanced codes redundancy. In: 2013 13th Canadian Workshop on Information Theory; Toronto, Canada; 2013. pp. 6-11.
[10] Dubé D, Mechqrane M. Almost minimum-redundancy construction of balanced codes using limited-precision integers. In: 2017 15th Canadian Workshop on Information Theory; Quebec City, Canada; 2017. pp. 1-5.
[11] Swart T, Weber J. Binary variable-to-fixed length balancing scheme with simple encoding/decoding. IEEE Communications Letters 2018; 22 (10): 1992-1995. doi: 10.1109/LCOMM.2018.2865350
[12] Rocha V, Lemos-Neto J, Pacheco A. Class of easily implementable fixed-length to variable-length balanced binary line codes. Electronics Letters 2019; 55 (5): 266-268. doi: 10.1049/el.2018.7032
[13] Immink K, Weber J. Very efficient balanced codes. Journal on Selected Areas in Communications 2010; 28 (2): 188-192. doi: 10.1109/JSAC.2010.100207
[14] Chien T. Upper bound on the efficiency of DC-constrained codes. Bell System Technical Journal 1970; 49 (9): 2267-2287. doi: 10.1002/j.1538-7305.1970.tb02525.x
[15] Salkuyeh D. Positive integer powers of the tri-diagonal Toeplitz matrices. International Mathematical Forum 2006; 1 (22): 1061-1065.
[16] Mambou EN, Swart T. Encoding and decoding of balanced q -ary sequences using a Gray code prefix. In: 2016 IEEE International Symposium on Information Theory; Barcelona, Spain; 2016. pp. 380-384.
[17] Mambou EN, Swart T. A construction for balancing non-binary sequences based on Gray code prefixes. IEEE Transactions on Information Theory 2017; 64 (8): 5961-5969. doi: 10.1109/TIT.2017.2766668
[18] Mambou EN, Swart T. Construction of q -ary constant weight sequences using a Knuth-like approach. In: 2017 IEEE International Symposium of Information Theory; Aachen, Germany; 2017. pp. 2028-2032.
[19] Ulrich W. Non-binary error correction codes. Bell System Technical Journal 1957; 36 (6): 1341-1388. doi: 10.1002/j.1538-7305.1957.tb01514.x
[20] Berrou C, Jezequel M, Douillard C, Kerouedan S. The advantages of non-binary turbo codes. In: Proceedings 2001 IEEE Information Theory Workshop; Cairns, Australia; 2001. pp. 61-63.
[21] Pfleschinger S, Declercq D. Getting closer to MIMO capacity with non-binary codes and spatial multiplexing. In: 2010 IEEE Global Telecommunication Conference; Miami, FL, USA; 2010. pp. 1-5.
[22] Karzand M, Telatar E. Polar codes for q-ary source coding. In: 2010 IEEE International Symposium on Information Theory; Austin, TX, USA; 2010. pp. 909-912.