Z-channel (information theory)

<h2 id="definition">Definition</h2>
A Z-channel is a channel with binary input and binary output, where each 0 bit is transmitted correctly, but each 1 bit has probability p of being transmitted incorrectly as a 0, and probability 1–p of being transmitted correctly as a 1. In other words, if X and Y are the <a href="/facts/Random_variable/TwTBXnLT">random variables</a> describing the probability distributions of the input and the output of the channel, respectively, then the crossovers of the channel are characterized by the <a href="/facts/Conditional_probability/QcN2UERV">conditional probabilities</a>:<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

Pr
                ⁡
                [
                Y
                =
                0
                
                  |
                
                X
                =
                0
                ]
              
              
                
                =
                1
              
            
            
              
                Pr
                ⁡
                [
                Y
                =
                0
                
                  |
                
                X
                =
                1
                ]
              
              
                
                =
                p
              
            
            
              
                Pr
                ⁡
                [
                Y
                =
                1
                
                  |
                
                X
                =
                0
                ]
              
              
                
                =
                0
              
            
            
              
                Pr
                ⁡
                [
                Y
                =
                1
                
                  |
                
                X
                =
                1
                ]
              
              
                
                =
                1
                −
                p
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}\operatorname {Pr} [Y=0|X=0]&=1\\\operatorname {Pr} [Y=0|X=1]&=p\\\operatorname {Pr} [Y=1|X=0]&=0\\\operatorname {Pr} [Y=1|X=1]&=1-p\end{aligned}}}

<h2 id="capacity">Capacity</h2>
The <a href="/facts/Channel_capacity/55wJYsS6">channel capacity</a> 
 
 
 
 
 
 c
 a
 p
 
 
 (
 
 Z
 
 )
 
 
 {\displaystyle {\mathsf {cap}}(\mathbb {Z} )}
 
 of the Z-channel 
 
 
 
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} }
 
 with the crossover 1 → 0 probability p, when the input random variable X is distributed according to the <a href="/facts/Bernoulli_distribution/ChCtYyvs">Bernoulli distribution</a> with probability 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 for the occurrence of 0, is given by the following equation:

c
            a
            p
          
        
        (
        
          Z
        
        )
        =
        
          
            H
          
        
        
          (
          
            
              1
              
                1
                +
                
                  2
                  
                    
                      
                        s
                      
                    
                    (
                    p
                    )
                  
                
              
            
          
          )
        
        −
        
          
            
              
                
                  s
                
              
              (
              p
              )
            
            
              1
              +
              
                2
                
                  
                    
                      s
                    
                  
                  (
                  p
                  )
                
              
            
          
        
        =
        
          log
          
            2
          
        
        ⁡
        (
        1
        
          +
        
        
          2
          
            −
            
              
                s
              
            
            (
            p
            )
          
        
        )
        =
        
          log
          
            2
          
        
        ⁡
        
          (
          
            1
            +
            (
            1
            −
            p
            )
            
              p
              
                p
                
                  /
                
                (
                1
                −
                p
                )
              
            
          
          )
        
      
    
    {\displaystyle {\mathsf {cap}}(\mathbb {Z} )={\mathsf {H}}\left({\frac {1}{1+2^{{\mathsf {s}}(p)}}}\right)-{\frac {{\mathsf {s}}(p)}{1+2^{{\mathsf {s}}(p)}}}=\log _{2}(1{+}2^{-{\mathsf {s}}(p)})=\log _{2}\left(1+(1-p)p^{p/(1-p)}\right)}

where 
 
 
 
 
 
 s
 
 
 (
 p
 )
 =
 
 
 
 
 
 H
 
 
 (
 p
 )
 
 
 1
 −
 p
 
 
 
 
 
 {\displaystyle {\mathsf {s}}(p)={\frac {{\mathsf {H}}(p)}{1-p}}}
 
 for the <a href="/facts/Binary_entropy_function/s9cwzz4n">binary entropy function</a> 
 
 
 
 
 
 H
 
 
 (
 ⋅
 )
 
 
 {\displaystyle {\mathsf {H}}(\cdot )}
 
.
This capacity is obtained when the input variable X has <a href="/facts/Bernoulli_distribution/ChCtYyvs">Bernoulli distribution</a> with probability 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 of having value 0 and 
 
 
 
 1
 −
 α
 
 
 {\displaystyle 1-\alpha }
 
 of value 1, where:

