Systolic implementation of digital filters

A systematic method for the mapping of digital filter algorithms onto systolic hardware is presented. The method is based on thez-domain characterization of the required filter. It yields filter structures that are modular, pipelined, and hierarchical, and can be used to obtain multidimensional structures. All the structures discussed have a latency of one sampling period and some have maximum concurrency. The paper also deals with the problems of line and frame wrap-around that are inherent in raster-scanned images and ways are suggested for their elimination.     

Fast Implementation of 3-D Digital Filters Via Systolic Array Processors

In this paper a fast implementation architecture of three-dimensional (3-D) FIR or IIR digital filters via systolic VLSI array processors is described. The modular structure presented is comprised of similar processing elements in a linear cascade configuration with local interconnections. High speed throughput rates are attained due to high concurrency, which is achieved by exploiting both pipelining and parallelism. The considered 3-D FIR and IIR filters may be used for the processing of reconstructed 3-D images and in medical imaging applications.     

Realization of 2-D Variable IIR Digital Filter Structures with a Small Amount of Calculations for Coefficient Update

This paper proposes 2-D variable IIR digital filter structures with a small amount of calculations for coefficient update. The proposed realization method uses the 2-D parallel allpass structure derived from the separable denominator 2-D filter as the prototype structure for 2-D variable digital filters. In order to reduce the amount of calculations, all the redundant first-order complex allpass sections are combined by modularization of the variable structure. Furthermore, we can realize a very compact variable structure with a minimal number of first-order complex allpass sections by combining complex allpass sections with their complex conjugate allpass sections. Comparison of the calculation loads of the variable structures is presented to demonstrate that the amount of calculations for coefficient update of the proposed variable structure is far less than that of the original and the modular variable structure.     

Design of zero-phase recursive 2-D variable filters with quadrantal symmetries

The digital filters with adjustable frequency-domain characteristics are called variable filters. Variable filters are useful in the applications where the filter characteristics are needed to be changeable during the course of signal processing. In such cases, if the existing traditional constant filter design techniques are applied to the design of new filters to satisfy the new desired characteristics when necessary, it will take a huge amount of design time. So it is desirable to have an efficient method which can fast obtain the new desired frequency-domain characteristics. Generally speaking, the frequency-domain characteristics of variable filters are determined by a set of spectral parameters such as cutoff frequency, transition bandwidth and passband width. Therefore, the characteristics of variable filters are the multi-dimensional (M-D) functions of such spectral parameters. This paper proposes an efficient technique which simplifies the difficult problem of designing a 2-D variable filter with quadrantally symmetric magnitude characteristics as the simple one that only needs the normal one-dimensional (1-D) constant digital filter designs and 1-D polynomial approximations. In applying such 2-D variable filters, only varying the part of 1-D polynomials can easily obtain new desired frequency-domain characteristics.     

Efficient algorithm and systolic architecture for modular division

A new efficient modular division algorithm suitable for systolic implementation and its systolic architecture is proposed in this article. With a new exit condition of while loop and a new updating method of a control variable, the new algorithm reduces the average of iteration numbers by more than 14.3% compared to the algorithm proposed by Chen, Bai and Chen. Based on the new algorithm, we design a fast systolic architecture with an optimised core computing cell. Compared to the architecture proposed by Chen, Bai and Chen, our systolic architecture has reduced the critical path delay by about 18% and the total computational time for one modular division by almost 30%, with the cost of about 1% more cells. Moreover, by the addition of a flag signal and three logic gates, the proposed systolic architecture can also perform Montgomery modular multiplication and a fast unified modular divider/multiplier is realised.     

Majority Logic Mapping for Soft Error Dependability

This work proposes the use of analog majority gates to implement combinational circuits that are intrinsically tolerant to transient faults. A new type of voter circuit, that uses some knowledge from the analog design arena is proposed, together with a new mapping approach to implement circuits given their input/output table. This new mapping approach is shown to compare favorably against a classic mapping. The implementation and validation of an adder circuit, using conventional triple modular redundancy (TMR), the classic mapping, and the proposed solution are analyzed, in order to confirm that the shown technique is indeed fault tolerant, and has advantages in terms of area and performance when compared to TMR. Finally, implementations of a subset of the ISCAS 85 benchmark circuits using TMR with the analog voter and the proposed approach are compared and the results analyzed.     

