Reduced-Complexity Decoding of Raptor Codes over Fading Channels
Ketai Hu, Jeff Castura, Yongyi Mao · 2006
Fountain codes are a universal class of rateless codes originally designed for erasure channels. Naturally adapting to channel states without channel knowledge at the transmitter, fountain codes have recently been demonstrated also as an appealing solution for communication over fading channels. However, their relatively high decoding complexity limits their practical use in a wireless setting. In this paper, we present a simple modification of the decoding algorithm for Raptor codes — a type of fountain codes — over fading channels, where the complexity is significantly reduced without sacrifice of performance. In this paper, we present a simple modification of the decoding algorithm for Raptor codes — a type of fountain codes — over fading channels. Similar to the original decoding algorithm, our algorithm is still based on the sum-product algorithm (13) on the factor-graph representation of the code. But instead of resetting the decoder at every decoding attempt, the results of previous decoding attempt are used to initialize the current decoding attempt. We show that comparing with the existing decoding algorithms, the modified algorithm in this paper offers a significantly reduced decoding complexity without any loss of performance. This paper is structured as follows. We will first review the rateless coding paradigm for wireless communications in Section II. We then describe the construction of Raptor codes and the existing decoding algorithms in Section III. In Section IV, we pause to introduce the performance and complexity metrics considered in this paper. In Section V, we present the modified decoding algorithm and provide some theoretical and intuitive justification. In section VI, we provide simulation results for our proposed algorithm and make comparison with the existing algorithms. The paper is concluded in Section VII.