# Connexions

You are here: Home » Content » Derivation of the equations for a Basic FDM-TDM Transmux

### Lenses

What is a lens?

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

#### In these lenses

• UniqU content

This module is included inLens: UniqU's lens
By: UniqU, LLCAs a part of collection: "An Introduction to the FDM-TDM Digital Transmultiplexer"

Click the "UniqU content" link to see all content selected in this lens.

### Recently Viewed

This feature requires Javascript to be enabled.

# Derivation of the equations for a Basic FDM-TDM Transmux

Module by: John Treichler. E-mail the author

Two intuitively reasonable approaches to developing the equations for the FDM-TDM transmultiplexer are presented in this section. The first emulates Figure 1. We first develop the equations for a digital counterpart of the analog tuners used in the filter bank and then observe that significant computational improvements can be obtained when the tuning frequencies are linked together in a simple way. The second subsection starts from a different point, that of using the discrete Fourier transform as a spectral channelizer. We ultimately find out that these two approaches yield essentially the same analytical results.

## The Transmux as a Bank of Single Channel Digital Tuners

### Fundamental equations for a Single-Channel Digital Tuner

The input FDM signal is assumed to be the continuous-time waveform xc(t)xc(t). The analog-to-digital converter shown in Figure 1 samples this waveform at the uniform rate of fs samples per second, producing the discrete-time sequence x(k)x(k), where x(k)xc(t=kT)x(k)xc(t=kT), the integer k is the time index, and T is the sampling interval given by T=1fsT=1fs. The spectrum of this sequence is shifted down in frequency by multiplying it by a complex exponential of the form e-j2πf0kTe-j2πf0kT, where f0 is the desired amount of the frequency downconversion. The product of x(k)x(k) and this exponential is then filtered in discrete time by using the pulse response h(k)h(k). The duration of the pulse response h(k)h(k) is assumed to be finite and in particular of length no greater than L, an integer. The filter output y¯(k)y¯(k) is then decimated by a factor of M, yielding the sequence y(r)y(r), where the integer r is the decimated time index.

These processing steps are shown in graphical form in Figure 2. Both sides of the two-sided spectrum of the sampled input signal are seen in Figure 2(a). For the moment, the input signal is assumed to be real-valued and therefore the spectrum is symmetrical around 0 Hz 1. A channel of interest in this spectrum has been shaded and its center frequency is noted to be f0. Multiplying the input signal by e-j2πf0kTe-j2πf0kT has the effect of shifting the spectrum to the left (assuming 0f0fs20f0fs2) and centering the desired channel at 0 Hz. The downconverted signal is now complex-valued, and therefore spectral symmetry around 0 Hz is neither required nor expected. The transfer function of the lowpass filter appears in Figure 2(c). The filter pulse response h(k)h(k) is chosen to attain the desired spectral characteristics. In particular, the filter needs to pass the channel of interest without degradation and suppress all others sufficiently. How to design such a pulse response is discussed in Appendix A. In general, the quality of the filter grows with the value of the parameter L. The filter shown here is symmetrical around 0 Hz and its pulse response h(k)h(k) can therefore be real-valued. This is not required however.

After the application of the shifted signal ρ(k)ρ(k) to the filter, the spectrum shown in Figure 2(d) results. The desired channel is isolated from all others. It is sampled, however, at a rate far faster than required by the Nyquist sampling theorem. The filter output is then decimated by the factor M, resulting in the spectrum shown in Figure 2(e). The channel's bandwidth is the same as before but now its percentage bandwidth, that is, its bandwidth compared to its final sampling rate, is much higher. In a good digital tuner the percentage bandwidth after decimation usually ranges between 0.5 and 0.9, where unity is the theoretical limit imposed by the sampling theorem.

In principle, the parameters fs (and hence T), f0, L, and M can be chosen arbitrarily. In fact, significant simplications to the implementation of the tuner occur if they are carefully chosen. To do this we must first develop a general equation for the decimated tuner output y(r)y(r).

The undecimated filter output y¯(k)y¯(k) can be written as the convolutional sum of ρ(k)ρ(k) and the filter pulse response h(k)h(k):

y ¯ ( k ) = l = 0 L - 1 h ( l ) ρ ( k - l ) . y ¯ ( k ) = l = 0 L - 1 h ( l ) ρ ( k - l ) .
(1)

Substituting the expression for ρ(k)ρ(k) yields

y ¯ ( k ) = l = 0 L - 1 h ( l ) x ( k - l ) e - j 2 π f 0 T ( k - l ) . y ¯ ( k ) = l = 0 L - 1 h ( l ) x ( k - l ) e - j 2 π f 0 T ( k - l ) .
(2)

Separating the two terms in the exponential produces the next expression:

