Two-dimensional weight-constrained codes through enumeration bounds |
| |
Authors: | Ordentlich E Roth RM |
| |
Affiliation: | iCompression Inc., Santa Clara, CA; |
| |
Abstract: | For a rational α∈(0,1), let 𝒜n×m,α be the set of binary n×m arrays in which each row has Hamming weight αm and each column has Hamming weight αn, where αm and αn are integers. (The special case of two-dimensional balanced arrays corresponds to α=1/2 and even values for n and m.) The redundancy of 𝒜n×m,α is defined by ρn×m,α=nmH(α)-log2|𝒜 n×m,α| where H(x)=-xlog2x-(1-x)log2(1-x). Bounds on ρn×m,α are obtained in terms of the redundancies of the sets 𝒜ℒ,α of all binary ℒ-vectors with Hamming weight αℒ, ℒ∈{n,m}. Specifically, it is shown that ρn×m,α⩽nρm,α+mρ n,α where ρℒ,α=ℒH(α)-log2|𝒜 ℒ,α| and that this bound is tight up to an additive term O(n+log m). A polynomial-time coding algorithm is presented that maps unconstrained input sequences into 𝒜n×m,α at a rate H(α)-(ρm,α/m) |
| |
Keywords: | |
|
|