MULTIPLE-INPUTS SYSTOLIC PRIORITY QUEUE FOR FAST SEQUENTIAL-DECODING OF CONVOLUTIONAL-CODES

The operating speed of a sequential decoder with stack algorithm is us ually limited by the time to search the best node for further extensio n. This problem can be completely alleviated by using the systolic pri ority queue to replace the stack memory. However, the systolic priorit y queues developed previously are accessible only in the cases when th e number of inputs processed is small. This is because the complexity of a queue grows up quickly as the volume of data flowing through it i ncreases. Since the largest amount of data flowing through a systolic priority queue is equal to the number of inputs to this queue, the sys tolic priority queue is not suitable for a system with many inputs. A modified version of previously developed circuits is proposed. The num ber of transmission gates required in this circuit is proportional to 3N instead of N-2, where N is the number of inputs. And the total numb er of control signals is proportional to 3N(2) instead of N-3. But the number of comparators required is proportional to C-2(N+1), as before . This modified circuit can be used in cases where the number of input s is small (N less than or equal to 8). A new algorithm for the multip le-inputs systolic priority queue (MISPQ) is proposed. By using this a lgorithm, a MISPQ may be implemented with several smaller queues, each is used to process a part of data in the MISPQ. Since the volume of d ata flowing through each queue is small, these queues will be simpler. However, some additional circuits should be used for the interactions between queues. A circuit for implementing this algorithm is presente d and its complexity is analysed. The number of transmission gates for the MISPQ is proportional to 3N, the number of control signals is pro portional to (3N(2)/2), and the number of comparators is proportional to 4C(2)(N/2+1). Thus this new architecture is feasible for large N (e .g. N greater than or equal to 8).