y ¯ ( k ) = e - j 2 π f 0 T k · l = 0 L - 1 h ( l ) x ( k - l ) e j 2 π f 0 T l . y ¯ ( k ) = e - j 2 π f 0 T k · l = 0 L - 1 h ( l ) x ( k - l ) e j 2 π f 0 T l .
(3)

Decimation by the factor M is introduced by evaluating y¯(k)y¯(k) only at the values of k where k=rMk=rM. We denote the decimated output as y(r)y(r), given by

y ( r ) y ¯ ( k = r M ) = e - j 2 π j 0 T r M · l = 0 L - 1 h ( l ) x ( r M - l ) e j 2 π f 0 T l y ( r ) y ¯ ( k = r M ) = e - j 2 π j 0 T r M · l = 0 L - 1 h ( l ) x ( r M - l ) e j 2 π f 0 T l
(4)

### Choosing Various System Parameters to Simplify the General Equation for the Tuner Output

Equation 4 holds for arbitrary choice of L, M, f0, and fs. To obtain the equations for the basic FDM-TDM transmultiplexer, we must first simplify the general equation for the output of the digital tuner. We do this by making the three key assumptions:

1. We assume that the sampling rate fs and the tuning frequency f0 are integer multiples of the same frequency step ΔfΔf. In the case of FDM multichannel telephone systems for example, ΔfΔf is typically 4 kHz. We define the integer parameters N and n with the expressions fsN·ΔffsN·Δf and f0n·Δff0n·Δf.
2. We next assume that the pulse response duration L is an integer multiple of the factor N defined above. We define the positive integer parameter Q where LQ·NLQ·N. This is a nonrestrictive assumption since Q can be chosen large enough to make it true for any value of L. If QNQN exceeds the minimum required value of L, then h(k)h(k) can be made artificially longer by padding it with zero values. The factor Q turns out to be an important design parameter. The parameters Q and N are determined separately and the resulting value of L follows from their choice.
3. We also assume that the decimation factor M is chosen to be closely related to the parameter N. Typical values are M=NM=N and M=N2M=N2

We can now examine the effects of these assumptions. First, the relationship between fs, f0, and ΔfΔf allows y(r)y(r) to be written as

y n ( r ) = e - j 2 π n r M N · l = 0 L - 1 h ( l ) x ( r M - l ) e j 2 π n l N . y n ( r ) = e - j 2 π n r M N · l = 0 L - 1 h ( l ) x ( r M - l ) e j 2 π n l N .
(5)

We subscript the decimated output y(r)y(r) by the parameter n to indicate that it depends on the tuning frequency f0=n·Δff0=n·Δf.

The second assumption, the definition of the parameter Q, permits the single sum to be split into a nested double sum. To do this, define the new integer indices q and p by the expressions

l q N + p , w h e r e 0 q Q - 1 a n d 0 p N - 1 . l q N + p , w h e r e 0 q Q - 1 a n d 0 p N - 1 .
(6)

Examination of Equation 6 shows that the pulse response running index l has a unique value in the range from 0 to L-1L-1 for each permissible value of p and q. This permits the single convolutional sum over the index l to be replaced (for reasons to be shown) with a double sum over the indices p and q. In particular,

y n ( r ) = e - j 2 π n r M N · l = 0 L - 1 h ( l ) x ( r M - l ) e j 2 π n l N = e - j 2 π n r M N · p = 0 N - 1 q = 0 Q - 1 h ( q N + p ) x ( r M - q N - p ) e j 2 π n ( q N + p ) N = e - j 2 π n r M N · p = 0 N - 1 q = 0 Q - 1 h ( q N + p ) x ( r M - q N - p ) e j 2 π n q N N e j 2 π n p N = e - j 2 π n r M N · p = 0 N - 1 e j 2 π n p N [ q = 0 Q - 1 h ( q N + p ) x ( r M - q N - p ) ] . y n ( r ) = e - j 2 π n r M N · l = 0 L - 1 h ( l ) x ( r M - l ) e j 2 π n l N = e - j 2 π n r M N · p = 0 N - 1 q = 0 Q - 1 h ( q N + p ) x ( r M - q N - p ) e j 2 π n ( q N + p ) N = e - j 2 π n r M N · p = 0 N - 1 q = 0 Q - 1 h ( q N + p ) x ( r M - q N - p ) e j 2 π n q N N e j 2 π n p N = e - j 2 π n r M N · p = 0 N - 1 e j 2 π n p N [ q = 0 Q - 1 h ( q N + p ) x ( r M - q N - p ) ] .
(7)

The first portion of the exponential term in the sum vanishes since its argument is always an integer multiple of 2π2π. Moving the terms of the summation in the last step is possible since the remaining term of the exponential does not depend on the running index q. It is useful to give a short name to the terms in brackets in the last equation. Noting that it is a function of the decimated time index r and the running index p, we define the variable v(r,p)v(r,p) by the expression

