# What's the decoding time complexity of LT codes?

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).

• 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?
– R B
Jan 19, 2020 at 2:48
• 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?
– R B
Jan 19, 2020 at 2:53
• @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.
– D.W.
Jan 19, 2020 at 3:44
• (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?
– R B
Jan 19, 2020 at 22:42
• 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.
– R B
Jan 19, 2020 at 22:46