Capacity-Approaching Non-Binary Balanced Codes Using Auxiliary Data

摘要

It is known that, for large user word lengths, the auxiliary data can be used to recover most of the redundancy losses of Knuth’s simple balancing method compared with the optimal redundancy of balanced codes for the binary case. Here, this important result is extended in a number of ways. First, an upper bound for the amount of auxiliary data is derived that is valid for all codeword lengths. This result is primarily of theoretical interest, as it defines the probability distribution of the number of balancing indices that results in optimal redundancy. This result is equally valid for particular non-binary generalizations of Knuth’s balancing method. Second, an asymptotically exact expression for the amount of auxiliary data for the ternary case of a variable length realization of the modified balanced code construction is derived, that, in all respects, is the analogue of the result obtained for the binary case. The derivation is based on a generalization of the binary random walk to the ternary case and a simple modification of an existing generalization of Knuth’s method for the non-binary balanced codes. Finally, a conjecture is proposed regarding the probability distribution of the number of balancing indices for any alphabet size.