Efficient schemes to multiplex and demultiplex large numbers of signals form the core of many DSP applications. The two most common multiplexing schemes are time-division and frequency-division multiplexing (TDM and FDM, respectively). Devices that convert from one scheme to another are called transmultiplexers. Two very useful DSP tools for TDM, FDM and transmultiplexing applications are polyphase filters and window-presum FFTs (see references). Both are efficient techniques for performing multirate DSP and for generating filter banks used in multiplexing applications. This article elaborates on those concepts by presenting a detailed design that employs polyphase filters to demultiplex an FDM signal. The FDM signal it describes is used in telephony systems worldwide, and with the details provided you're just a few steps away from a real-world implementation.

The FDM signal

Begin by considering an FDM signal composed of K = 18 separate analog voice signals, each with bandwidth B = 4 kHz. Each voice signal is single-sideband modulated (SSB) and frequency-shifted to one of 18 different frequencies, or channels, spaced 4 kHz apart. Fig 1 shows a representation of the FDM spectrum. For generality, the figure leaves the number of channels (K) unspecified, whereas the index k identifies individual channels.

Fig 1 -- The input signal x(n) consists of K single-sideband telephone channels packed in a frequency-division multiplex (FDM) structure.

The figure depicts the SSB signals as having triangular spectra, with upper sidebands shown on the positive frequency axis. Because the signals are real, the spectra exhibit even symmetry, and each channel at positive frequency has a reflection (the lower sideband) at negative frequency. Only the sidebands at ±f₀ directly abut one another. The entire FDM spectrum spans a bandwidth of KB = 72 kHz and should be digitized at the Nyquist rate of f_s = 2KB = 144 kHz.

In actual telephony systems, the 72-kHz FDM signal just described carries only 12 SSB voice signals, not 18, and it is known as a "Group." The other six channels (k = 0, 1, 2, 15, 16, and 17) are vacant. The reasons for this setup are historical, but the channelization remains the same as in Fig 1.

Fig 2 -- Channel filters can extract the SSB voice channels in Fig 1. Beginning with a prototype filter (a), you construct a bank of passband filters by translating the prototype's center frequency to each of the K channel frequencies (b through e).

One way to extract the voice signals from the composite FDM signal is to use individual channel filters (Fig 2). You derive each individual filter (Fig 2b-e) from a prototype (Fig 2a) by frequency shifting it to one of the channel-center frequencies, f_k = (2k+1)B/2, where 0 ≤ k < K. You accomplish the frequency shift by multiplying the prototype filter's impulse response, h(n), with a cosine, W_k (n):

where the sampling times are t_n = (2n+1)T_s /2 = (2n+1)/2f_s = (2n+1)/ (4KB), and where n ∈ {0, ±1, ±2, ...}. Notice that the sampling times are offset from zero by a half sample period, T_s/2. This offset is important for the symmetry relations (Eq 5 below). The impulse response of the kth filter, F_k (n), is then simply

The collection of these filters is a filter bank.

Fig 3 -- An inefficient but conceptually simple method to extract the K channel signals is to filter the FDM signal of Fig 1, x(n), by the K individual channel filters in Fig 2, and then decimate the output of each filter by a factor of K.

Fig 3 shows the "direct method" of applying a filter bank to extract all K channel signals. Consider the kth filter, F_k . It operates on the input signal and outputs the kth SSB voice signal, z_k (n). Because the channel bandwidth is only B = 4 kHz, the output z_k (n) is highly oversampled. There's no need to retain the excess samples, so decimate each filter output by a factor of K = 18 and reduce the sample rate from f_s = 2KB = 144 kHz to 2B = 8 kHz.

Even with decimation this approach isn't practical. It makes little sense to operate a filter at its full sample rate only to throw out 17 of every 18 output samples. A better method is to shift the input signal by K = 18 samples and operate the filters at the decimated rate. This approach is much better, but the filter bank still requires a large number of operations/sec to generate the K channel signals. Assuming that h(n) is an FIR filter with length L, the number of operations/sec is

Before showing how to reduce this computational load even further, it's worthwhile clarifying a few subtle points. Given the bandpass filters of Fig 2 and operation as in Fig 3, you might think that an additional step is needed to downconvert the SSB channels from the channel frequency, f_k, to baseband. As shown in Fig 4, however, decimation of the filtered signals causes aliasing that reflects them down to baseband (that is, to Channel 0) in an almost perfect manner. This result is no accident; rather it's due to judicious placement of the channels.

Fig 4 -- In the operation of the kth channel filter of Fig 3, (a) indicates the kth voice channel (solid gray), while b shows the kth passband filter that isolates and extracts that channel. The result after filtering and decimating appears in (c) and (d), depending upon the even or odd value of k.