v ( r , p ) q = 0 Q - 1 h ( q N + p ) · x ( r M - q N - p ) . v ( r , p ) q = 0 Q - 1 h ( q N + p ) · x ( r M - q N - p ) .
(8)

Notice that v(r,p)v(r,p) is a function of the input data x(k)x(k), the filter pulse response h(l)h(l), and the system parameters Q, M, and N, but it is not a function of the selected conversion frequency f0, represented in the equation for yn(r)yn(r) by the integer n.

Substituting v(r,p)v(r,p) into the equation for the decimated output yn(r)yn(r) of the tuner tuned to frequency f0=n·Δff0=n·Δf yields

y n ( r ) = e - j 2 π n r M N · p = 0 N - 1 e j 2 π n p N v ( r , p ) y n ( r ) = e - j 2 π n r M N · p = 0 N - 1 e j 2 π n p N v ( r , p )
(9)

Notice that the frequency dependency of the tuner shows up only in the exponential terms.

Before discussing this result in detail it remains to examine the effects of the third assumption. To do this, define the decimation factor M by the expression MNKMNK, where K=1K=1, 2, or 4. Look first at the exponential terms preceding the sum. It can now be written as

e - j 2 π n r M N = e - j 2 π n r K = [ e - j 2 π K ] n r = [ - j 4 K ] n r . e - j 2 π n r M N = e - j 2 π n r K = [ e - j 2 π K ] n r = [ - j 4 K ] n r .
(10)

With K defined this way, the most general expression for yn(r)yn(r) is

y n ( r ) = [ - j 4 K ] n r · p = 0 N - 1 e j 2 π n p N v ( r , p ) , w h e r e y n ( r ) = [ - j 4 K ] n r · p = 0 N - 1 e j 2 π n p N v ( r , p ) , w h e r e
(11)
v ( r , p ) = q = 0 Q - 1 h ( q N + p ) · x ( r N K - q N - p ) . v ( r , p ) = q = 0 Q - 1 h ( q N + p ) · x ( r N K - q N - p ) .
(12)

It can be verified that for K=1K=1, 2, or 4, the factor multiplying the sum is at most a negation or a swapping from imaginary to real or vice versa. Thus no actual multiplication is needed. By far the cleanest case is the one in which the other system parameters (for example, N, Q, and h( k) h(k)) are selected so that the decimation factor MM exactly equals N N, or equivalently that K=1K=1. In this case, the exponential preceding the sum collapses to unity, yielding what will be termed in this technical note as the basic FDM-TDM transmux equation2:

y n ( r ) = p = 0 N - 1 e j 2 π n p N v ( r , p ) , w h e r e y n ( r ) = p = 0 N - 1 e j 2 π n p N v ( r , p ) , w h e r e
(13)
v ( r , p ) = q = 0 Q - 1 h ( q N + p ) · x ( ( r - q ) N - p ) . v ( r , p ) = q = 0 Q - 1 h ( q N + p ) · x ( ( r - q ) N - p ) .
(14)

### Interpretation of the Basic Tuner equation in Terms of the Discrete Fourier Transform

Examination of Equation 14 shows that each sample of the tuner output, when tuned to frequency f0=nΔff0=nΔf, is the N-point inverse discrete Fourier transform (DFT) of the preprocessed data {v(r,p)}{v(r,p)}, evaluated at frequency index n. The signal flow described by the equation is shown in Figure 3. The sampled input data x(k)x(k) passes into a digital tapped delay line of length QNQN at the sampling rate fs. Every M-th sample, the complete contents of the delay line, all QNQN samples, are used to compute {v(r,p)}{v(r,p)}. Thus the v(r,p)v(r,p) are computed at the decimated rate fsMfsM. Each of the N elements of v(r,p)v(r,p) is computed by weighting Q of the delayed input samples by the appropriate coefficient from the pulse response vector h(k)h(k) and summing them together. Notice that at each decimated sampling interval all of the delayed data and all of the pulse response coefficients are used to compute the v(r,p)v(r,p). Notice also that since QNQN is usually much greater than M, each input sample is used in the production of the {v(r,p)}{v(r,p)} over several consecutive values of the decimated sampling index r.

The computation of the {v(r,p)}{v(r,p)} has several names in the literature. In some cases, it is referred to simply as the preprocessor or weighting processor. From the DFT-based filter bank interpretation of the transmultiplexer, in which the filter pulse function h(k)h(k) is viewed as a spectral window function, the operation is called windowing and folding. Some of the first researchers in the area [1] termed it polyphase filtering. Even though the reasons for this name are fairly obscure, it is commonly used.

