Zero-error feedback capacity via dynamic programming Academic Article uri icon


  • In this paper, we study the zero-error capacity for finite state channels with feedback when channel state information is known to both the transmitter and the receiver. We prove that the zero-error capacity in this case can be obtained through the solution of a dynamic programming problem. Each iteration of the dynamic programming provides lower and upper bounds on the zero-error capacity, and in the limit, the lower bound coincides with the zero-error feedback capacity. Furthermore, a sufficient condition for solving the dynamic programming problem is provided through a fixed-point equation. Analytical solutions for several examples are provided. Subjects: Information Theory (cs. IT) Cite as: arXiv: 0907.1956 [cs. IT](or arXiv: 0907.1956 v1 [cs. IT] for this version) Submission history From: Haim Permuter Henry [view email][v1] Sat, 11 Jul 2009 10: 20: 12 GMT (32kb)

publication date

  • July 11, 2009