A Spatial-Domain Technique for the Design of 3-D Separable-Denominator State-Space Digital Filters

In this paper,a technique for designing 3-D separable-denominator state-spacedigital filters is developed. The design process is divided intotwo phases. First, the coefficient matrices related to stabilityare constructed for the filter to be stable by using alternatingvariable method. Next, the other matrices are obtained by solvinglinear equations. These phases are repeated until there is nosignificant change in the squared error function.     

Systolic architectures for finite-state vector quantization

We present a new systolic architecture for implementing Finite State Vector Quantization in real-time for both speech and image data. This architecture is modular and has a very simple control flow. Only one processor is needed for speech compression. A linear array of processors is used for image compression; the number of processors needed is independent of the size of the image. We also present a simple architecture for converting line-scanned image data into the format required by this systolic architecture. Image data is processed at a rate of 1 pixel per clock cycle. An implementation at 31.5 MHz can quantize 1024×1024 pixel images at 30 frames/sec in real-time. We describe a VLSI implementation of these processors.     

低秩大模板二维卷积算法的脉动阵列设计

本文针对低秩大模板二维卷积运算的特点,给出了其快速算法,并利用基于相关图的三步骤映射法设计了其脉动阵列实现结构。该结构并行效率高,并可达到线性加速比。     

Design of separable-denominator 2-D digital filters using the reduced-dimensional decomposition model

A separable-denominator 2-D digital filter (SD-2DDF) can be decomposed into the cascade form of a pair of 1-D digital filters (1DDFs) with different delay elements. Based on this reduced-dimensional decomposition, in this paper, we propose a new technique for designing SD-2DDFs in the spatial domain. The technique determines the coefficient matrices of 1DDFs by nonlinear optimization techniques first, and then a SD-2DDF can be easily synthesized. In addition, since the existent 1-D linear system realization techniques can be used to choose a good starting point for the optimization, extremely accurate design results can be easily achieved.     

具有任意幅度频响的二维线性相位FIR数字滤波器的设计

本文提出了设计任意幅度频响的二维线性相位ＦＩＲ数字滤波器的解析最小二乘方法，通过最小化频域平方误差函数得到了滤波器系数的闭式解，运用导出的闭式式，可根据给定的任意幅度频响指标直接计算滤波器的系数，从而简化了滤波器设计程序，并大大降低了运算量。     

The advanced OCA for 2-D discrete periodized wavelet transformation

We develop a novel computation method for the 2-D discrete periodized wavelet transformation (DPWT). The new algorithm is based on the operator correlation algorithm (OCA). Compared with the classical 2-D pyramid algorithm, the new advanced operator correlation algorithm (AOCA) has two major advantages; it requires half the number of multiplications and can yield the same output SNR with half the precision of the DPWT filter coefficients. Furthermore, the modular structure of the ADCA makes it particularly suitable for a VLSI implementation     

具有任意角度的二维扇形FIR数字滤波器的设计

扇形数宇滤波器由于其良好的方向性而得到广泛的应用.本文导出了一组利用McClellan变换法设计二维零相位扇形数字滤波器的公式.利用该组公式设计的扇形数字滤波器的形状在均方意义下是最佳的.由于设计公式化,避免了设计中的优化过程,因而设计过程简单,设计所需的时间少。     

Two-dimensional digital filters for geophysical applications: A simple design method leading to an easy implementation

A simple procedure for the design of two-dimensional digital filters will be presented. Its main interest is in the field of geophysical signal processing, since the design implies in these cases simple structures for the implementation. The 2-D problem is reduced to one, two or complicated cases to several 1-D problems. By 3 examples, relevant in geophysics, the power of this method will be demonstrated. The design is applicable for arbitrary ideal frequency responses, however the simple realization will be lost in general. The result is a suboptimal filter, which can be used, if desired, as an initial solution for an L_∞-approximation. However, the efficiency of the presented method is established by the fact that the design and implementation go hand in hand and are adapted to the special problem under consideration.     