Once the input data has been preprocessed, windowed and folded, or polyphase filtered, as you will, the resulting N values of v(r,p)v(r,p) are Fourier-transformed to produce yn(r)yn(r). Notice that all of this computation must be repeated for each value of r.

It will be useful later to know how much computation is required to implement this simplified tuner. Assume for this calculation that the input data x(k)x(k) is complex-valued and that the pulse response h(k)h(k) is real-valued. If so, then 2QN2QN multiply-add operations are needed for each computation of the {v(r,p)}{v(r,p)} and 4N4N multiply-adds (approximately) are needed for the computation of the single point of the DFT, all of this at the decimated sampling rate of fsMfsM. A conventional tuner using a real-valued, L-point pulse response and complex input data requires 4fs4fs multiply-adds for the mixer and 2fsLM2fsLM multiply-adds for the filtering. Comparing the two shows that the filtering/weighting is exactly the same for the two, while the tuning vs. DFT comparison depends on the relative values of M and N. Using the example of the basic transmux, where N=MN=M, we find that the two are equal. When M<NM<N, the simplified equations actually require slightly more computation. Why then do we go to this trouble?

### Generalization to the FFT-Based Digital Transmultiplexer

What if we desire to tune a second channel, say one that has a center frequency of fl=m·Δffl=m·Δf ? Following through the derivation done before, we find that ym(r)ym(r) is given by the same equations except that n is replaced with m. Examining the situation more closely we notice that the {v(r,p)}{v(r,p)} need not be recomputed to obtain the second tuner output. In fact, the only operation required to obtain the second tuner output is to recompute the inverse DFT, but this time evaluated for the index m instead of n. The conventional tuning approach must be completely repeated to obtain the output for another channel. It is usually the case that the computation of the {v(r,p)}{v(r,p)} is much larger than the computation required for the DFT. The fact that it need not be repeated quickly makes the preprocessor/DFT scheme significantly more efficient than the conventional digital tuner approach as the number of channels to be tuned grows. If we use the number of multiply-adds as an indication of computational complexity, and if we denote the number of channels to be tuned by the integer C, we can quantify this comparison by noting that

G converntional = C [ 4 f s + 2 f s Q N M ] multiply - adds G converntional = C [ 4 f s + 2 f s Q N M ] multiply - adds
(15)

are needed for C conventional decimated digital tuners while

G D F T = 2 f s Q N M + 4 C f s N M multiply - adds G D F T = 2 f s Q N M + 4 C f s N M multiply - adds
(16)

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 N2N2 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=NC=N. In this case, the total multiply-add computation is given by

G D F T ( N channels ) = 2 f s Q N M + 4 f s N 2 M . G D F T ( N channels ) = 2 f s Q N M + 4 f s N 2 M .
(17)

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 2R or 4R24R2 , where R is some positive integer, resulting in what is known as the radix-2 or radix-4 FFT, respectively3.

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

G radix - 2 FFT ( N channels ) = 2 f s N M [ Q + l o g 2 N ] . G radix - 2 FFT ( N channels ) = 2 f s N M [ Q + l o g 2 N ] .
(18)

Comparison of this equation with Equation 16 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 log2Nlog2N. For example, suppose that: N=64N=64 for a particular problem. If more than log264=6log264=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 Figure 4.

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)v(r,p), and an FFT, which efficiently computes the DFT for every value of n. This structure is shown in Figure 5. 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.

The computational efficiency of the transmultiplexer can therefore be traced to two key items:

1. Separation of the tuning computation into two segments, one of which (the {v(r,p)}{v(r,p)}) need be computed only once
2. The use of the FFT algorithm to compute the inverse DFT

The first accrues from strategic choices of the sampling and tuning frequencies, while the second depends on N being chosen to be a highly composite integer.

## The Transmux as a DFT-based Filter Bank

We have just developed an FDM-TDM transmultiplexer by first writing the equations for a single, decimated digital tuner. The equations for a bank of tuners come from then assuming that (1) they all use the same filter pulse response and (2) their center frequencies are all integer multiples of some basic frequency step. In this section, we develop an alternate view, which happens to yield the same equations. It produces a different set of insights, however, making its presentation worthwhile.

### Using the DFT as a Filter Bank

Instead of building a bank of tuners and then constraining their tuning frequencies to be regularly spaced, suppose we start with a structure known to provide equally-spaced spectral measurements and then manipulate it to obtain the desired performance.

Consider the structure shown in Figure 6. The sampled input signal x(k)x(k) enters a tapped delay line of length N. At every sampling instant, all N current and delayed samples are weighted by constant coefficients w(i)w(i) (where w(i)w(i) scales x(k-i)x(k-i), for i between 0 and N-1N-1), and then applied to an inverse discrete Fourier transform4. The complete N-point DFT is computed for every value of k and produces N outputs. The output sample stream from the m-th bin of the DFT is denoted as Xm(k)Xm(k).

