Zero capacity region of multidimensional run length constraints. (English) Zbl 0943.94004

Electron. J. Comb. 6, No. 1, Research paper R33, 16 p. (1999); printed version J. Comb. 6, 443-458 (1999).
An \(n\)-dimensional pattern of zeros and ones arranged in an \(m_1\times m_2\times\cdots\times m_n\) hyper-rectangle is said to be \((d,k)\)-constrained if there are at most \(k\) consecutive zeros and between every two ones there are at least \(d\) consecutive zeros in the binary sequence in each of the \(n\) coordinate axis directions. The maximum number of bits of information that can be stored asymptotically per unit volume in \(n\)-dimensional space without violating the \((d,k)\)-constraint is said to be the \((d,k)\)-capacity. In the paper two theorems that characterize zero capacity region for finite dimensions and in the limit of large dimensions have been presented. One of them generalizes a result of the second and fourth authors [IEEE Trans. Inf.Theory 45, 1527-1540 (1999)].


94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
37E99 Low-dimensional dynamical systems


Zbl 0990.59934
Full Text: EuDML EMIS