The authors present two systolic architectures to speed up the computation of modular multiplication in RSA cryptosystems. In the double-layer architecture, the main operation of Montgomery's algorithm is partitioned into two parallel operations after using the precomputation of the quotient bit. In the non-interlaced architecture, we eliminate the one-clock-cycle gap between iterations by pairing off the double-layer architecture. We compare our architectures with some previously proposed Montgomery-based systolic architectures, on the basis of both modular multiplication and modular exponentiation. The comparisons indicate that our architectures offer the highest speed, lower hardware complexity, and lower power consumption.

We propose a new efficient serial architecture to implement the Berlekamp-Massey (1968, 1969) algorithm, which is frequently used in BCH and Reed-Solomon (1960) decoders. An inversionless Berlekamp-Massey algorithm is adopted which not only eliminates the finite-field inverter but also introduces additional parallelism. We discover a clever scheduling of three finite-field multipliers to implement the algorithm very efficiently. Compared to a previously proposed serial Berlekamp-Massey architecture, our technique significantly reduces the latency.

The Digital Versatile Disk (DVD) is an emerging standard to meet the ever increasing storage capacity requirement of future high quality video and audio applications. We implement a (208,192;8) Reed-Solomon decoder for the DVD Reed-Solomon product code (RS-PC). We propose a new area-efficient architecture which uses only three finite field multipliers (FFMs) to implement the inversionless Berlekamp-Massey (1968, 1979, 1969) algorithm. The error value evaluator employs an algorithm-based GF(2/sup m/) inverter instead of an inversion ROM-table. We implement the (208,192; 8) Reed-Solomon decoder using a 0.6 /spl mu/m SPDM CMOS technology with an area of 12.35 mm/sup 2/ (core area 6.45 mm/sup 2/). The chip can run at 16.67 MHz, while the DVD requirement is 3.74 MHz. A minor error was found in this first version which is corrected in the second version of the chip.

A new service scheduling scheme, reactive bandwidth arbitration (RBA), is proposed as an effective way to arbitrate the contention among priority classes or between unicast and multicast services in ATM switching. The RBA scheme integrates two previously proposed concepts: bandwidth allocation and reactive arbitration. In, RBA, guaranteed bandwidth is allocated to a connection at call set up based on the traffic characteristics and service requirements, while the arbitration of cell delivery takes into account the queue status to react to traffic fluctuation. Through simulation, we found that by bandwidth allocation, a set of queue threshold levels can be obtained to provide a good approximation to the desired delay performance. Furthermore, around this initial configuration, a linear relationship between the queue threshold and the resulting delay performance can be established to fine-tune the configuration parameters for the desired delay performance. Similar effects were observed as the RBA scheme was applied to arbitrate the contention between unicast and multicast connections in a shared buffer ATM switch. The proposed RBA scheme was incorporated in a queue manager chip for an 8/spl times/8 shared buffer ATM switch with four priority classes per port and link rate at 622 Mbps. The chip has 130 k gates in a chip area of 137.88 mm/sup 2/ and operates at 25 MHz.

The design of the queue manager is of key importance for the shared buffer ATM switch architectures. We propose the recycling queue manager (RQM) with reduced hardware complexity by eliminating the external FIFO for the avail queue. By separating the shared buffer into cell and address memories, the power consumption of idle accesses in the RQM can be reduced, and the linked list bubbles can be removed. The required storage for the proposed RQM and other queue managers of existing shared buffer ATM switches are compared, considering delay/loss priorities and partial sharing. It is found that the RQM requires the least storage size for most cases, and the reduction is more significant as the switch dimension grows. A two-level RQM-based scheme, with reduced storage, is also proposed for the shared multi-buffer switch architecture. An RQM prototype chip supporting a 16/spl times/16 switch with two priority classes and back pressure capability was implemented and successfully tested to verify the proposed architecture.

The Shared Buffer Memory Switch (SBMS) is one of the most attractive alternatives for the ATM switch design for future B-ISDN telecommunications. In an SBMS, cells destined for different output ports are stored in one shared buffer and organized as single-link lists. However, for some unexpected faults in address chain memory, catastrophic damage will result in the SBMS to read out the cells not belonging to the original port. More seriously, the cells incoming to the faulty port will never be read out from the shared memory, thus exhausting the available memory space eventually. In this paper, we survey fault tolerant methods to combat address chain faults in SBMS. Specifically, we propose a double-link list based SBMS architecture which is robust if the address chain memory has less than two faults for each port.>

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.>

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 address the problem of computing exact bounds on the path metric differences in maximum-likelihood sequence detectors based upon the Viterbi algorithm. The calculation of the bounds is formulated as a series of linear programming problems. Numerical results are presented for several examples of uncoded and coded partial-response channels of practical interest in digital data recording applications.>

LAGER is an integrated computer-aided design system for algorithm-specific integrated circuit design, targeted at applications such as speech processing, image processing, telecommunications, and robot control. LAGER provides user interfaces at behavioral, structural, and physical levels and allows easy integration of novel CAD tools. LAGER consists of a behavioral mapper and a silicon assembler. The behavioral mapper maps the behavior onto a parameterized structure to produce microcode and parameter values. The silicon assembler then translates the filled-out structural description into a physical layout, and, with the aid of simulation tools, the user can fine tune the data path by iterating this process. The silicon assembler can also be used without the behavioral mapper for high-sample-rate applications. A number of algorithm-specific ICs designed with LAGER have been fabricated and tested, and as examples, a robot arm controller chip and a real-time image segmentation chip are described.>

Summary form only given. The real-time application of trellis coding to partial response channels is described for a rate 8/10 matched-spectral-null (MSN) trellis code on the (1-D) partial response channel. The architectural and design issues of an experimental chip that implements the functions of encoding, decoding, and Viterbi detection are discussed. Two novel techniques in the design of the Viterbi detector are introduced. Modulo normalization of the path metrics, and area-efficient pipelining for the add-compare-select units. Both techniques are effective in producing a regular structure and reducing the number of required interconnections. Area-efficient realization is achieved with little speed degradation. The circuit and layout were designed using LAGER CAD tool. The chip was fabricated in 1.2 mu m CMOS.>