KR0140805B1 - Bit-serial operation unit - Google Patents

Abstract

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a bit serial arithmetic unit of an FIR filter, and has a bit serial structure that requires several times of computation time as compared to general bit parallel arithmetic, but does not include a control logic circuit or an adder in hardware implementation. This becomes very simple, which reduces the complexity of the hardware by more than a few times the number of bits. Therefore, the required VLSI area is much smaller than the bit parallel structure.

Description

Bit serial operation unit of FIR filter

1 is a transpose diagram of a FIR filter.

2 is a direct implementation structure diagram of a FIR filter.

3 is a bit serial structure diagram of a conventional SOPOT coefficient FIR filter.

4 is a structural diagram of a filter according to the present invention.

5 is an exemplary view illustrating the operation of the filter according to the present invention.

6 is a structural diagram when there is a negative coefficient.

7 is a structural diagram of a linear phase filter.

* Explanation of symbols for main parts of the drawings

D: Register

BACKGROUND OF THE INVENTION 1. Field of the Invention [0001] The present invention relates to a bit serial computing device of a one-dimensional FIR filter having a SOPOT (sum of power of two) coefficient, and more particularly, a bit serial computing device of a FIR filter having a smaller computational complexity and hardware complexity than a general one-dimensional filter. It is about.

In general, when implementing a FIR filter, you can perform filtering with floating point operations for accuracy when there is room for the given signal sample interval and the performance and price of a given circuit or processor. When there is no time or price, It is common to perform fixed-point arithmetic to achieve faster filtering even though the accuracy may be reduced. However, in digital image or video signal processing that requires very fast operation, even a very fast processor or VLSI structure may not be able to perform floating point as well as fixed point operation. Therefore, in this case, the coefficients of the filter should be expressed as SOPOT coefficients so that the multiplication can be replaced by one or two additions to enable faster filtering. Here, representing coefficients as SOPOT means that when a filter's coefficients are represented in binary, most of the bits are zero and only a few bits have nonzero values. For example, in general fixed-point arithmetic that requires a coefficient to be represented by 8 bits, up to seven additions are required to multiply with the input, but the SOPOT coefficient filter limits the number of nonzero values within eight bits to a smaller number. Multiplication can be performed. For example, if the number of non-zero bits is limited to two, multiplication can be done with only one addition. In this case, since the number of types that can be represented by 8 bits is smaller than that of general 8 bit integer representation, the performance of the filter may be greatly degraded. Actually, the real coefficient filter through an optimization technique using integer programming method, etc. SOPOT coefficient filter design with very small performance difference is possible.

Therefore, many studies on the VLSI implementation of such SOPOT filter have recently been proposed. These methods can be used when the filter expression is

H (z) = h ₀ + h ₁ z ^-1 + h ₂ z ^-2 +... h _N z ^-N (1)

The first is to help the pre-structure such as a base presenting the multiplication method of the coefficient h _i representation and input. According to the coefficient representation method, floating point, fixed point, and SOPOT operations can be classified as mentioned above, and they are divided into bit parallel and bit serial methods according to whether the calculation is performed in word units or bit units. As described above, the advantages and disadvantages of each coefficient representation method are the smallest complexity in the case of SOPOT and the noise due to the finite word length (FWL) effect. Comparing the bit serial method and the parallel method, the parallel method is fast because the calculation is performed in units of one word, but it has a disadvantage of occupying a very large VLSI area. On the other hand, since the bit serial method performs the operation bit by bit, the bit serial method has the advantage that it is slower but has a higher degree of integration than the bit parallel method. Therefore, bit parallelism should be used for maximum speed, and bit serialization should be used for maximum integration. More specifically, it can be said to present a bit serial structure of the SOPOT coefficient filter. Among the existing methods, the SOPOT coefficient filter is implemented as a bit serial structure in J. Evans, YC Lim, and B. Liu's A high speed programmable digital FIR filter (IEEE ISCAS 93, pp. 969-972, May 1993). have. However, since it does not use the pipeline method, the efficiency is considerably reduced and there is no definition of the subtraction operation. In addition, in the case of the linear phase filter, since the coefficients of Equation (1) have a symmetrical shape, the number of multiplications can be reduced by half.

