## 4 FFT Implementation Issues
The error floor is much lower if 12.5% of the \(x_{n}\) symbols at the receiver are substituted, _i.e.,_ a quarter of the odd positioned \(x_{n}\) symbols. In this case, an \(N\)/4-point FFT can be removed reducing the die area needed for its VLSI implementation. Of course, if the exchanged information is not sparse all the time, the \(N\)/4-point FFT must not be removed but can be deactivated for lower power consumption when sparse information reception is detected. The FFT requires Random Access Memory (RAM) memory for storing both its input and its intermediate results. The twiddle factor coefficients are usually stored in Read Only Memory (ROM). In VLSI FFT implementations with single memory, the butterflies are using the same memory for storing their inputs and their results requiring lower memory but they are slower since reading the input and writing the output values cannot be carried out concurrently. In dual memory architectures the butterfly results are stored in a separate memory concurrently with the reading of the input values. Pipeline architectures consist of multiple stages with intermediate storage requirements, thus, they have the highest memory requirements but they also can achieve the highest speed. Several more advanced FFT implementations have been proposed, with low memory requirements without compromising speed. In [21], a single radix-4 FFT with partitioned memory is used to implement a 256-point FFT in 6 us complying with the HomePlug standard. The required total RAM memory size is \(N\) in this architecture. In [22], a pipeline butterfly module is described requiring \(N\) RAM words grouped in two banks. In [23], the FFT implementation for an 8 \(\times\) 8 Multiple Input Multiple Output (MIMO) OFDM system is described. The 128-point Mixed Radix Multi-path Delay Commutator (MRDC) described in [23] accepts as input the eight streams of the MIMO system. The role of the input and output RAMs is data arrangement between the adjoined OFDM blocks such as OFDM subcarrier assignment and guard interval insertion. It is obvious from the FFT implementationsin [21], [22] and [23] that not all of the inputs of the FFT are stored in RAM. In fact in most of the implementations only half of the input values need to be stored initially and the rest are driven directly to the FFT inputs. Consequently, if an FFT implementation requires \(N\) RAM words, half of the words are used for input storage and the rest of them are used for intermediate results. In fact, in implementations like [22], even the _N_/2 words that are initially used for input values' storage, are also later used for storing intermediate results. Figure 5: Original FFT implementation of [22] (**a**) and Modified FFT implementation for the proposed undersampling method (**b**). The operations with the red font in Figure 5b indicate trivial operations that can be omitted. In this paper, we assumed that in the general case all the input values are stored initially in a RAM buffer and the 25% reduction that can be achieved is referring to this buffer as is the case in [23]. However, if sparse input data are used, then the trivial values appearing at the outputs of some FFT blocks, also affects the storage requirements for intermediate results. Thus, we can state that the 25% reduction in the memory requirements achieved by the proposed undersampling method, applies to the whole FFT architecture. This fact can be demonstrated by the 8-point example FFT architecture described in [22]. By slightly modifying the multiplexing scheme of the Memory Based FFT (MBFFT) presented in [22], the operations needed and the memory required for this 8-point FFT is shown in Figure 5.  
In Figure 5a, the original operations described in [22] are presented for an 8-bit FFT. Each one of the two RAM banks (RAM1 and RAM2) has four words and the RAM contents at the left are the input values to the operations shown in the middle column. The RAM contents at the right are the output values of these operations.