Purification of random linear codes

Here I suggest purifying a linear code. I take a finite code and check if it contains subsets of linearly dependent elements. The size of the subsets is bounded above by depth. Each time I find a subset containing linearly dependent elements, I completely remove from the original code one (the smallest) element of the subset. Thus from a code of a given rate I can obtain a code with a higher rate which do not contain any n linearly dependent elements, where .

For example by taking a random linear code of 10 source packets with the rate of 10/70 one can form a code of rate ½ by removing linearly dependent elements with a depth 4. The average number of excess packets for successful decoding is 1.62 with the original code and 1.09 with the purified code of rate ½.

This method can be applied on codes with constant desired degree. For random linear code of degree 3, 10 source packets and rate 10/70, we obtain, with a depth 3, a code of rate 1/2 , such that the average number of excess packets for decoding, that was initially 4.13, now, after the purification, becomes 1.45.

With a larger number of source packets a larger depth is required. Computation becomes much heavier. The improvement measured by the average number of excess packets is not as noticeable as with small number of source packets (see the output file).

- The program [cpp]

- The output [txt]

- Gaussian elimination class [cpp, h]

- Download all [zip]

* * *