The most straightforward way to directly implement the structure of the FIR filter of Equation (1) is to connect several coefficient taps as shown in Fig. 2.However, in order to actually implement the hardware, it is necessary to accept the following data after all additions are completed. As shown in the following example, if the filter has N taps, the following time must pass to obtain one output.

T = NT _add + T _mult (2)

Where T _add is the addition execution time and T _mult is the execution time of the multiplication. However, as shown in Figure 1, by reversing the shape of the filter, the pipeline can be executed. Therefore, one output can be obtained within the following time regardless of the number of filter taps.

T = T _add + T _mult (3)

Existing SOPOT coefficient filters, based on the structure of Figure 3, replace the product of each filter coefficient and its input with a few additions rather than the usual floating-point or fixed-point method. For example, J. Evans, YC Lim, B. Liu, etc. A high speed programmable digital FIR filters ( IEE ISCAS93, pp. 969-972, May 1993) proposed a method ^2-4 +2 coefficient of a filter tab When expressed as ^-6 , as shown in Figure 3, the product of the input and this coefficient is replaced by two additions. Since the calculation is performed in bit units, it takes longer than in the case of word units, but since the required adder is a 1-bit adder, it is much simpler than the structure of word units, and thus a higher order filter can be implemented.

The structure of FIG. 3 has a disadvantage in that the multiplication is not performed in a pipelined manner since the next input can be accepted only after the calculation of one input is completed. In other words, the output from this section has to be saved in some memory and sent to the next tab. In addition, there is no detailed description of the case in which one bit is represented as a negative number in the coefficient, and when each value is represented by two's complement, the adder cannot be replaced by a subtractor. In many cases, the shape of the filter is a linear phase filter. In this case, since the coefficients of the filter are symmetrical, the complexity of hardware implementation can be reduced, but a specific example of this structure is not presented.

The present invention devised to solve all the problems of the prior art, the bit serial operation apparatus of the FIR filter to further improve the operation speed of the SOPOT coefficient FIR filter by introducing a pipeline structure based on the bit serial method The purpose is to provide.

Another object of the present invention is to provide an efficient subtraction structure based on two's complement calculation when the coefficient is negative.

It is still another object of the present invention to provide a structure that further increases the VLSI density by reducing the number of multipliers in half when the FIR filter is a linear phase filter.

In order to achieve the above object, the present invention provides a data transmission between only adjacent elements and input signals are continuously input, the register for receiving the first input signal; A multiplier for adding and outputting a next input signal and a signal passing through the register; A plurality of registers and a multiplier continuously connected to the same structure as the register and the multiplier has a pipeline structure to sequentially add and output the input signals.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

FIG. 4 is based on the pre-FIR structure as shown in FIG. 1 and the calculation is performed in bits, so the only difference is that the general register D here is the same as in FIG. In other words, when the product of the input and the coefficient is represented by k bits, the overall structure is the same as that of FIG. 1 as shown in FIG. 4 (a), and each D is a k-bit shift register.

The core of the invention was characterized by the structure of the present invention with respect to a case, for example, a structure in which the dotted line the multiplication structure of the input and coefficients in a coefficient given as a dotted line in Figure 2 ^-3 +2 ^-5 4 (b). If the input x _i contains a sign bit and says 01110111, the actual input is x _i ^* = 01110111.00000000 as shown in the figure, resulting in 3 x and 5 bit shifted results of x _i ^* respectively. . Compared to FIG. 3, which is an existing structure, the addition result is forwarded again in the existing structure, whereas the proposed structure does not have such a structure, which is particularly advantageous for the VLSI structure.

