Glanced upon a paper from the 2009 ISIT, titled “LT Codes Decoding: Design and Analysis” by Feng Lu et al. The authors discusses LT decoding strategy which is Peeling decoder (conventional simple LT decoding) followed by an extension based on the well known Widemann algorithm solving a sparse homogeneous linear system. Here is a brief summary as I understood.

On packet erasure channels (internet being one close realization of a model of this kind, where, the TCP/IP suit, one can either gets packets correctly delivered or lost in the wild), Luby Transform (LT) codes forms an easy way to transfer information. It is well known that, asymptotically (When the number of information symbols (or packets) and the number of packets received $r$ are large) near full recovery is made possible by simple peeling decoder which grows in complextity at . The claim is that, for or so, with , on average we can, with high probability, recover all of information packets by simple unwrapping of xor-ed packets. A more precise statement will read as: If from information packets, each coded packet constructed independently by xor operation (the number of packets taken for xor operation follows a distribution; Plain vanila version of LT codes uses Soliton distribution), then the content of the original information source can be recovered from any packets with probability by an average of symbol operations. However, when the number of input symbols is not large (say less, ) the overhead term is not small. It is not too surprising, since we need sufficiently large and to converge the performance in expectation. One can think of solving the system of linear equations using Gaussian elimination and get the best figures, but the question mark stays on the complexity of this method over the cheaper peeling decoder complexity .

Conventional LT decoding based on Peeling decoding rule terminate, once the number of degree -1 packets (ripple as it is called in graph theory parlance) are void. One can hope to continue from there, by using Gaussian elimination and decode a a few more (if the graph matrix rank permits it). If the original graph is full rank, one can technically decode all of them. Gauissian eliminatio being heavy, one hope to find an easy, preferably recursive method. Indeed there comes Wiedemann and that is what the authors use. The authors propose what they call as full rank decoding, which essentially is LT decoding, until there are no more degree one packets. From there, they borrow a packet and then uses Wiedemann algorithm which is somewhat light on computational complexity.

The larger aspect on whether this scheme do any better than conventional LT peeling decoder is the other question they answer. To achieve full recovery we need to have a full rank matrix. Now, the matrix being a sparse matrix defined over where is the number of received packets. The probability of the matrix having a full rank will directly help us to infer the decoding merits. This is an interesting piece since I had looked into the computation of the rank of a binary matrix and also the probability of a random matrix rank being equal to an arbitrary value. All this was done during the Modern Coding Theory doctoral course by Ruediger Urbanke at EPFL. For binary random matrix, we can also setup a recursive formula and thereby a good inference on the probability of decoding can be arrived at.

## 5 comments

Comments feed for this article

May 25, 2010 at 7:57 am

Haifeng LuHey Ratnu,

I have also read this ISIT paper.

I also read your blog on the calculation of the probability of a random matrix rank. The calculation is based on that all the elements are chosen uniformly. But in LT coding, the elements in the coding matrix are chosen according to the Robust Soliton Degree distribution which is not uniform.

Could you please give me some hints on how to calculate the probability of a coding matrix used in LT code to be full rank?

Thank you:)

Haifeng

June 21, 2010 at 6:47 am

ratnuuThanks Haifeng. I couldn’t read your message any sooner than this. Apologies for that. Yes, your observation is correct. For LT, with arbitrary node distribution (say Omega) it is possible to compute the probability of the matrix having full rank. I have a small tech note written sometime ago. I shall dig it out and send to you. Unfortunately, at the moment, I dont have it with me in my work server. Shall get back to you on this.

Best regards

Ratnuu

June 21, 2010 at 6:48 am

ratnuuBy the way, it will not be a nice closed form expression, but it is numerically possible to evaluate. Anyway, we will discuss this.

February 18, 2011 at 12:24 pm

JacoI am currently working on LT and Raptor fountain codes. I believe I got the encoding of the LT correct, bu am struggling with the decoding algorithm. If anyone has some advise or code samples I will appreciate it very much. I basically want to run some tests on the code and see how it handles certain degrees of packetloss.

Thank you very much!

Regards

Jaco

November 22, 2014 at 9:01 am

leeyoonguDear all, I am working in LT code and resolving decoding problem of LT code. I am reading the algorithm of Haifeng Lu, “LT-W: Improving LT Decoding With Wiedemann Solver”. This is good way to resolve LT problem when ripple size is empty. However, it is more complex. Do you suggest to me other method to decode LT code when ripple size is empty?