Return to Answer

I clarified that the channel matrix in the theorem adapted from Ash must be square and non-singular. I feel that this should be explicitly stated (as it is stated by Ash) since, in general, DMC channel matrices are not square and there is a notion of left/right invertability for non-square matrices.

Source Link

edit approved May 19, 2015 at 20:35

Bullmoose

I adapt the following from Theorem 3.3.3 of Ash's information theory book: if the channel matrix $P$ of a discrete memoryless channel is square and nonsingular and

$d_k := \sum_j (P^{-1})_{jk} \exp \left ( -\sum_i (P^{-1})_{ji} H(Y|X = x_i) \right ) > 0$

for all $k$, then the channel capacity is

$C = \log \sum_j \exp \left ( -\sum_i (P^{-1})_{ji} H(Y|X = x_i) \right )$

and $d$ is proportional to a capacity-achieving distribution.

In general, the capacity of a DMC must be computed numerically using the Blahut-Arimoto algorithm (PDF of Blahut's original paper here). Here is a MATLAB M-file I wrote for this:

function y = blahutarimoto(P,e);

% channel capacity of a DMC with transition matrix P (not necessarily
% square); e is an error parameter
% except for P vs Q, we use Blahut's notation in Fig.1 of his paper

n = size(P,1);  % number of input symbols

% initializations 
p = ones(1,n)/n;  % input distribution
IU = 1; % upper bound for the capacity
IL = 0; % lower bound for the capacity
e = min(.5,e);

while IU - IL > e
    c = exp(sum(P.*log(P./repmat(p*P,[n 1])),2));
    IL = log(p*c);
    IU = log(max(c));
    p = p.*c'/(p*c);
end

C = IL;

y = [p,C];

I adapt the following from Theorem 3.3.3 of Ash's information theory book: if the channel matrix $P$ of a discrete memoryless channel is nonsingular and

$d_k := \sum_j (P^{-1})_{jk} \exp \left ( -\sum_i (P^{-1})_{ji} H(Y|X = x_i) \right ) > 0$

for all $k$, then the channel capacity is

$C = \log \sum_j \exp \left ( -\sum_i (P^{-1})_{ji} H(Y|X = x_i) \right )$

and $d$ is proportional to a capacity-achieving distribution.

In general, the capacity of a DMC must be computed numerically using the Blahut-Arimoto algorithm (PDF of Blahut's original paper here). Here is a MATLAB M-file I wrote for this:

function y = blahutarimoto(P,e);

% channel capacity of a DMC with transition matrix P (not necessarily
% square); e is an error parameter
% except for P vs Q, we use Blahut's notation in Fig.1 of his paper

n = size(P,1);  % number of input symbols

% initializations 
p = ones(1,n)/n;  % input distribution
IU = 1; % upper bound for the capacity
IL = 0; % lower bound for the capacity
e = min(.5,e);

while IU - IL > e
    c = exp(sum(P.*log(P./repmat(p*P,[n 1])),2));
    IL = log(p*c);
    IU = log(max(c));
    p = p.*c'/(p*c);
end

C = IL;

y = [p,C];

I adapt the following from Theorem 3.3.3 of Ash's information theory book: if the channel matrix $P$ of a discrete memoryless channel is square and nonsingular and

$d_k := \sum_j (P^{-1})_{jk} \exp \left ( -\sum_i (P^{-1})_{ji} H(Y|X = x_i) \right ) > 0$

for all $k$, then the channel capacity is

$C = \log \sum_j \exp \left ( -\sum_i (P^{-1})_{ji} H(Y|X = x_i) \right )$

and $d$ is proportional to a capacity-achieving distribution.

In general, the capacity of a DMC must be computed numerically using the Blahut-Arimoto algorithm (PDF of Blahut's original paper here). Here is a MATLAB M-file I wrote for this:

function y = blahutarimoto(P,e);

% channel capacity of a DMC with transition matrix P (not necessarily
% square); e is an error parameter
% except for P vs Q, we use Blahut's notation in Fig.1 of his paper

n = size(P,1);  % number of input symbols

% initializations 
p = ones(1,n)/n;  % input distribution
IU = 1; % upper bound for the capacity
IL = 0; % lower bound for the capacity
e = min(.5,e);

while IU - IL > e
    c = exp(sum(P.*log(P./repmat(p*P,[n 1])),2));
    IL = log(p*c);
    IU = log(max(c));
    p = p.*c'/(p*c);
end

C = IL;

y = [p,C];

Source Link

created May 10, 2012 at 2:37

Steve Huntsman

15.4k
7
75
130

I adapt the following from Theorem 3.3.3 of Ash's information theory book: if the channel matrix $P$ of a discrete memoryless channel is nonsingular and

$d_k := \sum_j (P^{-1})_{jk} \exp \left ( -\sum_i (P^{-1})_{ji} H(Y|X = x_i) \right ) > 0$

for all $k$, then the channel capacity is

$C = \log \sum_j \exp \left ( -\sum_i (P^{-1})_{ji} H(Y|X = x_i) \right )$

and $d$ is proportional to a capacity-achieving distribution.

In general, the capacity of a DMC must be computed numerically using the Blahut-Arimoto algorithm (PDF of Blahut's original paper here). Here is a MATLAB M-file I wrote for this:

function y = blahutarimoto(P,e);

% channel capacity of a DMC with transition matrix P (not necessarily
% square); e is an error parameter
% except for P vs Q, we use Blahut's notation in Fig.1 of his paper

n = size(P,1);  % number of input symbols

% initializations 
p = ones(1,n)/n;  % input distribution
IU = 1; % upper bound for the capacity
IL = 0; % lower bound for the capacity
e = min(.5,e);

while IU - IL > e
    c = exp(sum(P.*log(P./repmat(p*P,[n 1])),2));
    IL = log(p*c);
    IU = log(max(c));
    p = p.*c'/(p*c);
end

C = IL;

y = [p,C];