An O(1) time algorithm to multiply two K-bit binary numbers using an N/spl times/N bit-model of reconfigurable mesh is shown. It uses optimal mesh size and it improves previously known results for multiplication on the reconfigurable mesh. The result is obtained by using novel techniques for data representation and data movement and using multidimensional Rader Transform. The algorithm is extended to result in AT/sup 2/ optimality over 1/spl les/t/spl les//spl radic/N in a variant of the bit-model of VLSI.

Proposes an area-efficient VLSI architecture for fast Huffman decoder which can support HDTV rates. Huffman coding, which is known as optimal variable length coding, has been widely used to reduce storage and communication channel bandwidth, and several emerging image compression standards such as JPEG, MPEG, CCITT H.261 require to perform Huffman coding in real-time with high throughput. However, most known designs are not suitable for real-time operation or for implementation, especially in HDTV, since these require large amount of VLSI area or a large number of processing elements (PEs) for high performance. The proposed VLSI architecture for the Huffman decoder requires fewer comparators and smaller size of data rotator to simulate the Barrel shifter. It can decode up to 17 bits per cycle and employs a 40 MHz clock which can support HDTV rates. Thus, it can decode Huffman coded sequences up to 680 Mbits/s at peak. Compared with the parallel implementation in Mukherjee et al. (1991) which requires upto 1460 PEs and has 10 Mbps of throughput, the proposed architecture is a single PE design with competitive processing power. It requires 25% of the area of the known single PE design in Lei and Sun (1991).

The reconfigurable mesh captures salient features from a variety of sources, including the content addressable array parallel processor, the CHiP, the polymorphic-torus network and the bus automaton. It consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns between the processors. In this paper, we present a fast algorithm for computing the histogram of an N/spl times/N image with h grey levels in O(min{/spl radic/h+log*(N/h),N}) time on an N/spl times/N reconfigurable mesh assuming each PE has a constant amount of local memory. This algorithm runs on the PARBUS and MRN/LRN models. In addition, histogram modification can be performed in O(/spl radic/h) time on the same model. A variant of out algorithm runs in O(min{/spl radic/h+log log(N/h),N}) time on an N/spl times/N RMESH in which each PE has constant storage. This result improves the known time and memory bounds for histogramming on the RMESH model.>

We propose a design methodology for synthesis of a special class of Data Format Converters (DFCs) in which the site of I/O sequences and the delays between I/O sequences are specified. The need for such DFCs arises in many signal and image processing applications. Our DFCs are based on a two-dimensional architecture. The designs using our methodology have maximum throughput rate and are area-efficient. A VLSI architecture for computing the discrete wavelet transform is given as an example to illustrate the proposed design methodology. The design of a Zig-zag Scanner is also given. For several representative problems, the area requirements of our designs are compared against those obtained by earlier design methodologies. For all the problems considered, our methodology leads to compact designs.>

We show an O(1) time algorithm for computing the N-point Discrete Fourier Transform (DFT) on an NlogN x NlogN reconfigurable mesh, where each poitn is represented using \Theta(logN) bits. Based on the DFT algorithm, we derive O(1) time algorithms for N-bit multiplication, N-bit modular operations, and computing the quotient of two N-bit numbers on an N x N bit model of the reconfigurable mesh. The proposed algorithms lead to AT^2 optimal designs in the bit model of VLSI for 1 \leqslant T \leqslant \sqrt N. All these algorithms run on the MRN, RMESH, and PARBUS models of the reconfigurable mesh, and employ optimal size of the mesh.

Vector quantization (VQ) has become feasible to be employed for real-time applications by using VLSI technology. In this paper, the authors propose modular linearly connected VLSI architectures for VQ that can support real-time image processing applications. Each processing element in the design consists of an adder and a shift register instead of a multiplier. The designs require fixed I/O bandwidth with the host and allow codebook changes. The throughput is independent of the codebook size. These designs can be extended to the case when a fixed number of processors are available. A number of VQ schemes-single-stage and multistage VQ, classified VQ, etc.-can be implemented using this approach.>

Vector quantization (VQ) has become feasible for use in real-time applications by employing VLSI technology. The authors propose a new search algorithm and an architecture for implementing it, which can be used in real-time image processing. This search algorithm takes O(k) time units on a sequential machine, where k is the dimension of the codevectors, assuming unit time corresponds to one comparison operation. The proposed architecture employs a single processing element (PE) and O(N) external memory for storing N hyperplanes used in the search, where N is the number of codevectors. Compared with known architectures for VQ in the literature, the proposed design does not perform any multiplication operation, since the search method is independent of any L/sub q/ metric, 1>

Modular and area-efficient VLSI architectures are proposed for computing the arithmetic Fourier transform (AFT). By suitable I/O schedule and activation of PEs, nonuniform data dependencies in the AFT computation which require nonequidistant inputs and assignment of Mobius function values are resolved. The proposed design employs 2N+1 PEs to compute 2N+1 Fourier coefficients. Each PE has an adder and a fixed amount of local storage and one PE has a multiplier. I/O with the host is performed using a fixed number of channels. The design achieves O(N) speed up. Compared with known designs for AFT, the proposed design uses significantly less PEs and supports real-time applications. This design can be extended to achieve linear speed up in a fixed size array with 2p+1 PEs, 1>