AN O(lOg2 N)-LATENCY SISO WITH APPLICATION TO BROADBAND TURBO DECODING
Peter A. Beerel, K.M. Chugg · 2000
The standard algorithm for computing the softinverse of a finite-state machine (i.e., the Soft-in/Softout or SISO) module, is the forward-backward algorithm. These forward and backward recursions can be computed in parallel, yielding an architecture with latency O(N), where N is the block size. We demonstrate that the standard SISO computation may be formulated using a combination of a prefix and suffix operations. Based on well-known tree-structures for fast parallel prefix computations in the Very Large Scale Integration literature (e.g., tree adders), we propose a tree-structured SISO that has latency O(log2 N). The decrease in latency comes primarily at a cost of area, with, in some cases, only a marginal increase in computation. We discuss how this structure could be used to design a very high throughput turbo decoder, or more generally an iterative detector. Various sub-windowing and tiling schemes are also consider to further improve latency.