To see how this effect works out, consider what it takes to extract the kth channel. Fig 4a shows all K channels (hatched pattern) and highlights the kth channel in solid gray. The kth passband filter (Fig 4b) extracts that channel. Decimation of the filtered output causes a reduction in the sample rate down to 2B = 8 kHz. As with all digital signals, the resulting spectrum repeats at intervals of the sample rate. For even-numbered channels, the repeated (aliased) spectrum aligns correctly at baseband (Channel 0), and the resulting digital signal is the desired baseband voice (Fig 4c). Note that all the reflections in Fig 4c are reflections of the desired signal. This representation differs from Fig 4a, where each speckled spectrum represents a different signal. (For emphasis, the baseband reflection in Figs 4c and 4d is highlighted in light gray.)

The situation is somewhat different for odd-numbered channels. Fig 4d shows that their spectra reflect into the baseband position in an inverted manner. To revert them into an "upright" position, you must shift their spectra by B = 4 kHz. Do this by multiplying the odd channel signals with a B = 4 kHz sinusoid:

where t' is the decimated and shifted n sample time n/2B. In other words, perform the spectral inversion simply by negating every other output sample from the odd channels.

Build a polyphase filter

The discussion so far describes the general use of filter banks for FDM signals. Close examination of Fig 3 reveals that you can achieve great efficiencies by turning to a polyphase implementation. The efficiencies are a direct result of symmetries that exist in the weighting functions W_k (n), which you apply to the prototype filter h(n).

Fig 5--All the sinusoidal weighting functions, W_k (n), are harmonics of W₀ (n). Consequently, they all repeat every 4K samples, and their second 2K samples are equal to the negative of the first 2K samples.

To understand these efficiencies, start by examining the weighting functions W0(n) and W1(n) used in the first two channels (Fig 5). Note that the first 2K points of both waveforms are the same as the second 2K points except the sign is reversed. This alternation continues indefinitely beyond the 4K points shown. Also note that the first 2K points of both waveforms are antisymmetric about their Kth point. You can see these symmetries by closely examining Eq 1, and you can write them as:

Now consider what this symmetry means when constructing the kth filter of Fig 3. From Eq 2, you group together every 2Kth coefficient of h(n) into a subfilter. The first subfilter, H₀ , gets coefficients {h(0), -h(2K), h(4K), -h(6K),...}; the second subfilter, H₁ , gets coefficients {h(1), -h(2K+1), h(4K+1), -h(6K+1),...} and so on. As shown in Fig 6, the result is 2K different subfilters, and assuming that h(n) has L = 2MK coefficients, each subfilter has length M. Recall from Fig 5 and Eq 5a that every 2Kth coefficient of h(n) is multiplied by the same weight value but that the sign of the weight changes. Thus every other coefficient from h(n) alternates sign in the subfilters (Fig 6).

Fig 6 -- Exploit the symmetries in Fig 5 by dividing the prototype filter with length L = 2MK into 2K smaller subfilters, each of length M. Denote the subfilters by H ₀ , H ₁ , ..., H _2K-1 .

For purposes of comparison, let's use the subfilters of Fig 6 to recalculate the kth channel of Fig 3, whose output is z_k (n) just as before. Fig 7 shows the polyphase filter version of this calculation. The polyphase approach derives its name from the fact that it distributes different samples of the input signal x(n) to the 2K subfilters. Every subfilter (or subchannel) gets a decimated stream of samples, with the samples spaced by 2K. This operation of dividing an input stream into subchannels is often called commutation, and the system that performs this work is a commutator.

Fig 7--Calculate the kth channel by using the 2K subfilters (described in Fig 6), pairwise combining their outputs to exploit the symmetries in Fig 5 and scaling by the kth sinusoidal weighting function W_k (s). The single-channel output z_k (m) is the same filtered and decimated signal as calculated by the method of Figs 3 and 4. However, the intermediate signals y_k (m) are common to each of the K channel calculations, so you need apply only additional weighting functions to compute the entire set of K channel outputs.

After obtaining the output of each subfilter, you scale it by the appropriate weight, W_k (s), where k is the voice-channel number and s ∈ {0,1,...,2K-1} is the subfilter number. Remember, here you're combining all the subfilters (filter phases) to calculate one voice-channel output; the subfilters aren't processing different voice channels as was the case in Fig 3. Notice that Fig 7 takes the subfilter outputs and sums them, pairwise, with symmetry around subfilter number K. This operation is possible due to the symmetry described in Fig 5 and expressed in Eq 5b: two of the subfilters use the same value of W _k (s) but with alternate signs. Hence you subtract their outputs before the scaling operation.

