Note: Descriptions are shown in the official language in which they were submitted.
2~2~264
72167-3
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~
72167-3
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
A 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
B- 1
+ 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~ ~
2020264
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
72167-3
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
- 10-
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.
- 12-
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.
- 14-
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
- 16-
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.
, ,' .. -
