TY - JOUR

T1 - Low-complexity decoding for RaptorQ codes using a recursive matrix inversion formula

AU - Lu, Yi Pin

AU - Lai, I. Wei

AU - Lee, Chia Han

AU - Chiueh, Tzi Dar

PY - 2014/4

Y1 - 2014/4

N2 - In this letter, we propose a low-complexity recursive decoding algorithm for rateless RaptorQ codes, the next generation error correction codes adopted by several standards such as DVB-H. Conventionally, the decoding of RaptorQ codes requires inverting a huge receive code generator matrix (RCGM). Instead of such costly matrix inversion, we propose to calculate the inverse of the transmit code generator matrix (TCGM) beforehand. Then, based on this pre-calculated inverse, the Sherman-Morrison formula is applied to recursively compute the inverse of the RCGM at run time. Most computations are thus shifted offline. Moreover, this recursive decoding distributes the computations among different time slots, thereby significantly shortening the decoding latency and improving the hardware utilization. Numerical simulations demonstrate that the computational complexity of the proposed recursive decoding is as low as 6.5% of that required by the conventional method using direct matrix inversion.

AB - In this letter, we propose a low-complexity recursive decoding algorithm for rateless RaptorQ codes, the next generation error correction codes adopted by several standards such as DVB-H. Conventionally, the decoding of RaptorQ codes requires inverting a huge receive code generator matrix (RCGM). Instead of such costly matrix inversion, we propose to calculate the inverse of the transmit code generator matrix (TCGM) beforehand. Then, based on this pre-calculated inverse, the Sherman-Morrison formula is applied to recursively compute the inverse of the RCGM at run time. Most computations are thus shifted offline. Moreover, this recursive decoding distributes the computations among different time slots, thereby significantly shortening the decoding latency and improving the hardware utilization. Numerical simulations demonstrate that the computational complexity of the proposed recursive decoding is as low as 6.5% of that required by the conventional method using direct matrix inversion.

KW - Error correction code

KW - Raptor code

KW - RaptorQ code

KW - Sherman-Morrison formula

KW - fountain code

UR - http://www.scopus.com/inward/record.url?scp=84899634417&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84899634417&partnerID=8YFLogxK

U2 - 10.1109/WCL.2014.020314.130872

DO - 10.1109/WCL.2014.020314.130872

M3 - Article

AN - SCOPUS:84899634417

SN - 2162-2337

VL - 3

SP - 217

EP - 220

JO - IEEE Wireless Communications Letters

JF - IEEE Wireless Communications Letters

IS - 2

M1 - 6733534

ER -