The minimum acceptable word length for the representation of real numbers in Fast Fourier Transform (FFT) with undersampled inputs is studied in this paper. FFT is a critical module in Orthogonal Frequency Division Multiplexing (OFDM) telecommunication infrastructure also used in Internet of Things (IoT) environments. The FFT input/output values, the twiddle factors and its intermediate results are complex numbers that can be represented either in fixed point or floating-point format. A tradeoff has to be made between rounding error and complexity. We focus on FFT with sparse inputs such as the values generated by many IoT sensors, surveillance cameras, etc. A configurable new FFT architecture has been developed to test various FFT sizes, word lengths and Quadrature Amplitude Modulations (QAM). The simulation results show that 8 bits FFT word length is sufficient in the employed undersampling procedure.
Discrete Fourier Transform (DFT) is used for the representation of periodic
functions as a sum of sine and cosine functions. Fourier transform is used in several
scientific domains of mathematics (e.g., for the analysis of differential equations) and
signal processing (filtering, spectroscopy, etc.) [
The representation of the real numbers is very important to computationally
intensive operations like FFT. Due to the FFT’s high complexity, the real numbers
have to be implemented preserving a minimum word length, otherwise severe
rounding errors occur. The limited precision of fixed-point arithmetic for different FFT
algorithms is studied in [
The analysis for the FFT word length presented here concerns an OFDM transceiver
that has been recently presented in [
The OFDM and FFT architectures as well as the proposed undersampling method are described in Section 2. The simulation results are discussed in Section 3.
In [
The FFT input yk is split in two parts: yk_a and yk_b. In Radix-4 butterflies, 4 pairs of inputs are used and radices that are not powers of 2 (such as Radix-3, Radix-5) can also be employed. Decimation in Frequency (DIF) differs from DIT in the fact that the order of the butterfly inputs and outputs is bit reversed. The FFT software implementations are slow and thus, most of the modern telecommunication systems are based on hardware implementations.
There are log2(N) stages in the N-point FFT implemented in this paper. The real and imaginary parts of the stage p inputs are stored in a pair of buffers. A pair of operands are accessed through ports rp1 and rp2 while a pair of values can be stored to the buffer through write ports wp1, wp2. Each one of these read or write ports has size d. The twiddle factors w, are retrieved from a ROM with N/2p+1 size at stage p. Each Butterfly block performs the following calculations: 1(3+, ), 2 = 13, 2+ 13#2∙ {} − {3#} ∙ {}. 1(3+, ), 2 = 13, 2+ 13#2∙ {} + {3#} ∙ {}. 1(3+, )#2 = 13, 2− 13#2∙ {} + {3#} ∙ {}.
1(3+, )#2 = 13, 2− 13#2∙ {} − {3#} ∙ {}.
The sparseness level S is the fraction of the non-zero bits in the input data stream and is expected to be small (e.g., 1%-2%) if the input data are sparse. Many q-QAM symbols are expected to be equal (Xc) due to data sparsity and they form an IFFT input set with appropriate structure. A number of samples in this FFT input set are expected to be equal (due to the input sparseness) and they can replace each other. The ADC in does not need to sample all the values since some of them can be replaced by others already received. The ADC sampling rate can thus be reduced on the receiver for lower power. The OFDM undersampling method proposed for wired channels is based on the following DFT property:
The parameters yn, Yk are the N, DFT input, output symbols and Xk, xn are the N,
Inverse DFT (IDFT) input, output symbols respectively. The twiddle factors w are
defined as !" = #$"/!. The xn symbols of the OFDM transmitter IDFT output are sent
over the communication channel and they are received as yn at the input of the receiver
DFT module. FFT reduces the O(N2) operations required by DFT to O(N∙logN). FFT
building blocks are the Radix-r butterflies. Radix-2 butterflies operate on a pair of inputs
(y1 and y2) that are defined as follows [
, (8) n+ 2
n+ The outputs xn and x
N of the IDFT are equal, only if X k = X k +
N and k is odd. 2
n+
2 2 half of the yn symbols placed in odd positions with n>N/2, can be substituted by others. The ADC on the receiver can operate at half speed, 50% of the time in this case. The maximum number of substituted samples is R2=N/4 but this value would make sense only if all inputs are 0, otherwise a high error floor occurs. If the value of R is smaller, the error may be acceptable.
N ) can be replaced by xn (yn). On the receiver, up to
The effect of the rounding error caused by the limited FFT word length is studied through simulations. The two metrics used, are the Normalized Mean Square Error (NMSE) and the Symbol Error Rate (SER). If it is assumed that an FFT output Y corresponds to IFFT input X, its NMSE error can be expressed as = ‖ − ‖##/‖‖##. There is an area on the QAM constellation plane where Y is recognized as X due to shorter distance compared with the neighboring constellations. Although the NMSE is not 0 in this case this error does not affect SER. If e.g., Y is recognized as a different 16QAM symbol than X, only one of the 4 data bits that correspond to this constellation would be inverted. Thus, the effect of this error on the Bit Error Rate (BER) would be 4 times lower than on the SER.
(a) (b)
If two numbers of nb bits are multiplied, the rounding error is between ±
2
ds = 2-(nb-1) and if the error probability is uniform (1/ds), then the error variance is: ds2 /12
"
. The rounding noise for N-point FFT is up to [
Fig. 2 shows the simulation results for combination C1. When 6 bits (with 3 bits fraction) are used, truncation (“Trunc”) caused by limited word length plus undersampling error makes the quantization error much higher than the undersampling error alone (“NoTrunc” cases). However, the error is almost identical and equal to the undersampling error when 8 bits (with 5 bits fraction) are used i.e., the quantization error is small in this case. 2-(nb -1)
. If
Similar conclusions can be drawn from Fig. 3 and 4 for combinations C2 and C3, respectively. It should be noticed that the undersampling error is quite small with QPSK (C2) especially with R8, making the quantization error relatively high even when 8-bit word length is used. In the C3 combination, different NMSE values lead to similar SER behavior. NMSE can be drastically reduced when 8-bit word length is selected. Fig. 5 shows how the NMSE, SER can be projected in the range S=[0..10%] for one of the cases (C3). Similar plots can be retrieved for C1 and C2.
The effect of the selected FFT word length in an OFDM transceiver supporting undersampling when sparse information is exchanged as in the case of IoT sensors, surveillance cameras, etc. was studied. Simulation on three combinations of FFT size and QAM modulations, showed that the use of 8-bits in the FFT word length was adequate in order to keep the power consumption and complexity low.