a2) United States Patent
`US 6,347,122 Bl
`(0) Patent No.:
`Feb. 12, 2002
`(45) Date of Patent:
`Chenetal.
`
`US006347122B1
`
`(54) OPTIMAL COMPLEMENT PUNCTURED
`CONVOLUTIONAL CODES FOR USE IN
`DIGITAL AUDIO BROADCASTING AND
`OTHER APPLICATIONS
`
`(75)
`
`Inventors: Brian Chen, Somerville, MA (US);
`Carl-Erik Wilhelm Sundberg,
`Chatham, NJ (US)
`
`(73) Assignee: Agere Systems Guardian Corp.,
`Orlando, FL (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/006,570
`
`(22)
`
`Filed:
`
`Jan. 13, 1998
`
`(AY WN? sissccsincanisccannanannawen BOA SN2
`
`(52) U.S. Ch. we eeesenee 375/262; 375/219; 375/265;
`375/270; 375/296
`
`3. B.W. Kroeger and PJ. Peyla, “Compatibility of FM
`Hybrid In—Band On-Channel (IBOC) System for Digital
`Audio Broadcast,” IEEE Transactions on Broadcasting,vol.
`43, No. 4, pp. 421-430, Dec. 1997.
`4. Y. Yasuda, K. Kashiki and Y. Hirata, “High—rate punctured
`convolutional codes for soft decision Viterbi decoding,”
`IEEE Transactions on Communications, vol. 32, Mar. 1984.
`5. S. Kallel, “Complementary Punctured Convolutional
`Codes and Their Applications,” IEEE Transactions on Com-
`munications, vol. 43, No. 6, pp. 2005-2009, Jun. 1995.
`6. J. Hagenauer et al., “The Performance of Rate—Compat-
`ible Punctured Convolutional Codes for Digital Mobile
`Radio,” TEEE Transactions on Communications, vol. 38,
`No. 7, pp. 966-980, Jul. 1990.
`
`(List continued on next page.)
`
`Primary Examiner—Stephen Chin
`Assistant Examiner—Shuwang Liu
`(74) Attorney, Agent, or Firm—Ryan, Mason & Lewis, LLP
`
`(57)
`
`ABSTRACT
`
`The invention provides optimal complementary punctured
`convolutional codes for coding information bits in a com-
`munication system. In an illustrative embodiment, an opti-
`mal pair of complementary punctured codes is selected from
`a set ofpotential code pairs. The set of potential code pairs
`includes all non-catastrophic complementary punctured
`code pairs which combine to produce to a specified full-
`bandwidth code, and thus includes both equivalent and
`non-equivalent complementary codes. The optimal code pair
`
`5,844,922 A*12/1998 Wolf et al. scsseseeeee 371/431
`may be selected, for example, as the pair of equivalent or
`5,909,454 A
`6/1999 Schmidt
`ceesccsesceserereers 371/43.1
`non-equivalent codes which has the best free Hamming
`5,910,182 A *
`6/1999 Dent et al. ....
`we. 714/786
`
`distance and minimum information error weight ofall the
`.........
`-
`» 370/529
`9/1999 Kumar
`5,949,796 A
`6,005,894 A
`12/1999 KUmar® .....ccsccscssseesreee
`375/270
`pairs in the set.
`In addition,
`the invention provides both
`rate-compatible and rate-incompatible codes suitable for use
`in providing unequal error protection (UEP) for different
`classes of information bits. The invention further provides
`optimal bit assignment techniques for use in digital audio
`broadcasting or other applications in which digital informa-
`tion is transmitted on subcarriers in both an upper and a
`lower sideband of an analog carrier.
`
`(58)
`
`(56)
`
`Field of Search .
`
`
`‘i
`. 375/262, 340,
`375/265, 270,296, 216;371/43. 1; 714/786,
`774, 755, 790, 792
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`i?
`
`OTHER PUBLICATIONS
`
`1. B.W. Kroeger and A.J. Vigil, “Improved IBOC DAB
`‘Technology for AM and FM Broadcasting,” SBE Engineer-
`ing Conference, pp. 1-10, 1996.
`2. B.W. Kroeger and D. Cammarata, “Robust Modem and
`Coding Techniques for FM Hybrid IBOC DAB,” IEEE
`Transactions on Broadcasting, vol. 43, No. 4, pp. 412-420,
`Dec. 1997.
`
`45 Claims, 3 Drawing Sheets
`
`al/
`
`
`BICC!
`
`
`
`LOWER SIDEBAND
`
`UPPER SIDEBAND
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 1
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 1
`
`

`