α
        =
        1
        −
        
          
            1
            
              (
              1
              −
              p
              )
              (
              1
              +
              
                2
                
                  
                    
                      H
                    
                  
                  (
                  p
                  )
                  
                    /
                  
                  (
                  1
                  −
                  p
                  )
                
              
              )
            
          
        
        ,
      
    
    {\displaystyle \alpha =1-{\frac {1}{(1-p)(1+2^{{\mathsf {H}}(p)/(1-p)})}},}

For small p, the capacity is approximated by

c
            a
            p
          
        
        (
        
          Z
        
        )
        ≈
        1
        −
        0.5
        
          
            H
          
        
        (
        p
        )
      
    
    {\displaystyle {\mathsf {cap}}(\mathbb {Z} )\approx 1-0.5{\mathsf {H}}(p)}

as compared to the capacity 
 
 
 
 1
 
 −
 
 
 
 H
 
 
 (
 p
 )
 
 
 {\displaystyle 1{-}{\mathsf {H}}(p)}
 
 of the <a href="/facts/Binary_symmetric_channel/bFPGGghC">binary symmetric channel</a> with crossover probability p.

For any 
 
 
 
 p
 >
 0
 
 
 {\displaystyle p>0}
 
, 
 
 
 
 α
 >
 0.5
 
 
 {\displaystyle \alpha >0.5}
 
 (i.e. more 0s should be transmitted than 1s) because transmitting a 1 introduces noise. As 
 
 
 
 p
 →
 1
 
 
 {\displaystyle p\rightarrow 1}
 
, the limiting value of 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 is 
 
 
 
 1
 −
 
 
 1
 e
 
 
 
 
 {\displaystyle 1-{\frac {1}{e}}}
 
.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="bounds-on-the-size-of-an-asymmetric-error-correcting-code">Bounds on the size of an asymmetric-error-correcting code</h2>
Define the following distance function 
 
 
 
 
 
 
 d
 
 
 
 A
 
 
 (
 
 x
 
 ,
 
 y
 
 )
 
 
 {\displaystyle {\mathsf {d}}_{A}(\mathbf {x} ,\mathbf {y} )}
 
 on the words 
 
 
 
 
 x
 
 ,
 
 y
 
 ∈
 {
 0
 ,
 1
 
 }
 
 n
 
 
 
 
 {\displaystyle \mathbf {x} ,\mathbf {y} \in \{0,1\}^{n}}
 
 of length n transmitted via a Z-channel

d
            
          
          
            A
          
        
        (
        
          x
        
        ,
        
          y
        
        )
        
          
            
              
                =
              
              
                △
              
            
          
        
        max
        
          {
          
            
              
                |
              
            
            {
            i
            ∣
            
              x
              
                i
              
            
            =
            0
            ,
            
              y
              
                i
              
            
            =
            1
            }
            
              
                |
              
            
            ,
            
              
                |
              
            
            {
            i
            ∣
            
              x
              
                i
              
            
            =
            1
            ,
            
              y
              
                i
              
            
            =
            0
            }
            
              
                |
              
            
          
          }
        
        .
      
    
    {\displaystyle {\mathsf {d}}_{A}(\mathbf {x} ,\mathbf {y} ){\stackrel {\vartriangle }{=}}\max \left\{{\big |}\{i\mid x_{i}=0,y_{i}=1\}{\big |},{\big |}\{i\mid x_{i}=1,y_{i}=0\}{\big |}\right\}.}

Define the sphere 
 
 
 
 
 V
 
 t
 
 
 (
 
 x
 
 )
 
 
 {\displaystyle V_{t}(\mathbf {x} )}
 
 of radius t around a word 
 
 
 
 
 x
 
 ∈
 {
 0
 ,
 1
 
 }
 
 n
 
 
 
 
 {\displaystyle \mathbf {x} \in \{0,1\}^{n}}
 
 of length n as the set of all the words at distance t or less from 
 
 
 
 
 x
 
 
 
 {\displaystyle \mathbf {x} }
 
, in other words,

V
          
            t
          
        
        (
        
          x
        
        )
        =
        {
        
          y
        
        ∈
        {
        0
        ,
        1
        
          }
          
            n
          
        
        ∣
        
          
            
              d
            
          
          
            A
          
        
        (
        
          x
        
        ,
        
          y
        
        )
        ≤
        t
        }
        .
      
    
    {\displaystyle V_{t}(\mathbf {x} )=\{\mathbf {y} \in \{0,1\}^{n}\mid {\mathsf {d}}_{A}(\mathbf {x} ,\mathbf {y} )\leq t\}.}

