ROME: Rateless online MDS code for wireless data broadcasting

Packet level coding schemes are used to improve the transmission reliability and efficiency in data broadcasting applications, especially for wireless networks. However, existing coding schemes have large redundancy because packets are coded in random or certain probability distributions. Although the Maximum Distance Separable(MDS) codes are designed without coding redundancy, they are not effective if the packet erasure probability is high. To reduce the coding redundancy, lots of work use the receiver side information to adjust the codes construction on-the-fly, which is more beneficial. However, these work have disadvantages:1) the coding redundancy is also large; 2) the feedback schemes have great affect on code's performance. In this paper, we design a novel "Rateless Online MDS Code"(ROME) with a robust feedback scheme to eliminate the coding redundancy. Our contributions include that our codes are throughput optimal codes without redundancy, and we analyze the theoretical finite field size bound to achieve throughput optimal codes. We also design the finite field construction to speed up the encoding and decoding process. Finally, we compare the performance between ROME and other existing codes, like RLC, LT, RT oblivious and SLT codes, and their performance when feedbacks are erased.