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

概要

論文の詳細を見る
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.