# Digital Signal Processing Tricks – Frequency Translation without multiplication

Frequency translation is often called for in digital signal processingalgorithms. There are simple schemes for inducing frequency translationby 1/2 and 1/4 of the signal sequence sample rate. Let's take a look atthese mixing schemes.

Frequency Translation by f_{s} /2

First we'll consider a technique for frequency translating an inputsequence by fs/2 by merely multiplying a sequence by (-1)^{n} =1,-1,1, -1, …, etc., where f_{s} is the signal sample rate in Hz. This process may seem a bit mysteriousat first, but it can be explained in a straightforward way if we reviewFigure 13-1(a) below.

There we see that multiplying a time domain signal sequence by the(-1)^{n} mixing sequence is equivalent to multiplying the signal sequenceby a sampled cosinusoid where the mixing sequence samples are shown asthe dots in Figure 13-1(a) below.

Because the mixing sequence's cosine repeats every two samplevalues, its frequency is f _{s} /2. Figure 13 -1(b) and (c) showthediscrete Fourier transform (DFT) magnitude and phase of a 32-sample (-1)^{n} sequence. As such, the right half of those figures represents thenegative frequency range.

Figure13-1. Mixing sequence comprising (-1)n = 1,-1,1,-1, etc: (a)time-domain sequence; (b) frequency-domain magnitudes for 32 samples;(c) frequency-domain phase. |

Let's demonstrate this (-1)^{n} mixing by an example.Consider a real x(n) signal sequence having 32 samples of the sum ofthree sinusoids whose [X(m)] frequency magnitude and Phi (m) phasespectra are as shown in Figure 13-2(a)and (b) below .

If we multiply that time signal sequence by (“1)^{n} , theresulting x_{1} ,_{ – 1} (n) time sequence will have themagnitude and phase spectra are that shown in Figure 13-2(c) and (d).Multiplying a time signal by our (-1)^{n} , cosine shifts halfits spectral energy up by f _{s} /2 and half its spectral energydown by – f_{s} /2.

Notice in these non-circular frequency depictions that as we countup, or down, in frequency we wrap around the end points.

Here's a terrific opportunity for the DSP novice to convolve the (-1)^{n} spectrum in Figure 13-1 with the X(m) spectrum to obtain the frequencytranslated X_{1,- 1} (m) signal spectrum. Please do so; thatexercise will help you comprehend the nature of discrete sequences andtheir time and frequency domain relationships by way of the convolutiontheorem.

Figure13-2 A signal and its frequency translation by fs/2: (a) originalsignal magnitude spectrum; (b) original phase; (c) the magnitudespectrum of the translated signal; (d) translated phase. |

Remember now, we didn't really perform any explicit multiplications- the whole idea here is to avoid multiplications, we merely changedthe sign of alternating x(n) samples to get x1, -1(n).

One way to look at the X_{1,”1} (m) magnitudes in Figure13 – 2(c) is to see that multiplication by the (-1)^{n} mixingsequence flips the positive frequency band of X(m) [X(0) to X(16)]about the f_{s} /4 Hzpoint, and flips the negative frequency band of X(m) [X(17) to X(31)]about the – f_{s} /4Hzsample.

This process can be used to invert the spectra of real signals whenbandpass sampling is used. By the way, in the DSP literature be awarethat some clever authors may represent the (“1)n sequence with itsequivalent expressions of

Frequency Translation by – f_{s} /4

