Efficient m-ary balanced codes Original Research Article

An m-ary balanced code with r check digits and k information digits is a code over the alphabet Zm = {0,1, …, m−1} of length n = k+r and cardinality mk such that each codeword is balanced; that is, the real sum of its components (or weight) is equal to [(m − 1)n/2]. This paper contains new efficient methods to design m-ary balanced codes which improve the constructions found in the literature, for all alphabet size m ⩾2. To design such codes, the information words which are close to be balanced are encoded using single maps obtained by a new generalization of Knuthʹs complementation method to the m-ary alphabet that we introduce in this paper. Whereas, the remaining information words are compressed via suitable m-ary uniquely decodable variable length codes and then balanced using the saved space. For any m⩾2, infinite families of m-ary balanced codes are given with r check digits and k⩽[1/(1 − 2α)][mr − 1)/(m − 1)] − c1 (m, α) r −c2(m, α) information digits, where α ϵ [0, 1/2) can be chosen arbitrarily close to 1/2. The codes can be implemented with O(mk logm k) m-ary digit operations and O(m + k) memory elements to store m-ary digits.