Sequential Decoding with Adaptive Reordering of Codeword Trees

摘要

Modifications are presented for standard sequential decoding algorithms in anattempt to operate at rates greater than Ro, the compound cutoff rate. We call the new algorithms sequential decoding with reordering (SDR) algorithms. They observe the receive message at the channel output and use this information to reorder the digits in the codeword tree. The resulting tree is then searched by a sequential decoder; the goal of reordering is to obtain a tree that is easy to search. However, codeword trees associated with convolutional codes cannot be reordered and still retain their uniform structure and slow growth. For this reason, we use low-density codes, a class of block codes. The SDR algorithms are presented for the binary erasure and binary symmetric channels. Simulation results suggest that at high code rates, the algorithms can be used at rates nearly equal to or greater than Ro. Because of differences between codeword trees for low-density codes and convolutional codes, a new sequential decoding algorithm designed for low-density codes is presented. An SDR algorithm is presented that can be used as a soft decision decoder on channels with side information and channels with real-valued outputs. Theses. (JHD)