CA2020264C - Digital filter - Google Patents

Abstract

Abstract of the Disclosure:
A digital filter receives an input data of N bits and generates an output data obtained by totally summing partial products each of which corresponds to a product of each bit and a predetermined coefficient.
This digital filter comprises an input register for latching the input data in the form of L divided blocks each composed of M bits, a delay-latch circuit connected to the input latch and for outputting the N-bit data with a predetermined delay time, a multiplication circuit having M memories and for multiplying a predetermined coefficient to each bit for each of the M-bit blocks outputted from the input register and the delay-latch circuit, and an addition circuit for sequentially summing data, block by block, outputted from the multiplication circuit.

Description

2~2~264 Background of the Invention Field of the invention The present invention relates to a digital filter, and more specifically to a digital filter which has a multiplication circuit including a memory and which can play a major role in the field of digital signal processings.
Description of related art In the prior art, this type of digital filter has been dlscussed, for example, in the paper titled "A New Hardware Realizatlon of Digital Filters" on IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP-22, No. 6, pages 456-462, December, 1974. In the digital fllter, a memory, particularly, a ROM (read only memory) has been u~ed as one kind of look-up table in order to generate a partial product of an input data and a coefficlent. The partial products thus generated are totally summed to realize an effect equivalent to a multiplication.
Brief Descrlptlon of the Drawings Figure 1 i8 a function block diagram lllu~trating one example of a second-order recursive dlgital fllter;
Flgure 2 1B a block dlagram of the conventional digital filter reallzing the function shown ln Flgure l;
Flgure 3 is a block diagram of the addition circult ~hown in Figure l;
Flgure 4 illu~trates the multlpllcatlon operatlon proce~ performed in the digital filter shown ln Flgure l;
Figure 5 illu~trate~ an internal ~tructure of a part of the wired logic clrcuit shown in Flqure l;

~k 1 ~J~

..
. . ,~, . .

2~2026~

Figure 6 is a block diagram of a first embodiment of the digital filter in accordance with the present invention;
Figure 7 is a logic diagram illustrating the internal structure of the data selector shown in Figure 6;
Figure 8 is a logic diagram illustrating the internal structure of the l'complement circuit shown in Figure 6;
Figure 9 is a block diagram of the addition circuit shown in Figure 6;
Figure lOA and lOB illustrate the multiplication operation process performed in the digital filter shown in Figure 6;
Figure 11 is a timing chart for illustrating the operation of the digital filter shown in Figure 6;
Figure 12 is a function block diagram illustrating one example of a non-recursive digital filter;
Figure 13 is a block diagram of the digital filter in accordance with the present invention realizing the function shown in Figure 12; and Figure 14 iæ a timing chart for illustrating the operation of the digital filter shown in Figure 13.
Referring to Figure 1, there is shown a function block diagram illustrating one example of a second-order recursive digital filter.
In Figure 1, an input data xn applled to an lnput terminal is sequentlally lnputted and latched to delay-reglster clrcuits 12 and 13, which outputs data xn 1 and xn 2 respectlvelY~ The data x, xn_l and xn_2 2~20264 are respectively multiplied by coefficients ao, al and a2 by multipliers 321, 322 and 323 of a multiplication circuit 30B, and respective products are summed or totalized by an addition circuit 40B.
An output data Yn appearing on an output terrninal is sequentially inputted and latched to delay-register circuits 14 and 15, which outputs data Yn-1 and Yn-2, respectively. The data Yn-1 and Yn-2 are respectively multiplied by coefficients -bl and-b2 by multipliers 324 and 325 of the multiplication circuit 30B, and respective products are summed or totalized by the addition circuit 40B.
The above mentioned operation can be expressed by the following equation (1):
yn = a0Xn + alXn-l + a2xn-2-blyn-l -b2yn 2 .... (1) Here, assume that all data to be precessed is in the range of +1 to -1, and expressed by 2' complement of B bits in a fixed point representation having a sign bit. Therefore, B-l Xk =--XkO + ~: xki 2i .... (2) where -XkO is a sign bit, and Xki is representative of a bit at a jth place from the MSB bit, and Xki = 0 or 1 If the equation (2) is applied to the equation (1), the following equation is obtained.

. -.

. . .

