Version 3.0, Aug 24, 2001
(Press here
to download the most updated version)
ITIP is a piece of software running on MATLAB on Unix or PC for verifying Shannon-type inequalities.
For Unix
Information expressions of the following forms are recognized:
where E1 and E2 are linear combinations of entropies,
mutual informations, or their conditional versions. Moreover, the notation
I(X1;X2;X3;...;Xn)
for the mutual information between more than two random variables is accepted.
At most 26 variables (A-Z) can be used.
To facilitate checking a large number of similar expressions, MATLAB variables whose names are in the lower-case alphabet can be used as coefficients. Blanks and commas in the expressions are ignored.
0.8H(AZ)+I(A;ZY)>=3I(A;Y)-2.5H(Y|Z)
hello H(X) + world I(X;Y) <= fun H(X|Y)
Remark: Before using these environment variables, they must be
declared global in MATLAB's workspace.
b, t, n and m are for diagnostic purposes and their
values should be interpreted as follows:
n is a string of upper-case letters separated by blank spaces. They represent the random variables appearing in E1,E2,E3,...,En. If two or more letters are grouped together, it means that ITIP treated the corresponding random variables as one random variable.
b is a matrix whose elements are the coefficients of the joint entropies in the canonical form of the inputs. The column vectors represent E1,E2,E3,...,En sequentially. Note that two or more columns may be needed to represent a Markov chain. To determine which joint entropy the ith coefficient in a column corresponds to, we first find the binary representation of i. If the rth least significant bit is 1, the rth random variable shown in the string n is included in the joint entropy.
t is a column vector showing the type of expressions b represents. If the ith row of t is 1, the ith column of b represents an inequality.
m is the number of columns of b that are to be proved.
In the above, those inequalities which are not provable by ITIP
are actually invalid, as can be shown by examples. However, the non-Shannon-type
inequality below is valid but it cannot be proved by ITIP.
Nevertheless, only very few such inequalities are known so far.
Therefore, if an inequality cannot be proved by ITIP, it is very likely
to be invalid.
The files ITIP_kern.m and make_D.c are subroutines invoked
by ITIP.m. ITIP_kern is not designed to be used directly,
while make_D may be used to compute the matrix 'D' representing
the elemental inequalities. The following commands will produce the matrix
'D' for n random variables.
Each row of D represents one elemental inequality. To determine
which joint entropy the ith element corresponds to, we first find
the binary representation of i. If the rth least significant
bit is 1, the
rth random variable is included in the joint entropy.