Since DFTs are often associated with spectrum analysis, it may seem counterintuitive to consider the output bins as time samples. It is strictly legal from an analytical point of view, however, since the DFT is merely an N-input, N-output, memoryless, linear transformation. Even so, the relationship of this scheme and digital spectrum analysis will be commented upon later. We continue by first examining the path from the input to a specific output bin, the m-th one, say. For every input sample x(k)x(k) there is an output sample Xm(k)Xm(k). By inspection we can write an equation relating the input and chosen output:

X m ( k ) = p = 0 N - 1 x ( k - p ) w ( p ) e j 2 π m p N X m ( k ) = p = 0 N - 1 x ( k - p ) w ( p ) e j 2 π m p N
(19)

the m-th bin of an N-point DFT of the weighted, delayed data. We can look at this equation another way by defining w¯m(p)w¯m(p) by the expression

w ¯ m ( p ) w ( p ) · e j 2 π n p N w ¯ m ( p ) w ( p ) · e j 2 π n p N
(20)

and observing that Equation 19 can be written as

X m ( k ) = p = 0 N - 1 x ( k - p ) · w ¯ m ( p ) . X m ( k ) = p = 0 N - 1 x ( k - p ) · w ¯ m ( p ) .
(21)

From this equation it is clear Xm(k)Xm(k) is the output of the FIR digital filter that has x(k)x(k) as its input and w¯m(p)w¯m(p) as its pulse response. Since the pulse response does not depend on the time index k, the filtering is linear and shift-invariant. For such a filter we can compute its transfer function, using the expression

W m ( ω ) = p = 0 N - 1 w ¯ m ( p ) · e - j ω p T , - π T ω π T . W m ( ω ) = p = 0 N - 1 w ¯ m ( p ) · e - j ω p T , - π T ω π T .
(22)

Suppose that we first choose the simple case with uniform weighting, that is, w(p)=1w(p)=1 for 0pN-10pN-1 and, therefore, w¯m(p)=ej2πmpNw¯m(p)=ej2πmpN. In this case, Wm(w)Wm(w) is given by

W m ( ω ) = e - j π m N · e - j ( N - 1 ) ω T 2 · s i n N ω T 2 s i n ( π m N - ω T 2 ) W m ( ω ) = e - j π m N · e - j ( N - 1 ) ω T 2 · s i n N ω T 2 s i n ( π m N - ω T 2 )
(23)

The magnitude of this transfer function is plotted in Figure 7. From this plot we can conclude that the pulse response w¯m(p)w¯m(p) has what might be generally considered to be the frequency response of a bandpass filter. The filter is centered on bin m and its bandwidth is nominally fsNfsN. While it might be characterized as a bandpass filter, we also note that the passband is quite rounded and the stopband rejection is relatively poor. The first sidelobes are only 13 dB lower than the peak of the passband response.

We've now shown that the path from the input to the m-th bin can be described as a finite impulse response (FIR) filtering operation and that the transfer function of that filtering operation has a fairly sloppy bandpass characteristic, at least when the data weighting is uniform. What happens for other values of m then? The answer is "the same thing." For each value of m between 0 and N-1N-1, the pulse response w¯m(p)w¯m(p) is computed, leading to the transfer function Wm(ω)Wm(ω). An overlay of these bandpass responses is shown in the lower portion of Figure 7. From this we can conclude that the block diagram shown in Figure 6 describes a single-input, N-output bank of filters. The filter center frequencies are spaced uniformly in increments of fsNfsN Hz. All N outputs are sampled in time as frequently as the input. When the weighting function w(p)w(p) is uniform, then the bandpass filters have the form of Equation 23, shown in Figure 7.

### The Implications of Attaining the Desired Bandpass Characteristic

We've just shown that the DFT of delayed versions of the input sequence x(k)x(k) has the general properties of a bank of regularly-spaced bandpass filters. Two considerations leave us short of our goals. The first is that the shape of the transfer function for each bandpass filter is not good enough for most applications and must be improved. The second is that of reducing the amount of computation required. We address the first one in this section, and temporarily defer the computation issue.

Figure 8 shows two transfer functions. The one pointed to from the left is exactly the same as that shown in Figure 7 and defined in Equation 23. The one pointed to from the right is representative of the type needed for demultiplexing FDM multichannel telephone signals. It offers essentially flat response for most of the passband, has very sharp transition bands, and suppresses all energy outside of the transition bands by 55 dB or more. While other applications may require different transfer functions, as a rule they will be much more stringent than unweighted transfer function shown in Figure 8.

