Implementation issues for Shannon's Channel capacity and entropy

Question

Upon partioning a phase space into Alpha partitions, it is intended to find how good that partiton is. In this perspective, we need to find out the source entropy. Now, I googled a lot but could not find out what source entropy is. Can anyone explain:

• How is Shannon's entropy different from Source entropy and how to implement source entropy?

• How to calculate Channel capacity? Below is the code for calculating Shannon's entropy for a data x. I would be obliged if the following code is modified to calculate the channel capacity.

x = x(1:end);
    if nargin == 1        
        p = freq(double(x));
    else
        if numel(x) ~= numel(y)
            e = -1;
            warning('Sizes of vector do not match.');
            return;
        end
        y = y(1:end);
        p = joint_freq(double(x), double(y));
    end

    % Compute Shannon entropy
    xlogy(repmat(256, [length(p) 1]), p);
    e = -sum(p .* xlogy(repmat(256, [length(p) 1]), p));

• What is the difference between Kolgomorov entropy and Shannon's entropy in less technical jargon? It is confusing to understand the significance/implication of the complexity number returned by Kolgomorov complexity.

Answer 1

Addressing your last question first, Kolmogorov entropy is the entropy of the possible trajectories a system can take, i.e. it is a measure of the 'randomness' of the possible evolution of a system. Shannon entropy on the other hand is a measure of the randomness of the state of a system. From the fact that you are comparing x to y, rather than multiple trajectories of x to multiple trajectories of y, it looks like you should be computing the Shannon entropy.

Often we want to compute something called the mutual information, which is a measure of how much the entropy, or 'randomness' of our signal is reduced when we condition it on some other signal. In the case of your code above, you are trying to measure either how much entropy there is in x, or how much entropy there is in x given y. The difference between these two values is how much we have found out about x by knowing y. We call this different the mutual information or, if we first divide by the time-length of the series you're looking at, the channel capacity. (The source entropy would just be the entropy of y, assuming y is your 'source').

There are some problems with your code, and I can't know exactly what they are without knowing the implementation of joint_freq. To calculate the entropy of x given y you should be taking a 2D matrix of the joint probability distribution, computing the sum of the entropy in the x direction as you are now, but then also taking the mean along the remaining dimension.