Software Developed by our Research Group

Some of the software we developed for our research projects can be found below.

- Information Theoretic Converse Prover (ITCP): A GAP package for converse proofs in network coding. In particular, this software can generate statements of the converse coding theorems for network coding rate regions. Uses symchm and qsopt_ex-interface (see below). Those who have dabbled with computer assisted proofs of network coding rate regions and/or non-Shannon-type information inequalities, have probably come across ITIP and XITIP , which are softwares that can verify whether a putative inequality bounding a network coding rate region is implied by a collection of linear information inequalities and a collection of linear constraints on the entropy function. ITCP takes this business one step further, with the ability to produce all inequalities bounding a network coding rate region that are implied by a collection of linear information inequalities and network coding constraints on the entropy function, thus solving a generation problem instead of the much easier verification problem. Apart from network coding rate region outer bounds, it supports computation of lower bounds on worst case information ratio in secret sharing and upper bounds on guessing numbers of directed graphs. (git repo, pdf documentation, theoretical description ). This software was developed by Jayant Apte and John MacLaren Walsh.
- Information Theoretic Achievability Prover (itap)

itap can perform following tasks:- Testing achievability of a rate vector for a network coding instance using vector linear codes over a specified finite field
- Testing achievability of an information ratio in a secret sharing instance using multi-linear secret sharing schemes over a specified finite field
- Testing representability of an integer polymatroid over a specified finite field.

- Network Enumeration and Hierarchy: This package can enumerate all non-isomorphic (symmetry removed) networks for a given (K, E) pair, where K is the number of sources and E is the number of hyperedges. The rate regions of the enumerated networks can be calculated by our rate region calculation package. It also builds a hierarchy structure among networks with different sizes using the operations defined in [1][2].

This package is written in GAP. The source files and saved data can be downloaded here, while the user manual can be found here. This package was developed by Congduan Li and John MacLaren Walsh. - Rate Region Calculations: This package is used to calculate various bounds on rate regions of multi-source hyperedge networks, which can be enumerated by our network enumeration and hierarchy package. The bounds can be compared to determine the exact rate regions. Saved results can be obtained here. Details can be found in [1][2].

This package is written in Matlab with integration of some other packages. It can be downloaded here and the user manual can be found here. This package was developed by Congduan Li and John MacLaren Walsh. - Convex Hull Method

The convex hull method is a method of polytope projection which incrementally builds up inner bounds in the projected space by running cleverly selected linear programs over the original polyhedron [3]. A transformation enables this same method to calculate projections of unbounded polyhedra. You can find our C implementation of this method here and a brief set of use instructions here. The library makes use of rational arithmetic based QSOptex linear program solver and the Fast Library for Number Theory.

This software was developed by Jayant Apte primarily to serve our needs to calculate non-Shannon inequalities and rate regions for network coding and distributed storage. Please contact Jayant Apte regarding this implementation of CHM. This software will be integrated into a forthcoming release of a larger entropic vectors and rate region calculation package. - Entropic Vectors and Rate Region Calculations: This is a collection
of MATLAB routines related to bounding entropic vectors and calculating
rate regions of multilevel diversity coding systems (MDCS), which can
be extended to general network coding and distributed storage systems.

These routines were developed by Congduan Li. The full package with calculated results and dependent packages is available here along with a brief description here. A lighter version without saved results and dependent packages is available here. This package can be used to verify the results in [4], which is available at arXiv. - Distributed Estimation of Channel Gains in Wireless Sensor
Networks

A distributed estimation algorithm based on expectation propagation was proposed in [5] to estimate the channel gains in wireless sensor networks. This algorithm was simulated for a moderate size network using Matlab. The “.m” files developed for this simulation can be found here.

This zipped file consists of the following “.m” files.- EP_shadowing.m - simulates the algorithm for a 20-node network when both prior statistics and channel gains are generated with pathloss exponent 4.
- EP_shadowing_mismatch.m - simulates the algorithm for a 20-node network when prior statistics are generated with pathloss exponent 4 while channel gains are generated with a different pathloss exponent.
- RandSleepStrategy.m - generates a random sleep strategy for the network
- ChannelGainStatGen.m - generates prior statistics of the channel gains using only the path loss (n = 4) effect when node positions are Gaussian distributed.
- ChannelGainGen.m - generates channel gains with path loss exponent 4 and adds shadowing effects to the gains
- ChannelGainGenMismatch.m - generates channel gains with path loss exponent ≠4 and adds shadowing effects to the gains
- LMS_shadowing.m - applies diffusion LMS algorithm for the same network

- This is a place-holder for a page that is under construction. Our parallel computing software packages for binary entropy vector membership, variational Bayesian speech enhancement and speaker identification, parallelized reverse search vertex enumeration, and rate regions for coded collaborative estimation will be posted soon.

[1] C. Li, S. Weber, and J. M. Walsh, “On Multi-source Networks: Enumeration, Rate Region Calculation, & Hierarchy, ” IEEE Transactions on Information Theory, Jul 2015, submitted. [Online]. Available: http://arxiv.org/abs/1507.05728

[2] C. Li, “On Multi-source Multi-sink Networks: Enumeration, Rate Region Calculation, & Hierarchy, ” Ph.D. dissertation, Drexel University, 2015. [Online]. Available: http://www.ece.drexel.edu/walsh/CongduanLi_Thesis.pdf

[3] C. Lassez and J.-L. Lassez, “Quantifier elimination for conjunctions of linear constraints via a convex hull algorithm,” in Symbolic and Numerical Computation for Artificial Intelligence, Donald, Kapur, and Mundy, Ed. Academic Press, 1993.

[4] C. Li, S. Weber, and J. M. Walsh, “Multilevel Diversity Coding Systems: Rate Regions, Codes, Computation, & Forbidden Minors,” IEEE Transactions on Information Theory, Jul 2014, submitted. [Online]. Available: http://arxiv.org/abs/1407.5659

[5] S. Ramanan and J. M. Walsh, “Distributed Estimation of Channel Gains in Wireless Sensor Networks,” vol. 58, no. 6, pp. 3097–3107, Jun. 2010. [Online]. Available: http://dx.doi.org/10.1109/TSP.2010.2044840