On The Encoding,Decoding And Applications Of Rateless Spinal Codes

Spinal codes are the first class of rateless codes which can be proved to achieve the capacity of binary symmetric channels and that of the additive white Gaussian noise channels.By employing hash function successively,spinal codes can generate near infinite pseudorandom bits.The coding structure of spinal codes is very simple.In addition,spinal codes have an excellent rate performance and perform well for varying or unknown channel conditions.Even with a very short block length,the gap between the achievable rate of spinal codes and the capacity is very small.However,although rateless spinal codes can provide an excellent rate performance and have a complete theoretical proof for capacity-achievability,there still exist several problems on the investigations and applications of spinal codes.For instance,the decoding complexity of spinal codes is still high during rateless transmission.In addition,the successive encoding process degrades the error-control capability of spinal codes.Moreover,there still exists controversy over the applications of spinal codes in some complicated communication scenarios other than the conventional point-to-point link.The main work of this paper is on the study of encoding and decoding improvement,as well as the application of rateless spinal codes,including the following contents:In order to decrease the decoding complexity of spinal codes,this dissertation proposes a low complexity sequential decoding algorithm based on the stack algorithm,which is initially employed to decode the convolutional code.By dividing the code tree into several layers and executing stack search process for each individual layer,the large scale “jump”phenomena are restrained in the proposed decoding algorithm.Thus the number of the nodes searched by the proposed algorithm is reduced,resulting in low time complexity and space complexity.The simulation results show that the proposed decoding algorithm can significantly decrease the decoding complexity of spinal codes without sacrificing the rate performance.And the complexity of the proposed algorithm decreases with the channel conditions turning better.For the weakness of the spinal coding structure,especially for the bad error-control capability and the large possible transmission delay,a two-way spinal coding structure is proposed.By the two-way encoding process,the information of each message segment of the proposed code is conveyed by the coded symbols corresponding to all the message segments.Based on this two-way coding strategy,this dissertation provides an iterative decoding algorithm.And the iterative decoding process can converge quickly with a small iteration number.In addition,the transmission scheme is discussed for two-way spinal codes.The analysis indicates that different transmission schemes can be treated as the different tradeoffs between the performance and the decoding complexity.By choosing a suitable ratio of the forward pass number to the backward pass number,two-way spinal codes can provide excellent transmission performance with low decoding complexity.Simulation results show that two-way spinal codes can achieve a high transmission rate and a very low error probability with a small receiving cache.Aiming at the applications of rateless spinal codes,this dissertation proposes a superposition spinal coding scheme for the wireless relay channels.By the information rearrangement,superposition coding and signal mixing process,the proposed coding scheme completely implements information theoretic superposition coding structure and random binning process.The proposed coding scheme has a simple coding structure,which is flexible and effective.And all the encoders and decoders can maintain unchanged for the varying channel conditions.In addition,this dissertation provides the optimization methods for the superposition spinal coding scheme.Since only two parameters are considered in the optimization,the optimization can be realized with low complexity.The proposed optimization not only can provide suitable parameters to achieve good performance,but also can predict the rate performance.Simulation results show that the transmission rates of the proposed coding scheme are very close to the theoretic limits for both Gaussian relay channel and fading relay channel.Furthermore,this dissertation proves that the proposed coding scheme can achieve the theoretic limit of half-duplex DF relaying.By analyzing the achievable rate of the superposition coding scheme and the error probability at each node,the theoretic limit achieving property can be completed.And the proposed coding scheme is the first class of rateless coding schemes,which can be proved to achieve the theoretic limit of the wireless relay channel.