# Exercise 4.57: Capacity of a communication channel

Jump to: Source code Text output Plots Library index

    % Boyd & Vandenberghe "Convex Optimization"
    % JoÃ«lle Skaf - 04/24/08
    %
    % We consider a discrete memoryless communication channel, with input
    % X(t) \in {1,...,n}, and output Y(t) \in {1,...,m}, for t = 1,2,...
    % The relation between the input and output is given statistically:
    %           p_ij = Prob(Y(t)=i|X(t)=j), i=1,...,m,  j=1,...,n
    % The matrix P is called the channel transition matrix.
    % The channel capacity C is given by
    %           C = sup{ I(X;Y) | x >= 0, sum(x) = 1},
    % I(X;Y) is the mutual information between X and Y, and it can be shown
    % that:     I(X;Y) = c'*x - sum_{i=1}^m y_i*log_2(y_i)
    % where     c_j = sum_{i=1}^m p_ij*log_2(p_ij), j=1,...,m

    % Input data
    rand('state', 0);
    n = 15;
    m = 10;
    P = rand(m,n);
    P = P./repmat(sum(P),m,1);
    c = sum(P.*log2(P))';

    % Channel capacity
    cvx_begin
        variable x(n)
        y = P*x;
        maximize (c'*x + sum(entr(y))/log(2))
        x >= 0;
        sum(x) == 1;
    cvx_end
    C = cvx_optval;

    % Results
    display(['The channel capacity is: ' num2str(C) ' bits.'])

    Successive approximation method to be employed.
       sedumi will be called several times to refine the solution.
       Original size: 45 variables, 21 equality constraints
       10 exponentials add 80 variables, 50 equality constraints
    -----------------------------------------------------------------
     Cones  |             Errors              |
    Mov/Act | Centering  Exp cone   Poly cone | Status
    --------+---------------------------------+---------
     10/ 10 | 2.713e+00  4.909e-01  7.095e-08 | Solved
     10/ 10 | 4.540e-02  1.465e-04  8.655e-08 | Solved
     10/ 10 | 3.971e-03  1.151e-06  8.905e-08 | Solved
      0/ 10 | 2.034e-04  8.980e-08  8.895e-08 | Solved
    -----------------------------------------------------------------
    Status: Solved
    Optimal value (cvx_optval): +0.296291
    The channel capacity is: 0.29629 bits.