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

Yi Pin Lu, I. Wei Lai, Chia Han Lee, Tzi Dar Chiueh

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


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.

Original languageEnglish
Article number6733534
Pages (from-to)217-220
Number of pages4
JournalIEEE Wireless Communications Letters
Issue number2
Publication statusPublished - 2014 Apr
Externally publishedYes


  • Error correction code
  • Raptor code
  • RaptorQ code
  • Sherman-Morrison formula
  • fountain code

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Low-complexity decoding for RaptorQ codes using a recursive matrix inversion formula'. Together they form a unique fingerprint.

Cite this