Dorf, R C, Wan, Z, Millstein, L B, Simon, M.K"Digital Communication The electrical Engineering Handbook Ed. Richard C. Dorf Boca raton crc Press llc. 2000
Dorf, R.C., Wan, Z., Millstein, L.B., Simon, M..K. “Digital Communication” The Electrical Engineering Handbook Ed. Richard C. Dorf Boca Raton: CRC Press LLC, 2000
70 Digital Communication Richard C. Dorf 70.1 Error Control Coding University of California, davis Block codes· Convolutional codes· Code performance· Trellis Zhen wa Coded modulation 70.2 Equalization Linear Transversal Equalizers. Nonlinear Equalizers. Linear L. B. Milstein Receivers Nonlinear receivers University of California 70.3 Spread Spectrum Communications A Brief History. Why Spread Spectrum?. Basic Concepts and M. K. Simon Terminology. Spread Spectrum Techniques. Applications of oread Spectrum 70.1 Error Control Coding Richard C. Dorf and Zhen wan Error correcting codes may be classified into two broad categories: block codes and tree codes. a block code is a mapping of k input binary symbols into n output binary symbols. Consequently, the block coder is a memoryless device. Since n> k, the code can be selected to provide redundancy, such as parity bits, which are used by the decoder to provide some error detection and error correction. The codes are denoted by(n, k), where the code rate R is defined by r=k/n. Practical values of R range from 1/4 to 7/8, and k ranges from 3 to several hundred [Clark and Cain, 1981]. Some properties of block codes are given in Table 70.1 a tree code is produced by a coder that has memory Convolutional codes are a subset of tree codes. The convolutional coder accepts k binary symbols at its input and produces n binary symbols at its output, where he n output symbols are affected by v+ k input symbols. Memory is incorporated since v>0. The code rate is defined by R=k/n. Typical values for k and n range from 1 to 8, and the values for v range from 2 to 60 The range of R is between 1/4 and 7/8[ Clark and Cain, 1981 Block Codes In block code, the n code digits generated in a particular time unit depend only on the k message digits within that time unit. Some of the errors can be detected and corrected if d>s+t+1. where s is the number of errors that can be detected, t is the number of errors that can be corrected, and d is the hamming distance Usually, s2 t thus, d2 2t+ 1. A general code word can be expressed as a1, a2y,, G1, c2., k is the number of information bits and r is the number of check bits. Total word length is n=k+r. In Fig. 70.1, the gain h (i=1,2 j=1,2,, k)are elements of the parity check matrix H. The k data bits are shifted in each time, while k t r bits are simultaneously shifted out by the commutator. yclic Codes Cyclic codes are block codes such that another code word can be obtained by taking any one code word, shifting ne bits to the right, and placing the dropped-off bits on the left An encoding circuit with (n-k)shift registers is shown in Fig. 70.2 c 2000 by CRC Press LLC
© 2000 by CRC Press LLC 70 Digital Communication 70.1 Error Control Coding Block Codes • Convolutional Codes • Code Performance • TrellisCoded Modulation 70.2 Equalization Linear Transversal Equalizers • Nonlinear Equalizers • Linear Receivers • Nonlinear Receivers 70.3 Spread Spectrum Communications A Brief History • Why Spread Spectrum? • Basic Concepts and Terminology • Spread Spectrum Techniques • Applications of Spread Spectrum 70.1 Error Control Coding Richard C. Dorf and Zhen Wan Error correcting codes may be classified into two broad categories: block codes and tree codes. A block code is a mapping of k input binary symbols into n output binary symbols. Consequently, the block coder is a memoryless device. Since n > k, the code can be selected to provide redundancy, such as parity bits, which are used by the decoder to provide some error detection and error correction. The codes are denoted by (n, k), where the code rate R is defined by R = k/n. Practical values of R range from 1/4 to 7/8, and k ranges from 3 to several hundred [Clark and Cain, 1981]. Some properties of block codes are given in Table 70.1. A tree code is produced by a coder that has memory. Convolutional codes are a subset of tree codes. The convolutional coder accepts k binary symbols at its input and produces n binary symbols at its output, where the n output symbols are affected by v + k input symbols. Memory is incorporated since v > 0. The code rate is defined by R = k/n. Typical values for k and n range from 1 to 8, and the values for v range from 2 to 60. The range of R is between 1/4 and 7/8 [Clark and Cain, 1981]. Block Codes In block code, the n code digits generated in a particular time unit depend only on the k message digits within that time unit. Some of the errors can be detected and corrected if d ³ s + t + 1, where s is the number of errors that can be detected, t is the number of errors that can be corrected, and d is the hamming distance. Usually, s ³ t, thus, d ³ 2t + 1. A general code word can be expressed as a1, a2,...,ak, c1, c2,...,cr. k is the number of information bits and r is the number of check bits. Total word length is n = k + r. In Fig. 70.1, the gain hij (i = 1, 2,..., r, j = 1, 2,..., k) are elements of the parity check matrix H. The k data bits are shifted in each time, while k + r bits are simultaneously shifted out by the commutator. Cyclic Codes Cyclic codes are block codes such that another code word can be obtained by taking any one code word, shifting the bits to the right, and placing the dropped-off bits on the left. An encoding circuit with (n – k) shift registers is shown in Fig. 70.2. Richard C. Dorf University of California, Davis Zhen Wan University of California, Davis L. B. Milstein University of California M. K. Simon Jet Propulsion Laboratory
TABLE 70.1 Properties of Block Codes Codea BC Reed-Solomon Hamming Maximal Leng Block length n= m(2m-1)bits n=2-1 n=2 m=3,4,5, Number of parity bits r= 2t bits r=rml Minimum distance d≥2t+1 d= m(2r+ 1)bits d=3 d=2m-1 Number of information bits k2n-mt am is any positive integer unless otherwise indicated; n is the block length; kis the number of information bits; t is the number of errors that can be corrected; r is the number of parity bits; d is the distand Commutator FIGURE 70.1 An encoding circuit of (n, k) block code 11 a→o+l Switch s k Data digits n-kParity-check digits FIGURE 70. 2 An encoder for systematic cyclic code. Source: B P. Lathi, Modern Digital and Analog Communications,New York: CBS College Pul In Fig. 70.2, the gain gs are the coefficients of the generator polynomial g(x)=x*+gx-1+..+gux +1. The gains k are either 0 or 1. The k data digits are shifted in one at a time at the input with the switch s held at position Pi. The symbol D represents a one-digit delay. As the data digits move through the encoder, they are also shifted out onto the output lines, because the first k digits of code word are the data digits themselves. As soon as the last(or kth)data digit clears the last(n-k) register, all the registers contain the parity-check digits. The switch s is now thrown to position P2, and the n-k parity-check are one at a time onto the line e 2000 by CRC Press LLC
© 2000 by CRC Press LLC In Fig. 70.2, the gain gks are the coefficients of the generator polynomial g(x) = xn–k + g1xn–k–1 + . . . + gn–k–1x + 1. The gains gk are either 0 or 1. The k data digits are shifted in one at a time at the input with the switch s held at position p1. The symbol D represents a one-digit delay. As the data digits move through the encoder, they are also shifted out onto the output lines, because the first k digits of code word are the data digits themselves. As soon as the last (or kth) data digit clears the last (n – k) register, all the registers contain the parity-check digits. The switch s is now thrown to position p2, and the n – k parity-check digits are shifted out one at a time onto the line. TABLE 70.1 Properties of Block Codes Codea Property BCH Reed–Solomon Hamming Maximal Length Block length n = 2m – 1, n = m(2m – 1) bits n = 2m – 1 n = 2m – 1 m = 3, 4, 5, . . . Number of parity bits r = m2t bits r = m Minimum distance d ³ 2t + 1 d = m(2t + 1) bits d = 3 d = 2m – 1 Number of information bits k ³ n – mt k = m a m is any positive integer unless otherwise indicated; n is the block length; k is the number of information bits; t is the number of errors that can be corrected; r is the number of parity bits; d is the distance. FIGURE 70.1 An encoding circuit of (n, k) block code. FIGURE 70.2 An encoder for systematic cyclic code. (Source: B.P. Lathi, Modern Digital and Analog Communications, New York: CBS College Publishing, 1983. With permission.)
Constraint length K input frames HH器 Uncoded input data 非·非·。非 n bit frame YYZ Shift register FIGURE 70.3 Convolutional encoding (k=3, n=4, K=5, and R =3/4) Examples of cyclic and related codes are Bose-Chaudhuri-Hocquenhem(BCH) 2. Reed-Solomon 3. Hamming 4. Maximal lengt 5. Reed-Muller 6. Golay codes Convolutional Codes In convolutional code, the block of n code digits generated by the encoder in a particular time unit depends not only on the block of k message digits within that time unit but also on the block of data digits within a previous span of N-1 time units(N>1). A convolutional encoder is illustrated in Fig. 70.3 Here k bits(one input frame)are shifted in each time, and concurrently n bits(the output frame)are shifted out,where n>k. Thus, every k-bit input frame prod uces an 1 bit output frame. Redundancy is provided in the output, since n >k. Also, there is memory in the coder, since the output frame depends on the previous K input frames where K>1. The code rate is r= k/n, which is 3/4 in this illustration. the constraint length K, is the number of input frames that are held in the kk bit shift register. Depending on the particular convolutional code that is to be generated, data from the kK stages of the shift register are added(modulo 2) and used to set the bits in the n-stage output register Code performance The improvement in the performance of a digital communication system that can be achieved by the use of coding is illustrated in Fig. 70.4. It is assumed that a digital signal plus channel noise is present at the receiver input. The performance of a system that uses binary-Phase-shift-keyed(BPSK) signaling is shown both for the case when coding is used and for the case when there is no coding For the BPSK no code case, P=Q(2(EVN) For the coded case a(23, 12)Golay code is used; Pe is the probability of bit error-also called the bit error rate (BER)that is measured at the receiver output. c2000 by CRC Press LLC
© 2000 by CRC Press LLC Examples of cyclic and related codes are 1. Bose–Chaudhuri–Hocquenhem (BCH) 2. Reed–Solomon 3. Hamming 4. Maximal length 5. Reed–Muller 6. Golay codes Convolutional Codes In convolutional code, the block of n code digits generated by the encoder in a particular time unit depends not only on the block of k message digits within that time unit but also on the block of data digits within a previous span of N – 1 time units (N >1). A convolutional encoder is illustrated in Fig. 70.3. Here k bits (one input frame) are shifted in each time, and concurrently n bits (the output frame) are shifted out, where n > k. Thus, every k-bit input frame produces an n-bit output frame. Redundancy is provided in the output, since n > k. Also, there is memory in the coder, since the output frame depends on the previous K input frames where K > 1. The code rate is R = k/n, which is 3/4 in this illustration. The constraint length, K, is the number of input frames that are held in the kK bit shift register. Depending on the particular convolutional code that is to be generated, data from the kK stages of the shift register are added (modulo 2) and used to set the bits in the n-stage output register. Code Performance The improvement in the performance of a digital communication system that can be achieved by the use of coding is illustrated in Fig. 70.4. It is assumed that a digital signal plus channel noise is present at the receiver input. The performance of a system that uses binary-phase-shift-keyed (BPSK) signaling is shown both for the case when coding is used and for the case when there is no coding. For the BPSK no code case, Pe = Q ( ). For the coded case a (23,12) Golay code is used; Pe is the probability of bit error—also called the bit error rate (BER)—that is measured at the receiver output. FIGURE 70.3 Convolutional encoding (k = 3, n = 4, K = 5, and R = 3/4). 2(E N/b o
without coding Shannon s ideal system 14 10 Coding gain= 1.33 dB (23, 12)Golay coding Coding gain =2. 15 dB deal coin gan=11.2 Eb/No(dB) FIGURE 70.4 Performance of digital systems-with and without coding. E, is the energy-per-bit to noise-density at the receiver input. The function Q(x)is Q(x)=(1/v2Txe-snz TABLE 70.2 Coding Gains with BPSK or QPSK oding Gain(dB) Coding Gain(dB) Data Rate oding Technique Used at 10-BER at 10- BER Ideal coding 11.2 3.6 oncatenated Reed-Solomon and convolution iterbi decoding) 6.5-75 volutional with sequential decoding ft decisions 6.0-7.0 809.0 Modera Block codes(soft decisions) 50-6.0 Concatenated Reed-Solomon and short block 4.5-5.5 6.5-7.5 Very high Convolutional with Viterbi decoding 4.0-5.5 Convolutional with sequential decoding rd decisions 4.0-5.0 6.0-7.0 High Block codes(hard decisions) 3.0-4.0 4.5-5.5 Block codes with threshold decoding 2.0-4.0 3.5-5.5 Convolutional with threshold decoding 1.5-3.0 2.5-4.0 Very high BPSK: modulation technique-binary phase-shift keying: QPSK: modulation technique--quadrature phase shift keying: BER: bit error rate. Source: V.K. Bhargava, "Forward error correction schemes for digital communications, IEEE Communicatio Magazine, 21, 11-19,@ 1983 IEEE. with permission. Trellis-Coded Modulation Trellis-coded modulation(TCM) combines multilevel modulation and coding to achieve coding gain without bandwidth expansion [Ungerboeck, 1982, 1987]. TCM has been adopted for use in the new CCITTV32 modem that allows an information data rate of 9600 b/s(bits per second )to be transmitted over VF(voice frequency lines. The TCM has a coding gain of 4 dB [Wei, 1984]. The combined modulation and coding operation of TCM is shown in Fig. 70.5(b). Here, the serial data from the source, m(t), are converted into parallel(m-bit) e 2000 by CRC Press LLC
© 2000 by CRC Press LLC Trellis-Coded Modulation Trellis-coded modulation (TCM) combines multilevel modulation and coding to achieve coding gain without bandwidth expansion [Ungerboeck, 1982, 1987]. TCM has been adopted for use in the new CCITT V.32 modem that allows an information data rate of 9600 b/s (bits per second) to be transmitted over VF (voice frequency) lines. The TCM has a coding gain of 4 dB [Wei, 1984]. The combined modulation and coding operation of TCM is shown in Fig. 70.5(b). Here, the serial data from the source, m(t), are converted into parallel (m-bit) FIGURE 70.4 Performance of digital systems—with and without coding. Eb is the energy-per-bit to noise-density at the receiver input. The function Q(x) is Q(x) = (1/ x)e –x2/2. TABLE 70.2 Coding Gains with BPSK or QPSK Coding Gain (dB) Coding Gain (dB) Data Rate Coding Technique Used at 10–5 BER at 10–8 BER Capability Ideal coding 11.2 13.6 Concatenated Reed–Solomon and convolution (Viterbi decoding) 6.5–7.5 8.5–9.5 Moderate Convolutional with sequential decoding (soft decisions) 6.0–7.0 8.0–9.0 Moderate Block codes (soft decisions) 5.0–6.0 6.5–7.5 Moderate Concatenated Reed–Solomon and short block 4.5–5.5 6.5–7.5 Very high Convolutional with Viterbi decoding 4.0–5.5 5.0–6.5 High Convolutional with sequential decoding (hard decisions) 4.0–5.0 6.0–7.0 High Block codes (hard decisions) 3.0–4.0 4.5–5.5 High Block codes with threshold decoding 2.0–4.0 3.5–5.5 High Convolutional with threshold decoding 1.5–3.0 2.5–4.0 Very high BPSK: modulation technique—binary phase-shift keying; QPSK: modulation technique—quadrature phaseshift keying; BER: bit error rate. Source: V.K. Bhargava,“Forward error correction schemes for digital communications,” IEEE Communication Magazine, 21, 11–19, © 1983 IEEE. With permission. 2p