Multiple-inputs systolic priority queue for fast sequentialdecoding of convolutional codes

摘要

The operating speed of a sequential decoder with stack algorithmnis usually limited by the time to search the best node for furthernextension. This problem can be completely alleviated by using thensystolic priority queue to replace the stack memory. However, thensystolic priority queues developed previously are accessible only in thencases when the number of inputs processed is small. This is because thencomplexity of a queue grows up quickly as the volume of data flowingnthrough it increases. Since the largest amount of data flowing through ansystolic priority queue is equal to the number of inputs to this queue,nthe systolic priority queue is not suitable for a system with manyninputs. A modified version of previously developed circuits is proposed.nThe number of transmission gates required in this circuit isnproportional to 3N instead of N2, where N is the number ofninputs. Also the total number of control signals is proportional to 3Nn2 instead of N3. But the number of comparatorsnrequired is proportional to C2N+1, as before. Thisnmodified circuit can be used in cases where the number of inputs isnsmall (N⩽8). A new algorithm for the multiple-inputs systolicnpriority queue (MISPQ) is proposed. By using this algorithm, a MISPQ maynbe implemented with several smaller queues, each is used to process anpart of data in the MISPQ. Since the volume of data flowing through eachnqueue is small, these queues will be simpler. However, some additionalncircuits should be used for the interactions between queues. A circuitnfor implementing this algorithm is presented and its complexity isnanalysed. The number of transmission gates for the MISPQ is proportionalnto 3N, the number of control signals is proportional ton(3N2/2), and the number of comparators is proportional to 4Cn2N/2+1. Thus this new architecture is feasible fornlarge N (e.g.N⩾8)