Design of some new efficient balanced codes

Abstract

A balanced code with r check bits and k information bits is a binary code of length k+r and cardinality 2/sup k/ such that each codeword is balanced; that is, it has [(k+r)/2] 1's and [(k+r)/2] 0's. This paper contains new methods to construct efficient balanced codes. To design a balanced code, an information word with a low number of 1's or 0's is compressed and then balanced using the saved space. On the other hand, an information word having almost the same number of 1's and 0's is encoded using the single maps defined by Knuth's (1986) complementation method. Three different constructions are presented. Balanced codes with r check bits and k information bits with k/spl les/2/sup r+1/-2, k/spl les/3/spl times/2/sup r/-8, and k/spl les/5/spl times/2/sup r/-10r+c(r), c(r)/spl isin/{-15, -10, -5, 0, +5}, are given, improving the constructions found in the literature. In some cases, the first two constructions have a parallel coding scheme.