Gaussian elimination and Luby transform
methods
2006-03-24
A file can be chopped into equally sized packets. Instead of transmitting the source packets of the file we can transmit checksum packets of their various subsets. We compare the low cost Luby Transform (LT) decoding method [Luby02] with the Gaussian elimination exact decoding method which has a cubic cost [ MathWorld | PlanetMath | Wikipedia ]. The LT method is very simple and in considered examples is almost as good as the exact method.
In the present example:
- There are 18 source packets to be delivered to the receiver through an erasure channel
- The encoder transmits together with the 18 source packets 36 additional redundant packets
- Each redundant packet is a checksum of three source packets
- The 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
The below chart shows the performances of 270 considered all-sides K-ring hypergraphs according to the LT and Gaussian elimination methods:
[xls]
For all considered hypergraphs the performance of the LT decoding method follows the pattern of the theoretical upper bound curve with an almost constant little gap. It means that so far there are no pathological cases for which the LT decoding method is too bad.
The two decoding probability curves for the best of 270 hypergraphs are shown in the below chart:
[xls]
The simple low cost LT method is almost as good as the Gaussian elimination method with its cubic cost.
Related links:
- The C++ program [ cpp | txt | out ]
- MS Word version of this page [doc]
- Michael Luby, “LT codes”, The 43rd Annual IEEE Symposium on Foundations of Computer Science 2002, FOCS’02, November 16 – 19, pages 271 – 280 [Luby02]
- Gaussian elimination [ MathWorld | PlanetMath | Wikipedia ]
- Definition of hypergraph from MathWorld [hypergraph]
- Definition of hyperedge from MathWorld [hyperedge]
* * *