LaTeX conversion

1 Convert a small LaTeX file to mathjax supported format

Author

Soukthavy Sopha

Contact

soukthavy@yahoo.com

organization

self

status

Lean to convert the LaTex of IEEE format to reST using my old class homework.

revision

0.1

copyright

None

abstract

The Arimoto-Blahut algorithm is the algorithm used to solve the convex optimization problem for the maximum capacity of a discrete memoryless channel. We will implement their algorithm with MATLAB script to solve the given problem.

1.1 Introduction

For the discrete memoryless channel, Shannon's maximum channel capacity is:

\begin{equation*} C = max_{p_1 \cdots p_n} I(X,Y) \end{equation*}

where X and Y are random variables representing the input and output respectively. The optimization is taken all over the input probability distribution \(p = (p_1 \cdots p_n)\) with the constraints \(p_i \ge 0, \sum_{j=1}^{n}p_j = 1\) and the mutual information is defined as:

\begin{equation*} I(X,Y) = \sum_{i=1}^{m}\sum_{j=1}^{n} p(x_i|y_j)p(y_j) log\frac{p(x_i|y_j)}{\sum_{k=1}^{n}p(x_i|y_k)p(y_k)} \end{equation*}

The optimal \(p\) gives the distribution on the input symbol required to achieve the channel capacity.

1.2 Description of the algorithm

We reformulate the algorithm by introducing variable \(\phi(y_j,x_i)\), and define:

\begin{equation*} J(p,P,\phi) = \sum_{i=1}^{m}\sum_{j=1}^{n}p(x_i|y_j)p(y_j)log\frac{\phi(y_j|x_i)}{p(y_j)} \end{equation*}

and for fix \(p\)

\begin{equation*} max J(p,P,\phi) = \sum_{i=1}^{m}\sum_{j=1}^{n}p(x_i|y_j)p(y_j)log\frac{p(x_i|y_j)}{\sum_{k=1}^{n}p(x_i|y_k)p_{y_k}} \end{equation*}

where we attain at

\begin{equation*} \phi(y_j,x_i) = \frac{p(x_i|y_j)p(y_j)}{\sum_{k=1}^{n}p(x_i|y_k)p(y_k)} \end{equation*}

and the channel capacity

\begin{equation*} C = max_p max_\phi J(p,P,\phi) \end{equation*}

for fixed \(p, max_p J(p,P,\phi)\) is maximized when

\begin{equation*} p_j = \frac{exp(\sum_{k=1}^{m}p(x_k,y_j)log\phi(y_j|x_k)}{\sum_{i=1}^{n}exp(\sum_{k=1}^{m}p(x_k|y_l)log\phi(y_l,x_l)} \end{equation*}

The algorithm is to alternatingly finding the optimal \(\phi\) for a given \(p\) and the optimal \(p\) for a given \(\phi\)

1.2.1 Implementation

  1. Choose an initial \(p^i\) vector then iterate the following steps from \(t=1,2,\cdots\)

  2. Maximize \(J(p^t,P,\phi)\) with respect to \(\phi\). The maximized \(\phi\) \(\phi_j^t = \frac{p(i|j)p_j^t}{\sum_{k=1}^{n}p(i|k)p_k^t}, for j=1 \cdots n\)

  3. Maximize \(J(p,P,\phi^t)\) with respect to \(p\) by

\begin{equation*} p_j^{t+1} = \frac{r_j^t}{\sum_{k=1}^{n}r_k^t}, j = 1 \cdots n \end{equation*}

where

\begin{equation*} r_j^t = exp(\sum_{i=1}^{m}p(i|j)log\phi^t(j|i)), j=1 \cdots n \end{equation*}

1.3 Problems

Fig 1 (problem 3.27a) using image directive

The transition probability for Fig 1 is:

\begin{equation*} P = \left[ \begin{array}{cc} 0.7 & 0.1 \\ 0.1 & 0.7 \\ 0.2 & 0.2 \end{array} \right] \end{equation*}

Maximum channel capacity = 0.365148

Fig 2 (problem 3.27c) using figure directive

The transition probability for Fig 2 is

\begin{equation*} P = \left[ \begin{array}{ccc} 0.7 & 0 & 0.25 \\ 0.25 & 0.75 & 0 \\ 0 & 0.25 & 0.75 \end{array} \right] \end{equation*}

Maximum channel capacity = 0.773684

Fig 3 (problem 3.27d)

The transition probability for Fig 3 is:

\begin{equation*} P = \left[ \begin{array}{cc} 0.9 & 0.3 \\ 0.1 & 0.7 \end{array} \right] \end{equation*}

Maximum channel capacity = 0.296672

1.4 Conclusion

This exercise gives us a good examples on solving the discrete memoryless channel for its optimum value of probability distribution to achieve the maximum channel capacity.

1.5 Bibliography

CIT002

Lawrence Ip, The Blahut-Arimoto Algorithm for the Calculation of the Capacity of a Discrete memoryless channel, December 10 1999.

CIT003

H.~Kopka and P.~W. Daly, emph{A Guide to LaTeX}, 3rd~ed.hskip 1em plus 0.5em minus 0.4emrelax Harlow, England: Addison-Wesley, 1999.

CIT004

Various books and articles from various authors