Transcript ALGORITHM TYPES - Florida Institute of Technology

Polynomial Multiplication with
Discrete Fourier Transform
Fast Fourier Transform
7/17/2015
FFT
1
Signal
Amplitude /
Intensity /
Voltage
Time
7/17/2015
FFT
2
Signal as a linear combination of
sinusoidal waves
Strength and phase of
each component
Different components
Add them
Signal Spectrum
7/17/2015
FFT
3
Digital Signal
Amplitude
A sequence of numbers, or
Time-series
7/17/2015
FFT
4
Digital Signal
7/17/2015
FFT
5
Signal as a polynomial
f(t) = re(i2π ωt)
ω = root of equation (xn = 1)
Animation on wiki:
http://upload.wikimedia.org/wikipedia/commons/a/a5/ComplexSinInATimeAxe.gif
FFT
7/17/2015
6
Omega, or n-th root of 1
Im axis
8 complex roots of
x8 = 1
Re axis
f(t) = re(i2π ωt)
7/17/2015
FFT
ωn above, where
n is number of samples
7
Signals as Functions of roots of 1
Amplitude & Phase
f(t) = re(i2π ωt)
ωn above, where
n is the number of samples
7/17/2015
FFT
8
Signal Processing as Polynomial Multiplication
Not in details:
• Each Digital Signal is a polynomial over roots of 1
• Convolving is equivalent to Polynomial multiplication
7/17/2015
FFT
9
Polynomial Multiplication
f(x) = A0 + A1x1 + A2x2 + . . .+ An-1xn-1
2 Representations:
• Coefficients (A0, A1, A2, . . ., An-1)
• Evaluated at n points y(x0), y(x1), ..., y(xn-1)
• Exchangeable: Given A's, evaluate at n points,
• or, Given n points, solve for n coefficients
• Traditionally: O(n2) algorithms for each.
• Divide and Conquer DFT: O(n log n)
7/17/2015
FFT
10
Polynomial Multiplication
• Given A[0..n-1] DFT evaluates ==> on wn0, wn1, wn2, . . ., wnn-1,
• where wn is n-th root of the equation xn -1 = 1
• Takes O(n) for each evaluation, O(n2) for all
• Recursive divide conquer DFT takes O(n log n) time
7/17/2015
FFT
11
Polynomial Multiplication
• Given A[0..n-1] DFT evaluates ==> on wn0, wn1, wn2, . . ., wnn-1,
• where wn is n-th root of the equation xn -1 = 1
• Takes O(n) for each evaluation, O(n2) for all
• Recursive divide conquer DFT takes O(n log n) time
•
•
•
•
Why on those complex points?
Any set of n points would do, but, those points let us
develop O(n logn) DFT,
and convert it to fast iterative and parallelizable FFT
7/17/2015
FFT
12
Primary use of Efficient Polynomial Multiplication
Primary use of Efficient Polynomial Multiplication:
Convolution of Two Signals
Another advantage:
wn = e^(i*2pi(theta)/n) = cos(theta) + i*sin(theta), n number of samples
This allows us to do Fourier analysis of a signal
A[] => y() by DFT (or FFT):
transforms a frequency spectrum to time series, and
y() => A[] by inverseDFT (or IFFT):
transforms from time series to its frequency spectrum
7/17/2015
FFT
13
Polynomial Multiplication
Standard Procedure:
A(x) = a0 + a1x1 + a2x2 + … an-1xn-1
B(x) = b0 + b1x1 + b3x2 + … bn-1xn-1
A(x)*B(x) = b0(a0 + a1x1 + a2x2 + … an-1xn-1)
+ b1x(…) + b2(…) +
Example:
A(x) = 3 + 2x – 4x2
B(x) = -4 –x + 2x2
A(x)*B(x) = 3*(-4) -x(3+2x- 4x2) +2x2(3+2x-4x2)
Total O(n2) scalar multiplications
7/17/2015
FFT
14
Polynomial Multiplication
Another way:
Evaluate at n points:
A(x) = 3 + 2x – 4x2 , B(x) = -4 –x + 2x2
x=(1, 2, 3)
A(1) = 1, A(2)=-9, A(3)=-27
B(1) = -1, B(2)=2, B(3)=11
Multiply point by point:
R(1)=-1, R(2)=-18, R(3)=-297, R as resulting polynomial
Solve for coefficients of R: linear algebra / simultaneous eq solving
How many terms? Coefficients? Order of R?
Goes up to 4th power of x: r0, r1, r2, r3, r4
Can be handled by increasing power of A and B with 0 coefficients:
A(x) = 3 +2x -4x2 +0x3 +0x4 +0x5 , B(x) = …
and evaluating at 6 points, not 3
7/17/2015
FFT
15
Polynomial Multiplication by evaluated points
Evaluation at each point: O(n) multiplications
at x, x2, x3, …
Evaluation at n points: O(n2)
Multiplication for n points: O(n)
Inverse matrix to solve for coefficients: O(n2)
Total poly-mult: O(n2), no advantage over standard way
7/17/2015
FFT
16
Polynomial Multiplication by evaluated points
7/17/2015
FFT
17
DFT for Polynomial Multiplication
(0) Pad each polynomial to (2n-2)-th order by extending:
an=0, an+1=0, ..., a2n-1=0
(1) Evaluate each polynomial at the 2n-th complex roots of 1:
w2n0=1, w2n1=wn, w2n2, w2n3, ..., w2n2n-1
(2) Then, element-to-element multiply values at each evaluated pts above:
A(wnk)*b(wnk) =: C(wnk), for k=0 … 2n-1
(3) Find coefficients of polynomial C(x) by using w0 through w2n
Steps 1 & 3 each takes O(2n log2n), & Step-2 takes O(2n)
Total O(n logn)
7/17/2015
FFT
18
ωn, n-th root of xn=1
ωn =e(i2π/n)
ω81
7/17/2015
FFT
19
ωn, n-th root of xn=1
ωn
ω8 2 = ω41
=e(i2π/n)
n is number of coefficients,
in nearest power of 2
ω81
8 roots of
x8 = 1
ω81 =e(i2π/8)
k-th power: (ω81)k =ek(i2π/8)
k-th root: ω8k =ek(i2π/8)
7/17/2015
FFT
20
ωn, n-th root of xn=1
ω8 2 = ω41
ω8
Lower order roots and power
of higher order roots may be
1 same
So, for A(x) = 3 + 2x – 4x2 +0x3,
We will evaluate at four points:
ω41=i, ω42=-1, ω43=-i, ω44 =1
7/17/2015
FFT
21
Advantage of using complex roots of one:
Divide and Conquer can be faster
A(x) = 3 + 2x – 4x2 +0x3 , to be evaluated at 4 points ω1 , ω2 , ω3 , ω4
However: ω4 = i, but ω42= -1= ω3
Such modulo nature reduces actual number of evaluations
Specifically, rules used are:
ωnn/2 = ω2 =-1 (second root of x2=1)
ωnn =1
(ωnk+n/2)2 = (ωnk)2
8 roots of x8 = 1
ω81 =e(i2π/8)
k-th power: (ω81)k =ek(i2π/8)
k-th root: ω8k =ek(i2π/8)
7/17/2015
FFT
22
D&C Polynomial Evaluation
A(x) = A0(x2) + xA1(x2)
s.t.,
A0(x) = a0 + a2x + a4x2 + … + an-2xn/2-1
A1(x) = a1 + a3x + a5x2 + … + an-1xn/2-1
So, now evaluate at half the number of points,
and multiply one half by x= ωn
Hence, divide and conquer
7/17/2015
FFT
23
Discrete Fourier Transformation:
D&C Polynomial Evaluation
T(n) = 2T(n/2) + n/2 for loop: O(n)
By Master’s theorem: T(n) = O(n logn)
7/17/2015
FFT
24
Reshuffling of coefficients for recursive calls
7/17/2015
FFT
25
Polynomial Multiplication by evaluated points
There will be 2n point to point mult,
After the two polynomials are evaluated
7/17/2015
FFT
26
Computing the coefficients from points : interpolation
DFT: Y = VA
Inverse DFT: Solving simultaneous equations
Needs inversion of V matrix:
Normally O(n2) operation
7/17/2015
FFT
27
Computing the coefficients from points : interpolation
 A polynomial evaluation at ωn-1
