• 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