Filtering with finite impulse response (FIR) is a basic procedure in various digital signal processing devices involved in such research areas as speech processing, radar signal processing, filtering all sorts of noise in a wide range of human activities.

To improve performance of program filters, designers often move to frequency domain and use Fast Fourier Transform procedures. This method is based on the so called convolution theorem, theorem, which allows reducing the number of operations for higher-order filters. Nevertheless, the program implementation of FIR filters in signal processors or general purpose processors is strictly sequential, that cannot provide high performance in many practical cases. Often the bandwidth requirements in real devices can be met only for hardware implementation of constant-coefficient filters. Sacrificing flexibility in choosing coefficients as well as hardware costs, it is possible to provide the required level of performance using pipelined architecture for FIR filters implementation. The problem of constructing hardware FIR filters with fixed coefficients has been actively discussed in foreign publications in recent years [1, 2].

The process of further increase of the FIR filter’s performance involves the use of mathematical apparatus of residue number system (RNS) arithmetic which has repeatedly proved its effectiveness in the field of digital signal processing, in particular for digital filters design [3].

Besides using RNS principles, we propose to combine the idea of computation in frequency domain with the principles of parallel data processing in the same hardware FIR filter. In addition, RNS implementation of FIR filter using number-theoretic Fourier transform is proposed, which provides increased performance and better accuracy.

As it was already stated above, there are many ways of hardware implementation of FIR filters: sequential, parallel, in frequency/time domain, etc. RNS arithmetic provides means for structure parallelization at the level of arithmetic operations, and it can be used for the design of a FIR filter implemented by any method. However, the most promising is the use of RNS-based parallel implementation in frequency domain. There are several prerequisites for this conclusion, the main of which is that for finite fields there is an analogue of the convolution theorem. More precisely, there exists a transform over finite fields similar to Fourier transform, for which convolution theorem over finite fields holds and all symmetric properties are met, that allows using any fast algorithm for computing this transform. The conversion formula is as follows:

Here A_k - is the number-theoretic spectrum of the signal, a_n is the signal itself, p is the characteristic of the finite field, γ - is the primitive root with index 2^t [8]. If the number p is of the form p = q · 2^t + 1, then the primitive root with index 2^t always exists and equals γ = ɷ^q.

For a prime modulus m, there is at least one primitive root ɷ ≤ p - 1, such that the set |ɷⁱ|_m : i = 0,1,2,...,m - 2 forms all nonzero residues modulo m. The following example shows that ɷ = 3 is a primitive root modulo m = 7:

|3⁰|₇ = 1 |3³|₇ = 6

|3¹|₇ = 3 |3⁴|₇ = 4

|3²|₇ = 2 |3⁵|₇ = 5

Exponents of the primitive root by an arbitrary modulo are called "indexes".

Thus, the said conversion is an analog of the discrete Fourier transform for trigonometric basis, where the twiddle factors eij2πN are replaced by γ^ij, and the operations of addition and multiplication of complex numbers – by the corresponding operations over GF(p).

Besides the obvious advantages such as of computations paralleling, we achieve better accuracy, since the calculations are carried out in finite fields with integer twiddle factors that eliminates representation errors typical for standard trigonometric method. [4]

The RNS-based FIR filter implementation with the use of number-theoretic fast Fourier transform is presented in the (Fig. 3).

Fig. (3) Block schematic diagram of FIR filter in frequency domain.

The basic structure of the filter consists of forward and reverse converter units, as well as N residue channels of the same type that differ only in characteristic of the finite field over which all arithmetic calculations are carried out. All moduli must have the same binary rank, i.e. they must all be of the form p_i = q_i · 2^t + 1. This fact guarantees that a primitive root γ_i with index 2^t exists in every finite field, that allows to form RNS-based FFT of length 2^t. This parameter is the basis of FIR filter as a whole. It also determines the length of input data segments of the infinite sequence to be processed in residue channels and then "glued" in OVERLAP ADDITION block. Moreover, this parameter affects the filter order, and if it equals p_i = q_i · 2^t + 1, the number of filter coefficients must equal 2^t-1.

The modular channel consists of a zero padding block, forward FFT block, a unit for multiplication by filter coefficients, inverse FFT block (INV_FFT) and a module for data segments combination. FIR filter behavior in frequency domain implies that the relevant number of zeros are added to input data segments for correct “gluing” of the results in the block for combination of the processed data segments. Taking into consideration the pipelined device architecture, it is necessary to reduce data input frequency in half. In other words, internal FIR frequency F_clk should be two times higher than discretization frequency F_s. For this purpose frequency divider block is added to the schematic (Fig. 4).

Fig. (4) Zero padding block and frequency divider block.

Overlap addition block combines parts of processed data to make an infinite output sequence of filtered result. Inverse Fourier transform produces blocks of data of length 2^t, each of which must be divided into two parts. These two sequences must be combined through pairwise summation. Let’s consider t = 3, and show the overlapping process on (Fig. 5).

Fig. (5) Synthesis results for binary filter in the canonical form.

Now it is clear that for 2^t samples of input data overlap addition block produces 2^t-1 output samples. It means that we must use discretization frequency F_s for output data. Verilog code for overlap addition block is given below.

Fig. (6) Synthesis results for RNS filter based on convolution theorem over finite field.

Fig. (7) Comparison of RNS and binary schematics for fixed filter orders.

All internal blocks including Fourier transform block (FFT) are maximally pipelined to achieve the smallest clock frequency. Control unit MANAGER provides for the synchronization of device parts and device as a whole. It is also responsible for supplying the address of the cell holding the filter coefficient to the memory connected to the multiplier.

The result of the design is the IP core implementing RTL circuit description in Verilog HDL. All IP cores, developed during related work are available on the author’s web site [9]. IP core parameters are the filter coefficients and the input data digit capacity. To evaluate the efficiency of the proposed approach, experiment was carried out on the synthesis of RNS-based FIR filters using Synopsys CAD tools and Nangate 45 nm Open Cell Library. The order of the filter was chosen in the range of 4 to 32 points. Number of bits is in the range of 4 - 16. Critical path delay and circuit area were evaluated. Also, for the same set of parameters FIR filter in canonical form was designed. Results are presented in Figs. (6, 7) and Table 1.

Table 1

Comparison of RNS and binary schematics for fixed filter orders.

The synthesis results show that the proposed schematic outperforms the traditional variant with regard to clock frequency for large-scale input data and higher filter order, however, it requires sufficiently greater area. And if at first glance, the results may seem disappointing – actually it is not so. RNS-based filters have some advantages which are not reflected in the presented diagrams. First, the filtered output signal of the RNS block based on the FFT over a finite field is much more accurate than the output signal of the conventional binary filter. This is due to the fact that for FFT over a finite field twiddle coefficients are the elements of this finite field, i.e. integer numbers. Thus, we avoid errors in the representation of the coefficients. Another advantage of the proposed approach is the fact that by adding extra modular channels we are able to control and even correct errors that arise during the computation. Future developments will be directed to the implementation of sequential RNS filters based on FFT over a finite field.