[IEEE Trans. on Information Theory, September 2003, pp. 2115-2125]
Asymptotic Capacity of Two-Dimensional Channels with Checkerboard Constraints
Zsigmond Nagy and Kenneth Zeger
Abstract
A checkerboard constraint is a bounded measurable set S ⊆ R2, containing the origin.
A binary labeling of the Z2 lattice satisfies the checkerboard constraint S if
whenever t ∈ Z2 is labeled 1,
all of the other Z2-lattice points in the translate t+S are labeled 0.
Two-dimensional channels that only allow labelings of Z2 satisfying checkerboard constraints are studied.
Let A(S) be the area of S, and let A(S) → ∞ mean
that S retains its shape but is inflated in size in the form αS, as α → ∞.
It is shown that
for any open checkerboard constraint S,
there exist positive reals K1 and K2 such that
as A(S) → ∞,
the channel capacity CS decays to zero
at least as fast as
(K1log2 A(S))/A(S)
and at most as fast as
(K2log2 A(S))/A(S).
It is also shown that if S is an open convex and symmetric checkerboard constraint, then
as A(S) → ∞,
the capacity decays exactly at the rate
4 δ(S) (log2 A(S)) /A(S),
where δ(S) is the packing density of the set S.
An implication is that the capacity of such checkerboard constraint channels is asymptotically determined only
by the areas of the constraint and the smallest (possibly degenerate) hexagon that can be circumscribed about the constraint.
In particular, this establishes that channels with
square, diamond, or hexagonal checkerboard constraint all asymptotically have
the same capacity, since δ(S)=1 for such constraints.