Zero capacity region of multidimensional run length constraints

Hisashi Ito ; Akiko Kato ; Zsigmond Nagy ; Kenneth Zeger

The electronic journal of combinatorics, Tome 6 (1999)

Résumé

For integers $d$ and $k$ satisfying $0 \le d \le k$, a binary sequence is said to satisfy a one-dimensional $(d,k)$ run length constraint if there are never more than $k$ zeros in a row, and if between any two ones there are at least $d$ zeros. For $n\geq 1$, the $n$-dimensional $(d,k)$-constrained capacity is defined as $$C^{n}_{d,k} = \lim_{m_1,m_2,\ldots,m_n\rightarrow\infty} {{\log_2 N_{m_1,m_2,\ldots ,m_n}^{(n; d,k)}} \over {m_1 m_2\cdots m_n}} $$ where $N_{m_1,m_2,\ldots ,m_n}^{(n; d,k)}$ denotes the number of $m_1\times m_2\times\cdots\times m_n$ $n$-dimensional binary rectangular patterns that satisfy the one-dimensional $(d,k)$ run length constraint in the direction of every coordinate axis. It is proven for all $n\ge 2$, $d\ge1$, and $k>d$ that $C^{n}_{d,k}=0$ if and only if $k=d+1$. Also, it is proven for every $d\geq 0$ and $k\geq d$ that $\lim_{n\rightarrow\infty}C^{n}_{d,k}=0$ if and only if $k\le 2d$.

Détail

DOI : 10.37236/1465

Classification : 94A55, 37E99
Mots-clés : binary sequences, run length constraint, \(n\)-dimensional \((d,k)\)-constrained capacity, \(n\)-dimensional binary rectangular patterns