Digital Signal Processing Reference
In-Depth Information
algorithms [18-24]. For example, in the case of an FIR filter, the coefficients constitute an array of
constants in some signed Q-format where the tapped delay line forms the array of variables which
changes every sample clock. The DA logic replaces the MAC operation of convolution summation
of (6.5) into a bit-serial look-up table read and addition operation [18]. Keeping in perspective the
architecture of FPGAs, time/area effective designs can be implemented using DA techniques [19].
The DA logic works by first expanding the array of variable numbers in the dot product as a binary
number and then rearranging MAC terms with respect to weights of the bits. A mathematical
explanation of this rearrangement and grouping is given here.
Let the different elements of arrays of constants and variables be A
k
and x
k
, respectively. The
length of both the arrays is K. Then their dot product can be written as:
K
1
y ¼
0
A
k
x
k
ð
6
:
9
Þ
k¼
Without lost of generality, let us assume x
k
is an N-bit Q1. (N
1)-format number:
N
1
x
k
¼x
k
0
2
0
1
x
kb
2
b
¼x
k
0
2
0
þx
k
1
2
1
þx
kðN
1
Þ
2
N
1
þ
b¼
The dot product of (6.9) can be written as:
!
K
1
N
1
0
x
k
0
2
0
1
x
kb
2
b
y ¼
þ
A
k
k¼
b¼
K
1
0
ðx
k
0
2
0
þx
k
1
2
1
þx
kðN
1
Þ
2
N
1
y ¼
ÞA
k
k¼
Rearranging the terms yields:
K
1
N
1
2
b
K
1
k¼
0
x
k
0
A
k
2
0
y ¼
þ
0
x
kb
A
k
k¼
b¼
1
For K
¼
3 and N
¼
4, the rearrangement forms the following entries in the ROM:
ðx
00
A
0
þx
10
A
1
þx
20
A
2
Þ
2
0
þðx
01
A
0
þx
11
A
1
þx
21
A
2
Þ
2
1
þðx
02
A
0
þx
12
A
1
þx
22
A
2
Þ
2
2
þðx
03
A
0
þx
13
A
1
þx
23
A
2
Þ
2
3
The DA technique pre-computes all possible values of
K
1
0
x
kb
A
k
For the example under consideration, the summations for all eight possible values of x
kb
for
a particular b and k
¼
0, 1 and 2 are computed and stored in ROM. The ROM is P bits wide and 2
K
deep and implements a look-up table. The value of P is:
k¼
$
#
log
2
K
1
k¼
P ¼
0
Ajj
þ
1
Search WWH ::
Custom Search