READ ME for the SOFTWARE_MDCS; Aug 5, 2014
The main purpose of this package is to generate several types of bounds on rate
regions of multi-level diversity coding systems (MDCS). Extra features include:
I) the generation of matroid bounds on entropic vector region; II) the comparison
between bounds on rate regions; III) the enumeration of MDCS instances;
IV) the generation of human-readable converse proofs;
V) the testing of embedding relationships between MDCS instances.
a) Contents
b) System Requirements
c) Installation
d) Usage
e) Verify results in [1]
f) Version history
g) Contact
h) Copyright
i) Reference
=================================================================================
a) CONTENTS:
1. folder “src”: MATLAB source files, installed lrs package, optional packages such
as chmlib, cdd, etc;
2. folder “table”: MDCS instances with various numbers of levels and encoders;
3. folder “bounds”: various bounds on entropic vector region, including the Shannon
outer bound, binary (ternary) matroid inner bounds;
4. folder “results”: rate region results for different MDCS instances
5. folder “temp”: files and results generated when an arbitrary MDCS configuration
matrix is input.
6. README.txt: this file
==================================================================================
b) SYSTEM REQUIREMENTS:
Mac OS, or Linux, as lrs package requires.
SPACE: 3.1 GB available free space for the package with results files.
==================================================================================
c) INSTALLATION:
After downloading and unzipping this package in a proper directory, you only need to
I. open your MATLAB program
II. go to the directory of this package
III. go to ./src/
You are ready to use this package. Test the package:
genMDCSRegion(3,2,[1;2;3],1,1,1,1,1,0,1,1);
If the computer complaints about lrs package, then
read the file lrs_README.txt to reinstall the lrs package. Usually you just need to
cd to the directory ./src/ and type make all, or make all64 (for 64-bit machine).
NOTE: You are recommended to install the chmlib for faster polyhedral projection. Details
on chmlib can be found here: http://www.ece.drexel.edu/walsh/aspitrg/software.html. The
chmlib package with some required packages are in ./src/. READ the ./src/chmlib/README.txt
for installation of chmlib. After installing chmlib, make sure the path and name of the
executable binary file matches within the function ./src/projCHM.m. Change it accordingly,
if not match.
However, this package can still work without chmlib by using Fourier-Motzkin projection
method instead. For small networks, FM works fine. For larger networks, say number of
variables greater than 7, we recommend you to install chmlib, if the Shannon outer bound
on rate regions are desired.
==========================================================================================
d) USAGE:
1. Generate various bounds on rate region of a MDCS instance and human readable converse proof
which are all saved in ./temp/:
genMDCSRegion(nLevel,nEnc,conf,rerun,ifpop,Out,BI,TI,Vec,sp,pf);
where
% nLevel: number of sources
% nEnc: number of encoders
% conf: configuration matrix, where i-th row contains configurations for level i
decoders and the encoders that a decoder has access to is coded using the
associated integer value from {1,2,…,2^{|\mathcal{E}|}-1}. Details can be found
in Sec II of paper [1].
% rerun: if you want to rerun the results for input instance or try to pull out
from computed MDCS instance, 1 for TRUE, 0 for FALSE
% ifpop: if you want to display a window listing the inequalities in the rate region
1 for TRUE, 0 for FALSE
% Out: indicator of if the Shannon outer bound is desired, 1 for TRUE, 0 for FALSE
The default projection method is Fourier-Motzkin, if CHM is needed, input
[1 1] for this parameter;
% BI: if binary inner bound region is desired, 'BI' means binary inner, 1 for
TRUE, 0 for FALSE, if Vec is 0 or empty, only scalar binary inner bound
will be generated.
% TI: if ternary inner bound region is desired, ‘TI’ means ternary inner, 1 for
TRUE, 0 for FALSE, if Vec is 0 or empty, only scalar ternary inner bound
will be generated.
% Vec: a vector whose first element indicates if vector bound is desired,
if first element is 1, the following values should be the number of
elements to project from, which should be greater than the sum of number of sources
and encoders (nLevel+nEnc). e.g. [1 5 6] means vector bounds projecting from
5 and 6 variables are desired.
% sp: if superposition region is desired, sp means superposition, 1 for
TRUE, 0 for FALSE.
% pf: if human readable converse proof is needed, 1=TRUE, 0=FALSE
NOTE: The first 6 parameters are required. The rest are optional, depending on user.
2. Test if a MDCS A is embedded in MDCS B:
isEmbedded(numSourA,numEncA,confA,numSourB,numEncB,confB);
where
% numSourA: number of sources in A
% numEncA: number of encoders in A
% confA: configuration matrix of A
% numSourB: number of sources in B
% numEncB: number of encoders in B
% confB: configuration matrix of B
3. Test if a MDCS A is isomorphic to MDCS B:
isIsomorphic(confA,confB,numSour,numEnc);
where
% confA: configuration matrix of A
% confB: configuration matrix of B
% numSour: number of sources in A & B
% numEnc: number of encoders in A & B
NOTE: confA, confB must be with the same size.
4. Enumerate MDCS instances:
[finalwoperm finalwperm finalwopermind finalwpermind]=genMDCStableEfficient(nLevel,nEnc,ifsave);
where
% nLevel: number of sources
% nEnc: number of encoders
% ifsave: 1 means to save the results in ./table/; 0 otherwise
% finalwoperm: final list of configurations of MDCS instances without permutation, i.e. non-isomorphic
% finalwperm: final list of configurations of MDCS instances with permutation, i.e. isomorphic
% finalwopermind: final list of indices for the configurations of MDCS instances without permutation,
i.e. non-isomorphic. The indices are corresponding to the Sperner family list of nEnc in ./table/
% finalwpermind: final list of indices for the configurations of MDCS instances with permutation,
i.e. isomorphic. The indices are corresponding to the Sperner family list of nEnc in ./table/
*********** Some other functions for interested users are listed *******************************
5. Generate Shannon outer bound on region of entropic vectors
[b A]=genShannOuter(numVar,ifsave,format);
where
% numVar: number of variables
% ifsave: 1 to save results to ./bounds/Shannon/, 0 otherwise
% format: std for standard format which is Ax<=b; lrs for b+Ax>=0
6. Generate matroid bounds:
Binary Extreme-ray representation:
[b,A]=genBinMatrInnerBoundext(numVar); % numVar <= 8, and numVar is the number of variables
Binary Half-space representation:
[b A] = genBinMatrInnerBoundSM(N); % N: number of variables
Binary vector bounds in extreme-ray rep.:
[output b]=genVecBinfromNonisoNew(numBits,numVar,upto);
where
% numBits: number of elements to project from;
% numVar: number of variables to project down to;
% unto: the max rank you want to have, if empty, upto=numBits;
Ternary Extreme-ray representation:
[b,A]=genTerMatrInnerBoundext(numVar); % numVar <= 8, and numVar is the number of variables
Ternary Half-space representation:
[b A] = genTerMatrInnerBoundSM(N); % N: number of variables
Ternary vector bounds in extreme-ray rep.:
[output b]=genVecTerfromNonisoNew(numBits,numVar,upto);
where
% numBits: number of elements to project from;
% numVar: number of variables to project down to;
% unto: the max rank you want to have, if empty, upto=numBits;
7. Test Matroid minors:
[Rank ind] = MinorCheck(varargin);
where
% The first input should be the rank vector(s) to check, if multiple vectors are
input as a matrix, each row is a rank vector
% The second and rest input are minors to test, it should be the rank vector of
the minor except U24, U25 and U35, i.e., ‘U24’, ‘U25’, and ‘U35’ are
recognizable minors;
% Rank: the rank vector(s) after excluding minors in the list;
% ind: indicator vector associated with each input minor: i-th position is 1 means
input ranks contain i-th minor and 0 otherwise.
8. Test if a matroid rank is connected:
[is separator] = isConnected(rank);
% rank vector is input, is=1 if it is connected, 0 otherwise. If is=0, the
separator will be given.
************* SOME extra features which require the user know more about the input ********************
9. Generate human readable proof
HumanReadableProof(inputfile1,inputfile2,numR,outputfile,ifpop);
where
% inputfile1: name of original polyhedron file in lrs format with .ine extension,
Shannon + NetCons
% inputfile2: name of file containing projected rate region polyhedral cone in lrs format
% numR: number of encoders, also number of rate constraints
% outputfile: file to write the converse proof in, including the coefficients and
inequalities necessary to obtain each inequality in the rate region
% ifpop: if you want to display a window listing the converse proof;
1 for TRUE, 0 for FALSE
10. Compare bounds for MDCS instances
NM = comp_bounds(Nlevel,nEnc,casenum,bound1,bound2)
where
% Nlevel: level number, nEnc: number of encoders
% casenum: indices from the enumeration of MDCS instances in 3 above,
% bound1 and bound2, the two bounds you want to compare: BIV for binary
% inner bound obtained from V-method applying double description, same as
% TIV, O for outer bound, SP for superposition, from6BIRateRegion for vector
% inner bounds from 6 variables, etc.
% NM: indices that the input two bounds do NOT match
=======================================================================================
e) REGENERATE or VERIFY RESULTS in paper [1]:
A. Rate Region and/or human readable proof verification: For every MDCS instance you want
to verify, figure out its configuration matrix first and use the command genMDCSRateRegion
in 1 above to generate the rate region and/or human readable converse proof;
B. Compare bounds on rate regions:
Use 10 above to verify the number of non-matched instances for different MDCS problems.
NOTE: when check vector bounds from N’, the casenum should be the instances for which
vector bound from N’-1 are not tight. e.g. verify vector binary bound from 9 bits for
(2,4) MDCS, you need to load NMBIO24from8.mat, since if vector bound from 8 bits is
tight, off course the bound from 9 bits will be tight as well.
C. Forbidden minor relationships:
FindMinorsSBin; %%%% regenerate the forbidden minors figure for Scalar binary
FindMinorsSP; %%%% regenerate the forbidden minors figure for superposition
D. Regenerate MDCS instances:
Use 4 above to do this.
=======================================================================================
f) VERSION HISTORY:
v1.0 Aug 5, 2014
=======================================================================================
g) CONTACT:
For questions or comments, please contact Congduan Li via email congduan.li@gmail.com
3141 Chestnut St,
Drexel ECE Dept,
Philadelphia, PA 19104
=======================================================================================
h) COPYRIGHT:
Same as the integrated packages, all codes written by the author are free for learning purposes.
=======================================================================================
i) REFERENCES:
[1] Congduan Li, Steven Weber, John MacLaren Walsh, “Multilevel Diversity Coding Systems:
Rate Regions, Codes, Computation, & Forbidden Minors”, IEEE Transactions on Information Theory,
2014, SUBMITTED. [Online] Available: http://arxiv.org/abs/1407.5659