Stepping-Random Code: A Rateless Erasure Code for Short-Length Messages

Zan-Kai CHONG  Bok-Min GOI  Hiroyuki OHSAKI  Bryan Cheng-Kuan NG  Hong-Tat EWE  

IEICE TRANSACTIONS on Communications   Vol.E96-B   No.7   pp.1764-1771
Publication Date: 2013/07/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E96.B.1764
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Internet Architectures, Protocols, and Management Methods that Enable Sustainable Development)
rateless erasure code,  short-length messages,  

Full Text: PDF(1.8MB)>>
Buy this Article

Rateless erasure code is an error correction code that is able to encode a message of k uncoded symbols into an infinite number of coded symbols. One may reconstruct the original message from any k(1+ε) coded symbols, where ε denotes the decoding inefficiency. This paper proposes a hybrid code that combines the stepping code and random code and name it as Stepping-Random (SR) code. The Part I (first k) coded symbols of SR code are generated with stepping code. The rest of the coded symbols are generated with random code and denoted as Part II coded symbols. The numerical results show that the new hybrid code is able to achieve a complete decoding with no extra coded symbol (ε=0) if all the Part I coded symbols are received without loss. However, if only a portion of Part I coded symbols are received, a high probability of complete decoding is still achievable with k+10 coded symbols from the combination of Part I and II. SR code has a decoding complexity of O(k) in the former and O((βk)3) in the latter, where β ∈ R for 0 ≤ β ≤ 1, is the fraction of uncoded symbols that fails to be reconstructed from Part I coded symbols.