written 5.0 years ago by |
Let $x(n)$ be a finite duration complex-valued sequence of length $N .$
By definition, $X(k)=D F T[x(n)]=\sum_N x(n) \cdot W_{N}^{n k},$ where $k=0,1,2, \ldots N-1$ and W is the twiddle factor.
Let the real and imaginary components of $\mathrm{x}(\mathrm{n})$ and $W_{N}^{n k}$ be represented by $\mathrm{b}$ bits with fixed-point arithmetic. Each complex multiplication involves 4 real multiplications. Each real multiplication is rounded from 2 $\mathrm{b}$ bits to $\mathrm{b}$ bits, and hence there are four quantization (round-off) errors for cach complex-valued multiplication.
In the direct computation of the DFT, there are N complex-valued multiplications for each point in the DFT. So, there are 4 $\mathrm{N}$ real multiplications for each point. Hence, there are 4 $\mathrm{N}$ quantization errors.
Round-off errors in DFT multiplication are analyzed using Additive White Noise Model.
Following assumptions are made about the statistical properties of the quantization errors.
- Quantization (round-off) errors are uniformly distributed random variables in the range $\frac{-\Delta}{2}$ to $\frac{\Delta}{2}$ where $\Delta=2^{-b} .$
- 4 $\mathrm{N}$ quantization errors are mutually uncorrelated.
- 4 $\mathrm{N}$ quantization errors are uncorrelated with the sequence $\mathrm{x}(\mathrm{n}) .$
Variance of each quantization error $\sigma_{e}^{2}=\frac{\Delta^{2}}{12}=\frac{2^{-2 b}}{12}$
Variance of the quantization errors from the 4 $\mathrm{N}$ multiplications $\sigma_{q}^{2}=\frac{N}{3} 2^{-2 b}$
If $N=2^{m}$ then $\sigma_{q}^{2}=\frac{1}{3} 2^{-2(b-m / 2)}$
Hence the variance of the quantization error is proportional to the size of DFT. For every four-fold increase in the size $\mathrm{N}$ of the DFT requires an additional bit in computational precision to maintain same quantization error. Moreover, while computing DFT another Quantization error is occurs because of overflow due to addition To prevent overflow due to addition, the input sequence to the DFT must to scaled.
To satisfy the scaling condition $\sum_{n=0}^{N-1}|x(n)|\lt1,$ each point in the input sequence should be divided by N.