0.2 Derivation of the equations for a basic fdm-tdm transmux  (Page 5/10)

are needed for the preprocessor/DFT method.

The goal outlined in the section "What is an FDM-TDM Transmultiplexer" was to demultiplex all of the channels carried in the input FDM signal. If the input sampling rate is not chosen extravagantly, then the number of channels should be somewhat less than $\frac{N}{2}$ if the input signal is real-valued, and somewhat less than N if the signal is complex-valued. To obtain the worst-case situation, we assume that it is complex-valued and that $C=N$ . In this case, the total multiply-add computation is given by

Even though this value is less than that required by the direct tuning method, the quadratic dependence on the number of channels N makes this method expensive for situations where a large number of channels must be dealt with.

Solution to this problem comes in the form of the fast Fourier transform (FFT), a class of algorithms that can be used to efficiently compute all of the points of a DFT if N the size of the DFT, meets certain conditions. In particular, if N is a so-called highly composite number that is, it is the product of small positive integers, then various symmetries can be exploited to dramatically reduce the computation needed to compute the desired C tuner outputs.

In practice the size of the DFT, N , is typically chosen to equal 2 ^R or $4^{\frac{R}{2}}$ , where R is some positive integer, resulting in what is known as the radix-2 or radix-4 FFT, respectively An important exception to this is the so-called prime-factor transform in which N is the product of small, prime factors (e.g., 2, 3, 5 , 7, 11, etc). .

For discussion here we will assume the use of a radix-2 FFT (even though it is well known that the radix-4 algorithm is somewhat more computationally efficient). With this assumption we find that the number of multiply-adds needed to compute all N possible tuner outputs, is given by

Comparison of this equation with [link] shows that the FFT-based method always requires less computation than direct DFT computation of all N tuners and requires less than the direct DFT computation of C tuners when C exceeds $lo{g}_{2}N$ . For example, suppose that: $N=64$ for a particular problem. If more than $lo{g}_{2}64=6$ tuners are required, then the FFT is more efficient. If C is more on the order of 50, as it probably would be, then FFT-based computation of the DFT is about eight times more efficient than direct computation of the DFT and even more efficient compared to conventional computation of the tuner outputs. A graphical example is shown in [link] .

The generic FFT-based transmultiplexer consists of a preprocessor, which blocks, weights, and sums the input data to produce the N values of $v(r,p)$ , and an FFT, which efficiently computes the DFT for every value of n . This structure is shown in [link] . The input data is sampled (or provided by a preceding digital subsystem), preprocessed, and DFTed using the FFT algorithm. The FFT output bins are read out sequentially, thus producing the time division multiplexed (TDM) form promised originally.