[go: up one dir, main page]
Scribd
Upload
1K views12 pages

Finite Word Length Effects in FFT Algorithm

Finite word length effects cause round-off errors in FFT algorithms. Quantization introduces errors when converting continuous signals to discrete, finite length representations. Product quantization error arises from multiplying finite-bit data and coefficients that produce outputs larger than the register size. For an 8-point DIT FFT algorithm, each stage forms a new array from the previous using basic operations, introducing round-off noise modeled as additive noise. The variance of output noise is proportional to the number of butterflies affecting each DFT computation node, which is N-1 for each of the N output nodes.

Uploaded by

anu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
1K views12 pages

Finite Word Length Effects in FFT Algorithm

Finite word length effects cause round-off errors in FFT algorithms. Quantization introduces errors when converting continuous signals to discrete, finite length representations. Product quantization error arises from multiplying finite-bit data and coefficients that produce outputs larger than the register size. For an 8-point DIT FFT algorithm, each stage forms a new array from the previous using basic operations, introducing round-off noise modeled as additive noise. The variance of output noise is proportional to the number of butterflies affecting each DFT computation node, which is N-1 for each of the N output nodes.

Uploaded by

anu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 12

FINITE WORD LENGTH

EFFECTS IN FFT
ALGORITHM :
ROUND OFF ERRORS
Finite Word Length Effect
• Most of the signals in real world are continuous.
• In DSP,

Continuous Signal Quantized Signal


Discrete Signal
(infinite length) (Finite Length)

 To convert into finite length we either truncate / round off the sequence
Product Quantization Error

Arise at the output of a multiplier

 Multiplication of b bit data and b bit coefficient will produce 2b bit output

 But only b bit registers are available, hence output should be truncated/ rounded off to b bits

 This produces an error


x[n]
x(t) Sampler Quantizer xq[n]

Quantization error,
e(n) = x[n] - xq[n]
Assume a sinusoidal signal between -1 and 1

If ADC is used to convert, it employs (b+1) bits, including the sign bit

 Then number of levels available for quantizing x(n) is

Thus interval between two successive levels are

, q -> Quantization step size


Let us consider the computation of DFT using Radix-2 DIT FFT algorithm for N=8:
The DFT is computed in

at each stage a new array of N numbers are formed from the previous array by using the
basic operations of DIT FFT algorithm,

, here m and (m+1) refers to mth and (m+1)th array


p and q represent location of number in each array
Here product of causes ROUND-OFF ERROR

 Therefore, we shall model the round off noise by associating an additive noise generator

 Here e(m,q) represents a complex error introduced in multiplication.


We make the following assumptions:
1. Round off noise due to each multiplication is uniformly distributed in amplitude
between -2-b /2 to 2-b /2
2. All noise sources are uncorrelated to each other
3. All noise sources are uncorrelated with input and output
As input data and twiddle factor are complex, 4 real multiplications are associated for each
complex multiplication.
 Variance of the Round off Error,

To calculate the variance of any output noise at any output node, we consider butterflies
that affect the computation of dft at that node.

 Eg – the output node X(1) is connected to N-1 = 7 butterflies.

i.e, 7 noise sources affect dft computation of X(1)


This is applicable for all Output nodes

 Hence, (N-1) noise sources propagate to each output node, which results in an
output noise variance given by,

For large values of N,

 This is the same result that we obtained from direct computation of the DFT
Thank you

You might also like