Investigation On Decoding Algorithms And Complexity Analysis Of Rateless Spinal Code

With the rapid development of wireless communication, more and more attention has been paid to the reliable and efficient data transmission technology. How to adaptively choose the appropriate rate to transmit data efficiently is addressed urgently. The occurrence of rateless code provides us a new way to solve this problem. The rate of rateless code is not restricted.The character of rateless code is adaptive to the channel state and it does not require to send feedback signals to transmitter during the transmission. Rateless code is a kind of reliable and efficient error correction technology. In this thesis, we introduce Spinal code as a kind of rateless code applies to wireless communication with the advantages of simple structure, strong practicality and high efficiency. And it has been proved that Spinal code can achieve Shannon capacity for the binary symmetric channel(BSC) and the additive white Gaussian noise(AWGN) channel.We investigate the decoding algorithm of Spinal code in this thesis. Base on the structure of Spinal code and the sequential decoding algorithm of convolutional code, a stack decoding algorithm for rateless Spinal code is proposed. The Spinal stack decoding algorithm employs a stack to store and sort the decoding nodes which contains path information. At each decoding step, the decoder computes all successors of the best decoding node in the stack and then pushes them to the stack and sorts all the obtained nodes after erasing this best node. The decoding ends up with the acquisition of the best integrated decoding node or the stack overflows. We will get the estimated source information according to the path information in the best integrated decoding node.A lot of jumping occur in stack decoding when the decoder jumps to a new node from another node, where the two nodes are lying in two different integrated decoding paths. This phenomenon results in a high computational cost. Considering the disadvantages of the stack decoding,we proposed forward stack decoding(FSD) as an improved algorithm. This decoding algorithm divides the decoding tree of the spinal code into several layers, and then searches the decoding paths in each single layer.The FSD algorithm not only solves the oversize jumping but it also decreases the complexity further.Compares with the Bubble decoding algorithm which was initially decrease the complexity significantly, the proposed stack decoding algorithm and FSD algorithm can decrease the complexity significantly without sacrificing the rate performance. Simulation shows that the complexity of the Spinal stack decoding algorithm is only 50%~70% of that of the Bubble decoding algorithm. We also illustrate that the complexity of the FSD algorithm which decreases with the increase of the signal-to-noise(SNR), the complexity of FSD algorithm is the least in three algorithms, the complexity is only 15% of that of the bubble decoder when SNR is 20 d B. Theoretical analysis of Spinal stack decoding algorithm indicates that the complexity per decoded is bounded by a constant, no matter what channel conditions the upper bound of complexity is existent. As a result, the Spinal stack decoding algorithm and FSD algorithm are reliable and effective decoding algorithms.