Two other simple mixing sequences form the real and imaginary parts ofa complex – f_{s} /4oscillator used for frequency down-conversion to obtain a quadratureversion (complex and centered at 0 Hz of a real bandpass signaloriginally centered at f_{s} /4.

The real (in-phase) mixing sequence is cos[(pi x n)/2] = 1,0, -1,0,etc. shown in Figure 13-3(a) below .That mixing sequence's quadrature companion is “sin[(pi x n)/2] =0,- 1,0,1, etc. as shown in Figure 13-3(b). The spectral magnitudes ofthose two sequence are identical as shown in Figure 13 -3(c), but theirphase spectrum has a 90 degree shift relationship (what we call quadrature ).

Figure13″3 Quadrature mixing sequences for downconversion by fs/4: (a)inphase mixing sequence; (b) quadrature phase mixing sequence; (c) thefrequency magnitudes of both sequences for N = 32 samples; (d) thephase of the cosine sequence; (e) phase of the sine sequence. |

If we multiply the x(n) sequence whose spectrum is that in Figure13-2(a) and (b) by the in-phase (cosine) mixing sequence, the productwill have the I(m) spectrum shown in Figures13-4(a) and (b), below .

Again, X(m)'s spectral energy is translated up and down infrequency, only this time the translation is by ±f_{s} /4. Multiplying x(n)by the quadrature phase (sine) sequence yields the Q(m) spectrum inFigure 13-4(a) and (c).

Because their time sample values are merely 1, -1, and 0, thequadrature mixing sequences are useful because downconversion by f_{s} /4 can be implementedwithout multiplication.

Figure13″4. Spectra after translation down by fs/4: (a) I(m) and Q(m)spectral magnitudes; (b) phase of I(m); (c) phase of Q(m). |

That's why these mixing sequences are of so much interest:downconversion of an input time sequence is accomplished merely withdata assignment, or signal routing. To downconvert a general x(n) = x_{real} (n)+ jx_{imag} (n) sequence by f_{s} /4,the value assignments are:

13-2

If your implementation is hardwired gates, the above dataassignments are performed by means of routing signals (and theirnegatives). Although we've focused on downconversion so far, it's worthmentioning that upconversion of a general x(n) sequence by f_{s} /4 can be performedwith the following data assignments:

13-3 Filtering and Decimation after f_{s} /4Down-Conversion

There's an efficient way to perform the complex down-conversion andfiltering of a real signal by f_{s} /4process quadrature sampling schemes. We can use a novel technique togreatly reduce the computational workload of the linear-phase lowpassfilters[1-3]. In addition, decimation of the complex down-convertedsequence by a factor of two is inherent, with no effort on our part, inthis process.

Figure13″5 Down-conversion by fs/4 and filtering: (a) the process; (b) thedata in the in-phase filter; (c) data within the quadrature phasefilter. |

Considering Figure 13-5(a) above ,notice that if an original x(n) sequence was real-only, and itsspectrum is centered at fs/4, multiplying x(n) by cos[(pi x n)/2] =1,0,-1,0, for the in-phase path and -sin[(pi x n)/2] = 0,-1,0,1, forthe quadrature phase path to down-convert x(n)'s spectrum to 0 Hz,yields the new complex sequence x_{new} (n) = x_{i} (n) +x_{q} (n), or

13-4

Next, we want to lowpass filter (LPF) both the x _{i} (n) and x _{q} (n) sequences followed bydecimation by a factor of two.

Here's the trick. Let's say we're using five-tap FIR filters and atthe n = 4 time index; the data residing in the two lowpass filterswould be that shown in Figure 13 -5(b) and (c).

Due to the alternating zero-valued samples in the x _{i} (n) and x _{q} (n) sequences, we see that onlyfive non-zero multiplies are being performed at this time instant.Those computations, at time index n = 4, are shown in the third row ofthe rightmost column in Table 13-1below.

Table13″1 Filter Data and Necessary Computations after Decimation by Two |

Because we're decimating by two, we ignore the time index n = 5computations. The necessary computations during the next time index (n= 6) are given in the fourth row of Table 13-1, where again only fivenon-zero multiplies are computed.

A review of Table 13-1 tells us we can multiplex the real-valued x(n) sequence, multiply themultiplexed sequences by the repeating mixing sequence 1,-1, …, etc.,and apply the resulting x _{i} (n) and x _{q} (n) sequences to two filters, as shown in Figure 13-6(a) below . Those twofilters have decimated coefficients in the sense that theircoefficients are the alternating h(k) coefficients from the original lowpass filter in Figure 13-5.

Figure13″6 Efficient down-conversion, filtering and decimation: (a) processblock diagram; (b) the modified filters and data at time n = 4; (c)process when a half-band filter is used. |

The two new filters are depicted in Figure13-6(b) above , showing thenecessary computations at time index n = 4. Using this new process,we've reduced our multiplication workload by a factor of two. Theoriginal data multiplexing in Figure 13-6(a) is what implemented ourdesired decimation by two.

Here's another feature of this efficient down-conversion structure.If half-band filters are used in Figure 13-5(a), then only one of thecoefficients in the modified quadrature lowpass filter is non-zero.

This means we can implement the quadrature-path filtering as K unitdelays, a single multiply by the original half-band filter's centercoefficient, followed by another K delay as depicted in Figure 13-6(c).

For an original N-tap half-band filter, K is the integer part ofN/4. If the original half-band filter's h(N-1)/2 center coefficient is0.5, as is often the case, we can implement its multiply by anarithmetic right shift of the delayed x_{q} (n).

This down-conversion process is indeed slick. Here's anotherattribute. If the original lowpass filter in Figure 13-5(a) has an oddnumber of taps, the coefficients of the modified filters in Figure13-6(b) will be symmetrical and we can use the folded FIR filter scheme to reducethe number of multipliers (at the expense of additional adders) byalmost another factor of two!

Finally, if we need to invert the output x _{c} (n') spectrum, there are two waysto do so. We can negate the 1,-1, sequence driving the mixer in thequadrature path, or we can swap the order of the single unit delay andthe mixer in the quadrature path.

Usedwith the permission of the publisher, Prentice Hall, this on-goingseries of articles is based on copyrighted material from “UnderstandingDigital Signal Processing, Second Edition” by Richard G. Lyons. Thebook can be purchased on line.

Richard Lyons is a consultingsystems engineer and lecturer with Besser Associates. As alecturer with Besser and an instructor for the University of CaliforniaSanta Cruz Extension, Lyons has delivered digitasl signal processingseminars and training course at technical conferences as well atcompanies such as Motorola, Freescale, Lockheed Martin, TexasInstruments, Conexant, Northrop Grumman, Lucent, Nokia, Qualcomm,Honeywell, National Semiconductor, General Dynamics and Infinion.