# Presentation: 658188

- Capacity of Noiseless and Noisy Two-Dimensional Channels
- Paul H. Siegel
- Electrical and Computer Engineering
- Center for Magnetic Recording Research
- University of California, San Diego

- April 28, 1998

## Outline

- Shannon Capacity
- Discrete-Noiseless Channels
- One-dimensional
- Two-dimensional
- Summary

- April 28, 1998

## Claude E. Shannon

- April 28, 1998

## The Inscription

- April 28, 1998

## The Formula on the “Paper”

- Capacity of a discrete channel with noise [Shannon, 1948]
- For noiseless channel, Hy(x)=0,  so:
- Gaylord, MI:  C = W log (P+N)/N
- Bell Labs:  no formula on paper
- (“H = – p log p – q log q” on plaque)

- April 28, 1998

## Discrete Noiseless Channels(Constrained Systems)

- A constrained system S is the set of sequences generated   by walks on a labeled, directed graph G.
- 	Telegraph channel constraints [Shannon, 1948]

- DOT

- DASH

- DOT

- DASH

- LETTER SPACE

- WORD SPACE

- April 28, 1998

## Magnetic Recording Constraints

- Forbidden words F={101, 010}

- 0

- 1

- 0

- 0

- 1

- 1

- Biphase

- Even

- 1

- 0

- 0

- 0

- 1

- 1

- 1

- Forbidden word F={11}

**Runlength constraints          ****(“finite-type”: determined by finite list F of forbidden words)**

**Spectral null constraints    ****(“almost-finite-type”)**

- April 28, 1998

##  (d,k) runlength-limited constraints

- For                         , a    (*d,k*) runlength-limited
-     sequence is a binary string such that:
- F={11} forbidden list corresponds to
-  1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0

- April 28, 1998

## Practical Constrained Codes

-          Finite-state encoder 	             Sliding-block decoder
-             (from binary data into S)            	 (inverse mapping from S to data)

-   **Decoder**
**     ****Logic**

**n bits**

**m bits**

- We want: high rate R=m/n
-                 low complexity

- April 28, 1998

## Codes and Capacity

- How high can the code rate be?
- Shannon defined the capacity of the constrained system ***S:***
- 	where ***N*****(*****S,n*****)** is the number of sequences in ***S*** of length** *****n***.
- 	Theorem [Shannon,1948] : If there exists a decodable code at rate ***R= m/n*** from binary data to ***S***, then ***R ************ C***.
- 	Theorem [Shannon,1948] : For any rate ***R=m/n < C*** there exists a block code from binary data to ***S****** ***with rate ***k******m:******k******n***, for some integer ***k ************ *****1**.

- April 28, 1998

## Computing Capacity:Adjacency Matrices

- Let          be the adjacency matrix of the graph ***G*** representing ***S***.
- The entries in            correspond to paths in *G* of length ***n***.

- 0

- 0

- 1

- April 28, 1998

## Computing Capacity (cont.)

- Shannon showed that, for suitable representing graphs ***G ***,
- 	where                                                                           , i.e.,
- 	the spectral radius of the matrix       .
- Assigning “transition probabilities” to the edges of ***G***, the constrained system ***S*** becomes a Markov source ***x***, with  entropy ***H*****(*****x*****)*****.***  Shannon proved that
- 	and expressed the maximizing probabilities in terms of the spectral radius and corresponding eigenvector of        .

- April 28, 1998

## Maxentropic Measure

- Let        denote the largest real eigenvalue of        , with corresponding eigenvector
- Then the maxentropic (capacity-achieving) transition  probabilities are given by
- The stationary state distribution is expressed in terms of corresponding left and right eigenvectors.

- April 28, 1998

## Computing Capacity (cont.)

- Example:
- More generally,                             ,  where            is the
-      largest real root of the polynomial
-     and

- April 28, 1998

## Constrained Coding Theorems

- Stronger coding theorems were motivated by the problem of constrained code design for magnetic recording.
- 	Theorem[Adler-Coppersmith-Hassner, 1983]
- 	Let ***S*** be a finite-type constrained system.  If ***m/n ************ C***,  then  there exists a rate ***m:n*** sliding-block decodable, finite-state encoder.
- 	(Proof is constructive: state-splitting algorithm.)
- 	Theorem[Karabed-Marcus, 1988]
- 	Ditto if ***S*** is almost-finite-type.
- 	(Proof not so constructive...)

- April 28, 1998

## Two-Dimensional Constrained Systems

- Band-recording and page-oriented recording technologies require 2-dimensional constraints, for example:
- Two-Dimensional Optical Storage (TwoDOS) - Philips
- Holographic Storage  - InPhaseTechnologies
- Patterned Magnetic Media – Hitachi, Toshiba, ...
- Thermo-Mechanical Probe Array – IBM

- April 28, 1998

## TwoDOS

- Courtesy of Wim Coene, Philips Research

- April 28, 1998

## Constraints on the Integer Lattice Z2

