Real-Time Digital Signal Processing Sen M Kuo, Bob H Lee Copyright # 2001 John Wiley & Sons Ltd ISBNs: 0-470-84137-0 (Hardback); 0-470-84534-1 (Electronic) Practical DSP Applications in Communications There are many DSP applications that are used in our daily lives, some of which have been introduced in previous chapters DSP algorithms, such as random number generation, tone generation and detection, echo cancellation, channel equalization, noise reduction, speech and image coding, and many others can be found in a variety of communication systems In this chapter, we will introduce some selected DSP applications in communications that played an important role in the realization of the systems 9.1 Sinewave Generators and Applications When designing algorithms for a sinewave (sine or cosine function) generation, several characteristics should be considered These issues include total harmonic distortion, frequency and phase control, memory usage, execution time, and accuracy The total harmonic distortion (THD) determines the purity of a sinewave and is defined as THD ˆ spurious harmonic power , total waveform power …9:1:1† where the spurious harmonic power relates to the unwanted harmonic components of the waveform For example, a sinewave generator with a THD of 0.1 percent has a distortion power level approximately 30 dB below the fundamental component This is the most important characteristic from the standpoint of performance The other characteristics are closely related to details of the implementation Polynomials can be used to express or approximate some trigonometric functions However, the sine or cosine function cannot be expressed as a finite number of additions and multiplications We must depend on approximation Because polynomial approximations can be computed with multiplications and additions, they are ready to be implemented on DSP devices For example, the sine function can be approximated by (3.8.1) The implementation of a sinewave generation using polynomial approximation is given in Section 3.8.5 As discussed in Chapter 6, another approach of generating sinusoidal signals is to design a filter H(z) whose impulse response h(n) is the desired sinusoidal waveform With an impulse function d…n† used as input, the IIR filter will 400 PRACTICAL DSP APPLICATIONS IN COMMUNICATIONS generate the desired impulse response (sinewave) at the output In this section, we will discuss the lookup-table method for generating sinewaves 9.1.1 Lookup-Table Method The lookup-table method or wavetable generator is probably the most flexible and conceptually simple method for generating sinusoidal waveforms The technique simply involves the readout of a series of stored data values representing discrete samples of the waveform to be generated The data values can be obtained either by sampling the appropriate analog waveform, or more commonly, by computing the desired values using MATLAB or C programs Enough samples are generated and stored to accurately represent one complete period of the waveform The periodic signal is then generated by repeatedly cycling through the data memory locations using a circular pointer This technique is also used for generating computer music A sinewave table contains equally spaced sample values over one period of the waveform An N-point sinewave table can be computed by evaluating the function x…n† ˆ sin   2pn , N n ˆ 0, 1, , N 1: …9:1:2† These sample values must be represented in binary form The accuracy of the sine function is determined by the wordlength used to represent data and the table length The desired sinewave is generated by reading the stored values in the table at a constant (sampling) rate of step D, wrapping around at the end of the table whenever the pointer exceeds N The frequency of the generated sinewave depends on the sampling period T, table length N, and the sinewave table address increment D: f ˆ D Hz: NT …9:1:3† For the designed sinewave table of length N, a sinewave of frequency f with sampling rate fs can be generated by using the pointer address increment Dˆ Nf , fs D N : To generate L samples of sinewave x…l†, l ˆ 0, 1, , L such that k ˆ …m ‡ lD†mod N , …9:1:4† 1, we use a circular pointer k …9:1:5† where m determines the initial phase of sinewave It is important to note that the step D given in (9.1.4) may be a non-integer, thus (m ‡ lD) in (9.1.5) is a real number That is, a number consisting of an integer and a fractional part When fractional values of D are used, samples of points between table entries must be estimated using the table values SINEWAVE GENERATORS AND APPLICATIONS 401 The easy solution is to round this non-integer index to the nearest integer However, the better but more complex solution is to interpolate the two adjacent samples The lookup-table method is subject to the constraints imposed by aliasing, requiring at least two samples per period in the generated waveform Two sources of error in the lookup-table algorithm cause harmonic distortion: An amplitude quantization error is introduced by representing the sinewave table values with finite-precision numbers Time-quantization errors are introduced when points between table entries are sampled, which increase with the address increment D The longer the table is, the less significant the second error will be To reduce the memory requirement for generating a high accuracy sinewave, we can take advantage of waveform symmetry, which in effect results in a duplication of stored values For example, the values are repeated (regardless of sign change) four times every period Thus only a quarter of the memory is needed to represent the waveform However, the cost is a greater complexity of algorithm to keep track of which quadrant of the waveform is to be generated and with the correct sign The best compromise will be determined by the available memory and computation power for a given application on the target DSP hardware To decrease the harmonic distortion for a given table size N, an interpolation scheme can be used to more accurately compute the values between table entries Linear interpolation is the simplest method for implementation For linear interpolation, the sine value for a point between successive table entries is assumed to lie on the straight line between the two values Suppose the integer part of the pointer is i …0  i < N† and the fractional part of the pointer is f …0 < f < 1†, the sine value is computed as x…n† ˆ s…i† ‡ f
‰s…i ‡ 1† where ‰s…i ‡ 1† and i ‡ s…i†Š, …9:1:6† s…i†Š is the slope of the line segment between successive table entries i Example 9.1: A cosine/sine function generator using table-lookup method with 1024 points cosine table can be implemented using the TMS320C55x assembly code as follows: ; ; ; ; ; ; ; cos_sin.asm Table lookup sinewave generator with 1024±point cosine table range(0 p) Prototype: void cos_sin(int, int *, int *) Entry: arg0: T0 a (alpha) arg1: AR0 pointer to cosine arg2: AR1 pointer to sine def _cos_sin ref tab_0_PI sect "cos_sin" 402 PRACTICAL DSP APPLICATIONS IN COMMUNICATIONS _cos_sin mov sfts mov jj mov mov abs add and sub abs jj mov mov ret end T0, AC0 AC0, #11 #tab_0_PI, T0 hi(AC0), AR2 AR2, AR3 AR2 #0x200, AR3 #0x7ff, AR3 #0x400, AR3 AR3 *AR2(T0), *AR0 *AR3(T0), *AR1 ; T0 ˆ a ; Size of lookup table ; Table based address ; cos( a)ˆ cos(a) ; 90 degree offset for sine ; Modulo 0x800 for 11±bit ; Offset 180 degree for sine ; sin( a) ˆ sin(a) ; *AR0 ˆ cos(a) ; *AR1 ˆ sin(a) In this example, we use a half table (0 ! p) Obviously, a sine (or cosine) function generator using the complete table (0 ! 2p) can be easily implemented using only a few lines of assembly code, while a function generator using a quarter table (0 ! p=2) will be more challenging to implement efficiently The assembly program cos_sin.asm used in this example is available in the software package 9.1.2 Linear Chirp Signal A linear chirp signal is a waveform whose instantaneous frequency increases linearly with time between two specified frequencies It is a broadband waveform with the lowest possible peak to root-mean-square amplitude ratio in the desired frequency band The digital chirp waveform is expressed as c…n† ˆ A sin‰f…n†Š, …9:1:7† where A is a constant amplitude and f…n† is a quadratic phase of the form     fU fL f…n† ˆ 2p fL n ‡ n2 ‡ a, 2…N 1† 0nN 1, …9:1:8† where N is the total number of points in a single chirp In (9.1.8), a is an arbitrary constant phase factor, fL and fU , are the normalized lower and upper band limits, respectively, which are in the range  f  0:5 The waveform periodically repeats with f…n ‡ kN† ˆ f…n†, k ˆ 1, 2, …9:1:9† The instantaneous normalized frequency is defined as f …n† ˆ fL ‡  fU N  fL n, 0nN 1: …9:1:10† SINEWAVE GENERATORS AND APPLICATIONS 403 This expression shows that the instantaneous frequency goes from f …0† ˆ fL at time n ˆ to f …N 1† ˆ fU at time n ˆ N Because of the complexity of the linear chirp signal generator, it is more convenient for real-time applications to generate such a sequence by a general-purpose computer and store it in a lookup table Then the lookup-table method introduced in Section 9.1.1 can be used to generate the desired signal An interesting application of chirp signal generator is generating sirens The electronic sirens are often created by a small generator system inside the vehicle compartment This generator drives either a 60 or 100 Watt loudspeaker system present in the light bar mounted on the vehicle roof or alternatively inside the vehicle radiator grill The actual siren characteristics (bandwidth and duration) vary slightly from manufacturers The wail type of siren sweeps between 800 Hz and 1700 Hz with a sweep period of approximately 4.92 seconds The yelp siren has similar characteristics to the wail but with a period of 0.32 seconds 9.1.3 DTMF Tone Generator A common application of sinewave generator is the all-digital touch-tone phone that uses a dual-tone multi-frequency (DTMF) transmitter and receiver DTMF also finds widespread use in electronic mail systems and automated telephone servicing systems in which the user can select options from a menu by sending DTMF signals from a telephone Each key-press on the telephone keypad generates the sum of two tones expressed as x…n† ˆ cos…2pfL nT† ‡ cos…2pfH nT†, …9:1:11† where T is the sampling period and the two frequencies fL and fH uniquely define the key that was pressed Figure 9.1 shows the matrix of sinewave frequencies used to encode the 16 DTMF symbols The values of the eight frequencies have been chosen carefully so that they not interfere with speech The low-frequency group (697, 770, 852, and 941 Hz) selects the four rows frequencies of the  keypad, and the high-frequency group (1209, 1336, 1477, and 1633 Hz) 1209 1336 697 Hz A 770 Hz B 852 Hz C 941 Hz * # D Figure 9.1 1477 1633 Hz Matrix telephone keypad 404 PRACTICAL DSP APPLICATIONS IN COMMUNICATIONS selects the columns frequencies A pair of sinusoidal signals with fL from the lowfrequency group and fH from the high-frequency group will represent a particular key For example, the digit `3' is represented by two sinewaves at frequencies 697 Hz and 1477 Hz The row frequencies are in the low-frequency range below kHz, and the column frequencies are in the high-frequency between kHz and kHz The digits are displayed as they appear on a telephone's  matrix keypad, where the fourth column is omitted on standard telephone sets The generation of dual tones can be implemented by using two sinewave generators connected in parallel Each sinewave generator can be realized using the polynomial approximation technique introduced in Section 3.8.5, the recursive oscillator introduced in Section 6.6.4, or the lookup-table method discussed in Section 9.1.1 Usually, DTMF signals are interfaces to the analog world via a CODEC (coder/decoder) chip with an kHz sampling rate The DTMF signal must meet timing requirements for duration and spacing of digit tones Digits are required to be transmitted at a rate of less than 10 per second A minimum spacing of 50 ms between tones is required, and the tones must be present for a minimum of 40 ms A tone-detection scheme used to implement a DTMF receiver must have sufficient time resolution to verify correct digit timing The issues of tone detection will be discussed later in Section 9.3 9.2 Noise Generators and Applications Random numbers are useful in simulating noise and are used in many practical applications Because we are using digital hardware to generate numbers, we cannot produce perfect random numbers However, it is possible to generate a sequence of numbers that are unrelated to each other Such numbers are called pseudo-random numbers (PN sequence) Two basic techniques can be used for pseudo-random number generation The lookup-table method uses a set of stored random samples, and the other is based on random number generation algorithms Both techniques obtain a pseudo-random sequence that repeats itself after a finite period, and therefore is not truly random at all time The number of stored samples determines the length of a sequence generated by the lookup-table method The random number generation algorithm by computation is determined by the register size In this section, two random number generation algorithms will be introduced 9.2.1 Linear Congruential Sequence Generator The linear congruential method is probably the most widely used random number generator It requires a single multiplication, addition, and modulo division Thus it is simple to implement on DSP chips The linear congruential algorithm can be expressed as x…n† ˆ ‰ax…n 1† ‡ bŠmod M , …9:2:1† NOISE GENERATORS AND APPLICATIONS 405 where the modulo operation (mod) returns the remainder after division by M The constants a, b, and M are chosen to produce both a long period and good statistical characteristics of the sequences These constants can be chosen as a ˆ 4K ‡ 1, …9:2:2† where K is an odd number such that a is less than M, and M ˆ 2L …9:2:3† is a power of 2, and b can be any odd number Equations (9.2.2) and (9.2.3) guarantee that the period of the sequence in (9.2.1) is of full-length M A good choice of parameters are M ˆ 220 ˆ 10 48 576, a ˆ 4…511† ‡ ˆ 2045, and x…0† ˆ 12 357 Since a random number routine usually produces samples between and 1, we can normalize the nth random sample as r…n† ˆ x…n† ‡ M‡1 …9:2:4† so that the random samples are greater than and less than Note that the random numbers r(n) can be generated by performing Equations (9.2.1) and (9.2.4) in real time A C function (uran.c in the software package) that implements this random number generator is listed in Table 9.1 Example 9.2: Most of the fixed-point DSP processors are 16-bit The following TMS320C55x assembly code implements an M ˆ 216 …65 536† random number generator Table 9.1 C program for generating linear congruential sequence /************************************************************* * URAN This function generates pseudo-random numbers * *************************************************************/ static long n ˆ (long)12357; // Seed x(0)ˆ 12357 float uran() { float ran; // Random noise r(n) n ˆ (long)2045*n‡1L; // x(n)ˆ 2045*x(n 1)‡1 n ˆ (n/1048576L)*1048576L; // x(n)ˆ x(n) INT [x(n)/ // 1048576]*1048576 ran ˆ (float)(n‡1L)/(float)1048577; // r(n)ˆ FLOAT [x(n)‡1]/ // 1048577 return(ran); // Return r(n) to the main } // function 406 PRACTICAL DSP APPLICATIONS IN COMMUNICATIONS ; ; ; ; ; ; rand16_gen.asm 16±bit zero-mean random number generator Prototype: int rand16_gen(int *) Entry: arg0 AR0 pointer to seed value Return: T0 random number C1 C2 equ 0x6255 equ 0x3619 def _rand16_gen sect "rand_gen" _rand16_gen mov #C1, T0 mpym *AR0, T0, AC0 add #C2, AC0 and #0xffff, AC0 mov AC0, *AR0 sub #0x4000, AC0 mov AC0, T0 ret end ; seed ˆ(C1*seed‡C2) ; seed %ˆ 0x8000 ; Zero-mean random number The assembly program rand16_gen.asm used for this example is available in the software package 9.2.2 Pseudo-Random Binary Sequence Generator A shift register with feedback from specific bits can also generate a repetitive pseudorandom sequence A schematic of the 16-bit generator is shown in Figure 9.2, where the functional circle labeled `XOR' performs the exclusive-OR function of its two binary inputs The sequence itself is determined by the position of the feedback bits on the shift register In Figure 9.2, x1 is the output of b0 XOR with b2 , x2 is the output of b11 XOR with b15 , and x is the output of x1 XOR with x2 An output from the sequence generator is the entire 16-bit word After the random number is generated, every bit in the register is shifted left bit (b15 is lost), and then x is shift to b0 to generate the next random number A shift register length of 16 bits can b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 XOR XOR x2 x1 XOR Figure 9.2 A 16-bit pseudo random number generator x 407 NOISE GENERATORS AND APPLICATIONS readily be accommodated by a single word on the many 16-bit DSP devices Thus memory usage is minimum It is important to recognize, however, that sequential words formed by this process will be correlated The maximum sequence length before repetition is L ˆ 2M 1, …9:2:5† where M is the number of bits of the shift register Example 9.3: The PN sequence generator given in Table 9.2 uses many Boolean operations The C program requires at least 11 operations to complete the computation The following TMS320C55x assembly program computes the same PN sequence in 11 cycles: ; ; ; ; ; ; pn_gen.asm 16-bit zero-mean PN sequence generator Prototype: int pn_gen(int *) Entry: arg0 AR0 pointer to the shift register Return: T0 random number BIT15 BIT11 equ 0x8000 equ 0x0800 ; b15 ; b11 Table 9.2 C program for generating PN sequence /************************************************************* * PN Sequence generator * *************************************************************/ static int shift_reg; int pn_sequence(int *sreg) { int b2, b11, b15; int x1, x2; /* x2 also used for x } b15 ˆ *sreg  15; b11 ˆ *sreg  11; x2 ˆ b15^b11; b2 ˆ *sreg  2; x1 ˆ *sreg ^b2; x2 ˆ x1^x2; x2 &ˆ 1; *sreg ˆ *sreg  1; *sreg ˆ *sreg j x2; x2 ˆ *sreg 0x4000; return x2; */ /* First XOR bit15 and bit11 */ /* Second XOR bit2 and bit0 /* Final XOR of x1 and x2 */ */ /* Update the shift register */ /* Zero-mean random number */ 408 PRACTICAL DSP APPLICATIONS IN COMMUNICATIONS BIT2 BIT0 equ 0x0004 equ 0x0001 def _pn_gen sect "rand_gen" _pn_gen mov *AR0, AC0 bfxtr #(BIT15jBIT2), AC0, T0 bfxtr #(BIT11jBIT0), AC0, T1 sfts AC0, #1 jj xor T0, T1 mov T1, T0 sfts T1, # xor T0, T1 and #1, T1 or T1, AC0 mov AC0, *AR0 sub #0x4000, AC0, T0 jj ret end ; b2 ; b0 ; Get register value ; Get b15 and b2 ; Get b11 and b0 ; XOR all bits ; Final XOR ; Update register ; Zero-mean random number The C program pn_sequence.c and the TMS320C55x assembly program pn_gen.asm for this example are available in the software package 9.2.3 Comfort Noise in Communication Systems In voice-communication systems, the complete suppression of a signal using residual echo suppressor (will be discussed later in Section 9.4) has an adverse subjective effect This problem can be solved by adding a low-level comfort noise, when the signal is suppressed by a center clipper As illustrated in Figure 9.3, the output of residual echo suppressor is expressed as  y…n† ˆ av…n†, x…n†, jx…n†j  ... characteristics of the system are time-invariant, off-line modeling can be used to estimate H(z) during an initial training stage White noise is an ideal broadband training signal in system identification... arg0: T0 a (alpha) arg1: AR0 pointer to cosine arg2: AR1 pointer to sine def _cos_sin ref tab_0_PI sect "cos_sin" 402 PRACTICAL DSP APPLICATIONS IN COMMUNICATIONS _cos_sin mov sfts mov jj mov mov... program cos_sin.asm used in this example is available in the software package 9.1.2 Linear Chirp Signal A linear chirp signal is a waveform whose instantaneous frequency increases linearly with