Use the same DFT
with ωn-1
O(n logn)
7/17/2015
FFT
28
Computing the coefficients from points : interpolation
Solving simultaneous equations to find coefficients vector A:
A = V-1Y: but V-1kj = 1/(n* Vjk)
Use ωn =e(-i2π/n) in line 4 of DFT,
and divide the final returned vector by n
7/17/2015
FFT
29
Fast Fourier Transform: FFT
FFT: Iterative version of DFT
BIT-REVERSE-COPY: shuffle input vector
7/17/2015
FFT
30
FFT Circuit Visualization for n=8
7/17/2015
FFT
31
Evaluate 2 – x + 3x2 +4x3 -2x4 -2x6 +x7
At eight roots of x8=1
2
-1
ω20 =e(i2π/2)*0
=1
3
-4
=1
1
0
-2
1
7/17/2015
FFT
32
2
-1
3 +1*1 = 3
3
ω20 =e(i2π/2)*0
=1
=1
3 11*1 = 2
3 +1*(-2) = 1
3
-4
=1
3 -1*(-2) = 5
1
0
-2
1
7/17/2015
FFT
33
2
2 -1*1 = 1
1 +i*5
=i
1 -i*5
-1
3
-4
3 -1*(-2) = 5
1
0
-2
1
e(i2π/4)*1 = cos(Pi/2) + i sin(Pi/2) = i
7/17/2015
FFT
34
3
4
2
1 +i*5
1
-1
3-1=2
1
3
-4
5
1 -i*5
=i
-1
1
-1
0
-3
-2
1
-5
e(i2π/8)*1 = cos(Pi/4) + i sin(Pi/4) = (1/sqr-root_2)(1+i)
7/17/2015
FFT
35