Scribe Notes 6_2


  1. Feedback capacity

     The channel with feedback is illustrated as follows:        

         

     We define a Formula feedback code as a sequence of mappings Formula, where each Formula is a function only of Formula and the previous received values, Formula, and a sequence of decoding functions Formula. Thus Formula

when W is uniformly distributed over Formula.

 

Definition: The capacity with feedback, Formula, of a discrete memorylesss channel is the supermum of all rates achievable by feedback codes.

Theorem: Formula = Formula=Formula

Proof:

  Since a non-feedback code is a special case of a feedback code, any rate that can be achieved without feedback can be achieved with feedback, and hence

  Formula

  Instead of using Formula, we will use the index Formula and prove a similar series of inequalities.

  Let W be uniformly distributed over FormulaThen:

 

  Formulaby Feno's inequality

   Formula

                      Formula                              

                      Formula

Using the entropy bound:

Formula

                    Formula

                    Formula

                    Formula

Putting theses together, we obtain:

Formula

and divding by n and letting n tend to infinity, we conclude:

Formula

Thus we cannot achieve any higher rates with feedback than we can without feedback, and

Formula

As we have seen in the example of the binary erasure channel, feedback can help enormously in simplifying encoding and decoding, However, it cannot increase

the capacity of the channel.