LT codes are practical fountain codes that are near-optimal erasure correcting codes.

Simply stated, for encoding a $n$-block message, each packet first chooses a degree $d\in\{1,\ldots,n\}$ according to a specific distribution, and then $d$ random blocks are xor-ed to create the packet's message.

The analysis shows that $O(n)$ packets that make to the receiver are enough for decoding, by allowing finding degree-one packets and xoring its content from all other packets that contain the same block (decreasing their degree by one).

What I haven't found in Luby's paper, or anywhere else, is the runtime complexity of the decoding. That is, what's the overall time spend on computing the original message.

A simple argument shows that $O(n^2)$ time is enough. Can we do better?


The approach you describe can be implemented to run in linear time.

Build a bipartite graph where left-vertices are blocks and right-vertices are packets, and with an edge from block $b$ to packet $p$ if $b$ is one of the blocks xor-ed to create $p$'s message. Store the bipartite graph in adjacency list format. Also keep track of the degree of each packet, so given a packet $p$ you can compute its degree in $O(1)$ time.

Then it's easy to implement the algorithm you describe in $O(n)$ time, using a worklist algorithm. The worklist is a list of all packets of degree one. In each iteration, you remove a degree-one packet $p$ from the worklist, then process it as follows. Find the corresponding block $b$, then find all other packets $p'$ containing the block. Xor $b$ into $p'$, and delete the edge $(b,p')$ (and update the degree of $p'$). This can be done in $O(1)$ time. If the new degree of $p'$ is 1, add $p'$ to the worklist. Repeat until the worklist is empty.

The running time is $O(1)$ per edge in the bipartite graph, i.e., $O(m)$ time where $m$ counts the number of edges in the graph (the sum of degrees of all of the packets).

  • $\begingroup$ Thanks for the answer. I agree that O(m) is achievable this way. The two questions I have are: (1) what is m, as a function of n, for the distribution (Soliton / robust Soliton) that gives O(n) packets overall? And (2) can we get a faster algorithm by getting more than O(n) packets? $\endgroup$
    – R B
    Jan 19 '20 at 2:48
  • $\begingroup$ That is, the distribution presented in the paper aimed to minimize the number of packets, potentially without concerning the decode time. Is it optimal also when considering the decoding? $\endgroup$
    – R B
    Jan 19 '20 at 2:53
  • $\begingroup$ @RB, I don't know; the distribution isn't specified in the question, so I'm not in a position to answer about the asymptotics of $m$ as a function of $n$. That sounds worth a separate question, perhaps in Math.SE. It appears that (1) basically boils down to what is the expectation of that distribution. $\endgroup$
    – D.W.
    Jan 19 '20 at 3:44
  • $\begingroup$ (1) may boil to computing expectation, but perhaps we don't need to decode all edges to recover the message? That is, we need to get all blocks attached to a degree-1 packet at some point, but why do we have to remove all edges? Think of it this way -- say we decoded all blocks but 1. Now comes a new packet with high degree and without our missing block. Why should we bother with it? $\endgroup$
    – R B
    Jan 19 '20 at 22:42
  • $\begingroup$ That is to say, I agree that your approach gives $O(m)$ time; I am just not convinced that this is the best we can hope for. $\endgroup$
    – R B
    Jan 19 '20 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.