How then do we attain different transfer function characteristics? In fact, we use some of the remaining degrees of freedom, the weighting function w(p)w(p). By allowing w(p)w(p) to be non-uniform we can now alter the shape of the transfer function of each bandpass filter. By using well-known FIR filter design techniques (see An Introduction to the FDM-TDM Digital Transmultiplexer: Appendix A) it is possible to attain virtually any shape. It is not, however, possible to always attain the desired shape and the desired bandwidth while keeping the duration of the pulse response constant. In fact, as discussed in An Introduction to the FDM-TDM Digital Transmultiplexer: Appendix A, for a constant bandwidth, the pulse response duration must grow as the transition bandwidth is forced to be smaller and as the stopband suppression in increased. The chain of events described in Figure 9 then unfolds.

Shown across the top of Figure 9 is a stylized version of that seen in the bottom portion of Figure 7. The uniform weight shown on the top right leads to the bandpass filter shapes shown on the left. Note that the filters are separated in frequency by fsNfsN Hz.

Now suppose we employ non-uniform weighting to improve the shape of the bandpass filters. As discussed in Appendix A, such non-uniform weighting can be used to attain the desired transfer function shape, but virtually always at the expense of the bandpass filter's bandwidth. In fact, to obtain the desired characteristic shown in Figure 8, with its flat passband, sharp skirts, and high-attenuation stopband, the minimum passband bandwidth is more than a factor of ten larger than the unweighted response. Thus the use of a non-uniform weighting, as shown on the right of Figure 7(b), results in the situation shown on the left side. There are still N bandpass filters, and their center frequencies are still separated by integer multiples fsNfsN Hz, but each filter has been widened considerably, leading to a high degree of overlap.

The first problem to deal with is not the overlap, but rather the fact that the individual bandpass filters are far wider than the original goal of about fsNfsN Hz. This is dealt with by returning to Figure 6 and simply letting the delay line length, the number of weighting coefficients, and the DFT order grow until the filters are sufficiently narrowband to meet our objectives. Again using the example of the desired frequency response seen in Figure 8, the dimensions must grow by more than a factor of ten.

While the resulting dimensions can take on rather arbitrary values (above some minimum value) we'll assume here that the new size N' is an integer multiple of N. In particular, we assume that the delay line, and the weighting and DFT with it, are extended to the length N' where:

N ' = Q · N , N ' = Q · N ,
(24)

where Q is a positive integer. We further assume that Q is chosen to be large enough that a weighting function of length N' can be designed to produce not only the desired shape but also a bandwidth of about fsNfsN Hz. The resulting situation is shown in Figure 9(c). The weighting function is now longer than before (by a factor of Q). On the left we see that there are now N' filters in the filter bank. Each one of them now has the desired nominal bandwidth of fsNfsN Hz, but their center frequencies are now separated by δf=fsN'=fsNQδf=fsN'=fsNQ Hz instead of fsNfsN Hz. The overlap seen just above still exists but now there is a factor of Q more filters, a factor of Q narrower, and a factor of Q more closely spaced. Thus the positive effect of expanding the delay line dimension to QNQN is that the resulting filter bank includes the desired bandpass filters, both in bandpass characteristics and center frequencies. The negative aspects include the fact that the amount of weighting and DFT computation have gone up by a factor of Q and that there are now (Q-1)·N(Q-1)·N superfluous bandpass filters.

Suppose now that we choose to compute only every Q-th point of the DFT. The delay line is still QNQN samples long, there are still QNQN coefficients in the weighting function, and the DFT still has order QNQN, but we'll choose to only compute those output bins Xm(k)Xm(k) where m is an integer multiple of Q. This results in the situation shown in Figure 9(d). The same QN-point weighting function is used as immediately above. This case, with N filters of nominal bandwidth fsNfsN Hz and spaced fsNfsN Hz apart, was our objective. To achieve it, however, required expanding the dimensions of the preceding operations quite considerably.

We now develop some equations that describe the steps just traversed. Starting with Equation 19 we replace N with N'=QNN'=QN, obtaining an expression for the time sequence seen at the m-th DFT bin.

X m ( k ) = p = 0 Q N - 1 x ( k - p ) ω ( p ) e j 2 π m p Q N . X m ( k ) = p = 0 Q N - 1 x ( k - p ) ω ( p ) e j 2 π m p Q N .
(25)

Suppose, as discussed above, that we eliminate the filter overlapping by evaluating only every Q-th DFT bin. Thus we compute Xm(k)Xm(k) only for those values of m that are integer multiples of Q. Specifically, if n is assumed to be an integer, then we only compute Xm(k)Xm(k) for values of m given by m=Qnm=Qn. This is leads to

X m ( k ) = X Q n ( k ) X n ( k ) = p = 0 Q N - 1 x ( k - p ) w ( p ) e j 2 π n p N . X m ( k ) = X Q n ( k ) X n ( k ) = p = 0 Q N - 1 x ( k - p ) w ( p ) e j 2 π n p N .
(26)

