1
$\begingroup$

I am having a small clarification with the difference between LDPC and fountain codes.

  • In LDPC codes, each parity bit is depenedent on numerous data bits. Isn't that similar to fountain codes as the encoded blocks are dependent on each other(I'm thinking of luby transform codes)?

Also, my professor was explaining that it doesn't matter if some blocks are missed, as long as it receives a subset of the encoded blocks. Fountain codes can decode the message because it just keeps listening to receive more information as there is enough redundancy built in.

  • My doubt is that, if it just keeps listening, when does the transmitter transmit the next set of messages if it's always sending redundancy to make up for what could be possibly deleted? Especially since there is no feedback.

  • Or is it that the message sizes are so large and that the encoding is done so that the redundancy is built throughout the message so that even if certain blocks are lost, we can still decode the information?

  • Lastly, fountain code applications are lossy connection, etc. In which case, why is this only applied to erasure channels?

  • Because if it is good at combating lossy connection, then it should also be able to effectively combat deletion codes right?
$\endgroup$
1
$\begingroup$

LDPC codes are a subset of linear channel codes. In terms of functionality, they are similar to other linear channel codes. However, they are constructed using a sparse bipartite graph.

Fountain codes are rateless codes. These type of codes are more useful in broadcast/multicast settings. If we use fixed-rate codes in such settings, we need to make sure that each and every packet is correctly received at all receivers. This can become inefficient since each broadcast can potentially be re-iterated (depending on the re-transmission protocol) until all receivers receive all packets. Consider for example a case with 10 receivers, all have correctly received the packet #2 except one. This specific packet will be broadcast to all until the last receiver gets the packet. However, with a rateless code, the packet index is not a matter anymore (i.e. whether it is packet #2 or not). This is because a group of packets are selected at first and new encoded packets are generated randomly (hence, all randomly encoded packets look just like a new piece of information about the group and the index does not matter anymore). Any linearly independent subset of valid packets is enough to decode (acquire) the original group of packets.

Also I can see you have difficulty understanding acknowledge policy. We can have many different types of such policy. So based on the Ack protocol, the transmitter stops and listens for the ack from the receivers to find out their status in terms of the number or the index of missing/collected packets.

$\endgroup$
  • $\begingroup$ So in essence, when you said, linearly independent, is each message being treated as a vector and as long as those vectors can come to be linearly independent, it's decodeable? So this also means that the number of vectors(the number of transmitted packets) sent must be equal to or greater than the size of each vector right? $\endgroup$ – Christian Sep 3 '16 at 20:40
  • $\begingroup$ Also, when talking about ACK protocols, is that just a fancier way of saying feedback or is there some distinction? $\endgroup$ – Christian Sep 3 '16 at 20:42
  • $\begingroup$ Assuming $K$ vectors of size $l$ as the source (generation block), we generate encoded vectors of the same length ($l$). We need $K$ valid encoded vectors at the receiver (some of them are not received due to erasure). The original packets are recovered by solving a system of $K$ linear equations with $K$ unknown vectors. Regarding Ack, yes it resembles a form of feedback. But we have very different types of such mechanism which can be categorized into positive/negative or group/single Ack. $\endgroup$ – msm Sep 3 '16 at 22:50

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.