Many communications applications require similar processing functionality but are implemented independently. In particular, a number of applications (including trellis coding, encryption, and speech recognition) use techniques based on shortest path search algorithms. In this paper, we propose a high-throughput architecture that can search for the shortest path within a graph. The architecture can decode any data encoded with a finite state machine (FSM) or data encrypted in a dynamic trellis code and also serve as a specialized processor for other searching and matching applications. Balance between flexibility and hardware efficiency is achieved by an integrated design of architecture, in-place scheduling, and concurrent algorithms.

A common approach to reduce CMOS power consumption is to reduce the supply voltage. However, circuit speeds degrade rapidly as the supply voltage drops. This paper uses theoretical analyses and experiments to explore the effectiveness of circuit and process modifications for improving speed at low V/sub DD/. In particular, we find that circuits operating in ohmic mode have less speed-V/sub DD/ sensitivity and thus run faster at low supply voltages.>

The parallel Viterbi decoding is discussed for two different cases: uncontrollable sources and controllable sources. For general, uncontrollable Markov processes, a previously known parallel method is extended to a hierarchical parallel decoding approach, which achieves a lower latency. For controllable Markov sources in telecommunications applications, new parallel decoding methods are obtained by controlling the source processes in appropriate ways. The focus is on the parallel decoding methods for controllable sources because these methods have zero processing overhead. Because the methods modify the coding process, they bring positive changes to framing and negative changes to latency and code performance. However, one can adjust the parameters of the methods to make the degradation negligible. Because of their low overhead, the methods are most attractive for high-speed decoders for convolutional and trellis codes, and they are also applicable to other sequential algorithms for suboptimal decoding and estimation of complex Markov sources.>

In the state-parallel implementation of the Viterbi algorithm, one add-compare-select (ACS) unit is devoted to each state in the treillis. A systematic approach to partitioning, scheduling, and mapping N trellis states to P ACSs, where N>P, is presented here. The area saving of this architecture comes from the reduced number of ACSs and interconnection wires. The design of the ACS, path metric storage, and routing network is discussed in detail. The proposed architecture creates internal parallelism due to the ACS sharing, which can be exploited to increase the throughput rate by pipelining. Consequently, the architecture offers a favorable (smaller) area-time product, compared to the state-parallel implementation.>

In part I the theoretical foundations of a new class of area-efficient architectures for the Viterbi algorithm were established. Area-efficient architectures for practical codes are presented here to illustrate the design procedures and demonstrate the favourable area-time tradeoff results. Three examples from convolutional codes, matched-spectral-null (MSN) trellis codes, and Ungerboeck codes are presented. The application of the area-efficient techniques to codes with a very large number of states, codes with time-varying trellises, and a programmable Viterbi decoder is discussed.>

A high-throughput architecture that can search for the shortest path within a graph is proposed. The architecture can decode any data encoded with a finite state machine or data encrypted in a dynamic trellis code, and also serve as a specialized processor for other searching and matching applications. The proposed retargetable architecture is suitable for futuristic workstations equipped with wireless access, basic voice recognition, and high speed data services. Balance between flexibility and hardware efficiency is achieved by an integrated design of architecture, in-place scheduling, and concurrent algorithms.>

For pt.I see ibid, vol.2, no.2, p.187, 1992, For applications in graphic computers, image and video composition, high-definition television (HDTV), and optical fiber networks, Huffman-coded images need to be reconstructed at a high throughput rate. Part I showed several architectural and architecture-specific optimization techniques. However, due to the recursion within the reconstruction algorithm, the achievable throughput rate for a given decoding architecture in a given IC technology is limited. The authors propose various concurrent decoding methods to relax the throughput limit by using parallel or pipelined hardware. These methods are simple, effective, flexible, and applicable to general decoder architectures. Unlimited concurrency can be achieved at the expense of additional latency, the overhead is low, and the complexity increases linearly with the throughput improvement. It is believed that the proposed methods and architectures make it possible to reconstruct arbitrarily high resolution Huffman-coded images and video in real time with current electronics.>

A comparison is made of four modular composition methods suitable for pipeline architectures, including object-based and pel-based composition methods with absolute or relative ordering. For each composition method, it is shown what it does, what it means physically, and thus what limitation it imposes. The conclusion is that the object-based methods, although more efficient to describe video composition, are not completely general. A method is proposed to extend the generality of object-based composition while also retaining its efficiency in describing video composition.>

It is shown how to find in-place schedules for all kinds of trellises, including periodic and aperiodic in-place schedules. It is also shown how to verify the existence of aperiodic and periodic in-place schedules. With this in-place scheduling, one can improve data locality and thus reduce interprocessor communication bandwidths. This means a smaller overhead in chip routing area or communication cycles. The methods also apply to general parallel processing with trellis-like computational graphs.>

The authors demonstrate architectural techniques, for small-state feedback circuits that significantly improve the throughput without requiring circuit design efforts or advanced technologies. The method is flexible in terms of achievable implementations and speedups. The authors discuss a new high-throughput solution for systems with finite-level feedback values. As an example, the authors consider coding and signal processing systems for optical communications, which usually have very simple feedback. The authors demonstrate the method by realizing a 2 micron CMOS layout of a bimode 3B4B line coder. Simulation results show that, using standard cell design, the chip achieves a coding rate of 1.4 Gb/s. Other design options are discussed.>

The Huffman code is an efficient noiseless coding method for images, video, and other applications. For applications in graphic computers, high-definition televisions (HDTV), and optical fiber networks, Huffman-coded images need to be reconstructed at a high throughput rate. Due to the recursion within the reconstruction algorithm, the achievable throughput rate in a given IC technology is limited by the iteration bound. Methods of relaxing the iteration bound of the reconstruction process, thus increasing the concurrency in the decoding process, are proposed. These methods are simple, effective, and flexible. Unlimited concurrency can be achieved at the expense of additional latency. The incurred overhead is very low, and the complexity increases only linearly with the achieved throughput improvement.>