Simulation based Development of Efficient Hardware for Sort based Algorithms.
Niklas Hansson, J.H. Harris · 2003
The use of sub-optimal digital systems can at times lead to high speed, efficient, costeffective 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. Sort operations integral to metric based signal processing tree searching algorithms provide wide opportunity to explore tradeoffs between hardware complexity and speed. Speed is increased by performing operations in parallel, but operations performed in parallel require increased hardware. In this paper we describe a system that increases speed by terminating the final steps of an otherwise standard sort algorithm. Terminating the steps significantly reduces the complexity of the digital system that performs this task. The feasibility for the termination is established through simulations. The concept is applied to the M-algorithm for decoding convolutional codes [1-3]. Both process time and hardware complexity are reduced significantly when compared with standard implementation of the sort that is basic to the algorithm. Error correction results for the modularized system show a modest penalty, but temporal and complexity improvements are significant. We describe very useful error correction down to 3 db signal to noise ratio and also describe characteristics of a field programmable gate array implementation of the system. 1