Concurrency in trellis searching and traversing algorithms
Horng-Dar Lin · 1992
Finite state machines (FSMs) and estimators of FSM states with noisy observations have similar processing characteristics and throughput constraints, because they both contain feedback loops utilizing the results of the previous iteration. This thesis quantifies this similarity by representing the feedback core of finite state machines as path traversing, and the feedback core of estimators as path searching. From this representation, we derive the throughput constraints common to path traversing and searching, and describe general methods for introducing concurrency to improve throughput at the expense of latency. The methods are applicable to software and hardware implementation using parallelism or pipelining, and demonstrate that there is no theoretical limit to concurrency in a discrete-time finite state machine or its estimator. In practice, the methods can effectively improve the throughput, as opposed to the response time, for various path traversing and searching algorithms. An example design of a 1.4Gbps bimode 3B4B line coder in 2.0 micron CMOS illustrates the potential of the methods. Another example demonstrates that the principles developed here extend to concurrent decoding for the Huffman code, a feedback system with dependency not in the data processing itself, but in the time of restarting data processing. The thesis also proposes a multi-purpose path searching architecture to exploit hardware efficiency and flexibility provided by the methods. The methods described here use the algorithm restructuring approach, which reconstructs a new recurrence structure from manipulating the original FSM or estimator's recurrence function. The proposed algorithm restructuring approach is more general than existing methods, as it applies to a larger class of nonlinear feedback systems, and is also more flexible in its implementation.