202~2S4 B-l Yn = ao ( S xni 2i - x + al ( Xn-li 2i -Xn-1 ) j=l B-l + a2 ( ~ xn-2J 2 J--Xn-2 ) B-l -bl ( yn-li 2j -yn-lo ) J-B-l -b2 ( ~ Yn-2i 2i _ yn_2 ) j=l ....
Here, a function ~ is defined as follows:
~y(xl,x2~x3~x4~xs) = aoxl + alx2 + a2X3 - blx4 - b2X5 (4) The equation (3) can be modified as follows by using the equation (4).
B-l Yn = ~ 2j ~ (xnJ, xn lJ, xn-2J~ Yn-lJ, Yn-2J) - ~ (XnO, xn l~ xn-2o~ Yn-10, Yn-20) - - - (5) Thus, the function ~ can assume 32 different values (32 =25), and therefore, if the coefficients an and bn are fixed, the values of ~ can be stored in a ROM of 32 words. In addition, an arithmetic operation itself can be performed with addition and shifting, without requiring an ordinary multiplier.

.."
..

2~2026~

Referring to Figure 2, there is shown a block diagram of the hardware of the recursive digital filter constructed on the basis of the above mentioned principle.
The input data and the output data are represented by 8 bits, and each data in each of ROMs 301 to 308 is formed of 8 bits.
Data xn, Xn-l, Xn-2, Yn-l and Yn-2 are loaded in parallel to an input register 11, and the delay-registers circuits 12 to 15 Partial products ~ to ~7 outputted from the eight ROMs 301 to 308 are summed by an addition circuit 40B including a wired hardware for realizing a shift corresponding to the place of each bit, and the addition circuit 40B generates the output data Yn.
Referring to Figure 3, an internal structure of the addition circuit 40B is shown. All the outputs of the ROMs 301 to 308 are latched in a register 401 once, and then, applied to a Wallace Tree circuit 402 and a CLA adder (carry lookahead adder) 403, so that the outputs of the the ROMs 301 to 308 are summed at a high speed. Thereafter, an output of the adder 403 is inputted to an overflow controller 404, in which an overflow is checked and a necessary modification is performed so that high place 8 bits are outputted as the output data Yn. The arithmetic operation process performed in the addition circuit 40B shown in Figure 3 is illustrated in Figure 4.
Here, it should be noted that, since the data is expressed in 2' complement, a small modification is added to the partial products.
Namely, in order to make the position of the sign bit of each partial product consistent with each other, a bit or bits of the same value as the sign bit are placed at a position or positions higher than the position of the sign bit of each partial product. These bits are indicated by a double ~, 202026~
circle in Figure 4, and called an "extended bit". Even if these extended bits are added, the value of each partial product will not change.
Returning to Figure 2, a connection between the input register 11 and the delay-register circuits 12 to 15 and the ROMs 310 to 306 will be explained.
In order to realize the equation (5) mentioned hereinbefore, the eight bits of the output of each of the input register 11 and the delay-register circuits 12 to 15 are divided and rearranged by the wired logic circuit 35B so as to be distributed or assigned to an address of S bits for each of the ROMs 301 to 308. Figure 5 shows a portion of the wired logic circuit 35B, and the following Table 1 shows a correspondence between the address of the ROMs 301 to 308 and each bit of the wired logic circuit 35B.

A s 2~2~2~4 Table 1 Bit 0 Bit 1 Bit 2 Bit 3 Bit 4 (LSB) (MSB) R O M 301x n x n-1 x n-2 Yn-l Yn-2 R O M 302 x nl x n-ll x n-21 Yn-ll Yn-2 R O M 303 x n2 x n-12 x n-22 Yn-12 Yn-2 ROM 304 x n3 x n-13 x n-2 Yn-l Yn-23 R O M 305 x n4 x n-14 x n-24 Yn-14 Yn-2 ROM 306 x n5 x n-15 x n-25 Yn-15 Yn-25 ROM 307 x n x n-l x n-2 Yn-l Yn-2 ROM 308 x n7 x n-17 x n-2 Yn-l Yn-27 The R O Ms 301 to 308 used in the multiplication circuit 30B have an address of five bits and outputs an output data of eight bits. Therefore, each of the ROMs requires a memory capacity of 256 bits (= 25 x 8).
Accordingly, the overall digital filter requires a ROM capacity of 2048 bits (= 256 x 8).
As seen from the above explanation, the conventional digital filter requires memories (ROMs) of the same number as the bit number of an input data. Accordingly, assuming that the number of the coefficients for the digital filter are the same, the larger the bit number of an input data becomes, the larger the required total memory capacity becomes, and 1~ ~

therefore, the scale of the hardware becomes large. For example, if the input data have 16 bits in order to increase the precision of the arithmetic operation, the digital filter requires sixteen memories (ROMs) each of which has a capacity of 256 bits (= 25 x 8). The total memory capacity becomes 4048 bits (= 256 x 16). In addition, if the number of the memories (ROMs) is increased, the hardware of the addition circuit following the multiplication circuit inevitably becomes large.
,'.' Summary of the Invention Accordingly, it is an object of the present invention to provide a digital filter which has overcome the above mentioned defect of the conventional one.
Another object of the present invention is to provide a digital filter having a reduced amount of hardware and a high precision.
The above and other objects of the present invention are achieved in accordance with the present invention by a digital filter receiving an input data of N bits and for generating an output data obtained by totally summing partial products each of which corresponds to a product of each bit and a predetermined coefficient, comprising an input register for latching the input data in the form of L divided blocks each composed of M bits, a delay-latch circuit connected to the input latch and for outputting the N-bit data with a predetermined delay time, a multiplication circuit having M memories and for multiplying a predetermined coefficient to each bit for each of the M-bit blocks outputted from the input register and the delay-latch circuit, and an addition circuit for sequentially summing data, block by block, outputted from the multiplication circuit.

2~202~4 The above and other objects, features and advantages of the present invention will be apparent from the following description of the preferred embodiment~ of the invention with reference to Figures 6 to 14 of the accompanying drawings.
Description of the Preferred Embodiments Referring to Figure 6, there is shown a block diagram of a first embodiment of the digital filter in accordance with the present lnventlon. The shown digital filter realizes the second-order recursive digital filter shown in Figures 1 to 5. The shown digital fllter is adapted to receive an input data xn of 8 bits, and generates an output data Yn which is obtained by totally summing partial products between each bit of the input data and predetermlned coefficients.
The shown digital filter comprises an input register 11 receiving the lnput data xn of the eight bits and for latching the lnput data in two dlvided blocks each composed of four bits. The lnput reglster 11 is connected to a delay-register circuit 12, so that the input data is latched ln the delay-register circuit 12 after a predetermined delay time. The delay-reglster circuit 12 1~ also connected to another delay-reglster circuit 13, so that the input data 18 latched in the delay-register circuit 14 after the predetermined delay time.
The shown digital filter also comprises a delay-register clrcult 14 recelving the output data Yn and latching it after the predetermlned delay ,., ' ,: :~ ., ' 2~2026~

time, and another delay-register circuit 15 receiving the output data from the delay-register circuit 14 and latching it after the predetermined delay time. Each of the delay-register circuits 12 to 15 latches the received data in two divided blocks each composed of four bits. The input register 11 and the delay-register circuits 12 to 15 are connected to data selectors 21 to 25, respectively, so that data xn, xn 1, xn 2, yn 1 and yn-2 are supplied from the input register 11 and the delay-register circuits 12 to 15 to the corresponding data selectors 21 to 25. Each of the data selectors 21 to 25 is controlled by an controller 50 so as to select one of the two blocks of the received data.
The shown digital filter further comprises a multiplication circuit 30 including four ROMs 31 to 34, a wired logic circuit 35 and a l'complement circuit 36. For data of four bits outputted from each data selector, the multiplication circuit 30 executes a multiplication between each bit and a predetermined coefficient and outputs the result of the multiplication, which is supplied to an addition circuit 40 including a pair of adders 41 and 42. The addition circuit 40 operates to sequentially sum the data outputted from the multiplication circuit 30, block by block, and to output the result of the summing as the output data Yn. The controller 50 generates various control signals Vc for the purpose of controlling the timings of operation of various circuits.
Now, an operation of the above mentioned digital filter and a constrwction of each part will be explained.
The input data xn is first latched by the input register 11, and then, sequentially leaded to the delay-register circuits 12 and 13 with the predetermined delay time, respectively. On the other hand, the output 2~2026~
data Yn is sequentially leaded to the delay-register circuits 14 and 15 with the predetermined delay time, respectively.
As mentioned above, the input data xn is composed of 8 bits, and divided into two blocks each of which is composed of 4 bits. Processing is executed for each block of 4 bits. Each of the data selectors 21 to 25 is controlled by the control signal Vc of the controller 50 so as to select either high place four bits or lower place four bits of each received data.
Referring to Figure 7, there is shown the construction of the data selectors 21 to 25. Each of the data selectors 21 to 25 includes AND
circuits 201 to 208, an inverter 209, and OR circuits 210 to 213, which are connected as shown, so as to select and output the high place four bits when the control signal Vc is at a high level, and the lower place four bits when the control signal Vc is at a low level. The selected four bits are applied to the corresponding ROM as an address.
The wired logic circuit 35 is constructed similarly to that shown in Figure 5, so that the outputs of the data selectors 21 to 25 are divided one by bit and supplied to the respective ROMs 31 to 35. The following Table 2 and Table 3 show correspondence between the address of the ROMs 31 to 35 and each bit of the wired logic circuit 35.

202~26~

Table 2 _ Bit 0 Bit 1 Bit 2 Bit 3 Bit 4 (LSB) (MSB) ROM 31 Xn xn_la Xn 2 Yn-l Yn_2a ROM 32 xnb xn_lb Xn_2b Yn-lb Yn-2b ROM 33 xnc xn_lc Xn-2c Yn-lC yn_2C

ROM 34 Xn Xn-l Xn-2 Yn-l yn_2d Table 3 Control Signal a b c d High Place 4 5 6 7 Low Place 0 _ 2 3 Partial products of 8 bits outputted from the ROMs 31 to 34 are added by the adder 41 when they are directed to the high place four bits, and are added together with the output of the adder 41 by the adder 42 when they are directed to the low place four bits. An output of the adder 42 forms the outpwt data yn. However, the output of the ROM 34 is supplied to the adders 41 and 42 through the l'complement circuit 36 having a construction as shown in Figure 8.

2~202$~
The l'complement circuit 36 includes an AND circuit 360 and exclusive OR circuits 361 to 368 connected as shown in Figure 8, so that when the control signal Vc is at a high level, namely when the partial products between the high place bits of the data xn and the coefficients are outputted, the partial product outputted from the ROM 34 is converted into the form of l'complement. When the control signal Vc is at a low level, the output of the ROM 34 is supplied without modification to the addition circuit 40.
In the equation (5) as explained hereinbefore, only the partial product for the sign bit has a minus sign. Originally, 2'complement should be obtained, and therefore, 1'complement is obtained and thereafter 1 should be added to the LSB bit of the 1'complement.
However, even if addition of 1 is performed in the addition process of the partial products, an equivalent result can be obtained. The latter is effective since the total multiplication time can be shortened. For this reason, the l'complement circuit is provided.
Referring to Figure 9, there is shown the construction of the adders 41 and 42. For shortening the mulitplication time, the outputs of the ROMs 31 to 34 are latched by a register 411, and added by a Wallace Tree circuit 412. 1 is also added with a LSB bit.
In the adder 42, an intermediate result outputted from the adder 41 and the partial products outputted from the ROMs 31 to 34 and corresponding to the lower place four bits of the input data are latched by a register 421, and thereafter, added by another Wallace Tree circuit 422 at a high speed. An output of the Wallace Tree circuit 422 is supplied to a CLA adder 423, which generates a final result of addition. The final result of addition is examined by an overflow controller 424, so that the output data Yn of 8 bits is obtained.
Figures 10A and 10B illustrate a shifted addilion of the partial products. The arithmetic operation process of the adder 41 is shown in Figure 10A, and the arithmetic operation process of the adder 42 is shown in Figure 10B. These arithmetic operation processes of the adders 41 and 42 are executed under the timing control as shown in Figure 11.
During a period A in which the control signal Vc is at a high level, the arithmetic operation process shown in Figure 10A is executed, and during a period B in which the control signal Vc is at a low level, the arithmetic operation process shown in Figure 10B is executed.
As mentioned above, either the high place four bits or the low place four bits of the input data are alternatively applied as the address signal for the ROMs 31 to 34. Therefore, the result of the arithmetic operation executed in the period A is maintained until the period B, so that the result of the arithmetic operation executed in the period A is added together with the outputs of the ROMs 31 to 34 by the adder 42 when the data for the lower place bits is read from the ROMs 31 to 34.
The above mentioned embodiment is directed to the second-order recursive digital filter. However, the present invention can be applied to other type digital filters. Referring to Figure 12, there is shown an example of the fourth-order non-recursive digital filter (called a transversal filter) which can embody the present invention In ~igure 12, an input data Pn is sequentially supplied to delay-register circuit 12A, 13A, 14A and lSA, and the input data Pn and outputs of the delay-register circuit 12A, 13A, 14A and lSA are applied to multipliers 331 to 335 of a multiplication circuit 30A in parallel.

20202~
Outputs of the multipliers 331 to 335 are added by an adder 40A, which generates an output data Qn.
Figure 13 illustrate a digital filter circuit folmed on the basis of the principle shown in ~'igure 12. Figure 14 shows an operation timing of the digital filter shown in Figure 13.
In this embodiment, the input data Pn is composed of 12 bits and divided into three blocks each of which is composed of 4 bits, so that processing is performed for each divided block of 4 bits.
The input data Pn is latched in an input regis~er 1 lA and sequentially loaded in the delay-register circuit 12A, 13A, 14A and l5A
with predetermined delays, so that the input register llA and the delay-register circuit 12A, 13A, 14A and l5A outputs data Pn, Pn-l~ Pn-2 Pn 3 and Pn 4 to corresponding data selectors 21A to 25A, respectively.
Each of the data selectors 21A to 25A operates to select continuous four bits of the 12 bits of the received data, block by block, and to output the selected four bits through the wired logic circuit 35 to ROMs 31A to 34A.
A controller 50A generates a control signal Vc2 as shown in Figure 14, so that the partial products corresponding to the high place four bits are outputted from the ROMs 31A to 34A during a period Al of the address signal, the partial products corresponding to the middle place four bits are outputted from the ROMs 31A to 34A during a period A2 of the address signal, and the partial products corresponding to the low place four bits are outputted from the ROMs 31A to 34A during a period A3 of the address signal.
The partial products outputted from the ROMs 31A to 34A are applied to an addition circuit 40A including a register 44, an adder 43 and another register 45. Namely, the partial products outputted from the 2~202~

ROMs 31A to 34A are latched by the register 44, and sequentially summed by cooperation of the adder 43 and the register 45.
In this second embodiment, during the period Al, only the output of the ROM 34A is converted into a l'complement by the l'complement circuit, and "1" is added to the LSB bit of the adder 43, so that the value having the LSB bit added with "1" is latched in the register 45. During the period A2, the outputs of the registers 44 and 45 are added by the adder 43 and the result of the addition is latched by the register 45.
During the period A3, a similar addition operation is performed, so that the output of the register 45 generates the output data Qn.
If the digital filter were constituted in the conventional manner, twelve ROMs should have been required in the case of the input data of 12 bits. However, the present invention requires only one-third of the number required in the conventional digital filter.
In the embodiments explained above, the ROMs have been used as a memory, since the coefficients are fixed. If RAMs (random access memories) are used, it is possible to voluntarily change the coefficients of the digital filter so as to optimize the characteristics of the digital filter.
In the embodiments explained above, the digital filter is realized by exclusive hardwares. However, the digital filter in accordance with the present invention can be realized by a microcomputer and a memory.
~ s seen from the above explanation, in the digital filter in accordance with the present invention, the input data of N bits is divided into L blocks each of which is composed of M bits, and a partial product between each bit of the input data and a coefficient is obtained for each block, and thereafter, the partial products thus obtained are summed so as to give an output data. With this arrangement, the necessary amount of 2~202~

the memory can be reduced to l/L in comparison with the conventional digital filter. In addition, if the division number of the input data is made large, the bit length of the input data can be increased, so that a high degree of precision can be obtained with a limited amount of hardware.
The invention has thus been shown and described with reference to the specific embodiments. However, it should be noted that the present invention is in no way limited to the details of the illustrated structures but changes and modifications may be made within the scope of the appended claims.

, ,' .. -

Claims (4)

1. A digital filter receiving an input data of N bits and for generating an output data obtained by totally summing partial products each of which corresponds to a product of each bit and a predetermined coefficient, comprising an input register for latching the input data in the form of L
divided blocks each composed of M bits, a delay-latch circuit connected to the input latch and for outputting the N-bit data with a predetermined delay time, a multiplication circuit having M memories and for multiplying a predetermined coefficient to each bit for each of the M-bit blocks outputted from the input register and the delay-latch circuit, and an addition circuit for sequentially summing data, block by block, outputted from the multiplication circuit.

2. A digital filter claimed in Claim 1 further including a plurality of data selectors each receiving an output of a corresponding one of the input register and the delay-register circuit, each of the data selectors operating to select one divided block of M bits from among the received data of N
bits and to output the selected divided block.

3. A digital filter claimed in Claim 2 wherein the multiplication circuit includes M memories each storing partial products of 2L which is addressed by an address obtained by dividing outputs of the data selectors bits by bits and re-combining the divided bits, an output of each of the memories being supplied to the addition circuit.

4. A digital filter claimed in Claim 3 wherein the multiplication circuit further includes a logic circuit receiving all the outputs of the data selectors so as to distribute and rearrange bits of the the outputs of the data selectors into M groups so as to supply the M groups of bits to the M
memories, respectively.