In addition, in the conventional structure, the next input is input after the execution of one input is completely completed, but the structure of the present invention has the advantage that a pipeline structure in which the LSB of the next input is input subsequent to the MSB of the current input is possible. A more detailed description of the operation of the invention is shown in FIG. This figure shows what the values are for each time at points A, B, and C in Figure 4. Here, the first input x ₁ = 01111111 and the second input x ₂ = 01010101, based on time t = 16, indicate that 2-5x ₁ and 2-3x ₁ are currently input to the adder. As can be seen from the figure, when x ₂ ^* is input in succession to x ₁ ^* , it can be seen that (2 ⁻³ +2 ⁻⁵ ) x ₂ is output based on t = 32.

6 is a structural diagram in which one or more bits are negative, and shows an example in which the coefficient is 2 ^-3 -2 ^-5 .

In areas of the negative coefficient input x _i ^* is the shift in the 2's complement of x _i ^* by using the first inverter, as shown in the figure, because the other input deohaejyeoya Make it. In addition, two's complement is ( +1), so we need a controller that makes the carry one every 16 times. But that adds 1 in this case is the same as adding ^2-8 occurs only a slight error may be omitted.

When the filter has a linear phase characteristic that is frequently used for image processing, the filter of Equation (1) is as follows.

H (z) = h ₀ + h ₁ z ^-1 +... + h _{N / 2} z ^{-N / 2} +... + h ₁ z- ^(N-1) + h ₀ z ^-N (4)

Thus, if the current input is x _i , the filter output is

y _i -h ₀ (h _i + x _iN ) + h ₁ (x _i-1 + x _{i-N + 1} ) +. (5)

That is, since the coefficients of the filter are symmetrical, the VLSI area can be further reduced by using the structure of FIG. 7 which reduces the number of multipliers actually required.

The structure shown in FIG. 4 is a bit serial structure, which requires several times the computation time compared to the general bit parallel operation, but the hardware implementation of the control logic circuit and adder becomes very simple. The complexity of is reduced by more than twice the number of bits. Therefore, there is an advantage that the required VLSI area is much smaller than the bit parallel structure.

Comparing the structure of FIG. 3 with the conventional bit serial structure and FIG. 4 proposed in the present invention, since the shift result returns to the input structure of the adder in the conventional structure, the elements between the elements in the VLSI implementation are included. The connection line is long. In the VLSI structure, the metal lines connecting each element occupy a very large area, and in order to reduce this as much as possible, it violates the principle that each element should be connected only to adjacent ones. On the other hand, the proposed structure is more advantageous for VLSI implementation because it is connected only locally, with no line connecting far. In addition, the conventional structure saves time because the calculation is performed by accepting the next input after the output for one input is completely passed to the next tap, whereas the proposed structure saves time because the LSB of the next input may be entered immediately after the MSB of the current input. It also has the advantage of being able to.

In addition, when the filter is a linear phase filter as shown in Equation (4), the VLSI area becomes smaller because the required number of multiplications can be reduced by half using the structure as shown in FIG.

Claims (4)

An apparatus for serially bitting an FIR filter, the apparatus comprising: a register for transmitting data only between adjacent elements and receiving input signals consecutively, the first input signal being received; A multiplier for adding and outputting a next input signal and a signal passing through the register; And a plurality of registers and multipliers continuously connected to the same structure as the registers and multipliers, and having a pipelined structure so as to sequentially add and output the input signals. The bit serial arithmetic unit of claim 1, wherein the register is a shift register. The bit serial arithmetic unit of claim 1, wherein the inverter uses a inverter to make a complement and optionally adds 1 to make a complement of 2 or omit it. The method according to claim 1, wherein the formula H (z) = h ₀ + h ₁ z ⁻¹ +. + h _{N / 2} z ^{-N / 2} +... + h ₁ z- ^(N-1) + h ₀ z ^-N is arranged to reduce the number of multipliers required by arranging registers and multipliers so that the coefficients of the filter are symmetrical. Bit serial operation unit.