Simulation based Development of Efficient Hardware for Sort based Algorithms

N. Hansson and J.H. Harris (USA)


Sorting, error correction, convolutional codes, Malgorithm, parallel processing


The use of sub-optimal digital systems can at times lead to high speed, efficient, cost-effective structures that are sufficient to perform needed tasks. We describe here a system that reduces the processing time of a sort based signal processing algorithm and yields an area efficient structure. The system achieves significant processing time acceleration by performing partial sorts in parallel and by replacing the final stages of a sort by a minimal transfer of data between sorted sub-lists. The technique is applied to the M-algorithm for bit error correction in digital communication systems. As measured by loss in coding gain, sub-optimal but very good algorithmic performance is achieved using the limited exchange between parallel sorted lists. The data exchange is achieved with a compact bus structure. Simulation and synthesis results are presented for a register transfer level design described in a hardware descriptive language.

Important Links:

Go Back