Blahut-Arimoto Algorithm for Action-dependent Feedback (BAA-Action)

About

The software BAA-Action, is a matlab package which computes the maximum of normalized directed information for finite state channels with states known to the decoder, when the encoder takes cost constrained actions to determine whether or not the state is fed back to the encoder. Specifically the following quantity is evaluated for the figure shown above, $C_N(Gamma)=maxfrac{1}{N}I(X^Nrightarrow Y^N)$ where maximum is over causal conditioning distribution $r(x^N,a^Nparallel z^{N-1})$ such that the cost constraints on actions are satisfied. Please refer to the Section XI-A in the reference for more details. The software is specifically coded for the example in Section XI-B of the paper, where the channel is Markovian, all channel input symbols, output symbols and states being binary.

The Blahut-Arimoto Algorithm for Action-Dependent Feedback (BAA-Action) is as follows.

Installation and Execution

The matlab package can be found here. You will also need CVX package.
The software contains

BAA-Action.m : This function file computes the normalized directed information with action dependent feedback. The input parameters are :
- $Iter_{max}$ = Maximum Number of Iterations for a fixed block length and lambda.
- = Block Length to compute BAA-Action.
- = The vector of Lagrangian Multiplier valus that will sweep the cost-capacity trade-off curve.
- = Channel Transition Matrix.

BAA_Markov_Channel.m : This file computes the capacity upper and lower bounds for the Markovian Channel (cf. Fig. 7 in the reference). Typical bounds, computed for N=2, N=3 are shown below,

Reference

1. To Feed or Not to Feed Back
Himanshu Asnani, Haim Permuter, Tsachy Weissman, submitted to IEEE Transactions on Information Theory, Nov 2010.
A shorter version to appear in Proceedings of 2011 IEEE Interational Symposium on Information Theory, St. Petersburg, Russia, August 2011. (ISIT STUDENT PAPER AWARD FINALIST)