Efficient m-ary balanced codes which are invariant under symbol permutation
Raffaele Mascella, Luca G. Tallini · IEEE Transactions on Computers · 2006
A symbol permutation invariant balanced (SPI-balanced) code over the alphabet Zopfm= {0, 1, ..., m - 1} is a block code over Zopfmsuch that each alphabet symbol occurs as many times as any other symbol in every codeword. For this reason, every permutation among the symbols of the alphabet changes an SPI-balanced code into an SPI-balanced code. This means that SPI-balanced words are "the most balanced" among all possible m-ary balanced word types and this property makes them very attractive from the application perspective. In particular, they can be used to achieve m-ary DC-free communication, to detect/correct asymmetric/unidirectional errors on the m-ary asymmetric/unidirectional channel, to achieve delay-insensitive communication, to maintain data integrity in digital optical disks, and so on. This paper gives some efficient methods to convert (encode) m-ary information sequences into m-ary SPI-balanced codes whose redundancy is equal to roughly double the minimum possible redundancy rmin. It is proven that rminsime [(m - 1)/2]logmn - (1/2)[1 - (1/log2pim)]m - (1/log2pim) for any code which converts k information digits into an SPI-balanced code of length n = k + r. For example, the first method given in the paper encodes k information digits into an SPI-balanced code of length n = k + r, with r = (m - 1) logmk + O(m logmlogmk). A second method is a recursive method, which uses the first as base code and encodes k digits into an SPI-balanced code of length n = k + r, with r sime (m - 1) logmn - logm[(m - 1)!]