Graph-Based Encoders and their Performance for Finite-State Channels with Feedback

07/18/2019
by   Oron Sabag, et al.
0

The capacity of unifilar finite-state channels in the presence of feedback is investigated. We derive a new evaluation method to extract graph-based encoders with their achievable rates, and to compute upper bounds to examine their performance. The evaluation method is built upon a recent methodology to derive simple bounds on the capacity using auxiliary directed graphs. While it is not clear whether the upper bound is convex, we manage to formulate it as a convex optimization problem using transformation of the argument with proper constraints. The lower bound is formulated as a non-convex optimization problem, yet, any feasible point to the optimization problem induces a graph-based encoders. In all examples, the numerical results show near-tight upper and lower bounds that can be easily converted to analytic results. For the non-symmetric Trapdoor channel and binary fading channels (BFCs), new capacity results are eastablished by computing the corresponding bounds. For all other instances, including the Ising channel, the near-tightness of the achievable rates is shown via a comparison with corresponding upper bounds. Finally, we show that any graph-based encoder implies a simple coding scheme that is based on the posterior matching principle and achieves the lower bound.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset