Luby transform method
2006-03-28
A file can be chopped into equally sized source packets. Instead of transmitting these source packets we can transmit checksum packets of some of their subsets. In 060324-LT-vs-Rank [ ch | us ] we compared the low cost Luby Transform (LT) decoding method [Luby02] with the exact method for solving linear equations [ MathWorld | PlanetMath | Wikipedia ]. Here we present a new version of a C++ program carrying out the same comparison. The obtained results are the same. In this version the LT decoding is implemented on a matrix instead of on a graph (as in 060324-LT-vs-Rank [ ch | us ]).
In the present example (exactly as in 060324-LT-vs-Rank [ ch | us ]):
- There are 18 source packets to be delivered through an erasure channel to the receiver
- The encoder transmits together with the 18 source packets 36 additional redundant packets
- Each redundant packet is a checksum of three source packets
- Triplets of the source packets forming the checksum packets are selected such that each source packet is used in an equal number of checksum packets
- Each selection of checksums corresponds to a hypergraph [hypergraph]
- 270 hypergraphs are considered, called all-sides K-ring hypergraphs [ ch | us ]
- The decoding probability is a function of received excess packets. The sum of the decoding probabilities for all numbers of the excess packets is the performance of a specific hypergraph
- For each of 270 hypergraphs we compute the decoding probability function by passing through 10’000 different packet arrival sequences
- Decoding probabilities are computed with Luby transform method and with Gaussian elimination exact method
LT decoding and linear equation decoding performances of 270 considered hypergraphs:
[xls]
The decoding probability of one of the best hypergraphs (with the indexes: s1=3, s2=6, s3=13):
[xls]
Results are identical to that of the curves in 060324-LT-vs-Rank [ ch | us ].
Links:
|
|
Linear |
LT |
Graph |
- MS Word version of this page [doc]
- The previous version of this comparison [ ch | us ]
* * *