Coupled checksums of half-packets
2006-04-13
Abstract: in
random linear fountain code the source packets are decoded by solving linear
equations which result to a cubic complexity. The decoding probability of
random linear fountain code is high. Many other codes mimic the performance of
the random linear fountain reducing at the same time the decoding complexity.
The average number of excess packets needed for a successful decoding of random
linear fountain code is 1.6,
irrespectively to the number of source packets. If, (1) by dividing the source packets into half-packets we double the
number of source packets, (2) we apply
the random linear fountain code to these half-packets and (3) we pair the checksums into full-sized packets before transmission,
then we easily obtain a code with an average number of excess packets needed
for a successful decoding equal to 1.03
(instead of 1.6). Next, on examples with 10 to 12 source packets, we show that
the way how the checksum half-packets are coupled can further reduce the
average number of needed excess packets to 0.3!
In order to transmit a file over an erasure channel, the file can be copped into equally sized K source packets – symbol nodes. By XOR-ing any subset of the source packets of the file we can obtain a redundant packet – checksum node. We can imagine a bipartite graph where from one side we have the symbol nodes and from another side the checksum nodes. A checksum node is the XOR sum of all symbol nodes connected by the bipartite graph.
Random linear fountain
code is a size-less codeword, where any of checksum nodes is connected
to any of symbol nodes with an equal probability of 0.5. With random linear
fountain code the probability of decoding of the source file becomes quite high
after the receiver collects as many redundant packets as there are source
packets in the file. With a very little number of excess packets the decoding
probability quickly approaches to 1. Irrespectively to the number K of source packets (
) the decoding probability depends only on the number of
collected excess packets. In random linear fountain code the average number of
excess packets for successful decoding is 1.61.
|
Fig. 1. Random linear fountain [xls] |
Constant symbol degree and constant checksum degree code is using a bipartite graph in which the degree of nodes is constant on both sides. In the example of 060406-setof-checksums [ ch | us ] we have shown that the performance of the constant degree code can be better than that of the random linear fountain. In the constant degree code the number of redundant packets is however must be predefined. The average number of excess packets needed for the successful decoding of 10 source packets is 1.21.
|
Fig. 2. 10 source packets, 30 transmitted packets, degree of
checksum nodes 3, degree of symbol nodes 9 [xls], source excel file of 060406-setof-checksums
[ ch
| xls
| cpp
| out
| us
| xls
| cpp
| out
] |
Fig. 3. 20 source packets, 60 transmitted packets, degree of checksum nodes 5, degree of symbol nodes
15 [xls], source excel file of 060406-setof-checksums [
ch
| xls
| cpp
| out
| us
| xls
| cpp
| out
] |
Paired checksums of half-packets
can improve the decoding probability. Each of K packets of the file can be divided into two sub-packets. Then all
sub-packets can be
regarded as symbol nodes and the checksum nodes corresponding to these half-sized
source packets can be generated with one of the above discussed techniques – either
with random linear fountain code or with
constant symbol degree and constant source
degree code. Further, the small checksum packets can be randomly paired back
into full-sized packets and then transmitted. Assuming that the decoding
probability f as a function of the
number of excess packets is known for source packets, the
decoding probability g of paired
checksums is computed as follows: 
, 
, … 
. The average number of excess packets successful decoding
with paired checksums of half-packets using random linear fountain is 1.03. The
average number of excess packets for decoding 10 source packets with randomly
paired checksums of half-packets using constant symbol degree and constant
checksum degree code (for 20 source half-packets) is 0.97.
|
Fig. 4. Pairing the random checksums of half-packets [xls] |
Fig. 5. 10 source packets, 20 source half-packets, 60 checksum half-packets, 30 transmitted packets [xls] |
Efficient coupling of checksums of the half-packets can significantly change the decoding probability of the code. The decoding probability changes with the way how the checksums packets of half-packets are coupled into full size packets before transmission. With a good coupling the average number of excess packets for successful decoding can be further decreased to 0.29.
|
Fig. 6.
Coupling of the half-packets
of a regular degree code, 10 source packets, 20 source half-packets, 40
checksum half-packets of degree 7 and 20 transmitted coupled packets [ xls | csv | cpp | out ] |
A good coupled
half-packet checksum codes is found by generating its random variants. Let
K be the number of half-packets, such
that 
is the number of
full-packets. The K half-packets are simply
the source packets of the file and thus we can create checksum
packets. We relay on the constant symbol degree and constant checksum degree
code described in 060406-setof-checksums [ ch
| us
]: we cyclically order all K source
packets. Then we form the first block of K
checksum packets. Each checksum packet is placed in association with one source
packet in the cycle, without necessarily including that source packet into the
computation of the associated checksum packet. Let d be the desired constant degree of all checksum packets. The d source packets for computing any given
checksum packet are chosen from the cycle of the source packets according to d distances relatively to the associated
source packet. The d distances are
distinct and are the same for all K
checksum packets. With the second different set of d distinct distances we can similarly create another block of K checksum packets. With such method the
degree is regular on both sides of the bipartite graph. Now recall that the checksum packets have
the half of the size of the packets to be transmitted. The two blocks of K checksum packets are cyclically ordered.
The transmitted checksum packets are obtained by sequentially coupling the
checksum packets from the first block with the corresponding checksum packet of
the second block according to their cyclical order. This code can be therefore
created from two sets of d distinct
distances.
For K equal to 20 (i.e. 10 full sized source packets) and the degree of checksum packets equal to 7 with the above described method we randomly generated 8000 codes of coupled checksums. The performance of each code is measured by the average number of excess packets needed for the successful decoding, computed by passing 4000 random receive sequences. The 8000 random codes, sorted according their performance, are shown in the below chart:
|
Fig. 7. Coupled half-packet checksum codes, number of full-sized source
packets 10, number of transmitted packets 20 [ xls | csv | cpp ] |
The drop of the average number of excess packets at the end of the chart represents a dozen of coupled checksum codes which are decoded with an average excess of 0.27 to 0.42 packets. The dozen of these codes are checked with one million [ cpp | out ] and hundred thousands [ cpp | out ] of random receive sequences and the low average number of excess packets is confirmed. If, in these good coupled checksum codes we change only the coupling pairs, conserving however the regular degree coding of the half-packets, the average number of the needed excess packets rises immediately to its usual level of about 1.
Similar coupled half-checksum codes are found for 11 full-sized source packets, with an average number of needed excess packets 0.31 to 0.42 [ cpp | csv | xls ] and for 12 full-sized source packets with an average number of needed excess packets 0.31 to 0.37 [cpp | csv | xls ].
Related links:
- Robert G. Gallager, “Low-Density Parity-Check Codes”, 1963 [Gallager63]
- Daniel A. Spielman “Finding Good LDPC Codes”, 1998 [Spielman98]
- Amin Shokrollahi “LDPC Codes: An Introduction”, 2003 [Shokrollahi03]
- C++ program trying random variants of coupled half-packet checksum codes [ cpp | csv | xls ]
- Classes and functions used in the program [ recv.cpp | recv.h | graph.cpp | graph.h | linear.cpp | linear.h | lt.cpp | lt.h ]
- Download all program files [zip]
- MS Word version of this web page [doc]
- Pre-computed sets of checksum packets of constant degree with various size factors [ ch | us ]
- The average number of excess packets needed for successful decoding in a pre-computed set of checksum packets of constant degree [ ch | us ]
- Random linear fountain code versus pre-computed collection of “good” checksum packets of constant degree [ ch | us ]
* * *
© Switzernet Sŕrl (www.switzernet.com)