DocumentCode
3278517
Title
Zero/positive capacities of two-dimensional runlength constrained arrays
Author
Etzion, Tuvi ; Paterson, Kenneth G.
Author_Institution
Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel
fYear
2001
fDate
2001
Firstpage
269
Abstract
A binary sequence satisfies a one-dimensional (d, k) runlength constraint if every run of zeroes has length at least d and at most k. A binary sequence satisfies a one-dimensional (d1, k1, d2, k2) runlength constraint if every run of zeroes has length at least d1 and at most k2 and every run of ones has length at least d2 and at most k2. A two-dimensional binary array is said to satisfy a (d1, k1, d2, k2; d 3, d4, k4) runlength constraint if it satisfies the one-dimensional (d1, k1, d2 , k2) runlength constraint horizontally (i.e. on every row) and the one-dimensional (d3, k3, d4, k4) runlength constraint vertically (i.e. on every column). For convenience, we will say that a binary array satisfies the (d,k) runlength constraint if each row and each column satisfy the (d,k) runlength constraint and that a binary array satisfies the (d1, k1, d2, k2) runlength constraint if it is (d1, k1, d2 , k2) runlength constrained both horizontally and vertically. We say that a binary array satisfies the (d1, k 1; d3, k3) runlength constraint if each row satisfies the (d1, k1, d1, k1 ) runlength constraint and each column satisfies the (d3, k3, d3, k3) runlength constraint. Finally, we always allow violation of the smallest runlength constraint at the beginning and the end sequences and at the edges of arrays. In this work we examine the following basic question: for which values of d1, k1, d2, k2, d 3, k3, d4, k4, is C(d1 , k1, d2, k2; d3, k 3, d4, k4) positive and for which values is it equal to zero?
Keywords
binary codes; binary sequences; channel capacity; channel coding; runlength codes; beginning sequences; binary sequence; end sequences; one-dimensional runlength constraint; positive capacities; two-dimensional binary array; two-dimensional runlength constrained arrays; zero capacities; Binary sequences;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory, 2001. Proceedings. 2001 IEEE International Symposium on
Conference_Location
Washington, DC
Print_ISBN
0-7803-7123-2
Type
conf
DOI
10.1109/ISIT.2001.936132
Filename
936132
Link To Document