Shifting is necessary when performing a fixed point FFT due to the limited dynamic range of fixed point arithmetic. To help maximize the dynamic range, prior to the FFT, the input data buffer is normalized (upshifted) to full scale of the data type. During the FFT process the data is down-shifted to prevent overflow. The FFT algorithm requires complex algebra. After each Radix-2 butterfly stage, the resulting data could be twice as large as the input.
There are a couple methods to handle the down-shift scaling of fixed point FFTs. The first is to pre-scale the data based on the number of butterfly stages there will be in the FFT. For example, for a 256 FFT, the input data will be down shifted by 8 (i.e. divide by 256). Alternatively, the data can be checked before each stage to determine if the data is greater than half the max value that can be represented by the data type. If so, then the data will be down-shifted by 1 (i.e., divide by 2). The combination of the normalization shift and the downshift is considered the exponent of the resulting data. This exponent can be used to rescale the data to larger data type.
The images below show the pseudocode for each method.
/* find max value of input buffer */ max_value = find_max(input);
/* count number of leading zeros */ norm_shift = clz(max_value);
/* normalize data */ for (i = 0; i < fft_size; i++) { input[i] = input[i] << norm_shift; }
/* pre-scale input data */ for (i = 0; i < fft_size; i++) { input[i] = input[i] >> fft_order; }
/* … */ /* perform bufferfly stages */ for (i = 0; i < fft_order; i++) { perform_bufferfly_calc(input); } |
/* find max value of input buffer */ max_value = find_max(input);
/* count number of leading zeros */ norm_shift = clz(max_value);
/* normalize data */ for (i = 0; i < fft_size; i++) { input[i] = input[i] << norm_shift; }
/* … */ /* perform bufferfly stages */ fft_shift = 0; for (i = 0; i < fft_order; i++) { /* find max value of input buffer */ max_value = find_max(input); if (max_value > HALF_MAX_SIGNED_VALUE) { /* nearly overflow, rescale */ fft_shift++; for (i = 0; i < fft_size; i++) { input[i] = input[i] >> 1; } } perform_bufferfly_calc(input); } |
The advantage of pre-scaling the data before performing the FFT is the reduced computational complexity. The advantage of the scaling during the FFT is the increased precision by only shifting when necessary.