Study On Decoding Algorithms Of Spinal Codes

With the rapid development of wireless communication technology,higher requirements for efficient and accurate information transmission are put forward.In many cases,when the information is transmitted in the complex and changeable environment,the sender can not know the state of the channel accurately to adjust a appropriate coding rate.The rateless codes solve this problem well.The characteristics of producing everfount encoding symbols guarantee the adaptive transmission and little feedback,which perfectly fit the data transmission in complex channel.Up to now,several rateless codes have been invented including LT codes,Raptor codes,SRLDPC codes,Kite codes and Spinal codes and so on.Spinal codes have an advantage of simple encoding and decoding structure,achieve the Shannon capacity over both Additive White Gaussian Noise(AWGN)and Binary Symmetric Channel(BSC)models,so Spinal codes get more and more attetion.This thesis mainly introduces the decoding algorithms of Spinal codes.Based on this topic,the existed rateless codes are firstly introduced.Then,we briefly introduce the principle and encoding structure of Spinal codes.After that,we introduce two kinds of decoding algorithms of Spinal codes,which are Bubble decoding algorithm and Forward Stack decoding algorithm.Bubble decoding algorithm is simple in principle.Compared with searching the entire Spinal code decoding tree,Bubble algorithm executes a prune on it.As a result,the Bubble algorithm lowers the decoding complexity without the loss of performance.Using the Bubble algorithm,Spinal codes achieve the Shannon capacity over both Additive White Gaussian Noise(AWGN)and Binary Symmetric Channel(BSC).The Forward Stack decoding algorithm is based on the Stack decoding algorithm.By layering the decoding tree,the decoder can only transfer within one layer.Compared with the Bubble decoding algorithm,the Forward Stack algorithm further reduces the complexity without any performance loss.Meanwhile,the Forward Stack algorithm outperforms the stack decoding algorithm in storage space requirements.Based on the Fano decoding algorithm,we propose a modified unquantized Fano decoding algorithm.Firstly,we deduce the formula used in the algorithm and set the parameter in it by simulating.Then we introduce the unquantized Fano decoding algorithm.Compared with the Fano decoding algorithm,the threshold value's change is no longer a fixed value,therefore the unquantized Fano algorithm is more suitable for decoding in AWGN channel.After that,we do the simulation of the unquantized Fano decoding algorithm for Spinal codes and analyze the cause of inconformity.Finally,we propose the modified unquantized Fano decoding algorithm.It adds storage space limit,at the same time,keeps the nodes that the decoder has calculated.On one hand,the modified unquantized Fano decoding algorithm reduces the calculation of the repeated nodes since they have been stored already.On the other hand,when the decoder can not converge rapidly to the last level of the tree,we can stop the decoding in time,wait for a new pass of encoding symbols.simulation proves that the modified unquantized Fano decoding algorithm reduces the decoding computation further,while the performance are the same with the other two algorithms.