Since we have achieved the goal of constructing spectrally concentrated bandpass filters (albeit at the cost of expanding the size of all steps preceding the final DFT computation), we can now consider decimating the filter outputs. Since the filter bandwidths are nominally fsNfsN Hz, decimation by up to N is possible without violating the sampling theorem. Suppose we decimate by the factor M, where 0<MN0<MN. This means evaluating the integer time index k only at integer multiples of M. If we allow the integer to be the decimated time index, the decimated version of the n-th DFT bin output is

X n ( k = r M ) = X n ( r ) = p = 0 Q N - 1 x ( r M - p ) w ( p ) e j 2 π n p N . X n ( k = r M ) = X n ( r ) = p = 0 Q N - 1 x ( r M - p ) w ( p ) e j 2 π n p N .
(27)

At this point we can start making comparisons. Equation 3 closely resembles Equation 26 and Equation 4 closely resembles Equation 27. In fact, if we use the definition of v(r,p)v(r,p) developed earlier, then Equation 27 becomes

X n ( r ) = p = 0 N - 1 v ( r , p ) · e j 2 π n p N X n ( r ) = p = 0 N - 1 v ( r , p ) · e j 2 π n p N
(28)

which differs from the equation for yn(r)yn(r) developed in Equation 9 only in the absence of a residual carrier term. If, for example, we want to compute yn(r)yn(r), we can do it by selecting the right DFT output bin (n in this case) and multiplying it by the residual carrier term, if any. Thus for all practical purposes, the bank of tuners viewpoint and the DFT-based filter bank viewpoint yield the same structure and same results.

### The Effect of Bin Decimation on an FFT

More insight into the relationship between the DFT-based filter bank and the basic FDM-to-TDM transmultiplexer shown in Figure 5 can be gained by considering the common situation where an FFT is used to compute the DFT. In the preceding section, it was shown that the DFT filter implicitly uses a QN-point DFT but in fact only N output bins are computed. Consider now the FFT flow graph shown in Figure 10(a). The input is QNQN (8, in this case) weighted input samples x¯(p)x¯(p) and the output is QNQN bins. Suppose now that all we want is the odd numbered output bins. Careful examination of the flow graph shows that more than just the output points can be deleted. Look at x(0)x(0), for example. It is computed using numbers from the previous stage which are only used to compute undesired outputs. Thus these intermediate terms need not be computed either. This process can continue until the point where the intermediate points are needed. To see how this works, examine Figure 10(b). Removing all unneeded nodes reveals something very interesting. The FFT processing naturally breaks into two sections. The second section, the QN-point FFT pruned of all unneeded nodes, is recognized to have the flow graph of an N-point FFT. In fact, if the bin decimation is not offset from bin 0, then the twiddle factors are exactly those of an N-point FFT as well. The section preceding the N-point FFT can be written as N Q-point sums of weighted, delayed input data samples. These sums can be recognized as the {v(r,p)}{v(r,p)}. Thus by pruning out the unneeded nodes in a QN-point FFT taken over the weighted input data, the computation of the filter bank gracefully separates into the cascade of a preprocessor that computes the {v(r,p)}{v(r,p)} and an N-point FFT. The resulting block diagram is exactly the same as that shown in Figure 5.

### Relationship of the Filter Bank Approach to Digital Spectrum Analysis

A matter of confusion to many engineers is that the filter bank scheme seems to produce time samples from FFT bins. This confusion has its root in the fact that the DFT, and hence the FFT, are usually discussed in the context of digital spectrum analysis and are typically spoken of as methods of converting from the time domain to the frequency domain. How then can a DFT-based filter bank produce time samples from spectral bins? In fact, the right perspective is the opposite one.

Consider again Figure 6 from the viewpoint of digital spectrum analysis. A simple FFT-based spectrum analyzer accepts N samples of the input sequence, weights or windows the data, transforms it by using an N-point FFT, and then estimates the power spectral density by computing the magnitude square of the bin outputs. Comparing these steps to Figure 6, we see that they are identical except for two things: (1) the magnitude squaring operation at the bin outputs and (2) the fact that in spectrum analysis the window and transform operation is rarely done for every input sample. (Typically it is done every N-th sample [called 1:1 overlapping] or even less frequently.) These facts suggest that DFT/FFT-based digital spectrum analysis is derived from the filter bank concept rather than the other way around. The filter bank shown in Figure 6 uses a transform computed over a record of weighted, delayed input data to split the input signal's energy into N spectral bands. The degree to which this separation is completed depends on the choice of windowing or weighting function and on the length of the transform. If the function is chosen properly, the windowing operation and the DFT/FFT computation can be computed less frequently, that is, decimation can be introduced. In this context, the simple FFT-based spectrum analyzer can be recognized to perform an instantaneous power measurement at the output of each of the filters in the bank. The quality of the analyzer depends on the window function chosen and the DFT/FFT order N (as they affect the passband shape), the rate at which the filter outputs are computed (given by the decimation factor M), and the number of instantaneous power measurements averaged to obtain the spectral estimate. Thus we can conclude that the digital spectrum analyzer approximates the true power spectrum by measuring the power seen in each of the bandpass filter outputs produced by the DFT-based filter bank.

