Random checksums according a degree distribution and checksums
according a hypergraph
A file can be chopped into equally sized source packets. Instead of transmitting the source packets of the file we transmit checksum packets of some source packets. Here we present a C++ program which simulates the reception of packets through an erasure channel followed by two decoding processes: (1) by completely solving the system of linear equations and (2) by applying Luby’s [Luby02] fast decoding method. The C++ program contains four classes:
- LT class for decoding according Luby’s message-passing algorithm
- Linear class for decoding by completely solving the linear equations with Gaussian elimination algorithm
- Graph classes for simulating the reception on the erasure channel, where the reception can be operated in four modes:
o mode 0: random linear fountain
o mode 1: random transmission according to a given distribution of degrees
o mode 3: reception in a random order of distinct packets from a pre-computed set of packets (when the packets are expired, zero packets will be received)
o mode 2: random reception of copies of the packets of the pre-computed set (multiple copies are possible)
- Recv class receives the packets from the erasure channel and decodes them with the LT and Linear classes building correspondingly their decoding probability curves (as functions from the number of received packets)
Here we present an example where we generate about 2500 possible ways for combining 18 source packets with 54 checksum packets (each with a degree of 3). Each pre-computed set with 72 packets is rated by the average number of excess packets needed for the decoding. These 2500 sets (or hypergraphs) are sorted according the average number of excess packets required by LT (or message-passing) decoding.
For the best hypergraph we compute the decoding probability function in the mode of receiving the distinct packets and in the mode of receiving the random copies. For each mode there are two curves: for decoding with LT method and for decoding with Linear method. For comparison we provide also the decoding probability for the random transmission of packets with degree 3 and 1 (three times more packets with degree 3 than with degree 1). The decoding probability curve of the random linear fountain code is also provided:
Related links:
|
Generating 2500 hypergraphs |
|
|
Decoding probability curves of the best hypergraph |
|
|
Solving the linear equations with Gaussian elimination |
|
|
Decoding with message-passing algorithm |
|
|
Four types of reception patterns |
- MS Word version of this page [doc]
- The previous version of this program [ us | ch ]
* * *