SEQUENTIAL-DECODING OF CONVOLUTIONAL-CODES BY A COMPRESSED MULTIPLE QUEUE ALGORITHM

The conventional multiple stack algorithm (MSA) is an efficient approa ch for solving erasure problems in sequential decoding. However, the r equirements of multiple stacks and large memory make its implementatio n difficult. Furthermore, the MSA allows only one stack to be in use a t a time: the other stacks will stay idle until the process in that st ack is terminated. Thus it seems difficult to implement the MSA with p arallel processing technology. A two-stack scheme is proposed to achie ve similar effects to the MSA. The scheme greatly reduces the loading for data transfer and I/O complexity required in the MSA, and makes pa rallel processing possible. An erasure-free sequential decoding algori thm for convolutional codes, the compressed multiple-queue algorithm ( CMQA), is introduced, based on systolic priority queue technology, whi ch can reorder the path metrics in a short and constant time. The deco ding speed will therefore be much faster than in traditional sequentia l decoders using sorting methods. In the CMQA, a systolic priority que ue is divided into two queues by adding control signals, thereby simpl ifying implementation. Computer simulations show that the CMQA outperf orms the MSA in bit error rate, with about one-third the memory requir ement of the MSA.