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

Abstract

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.