`US 6,347,122 B1
`
`Page 2
`
`OTHER PUBLICATIONS
`
`7. J. Hagenauer, “Rate Compatible Punctured Convolutional
`Codes (RCPCCodes) and their Applications,” IEEE Trans-
`actions on Communications, vol. 36, No. 4, pp. 389-400,
`Apr. 1988.
`8. R.V. Coxet al., “Sub-band Speech Coding and Matched
`Convolutional Channel Coding for Mobile Radio Chan
`
`nels,” IEEE ‘Transactions on Acoustics, Speech and Signal
`Processing, vol. 39, No. 8, pp. 1717-1731, Aug. 1991.
`9. A.R. Calderbank and N. Seshadri, “Multilevel Codes for
`Unequal Error Protection,” [EEE Transactions on Informa-
`tion Theory, vol. 39, No. 4, pp. 1234-1248, Jul. 1993,
`
`* cited by examiner
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 2
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 2
`
`

`

`U.S. Patent
`
`Feb. 12, 2002
`
`Sheet 1 of 3
`
`US 6,347,122 BI
`
`FIG.
`(PRIOR ART)
`
`ANALOG
`
`HOST
`
`aaeo/
`
`
`i
`
`4
`
`30
`
`VV
`
`FIG.
`
`3A
`
`FIG. 3B
`
`eEPE] Bee
`
`LOWER SIDEBAND
`
`UPPER SIDEBAND
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 3
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 3
`
`

`

`U.S. Patent
`
`Feb. 12, 2002
`
`Sheet 2 of 3
`
`US 6,347,122 Bl
`
`FIG. 4
`
`x FF A (A=4/10)
`o FF FF 88
`(A=4/9)
`+ FF FF EE
`
`(R=4/44)
`
`
`-Ms
`
`-4
`
`-2
`Fs/No (dB)
`
`0
`
`00
`17!
`
`197°
`
`109
`
`10-4
`
`1079
`
`BER
`
`19 0
`
`1072
`
`107¢
`
`1073
`
`474
`
`1079
`
`BER
`
`FIG. 5
`
`x 692 (R=8/10)
`© 3C C3 08 (A=8/9)
`+ 06 05 6A (R=B/14)
`‘FQ 2A B4
`(R=B/ 44)
`
`
`
`-6ie:
`
`0
`
`2
`Es/No (dB)
`
`4
`
`6
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 4
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 4
`
`

`

`U.S. Patent
`
`Feb. 12, 2002
`
`Sheet 3 of 3
`
`US 6,347,122 BI
`
`FIG. 6
`
`A=1/3
`
`a Na
`
`_
`Prd/i] ~-onernnns
`
`en
`R-4/9
`
`(FULL BANDWIDTH
`AVERAGE RATE 2/5
`
` d
`
`r
`
`=f)/Q
`
`—_—_—_—— =
`
`(HALF BANDWIDTH)
`
`ue Nene fate Ae
`oh
`ee
`p=8/14
`;
`Lo----------Jennnnon-I
`i"eeeeee i
`U
`L
`U
`
`L
`
`FIG. 7
`
`10°
`4
`
`10
`
`30 C3 29
`x
`o 06 05 6A
`+
`FQ 2A Bd
`
`BER
`
`=2
`
`0
`
`2
`Es/No (dB)
`
`4
`
`6
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 5
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 5
`
`

`

