HP Labs Technical Reports

Click here for full text: Postscript PDF

On the Redundancy of Two-Dimensional Balanced Codes

Ordentlich, Erik; Roth, Ron M.


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

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map][Home] [Hewlett-Packard]