HP Labs Technical Reports

On the Redundancy of Two-Dimensional Balanced Codes

Ordentlich, Erik; Roth, Ron M.

HPL-97-143

Keyword(s): balanced arrays; DC-free codes; two-dimensional coding

Abstract: Let A(sub n x m) be the set of binary n x m arrays in which each row, and respectively each column, has the same number of 0's and 1's. We prove the lower bound log(sub2) (sub n x m) greater than or equal to nm - 1/2 (n log(sub2)(2m) + m log(sub2) (2n)). We also show that this bound is tight up to an additive term O(n + log m).

15 Pages

Back to Index