A crucial point to notice from Fig 7 is that the intermediate signals y_k (m) are all the same, regardless of the value of the channel number, k. Thus you can reuse them for each of the other K-1 channels by simply changing the weights shown in the dotted box. (This phenomenon is fairly amazing!) You can express the weighting operation in vector notation as

where superscript T indicates vector transpose. Because there are K sets of weights, you can express them as a K x K square matrix

You calculate the K channels as shown in Fig 8, or in vector notation as:

It's worth emphasizing that y_k (m) and z_k (m) are scalars with values at the decimated sample time m, whereas Y(m) and Z(m) are row vectors, and W is a constant matrix. The values calculated here are identical to those in Fig 3, and just as before, the odd channels require spectral inversion to be made upright.

The z_k (m) outputs are the individual voice signals, digitally sampled at an 8-kHz rate. If you run the samples from one of these channels through a D/A converter, amplifier and speaker, you'll hear the original voice. On the other hand, if the final conversion to voice isn't done locally, you can exploit the availability of the digital samples by multiplexing them into an appropriate TDM format. In doing so, you accomplish a transmultiplexing of the original signal from FDM to TDM, and route the data to its final destination.

Because the weights in the matrix W are all harmonically related cosines, you can perform the matrix multiplication more efficiently by replacing it with a discrete cosine transform (DCT). The matrix multiply requires K² operations, whereas you can perform an efficient DCT in roughly Klog(K) operations. Thus the number of operations/sec (multiplications) for a polyphase filter implementation is

Prototype channel filter

To see what this efficiency means for the FDM application, complete the polyphase design by specifying a prototype filter capable of extracting the SSB voice channels (Fig 2a). Fig 9 shows a template with the specs and indicates that a Kaiser-Bessel filter of length L = 792 = M(2K) = (22)(36) does the job. Because L is a multiple of 2K, the subfilters (Fig 6 and 7) each have a length of only M = 22.

Fig 9 -- The prototype filter for this FDM application must meet the specs (dotted lines) described by this template. For polyphase implementation, the filter length should be a multiple of 2K (= 36 in this case). A Kaiser-Bessel filter with b = 5.1, length 792 = (22)(36) and cutoff frequency of 3925 Hz does the job (dashed curve).

For the polyphase approach, N _ops/sec = (2M + Log₂(K))f _s = (44+5)f_s = 49f_s. In contrast, the method of Fig 3 requires 792f_s computations (Eq 3), indicating that the polyphase approach is more than 15x more efficient! The actual value is 792/49 ≈ 16.2. And even though it appears that a polyphase design is much more difficult to understand than the direct approach of Fig 3, Fig 10 shows that the implementation actually involves five stages, each of which is quite easy to grasp.

Fig 10 -- Five relatively simple steps summarize the operations for this polyphase filter-bank implementation. The input x(n) is a wideband FDM signal, and the output Z(m) is a set of K narrowband baseband voice signals.

As stated in the references, polyphase filters can be extremely beneficial for some hardware implementations. An alternate approach using the window-presum FFT (Ref 4) has virtually identical efficiency and might be better suited for a given hardware design. An additional option, to be explored in a future article, is the use of wavelets in filter-bank designs.

Acknowledgment

The author would like to acknowledge his deep indebtedness to Constantine Gumacos for his insight into this topic and other tutelage over many years.

References

1. Sullivan, M, "Simple manipulations make boxcar filters suited for high decimation/interpolation rates," Personal Engineering & Instrumentation News, April 1996, pgs 57-58. 

2. Sullivan, M, "Multirate DSP improves algorithm efficiency," Personal Engineering & Instrumentation News, December 1996, pgs 60-62.

3. Gumas, C, "Window choices become crucial in high-dynamic-range FFT processing," Personal Engineering & Instrumentation News, May 1997, pgs 53-59.

4. Gumas, C, "Window-presum FFT achieves high dynamic range, resolution," Personal Engineering & Instrumentation News, July 1997, pgs 58-65.

Charles (Chuck) Gumas serves as Project Lead/Communications Engineer at the MITRE Corp's Information Systems and Technology Div ( Reston, VA). He received an MSEE from Lehigh Univ and a BS in physics from the Univ of Pennsylvania. He maintains a web site at www.dc.net/spartan/chuck.html and can be contacted via email at cgumas@mitre.org.

This article originally appeared in Personal Engineering & Instrumentation News , September 1997, pgs 47-52. Reprinted with permission of PEC Inc; all rights reserved.

		Click here to get your listing up.