Scribd Logo
Upload

Welcome to Scribd!

  • 690 views

    Finite Word Length Effects in FFT Algorithm

    Uploaded by

    anu
    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.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Finite Word Length Effects in FFT Algorithm

    Uploaded by

    anu
    690 views12 pages
    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.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    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.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    690 views12 pages

    Finite Word Length Effects in FFT Algorithm

    Uploaded by

    anu
    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.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 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