A <a href="/facts/Code/CSntvnEo">code</a> 
 
 
 
 
 
 C
 
 
 
 
 {\displaystyle {\mathcal {C}}}
 
 of length n is said to be t-asymmetric-error-correcting if for any two codewords 
 
 
 
 
 c
 
 ≠
 
 
 c
 
 ′
 
 ∈
 {
 0
 ,
 1
 
 }
 
 n
 
 
 
 
 {\displaystyle \mathbf {c} \neq \mathbf {c} '\in \{0,1\}^{n}}
 
, one has 
 
 
 
 
 V
 
 t
 
 
 (
 
 c
 
 )
 ∩
 
 V
 
 t
 
 
 (
 
 
 c
 
 ′
 
 )
 =
 ∅
 
 
 {\displaystyle V_{t}(\mathbf {c} )\cap V_{t}(\mathbf {c} ')=\emptyset }
 
. Denote by 
 
 
 
 M
 (
 n
 ,
 t
 )
 
 
 {\displaystyle M(n,t)}
 
 the maximum number of codewords in a t-asymmetric-error-correcting code of length n.
The Varshamov bound.
For n≥1 and t≥1,

M
        (
        n
        ,
        t
        )
        ≤
        
          
            
              2
              
                n
                +
                1
              
            
            
              
                ∑
                
                  j
                  =
                  0
                
                
                  t
                
              
              
                
                  (
                  
                    
                      
                        
                          (
                        
                        
                          
                            ⌊
                            n
                            
                              /
                            
                            2
                            ⌋
                          
                          j
                        
                        
                          )
                        
                      
                    
                    +
                    
                      
                        
                          (
                        
                        
                          
                            ⌈
                            n
                            
                              /
                            
                            2
                            ⌉
                          
                          j
                        
                        
                          )
                        
                      
                    
                  
                  )
                
              
            
          
        
        .
      
    
    {\displaystyle M(n,t)\leq {\frac {2^{n+1}}{\sum _{j=0}^{t}{\left({\binom {\lfloor n/2\rfloor }{j}}+{\binom {\lceil n/2\rceil }{j}}\right)}}}.}

The constant-weight code bound.
For n > 2t ≥ 2, let the sequence B0, B1, ..., Bn-2t-1 be defined as

B
 
 0
 
 
 =
 2
 ,
 
 
 B
 
 i
 
 
 =
 
 min
 
 0
 ≤
 j
 <
 i
 
 
 {
 
 B
 
 j
 
 
 +
 A
 (
 n
 
 +
 
 t
 
 +
 
 i
 
 −
 
 j
 
 −
 
 1
 ,
 2
 t
 
 +
 
 2
 ,
 t
 
 +
 
 i
 )
 }
 
 
 {\displaystyle B_{0}=2,\quad B_{i}=\min _{0\leq j<i}\{B_{j}+A(n{+}t{+}i{-}j{-}1,2t{+}2,t{+}i)\}}
 
 for 
 
 
 
 i
 >
 0
 
 
 {\displaystyle i>0}
 
.
Then 
 
 
 
 M
 (
 n
 ,
 t
 )
 ≤
 
 B
 
 n
 −
 2
 t
 −
 1
 
 
 .
 
 
 {\displaystyle M(n,t)\leq B_{n-2t-1}.}

<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/David_J._C._MacKay/NK3D8JME">MacKay, David J.C.</a> (2003). <a href="http://www.inference.phy.cam.ac.uk/mackay/itila/book.html">Information Theory, Inference, and Learning Algorithms</a>. Cambridge University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-64298-1.</li>
<li>Kløve, T. (1981). "Error correcting codes for the asymmetric channel". Technical Report 18–09–07–81. Norway: Department of Informatics, University of Bergen.</li>
<li>Verdú, S. (1997). "Channel Capacity (73.5)". The electrical engineering handbook (second ed.). IEEE Press and CRC Press. pp. 1671–1678.</li>
<li>Tallini, L.G.; Al-Bassam, S.; Bose, B. (2002). On the capacity and codes for the Z-channel. Proceedings of the IEEE International Symposium on Information Theory. Lausanne, Switzerland. p. 422.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">MacKay (2003), p. 148. - MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1. <a href="http://www.inference.phy.cam.ac.uk/mackay/itila/book.html" target="_blank">http://www.inference.phy.cam.ac.uk/mackay/itila/book.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">MacKay (2003), p. 159. - MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1. <a href="http://www.inference.phy.cam.ac.uk/mackay/itila/book.html" target="_blank">http://www.inference.phy.cam.ac.uk/mackay/itila/book.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Z-channel (information theory) open-in-new

Z-channel (information theory)