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