Generating 2-D FIR filter functions by Christoffel–Darboux formula for Chebyshev polynomials of the second kind

Global Christoffel–Darboux formula for different polynomials has already been used for the filter design. Here, this formula for orthonormal Chebyshev polynomials of the second kind and for two independent variables is applied in generating novel class linear-phase two-dimensional (2-D) finite impulse response (FIR) digital filter functions. In this way, 2-D filters with some specific features including economy, phase linearity, symmetry and selectivity are designed. Representative examples of the 2-D FIR digital filters of a new class obtained by the proposed approximation technique are given. A filter generated by the proposed approach is compared with the corresponding one generated by the procedure from literature.     

An Integrated Systolic Array Design for Video Compression

This paper presents an integrated systolic array design for implementing full-search block matching, 2-D discrete wavelet transform, and full-search vector quantization on the same VLSI architecture. These functions are the prime components in video compression and take a great amount of computation. To meet the real-time application requirements, many systolic array architectures are proposed for individually performing one of those functions. However, these functions contain similar computational procedure. The matrix-vector product forms of the three functions are quite analogous. After extracting the common computation component, we design an integrated one-dimensional systolic array that can perform aforementioned three functions. The proposed architecture can efficiently perform three typical functions: (1) the full-search block matching with block of size 16 × 16 and the search are from –8 to 7; (2) the 2-D 2 level Harr transform with block of size 8 × 8; and (3) the full-search vector quantization with input vector of size 2 × 2. A utilization rate of 100% to 97% is achieved in the course of executing full-search block matching and full-search vector quantization. When it comes to perform 2-D discrete wavelet transform, the utilization rate is about 32%. The proposed integrated architecture has lowered hardware cost and reduced hardware structure. It befits the VLSI implementation for video/image compression applications.     

Implementation of 2-D pseudo-rotated digital filters using a forward lattice structure

The 1-D FDLS shows the localized feedback property and is suitable for modular and concurrent implementation. It is known that the 1-D FDLS shows interesting properties with respect to finite word-length effects. In this paper, a new result is given for the estimation of the lower and upper bound of the variance of the roundoff noise. It is presented how the FDLS can be incorporated to implement 2-D pseudo-rotated digital filters. The 1-D roundoff noise analysis is extended to the 2-D case. It is indicated how 2-D filter banks can be derived from the FDLS.     

Novel and efficient realizations of FIR digital filters

An FIR filter can usually be realized in the direct form or in cascade form. The Chebyshev-type structures, known for the 2-D FIR filter implementation, are generalized to the realization of arbitrary 1-D causal FIR filters. The new realizations show several attractive properties and can be implemented using modular pipelineable processor arrays     

Mapping dynamic programming onto a linear systolic array

In the paper we show a single, efficient implementation of dynamic programming on alinear array using a new mapping methodology. In this method, we start with a known 2-D array onto which the dynamic programming algorithm has been mapped. By partitioning and stretching, this 2-D array is mapped onto a linear array. We derive a data movement scheme to simulate the data streams and the computations in the 2-D array. This scheme is implemented usingfast/slow data channels. Compared to known designs in the literature our design uses constant storage in each PE, constant number of I/O lines and continuous I/O sequence. Besides, the data and control flow in the array is unidirectional. This property makes the design suitable for implementation on the well-known fault-tolerant Wafer Scale Integration model.This research was supported in part by the National Science Foundation under grant IRI-8710836 and by AFOSR under grant AFOSR-0032.     

Design and simulation of component-based manufacturing machine systems

This paper presents the modular machine design environment (MMDE), a software environment that enables the ‘virtual design/engineering' of component-based manufacturing machine systems. It consists of a suite of highly integrated tools supporting the visualisation, design, programming, verification and evaluation of machine systems built from mechanical, electronic and software components/modules in a virtual environment. Using three-dimensional (3-D) graphical simulation with a number of add-on tools, MMDE supports visualisation, design, simulation and verification of both the physical model and control logic for design and/or re-configuring machine systems to satisfy new or changed application/customer requirements before any real implementation is made. System design, implementation techniques, and evaluation of MMDE in a real industrial test case are covered in detail.