On symbol permutation invariant balanced codes
Raffaele Mascella, Luca G. Tallini · 2005
A symbol permutation invariant balanced (SPI-balanced) code over the alphabet ZZm= {0, 1,....,m - 1} is a block code over ZZmsuch 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 a SPI-balanced code into a 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. The 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 rminsime [(m - 1)/2] logmn - (1/2)[1 $(1/log2pim)] m - (1/log2pim) for SPI-balanced code with k information digits and length n = k + r. For example, the first method given in the paper encodes k information digits into a SPI-balanced code of length n = k + r, with r = (m - 1) logmk + O(m logmk). A second method is a recursive method, which uses the first as base code, and encodes k digits into a SPI-balanced code of length n = k + r, with r sime (m - 1) logmn $logm[(m - 1)!]