-            :                         constraint  in  *x - y*  directions:

- Hard-Square Model

**1**

**1**

**1**

**1**

**1**

**1**

**1**

**1**

**1**

**1**

**1**

**1**

**1**

**1**

**1**

**1**

- Independent Sets

- April 28, 1998

## (d,k) Constraints on the Integer Lattice Z2

- For 2-dimensional (*d,k*) constraints          , the capacity is given by:
- The only nontrivial (*d,k*) pairs for which              is known precisely are
-       those with zero capacity, namely [Kato-Zeger, 1999] :

- April 28, 1998

## (d,k) Constraints on Z2 – Capacity Bounds

- Transfer matrix methods provide numerical bounds on
-      [Calkin-Wilf, 1998] , [Nagy-Zeger, 2000]
- Variable-rate “bit-stuffing” encoders for         yield best known lower bounds on           for *d >*1 [Halevy, et al., 2004]:

| d | Lower bound | d | Lower bound |
| --- | --- | --- | --- |
| 2 | 0.4267 | 4 | 0.2858 |
| 3 | 0.3402 | 5 | 0.2464 |

- April 28, 1998

## 2-D Bit-Stuffing             RLL Encoder

- Source encoder converts binary data to i.i.d bit stream (biased bits) with                              ,  rate penalty        .
- Bit-stuffing encoder inserts redundant bits which can be identified uniquely by decoder.
- Encoder rate *R(p)* is a lower bound of the capacity.        (For *d*=1,  we can determine *R(p) * precisely.)

- April 28, 1998

## 2-D Bit-Stuffing  (1,∞) RLL Encoder

- Biased sequence:  1 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0

- 1

- 0

- 0

- 0

- 0

- 0

- 0

- 1

- 1

- 1

- 1

- 1

- 0

- 0

- 0

- 1

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- 0

- Optimal bias  Pr(1) = *p *= 0.3556
-  *R*(*p*)=0.583056   (within 1% of capacity)

- April 28, 1998

## Enhanced Bit-Stuffing Encoder

- Use 2 source encoders, with parameters  *p**0** , p**1 **.*

**0**

**0**

**1**

- Optimal bias
- Pr(1) = *p**0 **= 0.328167*

- Optimal bias
- Pr(1) = *p**1 **= 0.433068*

*R*(*p**0* , *p**1*)=0.587277   (within 0.1% of capacity)

- April 28, 1998

## Non-Isolated Bit (n.i.b.) Constraint on Z2

- The non-isolated bit constraint              is defined by the forbidden set:
- Analysis of the coding ratio of a bit-stuffing encoder yields:
-                     0.91276 ≤ *C**sq**nib **≤ *0.93965

- April 28, 1998

## Constraints on the Hexagonal Lattice A2

-            :                         constraints:

- Hard-Hexagon Model

- April 28, 1998

## Hard Hexagon Capacity

- Capacity of hard hexagon model           is known precisely! [Baxter,1980]*

-  So,

- April 28, 1998

## Hard Hexagon Capacity

- Alternatively, the hard hexagon entropy constant       satisfies a degree-24 polynomial with (big!) integer coefficients.
- Baxter does offer this disclaimer regarding his derivation, however:

- *“It is not mathematically rigorous, in that certain analyticity properties of κ are assumed, and the results of Chapter 13 (which depend on assuming that various large-lattice limits can be interchanged) are used. However, I believe that these assumptions, and therefore (14.1.18)-(14.1.24), are in fact correct.”

- April 28, 1998

## (d,k) Constraints on A2 – Capacity Bounds

- Zero capacity region partially known [Kukorelly-Zeger, 2001].
- Variable-to-fixed length “bit-stuffing” encoders for
-      yield best known lower bounds on               for   *d>*1

| d | Lower bound | d | Lower bound |
| --- | --- | --- | --- |
| 2 | 0.3387 | 4 | 0.2196 |
| 3 | 0.2630 | 5 | 0.1901 |

- [Halevy, et al., 2004]:

- April 28, 1998

## Practical 2-D Constrained Codes

-   There is no comprehensive algorithmic theory for
-    constructing encoders and decoders for 2-D constrained
-    systems.
-   Very efficient bit-stuffing encoders have been defined and
-    analyzed for several 2-D constraints, but they are not
-    suitable for practical applications [Roth et al., 2001] ,
-    [Halevy et al., 2004] , [Nagy-Zeger, 2004].
-   Optimal block codes with  *m x n*   rectangular code arrays
-    have been designed for small values of *m* and *n, *and* *some
*   *finite-state encoders have been designed, but there is no
-    generally applicable method  [Demirkan-Wolf, 2004] .

- April 28, 1998

## Concluding Remarks  

- The lack of convenient graph-based representations of 2-D constraints prevents the straightforward extension of 1-D techniques for analysis and code design.
- There are strong connections to statistical physics that may open up new approaches to understanding 2-D constrained systems (and, perhaps, vice-versa).

- April 28, 1998