`US 6,347,122 Bl
`
`1
`OPTIMAL COMPLEMENT PUNCTURED
`CONVOLUTIONAL CODES FOR USE IN
`DIGITAL AUDLO BROADCASTING AND
`OTHER APPLICATIONS
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to convolutional
`codes for use in communication systems, and more particu-
`larly to punctured convolutional codes optimized for use in
`conjunction with digital audio broadcasting and other types
`of communication system applications which utilize diver-
`sity in frequency, time, space, polarization or other system
`parameters.
`
`BACKGROUND OF THE INVENTION
`
`15
`
`2
`complementary in the sense that they are both of a rate
`which is twice that of the mother code obtained by com-
`bining the two codes. Increased puncturing leads to higher
`punctured code rates. It can be shown that punctured codes
`of a certain rate generally provide performance which is
`almost as good as that of optimal codes at the same rate.
`Unfortunately,
`the conventional CPPC codes which have
`been proposed for use in the IBOC system described in the
`above-cited B. W. Kroeger and A. J. Vigil reference gener-
`ally do not provide optimal or near-optimal performance,
`and in some cases are even catastrophic. This may be due in
`part
`to a perceived requirement
`that
`the code pairs be
`so-called “equivalent” codes, as defined in S. Kallel,
`“Complementary Punctured Convolutional Codes and Their
`Applications,” IEEE Transactions on Communications, Vol.
`43, No. 6, pp. 2005-2009, June 1995, which is incorporated
`by reference herein. However, this perceived requirement
`has had the effect of unduly restricting the scope of search
`for CPPC codes. A need therefore exists for
`improved
`punctured convolutional codes which can provide better
`performance than conventional codes in the above-described
`IBOC digital audio broadcasting system and other applica-
`tions.
`
`SUMMARYOF THE INVENTION
`
`The invention provides optimal punctured convolutional
`codes for use in digital audio broadcasting as well as other
`types of communication systems. Optimal punctured con-
`volutional codes are provided for equal error protection
`(EEP) applications, and both rate-compatible and rate-
`incompatible codes for are provided for unequal error pro-
`tection (UEP)applications. In an exemplary embodiment, an
`optimal code is selected as a code which has the best free
`Hamming distance and the minimum information error
`weight from amonga set of potential non-catastrophic codes
`for a given set of operating parameters. Unlike conventional
`punctured code sets used for digital audio broadcasting
`applications, a set of potential non-catastrophic codes in
`accordance with the invention can include codes which are
`not equivalent in terms of their distance or performance
`properties. The selected optimal code thus provides perfor-
`mance advantages relative to a code selected from a set
`restricted to only equivalent codes. Although particularly
`well suited for use with complementary code pairs,
`the
`techniques of the invention can be readily extended for use
`in selecting an optimal group of n complementary codes
`from a set of such groups.
`The invention may be implemented in an exemplary
`system in which digital audio information is transmitted on
`subcarriers in both an upper and a lower sideband of an
`analog carrier. In such a system, an optimal complementary
`code pair is selected from a set of code pairs defined in the
`manner described above. The complementary codes in the
`selected code pair may each be, for example, a rate-4/5
`half-bandwidth convolutional code which is generated by
`puncturing a rate-2/5 full-bandwidth convolutional code.
`The full-bandwidth code may itself be generated by punc-
`turing a rate-1/3 mother code. The invention also provides
`an optimal bit assignment strategy for use in such a system.
`In accordance with this strategy,bits from a designated code
`generator may be assigned to the upper and lower sideband
`subcarriers which are located furthest
`from the analog
`carrier. These and other techniques of the invention can be
`readily extended to a wide variety of different
`types of
`communication systems. For example, the invention can be
`implemented in communication system applications which
`utilize diversity in frequency, time, space, polarization or
`any other system parameter.
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 6
`
`FIG. 1 shows a portion of a frequency spectrum in an
`exemplary In Band On Channel (IBOC) system for imple-
`menting digital audio broadcasting (DAB)in existing analog
`frequency modulation (FM) radio bands.
`In this IBOC
`system, an analog FM carrier signal 10 serves as a “host” for
`transmission of digital audio information of CD-like quality.
`The same digital audio informationis transmitted on both a
`lower sideband 12 and an upper sideband 14 of the analog
`host 10, using a multicarrier OFDM technique. This ensures
`that all ofthe digital information can be recovered when one
`of the sidebands is corrupted, or even completely lost, due
`to effects such as fading or interference in the crowded
`analog FM band. Thedigital audio subcarriers transmitted in
`region B of the lower and upper sidebands 12, 14 are
`generally less susceptible to interference from adjacent FM
`channels or the analog host 10 than the carriers in regions A
`or C. The subcarriers in region A of sidebands 12, 14 are
`more susceptible to adjacent channel
`interference, while
`those in region C are more susceptible to interference from
`the analog host 10. The transmission in region C may make
`use of precancellation techniques which allow the interfer-
`ence with the analog host 10 to be canceled. Additional
`details regarding this exemplary IBOC system can be found
`in B. W. Kroeger and A. J. Vigil, “Improved IBOC DAB
`Technology for AM and FM Broadcasting,” SBE Engineer-
`ing Conference, pp. 1-10, 1996,
`It has been proposed that complementary convolutional
`codes be utilized for channel coding in DAB systems such
`as the [BOC system described in conjunction with FIG. 1.
`For example, a pair of complementary codes can be used
`individually on both sides of the analog host 10 in the system
`of FIG. 1. A pair of complementary codes can be generating
`by “puncturing” a low-rate “mother” code to twice its
`original rate. Puncturing a mother code is a well-known
`technique for obtaining high-rate convolutional codes which
`exhibit good performance and which can be decoded using
`the same basic Viterbi algorithm that is used for the mother
`code. See, for example, G. C. Clark, Jr. and J. B. Cain, “Error
`Correcting Codes for Digital Communications,” Plenum :
`Press, 1981, S. Lin and D. J. Costello Jr, “Error Control
`Coding: Fundamentals and Applications,” Prentice-Hall,
`1983 and Y. Yasuda, K. Kashiki and Y. Hirata, “High-rate
`punctured convolutional codes for soft decision Viterbi
`decoding,” IEEE Transactions on Communications, Vol. 32,
`March 1984.
`
`20
`
`40
`
`45
`
`50
`
`60
`
`Puncturing generally involves removing bits from the
`low-rate mother code such that the remaining code bits form
`one of the complementary codes, while the punctured bits
`form the other complementary code of the code pair. The
`resulting pair of codes, which are referred to as complemen-
`tary punctured-pair convolutional
`(CPPC) codes, are
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 6
`
`

`

`US 6,347,122 Bl
`
`3
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`1 shows a portion of a frequency spectrum in a
`FIG.
`conventional In Band On Channel (IBOC) digital audio
`broadcasting system.
`FIG, 2 is a block diagram of a communication system
`which may be configured to utilize complementary punc-
`tured convolutional codes in accordance with the invention.
`
`FIGS. 3A and 3B illustrate exemplary bit assignment
`patterns for use in implementing optimal complementary
`punctured codes in accordance with the invention.
`FIGS. 4, 5 and 7 show plots of simulated bit error rate
`(BER) for a number of different punctured convolutional
`codes in accordance with the invention.
`FIG. 6 shows rate-compatibility relationships for an
`IBOC system configured with unequal error protection
`(UEP) in accordance with the invention.
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`4
`The modulated carrier is transmitted via transmit antenna 29
`to the receiver 24. The transmitter 22 may include additional
`processing elements, such as multiplexers, upconverters and
`the like, which are not shown in the FIG. 2 embodiment.
`The receiver 24 receives the transmitted signal via receive
`antenna 30, and performs demodulation operations in
`demodulator 31 to recover the interleaved symbols. The
`symbols are deinterleaved in a deinterleaver 32, and the
`resulting symbol sequence is converted to a digital bit
`stream in decoder 33 using a soft Viterbi decoding process.
`The digital bit stream is then decoded in audio decoder 34
`to reconstruct the original audio signal. Like the transmitter
`22, the receiver 24 may include additional processing ele-
`ments which are not shown in FIG. 2. It should also be noted
`that various elements of the system 20, such as the inter-
`leaver 27 and the deinterleaver 32, may be eliminated in
`alternative embodiments. Moreover, various elements of the
`system 20, such as the audio coder 25, convolutional
`encoder 26, Viterbi decoder 33 and audio decoder 34, may
`be implemented using portions of an application-specific
`integrated circuil, microprocessor or any other type ofdigital
`data processor. Various aspects of the invention may also be
`implemented in the form of one or more software programs
`executed by a central processing unit (CPU)or the like in the
`digital data processor.
`A number of sets of optimal CPPCcodes suitable for use
`in system 20 of FIG. 2 will now be described. It will be
`assumed for purposes of illustration that
`the operating
`parameters of system 20 are similar to those of the IBOC
`DAB system described in conjunction with FIG. 1 and in the
`above-cited B. W. Kroeger and A. J. Vigil
`reference,
`“Improved IBOC DAB Technology for AM and FM
`Broadcasting,” SBE Engineering Conference, pp. 1-10,
`1996, This exemplary [BOC system can be configured to
`utilize rate-4/5 forward error correction codes for both the
`upper andlower sideband channels. These rate-4/5 codes are
`referred to as half-bandwidth codes, and combine to form a
`rate-2/5 error correction code referred to as a full-bandwidth
`code. It will be shown below that, utilizing the techniques of
`the invention, a rate-1/3 mother code can be punctured to
`meet these exemplary IBOCcode requirements.
`The rate-1/3 mother code may be a rate-1/3 convolutional
`code having a constraint length K=7 as described in J.
`Hagenauer, “Rate-compatible punctured convolutional
`codes (RCPC codes) and their applications,” IEEE Trans-
`actions on Communications, Vol. 36, No. 7, pp. 389-400,
`April 1988. The code rate is the ratio of input bits to output
`bits for the convolutional encoder, A rate-1/3 encoder gen-
`erates three output bits for each input bit. A group ofthree
`coded output bits is referred to as a symbol. The value of K
`refers to the number of uncoded input bits which are
`processed to generate cach output symbols. For example, a
`rate-1/3 convolutional encoder with K=7 generally includes
`a seven-bit shift register and three modulo-two adders. The
`inputs of the each of the adders are connected to a different
`subset of the bits of the shift register. These connections are
`specified by the “generators” of the encoder. Because a
`given output symbol in this example is generated using the
`latest input bit as well as the previous six input bits stored
`in the shift register,
`the K=7 encoder is said to have a
`“memory” of six. The rate-1/3, K=7 code used in this
`example has the following three generators:
`g,=1011011
`g,=1111001
`g,=1100101
`Each of the generators may be viewed as specifying the
`connections between bits ofthe seven-bit shift register and
`inputs of one of the modulo-2 adders. For example, the adder
`corresponding to generator g,, generates the first bit of each
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 7
`
`The inventionwill be described below in conjunction with 7
`exemplary complementary punctured convolutional codes
`optimized for use in a particular digital audio broadcast
`system. It should be understood, however,that the coding
`techniques of the invention may be applied to many other
`types of communication systems, For example, although the
`digital audio broadcast system described herein utilizes a
`frequency diversity technique, the invention could also be
`implemented in systems which utilize time diversity, space
`diversity, polarization diversity, as well as other types of
`diversity techniques. The description of the exemplary ;
`embodiments will use the term “optimal” to refer to a code
`which has the best free Hamming distance and the minimum
`information error weight from among a set of potential
`non-catastrophic codes for a given set of operating param-
`eters. Acode is considered “catastrophic”if its state diagram
`contains a loop of zero weight other than the self-loop
`around the zero state. The concepts of free Hamming
`distance,
`information error weight and non-catastrophic
`codes are described in greater detail in, for example, S. Lin
`and D. J. Costello Jr., “Error Control Coding: Fundamentals
`and Applications,” Prentice-Hall, 1983, and G. C. Clark,Jr.
`and J, B. Cain, “Error Correcting Codes for Digital
`Communications,” Plenum Press, 1981, which are incorpo-
`rated by reference herein. Complementary codes in a given
`pair or other group of codes are considered “equivalent” if
`their puncturing patterns are cyclic permutations of one
`another, as described in S. Kallel, “Complementary Punc-
`tured Convolutional Codes and Their Applications,” IEEE
`Transactions on Communications, Vol. 43, No. 6, pp.
`2005-2009, June 1995. Optimal codes in accordance with
`the invention may be equivalent or non-equivalent.
`FIG. 2 is a block diagram of an exemplary communication
`system 20 in which CPPC codes in accordance with the
`invention may be utilized. The system 20 includes a trans-
`mitter 22 and a receiver 24, The transmitter 22 includes an
`audio coder 25 for generating a digital bit stream from an
`analog audio signal. The digital bit stream from audio coder
`25 is applied to a convolutional encoder 26 which utilizes
`CPPC codes, which will be described in greater detail below,
`to encode the bit stream into a sequence of symbols.
`Although this embodimentuses a bit stream generated from
`audio data, the invention is more generally applicable to bits
`generated by any type ofdigital source. The sequence of
`symbols from convolutional encoder 26 are interleaved in an
`interleaver 27, and then applied to a modulator 28. The
`modulator 28 may perform several stages of modulation
`such as, for example, modulating the interleaved symbols
`onto one or more sub-carriers, and then frequency modu-
`lating the sub-carriers onto a radio frequency (RF) carrier.
`
`45
`
`50
`
`60
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 7
`
`

`

`5
`output symbol as the modulo-2 sum of the bits in the first,
`third, fourth, sixth and seventh bit positions in the shift-
`register, with the first bit position containing the latest input
`bit. Similarly, the generators g, and g, generate the second
`and third bits,
`respectively, of each output symbol as
`modulo-2 sumsofthe bits in the positions designated by the
`respective generator values. The free Hamming distance dy
`of the rate-1/3, K=7 code with the above-noted generators is
`14, andits information error weight c,,/P is one. Whenthis
`code is punctured in a rate-compatible manner to rates of
`4/11, 4/10, 4/9 and 1/2, the resulting rate-1/2 codeis also the
`best rate-1/2, K=7 convolutional code.
`Two different puncturing patterns were used to obtain the
`following full-bandwidth codes from the rate-1/3 mother
`code: (1) a rate-2/5 code as described in the above-cited
`Hagenauer reference; and (2) a rate-2/5 code as described in
`B. W. Kroeger and D. Cammarata, “Complementary punc-
`tured convolutional codes with application to IBOC DAB,”
`1997. The puncturing patterns and other properties for these
`full-bandwidth codes are given by:
`Hagenauer Rate-2/5 Code: (1111, 1111, 1100), (d,=11,
`c4/P=1).
`,
`Kroeger Rate-2/5 Code: (1111, 1111, 1010), (dy=11, ¢,,/
`P=2). These codes were then punctured in accordance
`with the techniques of the invention to form rate-4/5
`CPPC codes which are optimal
`in terms of having
`maximum worst-case free Hamming distance and mini-
`mum Worst-case information error weight. These opti-
`mal codes are given in TABLES 1 and 2 below.
`The optimal CPPC codes are determined in this embodi-
`ment by first calculating the pairs of free distances and
`information error weights of all non-catastrophic comple-
`mentary codes that combineto oneofthe two rate-2/5 codes
`noted above. The worst-case free distance of the comple- 3
`mentary pair is the minimum ofthe pair of free distances.
`The worst-case information error weight (c,,,,.,) is the
`maximum ofthe pair of information error weights. Among
`the code pairs that have the maximum worst-case free
`distance, the pair with the lowestc,,_.,,.,/P value is considered
`CafP
`dy
`Full Rate
`Full Pattern
`LSB Pattern
`the optimal pair. The free distances and information error
`
`(0110, 1001, 0000)=(1111, 1111, 1000) /9 10 1.75
`
`
`weights may be calculated using an augmented-metric Vit-
`(0110, 0001, 0000)
`(1111, 0111, 1000)
`4/8
`8
`0.75
`erbi algorithm, Other optimization criteria may be used in
`(0110, 0000, 0000)
`(1111, 0110, 1000)
`4/7
`7
`2.00
`alternative embodiments of the invention.
`(0010, 0000, 0000)
`(1011, 0110, 1000)
`4/6
`5
`0.75
`TABLES1 and 2 belowlist the non-catastrophic comple-
`mentary rate-4/5 codes with puncture period P=4 that have
`a maximum worst-case free distance, as generated from the
`ralte-2/5 Hagenauer and Kroeger codes, respectively. The
`codes are listed in order of optimality. It should be noted that
`the optimum pair listed on the top line of TABLE 2 have
`puncture patterns which are cyclically-shifted versions of
`each other and are thus “equivalent” as defined in the
`above-cited S. Kallel reference. However,
`it can be seen
`from the optimum pair of TABLE 1
`that optimal CPPC
`codes in accordance with the invention need not be equiva- ;
`lent.
`
`Rate-4/5 CPPC codes that combine to Kroeger rate-2/5 code,
`with P = 4,
`
`Puncture Pattern
`
`(0110, 1001.0010)
`(0110, 1001, 1000)
`
`d;
`
`4
`4
`
`cy/P Complementary Pattern
`
`2.50
`12.00
`
`(1001, 0110, 1000)
`(1001, 0110, 0010)
`
`dp
`
`4
`4
`
`CaP
`
`2.50
`12.00
`
`As noted above, the IBOC system described in conjunc-
`tion with FIG.
`1 utilizes a multicarrier modulation
`technique, with varying amounts of interference suscepti-
`bility on the different digital audio subcarriers in portions A,
`B and C of the upper and lower sidebands. Moreparticularly,
`the subcarriers farthest away from the analog host are most
`susceptible to interference. Thus, the mapping of code bits
`to subcarrier frequencies can affect performance. The inven-
`tion provides a mapping of code bits to subcarriers which
`improves performance relative to conventional mappings.
`This mapping is determined by puncturing each sideband of
`the full-bandwidth codes in an RCPCfashion while keeping
`all of the bits in the other sideband. For example, assume
`that
`the two complementary codes from the top line of
`TABLE 2 are the respective lower sideband and upper
`sideband half-bandwidth codes. Since the outermost subcar-
`riers on each sideband are most susceptible to interference,
`the bits from the third generator g, are mapped to these
`frequencies. Thus, if both outer regions A in the upper and
`lower sidebands of FIG. 1 are corruptedor lost, the remain-
`ing code would be an industry-standard rate-1/2 code. At
`each puncturing step, the punctured bit is assigned to the
`oulermost unassigned subcarrier. The optimal puncture pat-
`terns for the lower sideband (LSB) and upper sideband
`(USB) are shown in TABLES3 and 4, respectively.
`
` TABLE 3
`
`Lower Sideband Puncture Pattern for Bit Assignment
`
`FIGS. 3A and 3B illustrate the above-described optimal
`bit assignment strategy for the lower sideband and upper
`sideband, respectively. The notation GO,, G1,, and G2, refers
`to the ith bit, modulo 4, from the generators gp, 2, and g.,
`respectively. The second bit modulo 4 from the third gen-
`erator g, is assigned to the outermost subcarrier of the lower
`sideband, and the zeroth bit modulo 4 from the third
`generator g, is assigned to the outermost subcarrier of the
`upper sideband. This bit assignment optimizes performance
`in the presence of interference for the exemplary IBOC
`system of FIG, 1. The bit assignment
`techniques of the
`invention could also be used to provide similar improve-
`ments in other types of communication systems.
`
`US 6,347,122 Bl
`
`6
`
`TABLE 2
`
`20
`
`40
`
`45
`
`50
`
`TABLE1
`
`Rate-4/5 CPPC codes that combine to Hagenauer rate-2/5 code,
`with P= 4.
`
`60
`
`TABLE 4
`
`Upper Sideband Puncture Pattern for Bit Assignment
`Puncture Patten dp=Cy/Pdy Cy/P Complementary Pattern
`
`
`(1011, 0100, 1000)
`4
`8.00
`(0100, 1011, 0100)
`4
`2.75
`(1000, 0011, 1100)
`4
`9.50
`(0111, 1100, 0000)
`4
`6.25
`(1011, 0100, 0100)
`4
`21.25
`(0100, 1011, 1000)
`4
`9,75
`
`USB Pattern
`(1001, 0110, 0000)
`(1001, 0100, 0000)
`
`Full Pattern
`(1111, 1111, 0010)
`(1111, 1101, 0010)
`
`Full Rate
`9
`4/8
`
`dy
`10
`8
`
`CadP
`1.75
`0.75
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 8
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 8
`
`

`

`US 6,347,122 Bl
`
`7
`
`TABLE 4-continued
`
`Upper Sideband Puncture Pattern for Bit Assignment
`
`USB Pattern
`(1001, 0000, 0000)
`(1000, 0000, 0000)
`
`Full Pattern
`(1111, 1001, 0010)
`(1110, 1001, 0010)
`
`Full Rate
`47
`4/6
`
`dr
`7
`2
`
`CafP
`2.00
`0.75
`
`It has been proposed that DAB broadcasters be allowed
`the option of transmitting with wider bandwidth codes by
`adding tones closer to the analog host. In this mode, the
`full-bandwidth code may be the full, un-punctured, rate-1/3
`mother code described above. The half-bandwidth codes,
`which will be referred to as “half-bandwidth+” codes, will
`then each have a rate of 2/3. TABLE 5 below gives the
`optimal code pairs for two different compatibility con-
`straints. The code pair on the top line of TABLE5 is the best
`puncturedpair overall. The pair on the secondlineis the best
`pair that is rate-compatible with the optimal rate-4/5 code
`pair from TABLE 2. The advantage ofthis secondpairis that
`if the additional inner tones were erased by the channel orif
`the receiver were incapable of receiving these inner tones,
`the remaining codes would be the optimal half-bandwidth
`tones previously described,
`
`20
`
`ba wn
`
`TABLE 5
`Optimal Half-Bandwidth + Codes, with P = 4.
`
`Puncture Pattern
`(0101, 0101, 1010)
`(0110, 1001, 0011)
`
`dy
`6
`5
`
`¢g/P Complementary Pattern
`3.00
`(1010, 1010, 0101)
`0.75
`(1001, 0110, 1100)
`
`dr
`6
`5
`
`cadP
`3.00
`0.75
`
`8
`Hagenauer reference. More particularly, the Class I bits
`should follow the Class IT bits, and the unpuncturedbits in
`the Class II code must be a subset ofthe unpuncturedbits in
`the Class I code. TABLES 6 and 7 below show candidate
`punctured convolutional codes for Class I and Class II bits,
`respectively,
`in the IBOC system. TABLE 6 shows the
`puncture patterns, with a puncture period P=8,for all non-
`equivalent
`rate-4/11 codes compatible with an industry-
`standard rate-1/2 code obtained with the puncture pattern
`(1111, 1111, 1111 1111, 0000 0000). TABLE 7 shows the
`puncture patterns, with P=8,for all non-equivalent rate-4/9
`codes compatible with the industry-standard rate-1/2 code. It
`should be noted that cyclic shifts of the puncture patterns in
`TABLES6 and 7 will provide equivalent performance. The
`mother code used to generate the punctured codes in
`TABLES 6 and 7 is the same rate-1/3 convolutional code
`used in the previously-described equal error protection
`(EEP) examples. With a pair of rates (R, R,,)=(4/11, 4/9)
`and equal numbers of Class I and ClassII bits, the average
`rate of the full-bandwidth code is 2/5 and therefore satisfies
`the rate requirements for the exemplary IBOC system.
`
`TABLE 6
`
`Full-Bandwidth Codes for Protection of Class [ Bits in
`DAB System with UEP
`
`Puncture Pattern
`
`Cd,/P
`0.250
`12
`(1111 1111, 1111 1111, 1110 1110)
`0.250
`12
`(1111 1111, 1114 1111, 1110 1101)
`0.500
`12
`(1111 1111, 1141 1111, 1111 1100)
`0.625
`12
`(1111 1111, 1111 1111, 1111 1010)
`
`dy
`
`Another aspect of the invention relates to providing
`unequal error protection (UEP) in a DABor other commu-
`nication system. In order to configure the above-described
`IBOC system to provide UEP, one would still need an
`average rate of 2/5 for the fill-bandwidth code and an
`average rate of 4/5 for
`the half-bandwidth codes. The
`invention satisfies this requirement through the use of time
`multiplexing. The time multiplexing will be illustrated for a
`case in which two classes of information bits are to be
`unequally protected. Class I bits are the most important bits
`and must be protected with a low-rate(i.e., high redundancy)
`code. Class II bits are the less important class of bits.
`Generalization to three or more classes of bits is
`straightforward, and will not be described in detail herein.
`The rates for the codes protecting the different classes of
`bits may be selected to satisfy an average rate constraint
`such as those noted above for the IBOCsystem. If the ~
`fraction of Class I bits is f and the fraction of Class II bits
`is 1-f, the rates of the codes mustsatisfy:
`
`40
`
`45
`
`
`
`Ry *
`
`(1)
`
`TABLE 7
`
`Full-Bandwidth Codes for Protection of Class II Bits in
`DAB System with UEP
`
`Puneture Pattern
`
`(1111 1111, 1111 1111, 1000 1000)
`(1111 1111, 1111 1111, 1001 0000)
`(1111 1111, 1111 1111, 1100 0000)
`(1111 1111, 1111 1111, 1010 0000)
`
`dy
`
`10
`10
`10
`10
`
`Cdy/P
`
`1.750
`2.500
`3.000
`3.125
`
`FIG. 4 shows plots of simulated bit error rate (BER)
`performance for
`full-bandwidth EEP and UEP code
`examples given above. It is assumed for these plots, and the
`BER plots of FIGS. 5 and 7, that the information source is
`a sequence of 10° pseudo-randomly generated bits, and the
`channel is an additive white Gaussian noise (AWGN) chan-
`nel. The EEP code used in the plots is the above-noted
`full-bandwidth Kroeger rate-2/5 (i.c., 4/10) code with a
`puncture pattern of (1111, 1111, 1010), or FFA in hexadeci-
`mal notation. The UEP codes are the best full-bandwidth
`Class I (rate-4/11 )and Class II (rate-4/9) codes taken from
`the top lines of TABLES6 and7, respectively. These codes
`in hexadecimal notation may be written as FF FF EE and FF
`FF 88, respectively. It can be seen that the rate-4/11 Class |
`code provides the best BER performance, followed by the
`rate-2/5 EEP code, with the rate-4/9 Class II code providing
`the worst BER performance of the three full-bandwidth
`codes.
`
`where R is the average rate, and R, and R,, are the rates of
`the codes for the Class I and ClassII bits, respectively. For
`example, with R=2/5 and f='4, the pair ofrates (R,, R,)=
`(4/11, 4/9) satisfies equation (1) above.
`As in the EEP examples described previously, half-
`A full-bandwidth code with a set of rates satisfying
`bandwidth codes for an IBOC system with UEP can be
`equation (1) can be constructed by puncturing a common
`convolutional mother code. Furthermore, if one wants to
`formed by puncturing the full-bandwidth codes given in
`TABLES6and7. Halfofthe bits for each ofthe Class I and
`avoid inserting termination bits between the Class I and
`C