An interesting sidelight is that the most common name for the transmultiplexer preprocessor stems from the filter bank's relationship with digital spectrum analysis. Look again at Figure 10. The input to the QN-point FFT is QNQN weighted and delayed input samples. From the bank-of-tuners viewpoint we know that the weighting function w(k)w(k) is just the tuner pulse response h(k)h(k) needed to bandlimit the tuned signal properly. In the context of spectrum analysis, however, this function is called a data window. They are in fact identical and the tuner viewpoint provides the analytical basis on which to design the needed window. We've already observed that after pruning the FFT, the QN-point transform separates into two sections. The first section folds together Q windowed samples at a time to generate the N-point input to the FFT. From this viewpoint, it is commonly referred to as the window-and-fold section of the FDM-to-TDM transmultiplexer.

## Stylized FORTRAN Implementation of a Basic FDM-TDM Transmux

Table 1 shows a stylized example of a software implementation of an FDM-TDM transmultiplexer. Some details of the initialization steps have been blurred for the sake of simplicity and the parameters user are certainly not those appropriate to all applications, but the code should serve as an accurate guide to the amount of computation needed and its organization.

 SUBROUTINE TMUX(INPUT_ARRAY, INPUT_POINTER, OUTPUT_VECTOR) C C SUBROUTINE TMUX - IMPLEMENTS A BASIC FDM-TO-TDM TRANSMUX. C A NEW VECTOR OF CHANNELIZED CHANNEL OUTPUTS, CALLED C "OUTPUT_VECTOR" IS PRODUCED EACH TIME THE SUBROUTINE IS CALLED, C UNLESS THE DATA IN "INPUT_ARRAY" IS EXPENDED. C PARAMETER N = 64 !NUMBER OF CHANNELS AND/OR BINS PARAMETER Q = 3 !WEIGHTING FUNCTION EXPANSION FACTOR PARAMETER M = N !DECIMATION FACTOR C THIS CHOICE OF M YIELDS BASIC TRANSMUX C INTEGER M, N, Q, INPUT_POINTER, J, K, INDEX COMPLEX INPUT_ARRAY(1), OUTPUT_VECTORS(N), VRP(N) REAL WEIGHTING(N*Q) C DATA WEIGHTING/ * QN values of the weighting function h(k) */ C C ****************** MOVE TIME POINTER ************************** C INPUT_POINTER = INPUT_POINTER + M C C ****************** COMPUTE v(r,p) ***************************** C DO 10 J=1,N 10 VRP(J) = CMPLX(0.,0.) !ZERO THE VECTOR VRP C DO 30 J=1,N DO 20 K=1 Q INDEX = (K-1)*N+J-1 !COMPUTE OFFSET IN DATA AND WEIGHTING VRP(J) = VRP(J) + INPUT_ARRAY(INPUT_POINTER -INDEX) * 1 WEIGHTING(INDEX+1) 20 CONTINUE 30 CONTINUE C C ****************** COMPUTE VECTOR OF OUTPUTS ****************** C ****************** USING INVERSE FFT ROUTINE ****************** C CALL IFFT(VRP,OUTPUT_VECTOR,N) C C ****************** REMOVE RESIDUAL CARRIER TERM *************** C C ------------ IF M NOT EQUAL TO N, REMOVE CARRIER HERE C C ********************* NORMAL RETURN *************************** C RETURN C END 

## Footnotes

1. Even though real-valued inputs are assumed here, all of the ensuing analysis applies to complex-valued signals as well.
2. Because of the K=1K=1 assumption, this equation is the simplest of all those seen to this point and will be referred to as the basic equation. Many applications require M to be chosen differently however (see Section 4 for example) and in these cases equation 12 should be used.
3. 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).
4. Whether or not it is implemented with an FFT is irrelevant at this point. Also, we happen to use the inverse DFT to produce a result consistent with that found in the proceeding subsction, but the forward DFT could also be used.

## References

1. M.G. Bellanger, et. al. (1976, April). Digital filtering by Polyphase Network: Application to Sample Rate Alteration and Filter Banks. IEEE Trans. on Acoustics, Speech, and Signal Processing, (2), 109-114.

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks