A Fast Raptor Codes Decoding Strategy for Real-Time Communication Systems

We propose an efficient algorithm for Raptor decoding, which reduces the computational complexity of the most time-consuming steps in systematic decoding. Our proposed algorithm includes two aspects- First, to handle the decoding failure of the Raptor decoding, we propose a scheme, which is called the No-Wrapup Failure Handling scheme. It can resume the decoding process from where it fails after receiving a pre-defined number of additional encoded symbols, and thus avoids the repetition of time-consuming steps in the decoding process. Second, in order to reduce the time of finding the row with the minimum degree in the precode, we propose a Fast Min-Degree Seeking (FMDS) scheme. FMDS automatically maintains and updates the row degrees of the precode when converting the precode into an identity matrix through Gaussian elimination and Belief-propagation. Experimental results show that, compared to other Raptor decoding schemes, the proposed scheme achieves a much shorter decoding time, and can greatly speed up the data recovery in real-time applications.