(12) United States Patent
`US 6,347,122 B1
`(10) Patent N0.:
`Chen et al.
`{45) Date of Patent:
`Feb. 12, 2002
`
`
`
`USOUGM'J'I 22131
`
`(54) OPTIMAL COM PLEMEN'I' PUNC'I'URED
`CONVOI.UTIONAL CODES FOR USE IN
`DIGITAL AU D10 BROADCASTING AN D
`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 ofthis
`patent is extended or adjusted under 35
`USC. 154(b) by 0 days.
`
`(21) Appl. No.: 091006570
`
`(22
`
`Filed:
`
`Jan. 13, 1998
`
`(51)
`
`Int. CL?
`
`(52) U.S. CI.
`
`H04L 5,112
`
`3751262; 3751219; 3751265;
`3751270; 3751296
`
`(58)
`
`(55)
`
`Field of Search
`
`
`.375(262. 340
`37513265. 270m296.thi;37.111431; 714.786.
`774 "1'55. 790. 792
`
`References Cited
`U.S. I’A'I'IJN'I' DOCUMENTS
`
`5.1914922 A
`Symasst A
`5.910.182 A "
`5.949396 A
`(3.115.894 A
`
`"
`
`1211908 Wolfelal.
`37114.11
`011090 Schmidt ............. 371.1411
`6.11999 Dent et al.
`T141780
`
`9.11999 Kuntar
`..
`.. 3?”,"529
`[21"]999 Kumar
`3751??”
`OTHER PUBLICATIONS
`
`l. B.W. Kroeger and AJ. Vigil, “Improved IBOC DAB
`Technology for AM and [iM 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
`'l‘ransact ions on Broadcasting, vol. 43, No. 4. pp. 412—420.
`Dec. 1997.
`
`3. B.W. Kroeger and PJ. Peyla, "Compatibilityr of I’M
`Hybrid ln—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." IEEE Transactions on Communications. vol. 38.
`No. 7, pp. grouse. Jul. 1990.
`
`(List continued on next page.)
`
`Primary Emmincr41ephen Chin
`Assistant Iiirrmtiner—Shuwang Liu
`(74) Attorney. Agent. or Firm—Ryan. Mason & Lewis, UP
`
`(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 ol‘polential 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
`may be selected. for example. as the pair of equivalent or
`non-equivalent codes which has the best free llamming
`distance and minimum inl‘onrtation error weight of all the
`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 dili‘erent
`classes of information bits. The invention further provides
`optimal bit assignment techniques [or 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.
`
`45 Claims, 3 Drawing Sheets
`
`Human
`
`
`
`
`nuwwn
`
`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.1.Hagcnauer. “Rate Compatible Puncturcd Convolutional
`Codes (RCPC Codes.) and their Applications." IEEE Trans-
`actions on Communications. vol. 36. No. 4, pp. 389—400.
`Apr. 1988.
`8. RV. Cox ct 3L. "Sub—band Speech Coding and Matched
`Convolutional Channel Coding for Mobile Radio Chan
`
`nels,“ IEEE Transactions on Acoustica. Speech and Signal
`Processing, vol. 39, No. 8, pp. 1717—1731, Aug. 1991.
`9. AR. Calderbank and N. Soshadri, “Multilevel Codes for
`Unequal Error Protection." IEEE 'l'ransaclions 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
`
`

`

`US. Patent
`
`Feb. 12, 2002
`
`Sheet 1 off:
`
`US 6,347,122 B1
`
`1
`FIG.
`[PRIOR ART)
`
`:
`
`ANALOG
`
`
`
`TRANSMITTER
`
`25
`
`26
`
`27
`
`28
`
`\r——————————————————————°———————————————————,
`
`
` A
`
`30%
`V
`
`. '
`
`24
`
`3
`
`3
`
`FI G .
`
`3A
`
`FIG . SB
`
`Manna Hanan
`
`LOWER SIDEBAND
`
`UPPER SIDEBAND
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 3
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 3
`
`

`

`US. Patent
`
`Feb. 12, 2002
`
`Sheet 2 of 3
`
`US 6,347,122 B1
`
`
`
`BER
`
`Es/No [dB]
`
`FKII3.
`
`E3
`
`BER
`
`
`
`
`[R=B/10)
`x 5 9 2
`0 ac c3 03 (nzaigl
`+ 06 05 6A (R=B/11}
`~ F9 2A 84 (9:3!11)
`
`
`
`Es/No [dB]
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 4
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 4
`
`

`

`US. Patent
`
`Fch.12,2002
`
`Sheet 3 of3
`
`US 6,347,122 B1
`
`FIG. 6
`
`R=1/3
`
`/ \1
`/H"V11""""" /”‘4/9\
`Ra'm
`Rig/11
`92/9
`FIE/9
`L ...........‘a........l
`:
`r
`l
`'. ___________________ a
`
`=
`
`
`
`=
`
`_
`
`_____ _
`
`= _ =
`
`(FULL BANDHIDTH
`
`1
`AVERAGE RATE 2/5
`AVERAGE RATE 4/5
`
`(HALF BANDHIDTH]
`
`L
`
`U
`
`L
`
`U
`
`FIG. 7
`
`100
`
`,1
`
`10
`
`a at ca 29
`
`o 05 [15 BA
`+ F9 2A 34
`
`BER
`
`Es/Nn (dB)
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 5
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 5
`
`

`

`US 6,347,122 B1
`
`1
`OPTIMAL COMPLEMENT PUNCTURED
`CONVOLUTIONAL CODES FOR USE IN
`DIGITAL AUDIO BROADCASTING AND
`0TH ER 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
`
`ID
`
`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. .I. 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-
`lions.
`
`SUMMARY OF 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-
`incompatiblc 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 among a set of potential non-catastrophic codes
`for a given set ol'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-4i5
`half-bandwidth convolutional code which is generated by
`puncturing a rate-25 full-bandwidth convolutional code.
`The full-bandwidth code may itself be generated by punc-
`turing a rate-IE 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 information is transmitted on both a
`lower sideband 12 and an upper sideband 14 of the analog
`host 10. using a mullicarrier 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. The digital 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 (7 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. .I. 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 IBOC 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. Apair 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 .I. B. Cain, “Error
`Correcting Codes for Digital Communications," Plenum _
`Press, 1981, S. Lin and D. J. Costello .Ir._. “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.
`
`40
`
`45
`
`50
`
`00
`
`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 B1
`
`3
`BRIEF DESCRIPTION or THE DRAWINGS
`
`1 shows a portion of a frequency Spectrum in a
`FIG.
`conventional In Band 0n 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 diflerent punctured convolutional
`codes in accordance with the invention.
`
`ID
`
`4
`The modulated carrier is transmitted via transmit antenna 29
`to the receiver 24. The transmitter 22 may include additional
`processing elemean. 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
`
`FIG. 6 shows rate-compatibility relationships for an
`[ECG system configured with unequal error protection
`(UEP) in accordance with the invention.
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`15
`
`The invention will be described below in conjunction with
`exemplary complementary punctured convolutional codes
`optimized for use in a particular digital audio broadcast
`system. It should he 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. 8. Lin
`and D. J. Costello Jr., "Error Control Coding: Fundamentals
`and Applications.” Prentice-Hall. 1983. and G. C. Clark, J r.
`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. Kalle], “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 embodiment uses a bit stream generated from
`audio data, the invention is more generally applicable to bits
`generated by any type of digital 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.
`
`40
`
`45
`
`50
`
`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 circuit, microprocessor or any other type of digital
`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 CPPC codes 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 130C
`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 IBOC system can be configured to
`utilize rate-45 forward error correction codes for both the
`upper and lower sideband channels. These rate-45 codes are
`referred to as half-bandwidth codes, and combine to form a
`rate-25 error correction code referred to as a full-bandwidth
`code. It will be shown below that, utilizing the techniques of
`the invention, a rate-.18 mother code can be punctured to
`meet these exemplary IBOC code requirements.
`The rate-13 mother code may be a rate-U3 convolutional
`code having a constraint length K-7 as described in J.
`I-Iagenauer. "Rate-compatible punctured convolutional
`codes (RCPC codes) and their applications." IEEE Trans
`actions on Communications, Vol. 36, No. 7, pp. 389—411),
`April 1988. The code rate is the ratio of input bits to output
`bits for the convolutional encoder. A rate—18 encoder gen—
`erates three output bits for each input bit. A group of three
`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 each output symbols. For example, a
`rate-1.8 convolutional encoder with K-‘r‘ 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 [(-7 encoder is said to have a
`“memory" of six. The rate-1!}. [(-7 code used in this
`example has the following three generators:
`g0=1011011
`g,=1111001
`g,—11txuni
`Each of the generators may be viewed as specifying the
`.‘ connections between bits of the seven-bit shift register and
`inputs of one of the modulo-2 adders. For example, the adder
`corresponding to generator go generates the first bit of each
`
`00
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 7
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 7
`
`

`

`US 6,347,122 B1
`
`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 g1 and g2 generate the second
`and third bits,
`respectively, of each output symbol as
`modulo-2 sums of the bits in the positions designated by the
`respective generator values. The free Hamming distance (if
`of the rate-113. K-7 code with the above-noted generators is
`14, and its information error weight ca.
`is one. When this
`code is punctured in a rate-compatible manner to rates of
`4111, 4110, 419 and 112. the resulting rate-1Q code is also the
`best rate-112. [(-7 convolutional code.
`
`Two difl'erent puncturing patterns were used to obtain the
`following full-bandwidth codes from the rate-113 mother
`code: (1} a rate-215 code as described in the above-cited
`Hagenauer reference; and (2) a rate-215 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:
`
`10
`
`15
`
`r.) U!
`
`Hagenauer Rate-215 Code: (1111. 1111, 110(1), (df-ll.
`cdy'P=1).
`‘
`Kroeger Rate-.15 Code: (1111, 1111, 1010), (d_f=11, cdy’
`P=2). These codes were then punctured in accordance
`with the techniques of the invention to form rate-415
`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 combine to one of the two rate-215 codes
`noted above. The worst-case free distance of the comple- .
`mentary pair is the minimum of the pair of free distances.
`The worst-case information error weight
`(chum)
`is the
`maximum of the pair of information error weights. Ainong
`the code pairs that have the maximum worst-case free
`distance. the pair with the lowest cwmy'P value is considered
`the optimal pair. The free distances and information error
`weights may be calculated using an augmented-metric Vit-
`erbi algorithm. Other optimization criteria may be used in
`alternative embodiments of the invention.
`TABLES l and 2 below list the non-catastrophic comple~
`mentary rate-415 codes with puncture period P-4 that have
`a maximum worst-case free distance, as generated from the
`rate-215 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. Kalle] 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.
`
`40
`
`45
`
`50
`
`6
`
`TABLE 2
`
`Rate-41'.“ CPPC codes that combine to Kroeger rate-2:5 code,
`with P: 4.
`
`Puncture Pattern
`
`(0110, 1001,0010}
`(0110, 11101.10110]
`
`df
`
`4
`4
`
`cflrl'P Complementary Pattern
`
`2.50
`12.011
`
`(1001, 0110. 11100}
`(1001. 0110. [11.1101
`
`d,
`
`4
`4
`
`cdp'P
`
`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 diflerent digital audio subcarriers in portions A,
`B and C of the upper and lower sidebands. More particularly,
`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 hits to subcarriers which
`improves performance relative to conventional mappings.
`This mapping is determined by puncturing each sideband of
`the full-bandwidth codes in an RCPC fashion 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 g2 are mapped to these
`frequencies. Thus. if both outer regions A in the upper and
`lower sidebands of FIG. 1 are corrupted or lost, the remain-
`ing code would be an industry-standard rate-ls? code. At
`each puncturing step, the punctured bit is assigned to the
`outermost unassigned subcarrier. The optimal puncture pat-
`terns for the lower sideband (LSB) and upper sideband
`(USB) are shown in TABLES 3 and 4. respectively.
`
` TABLE 3
`
`Lower Sidebnnd Puncture Pattern for Bit Assignment
`
`1.513 Pattern
`(0110. 1001, 0000}
`(mm. non, noun;
`(0110. [1000. 00110)
`(0010. 11100. 01100]
`
`Full Pattern
`(Jill. 1111. 1000)
`(1111. 0111, 100th
`(1111, [1110. 111110)
`(11111. 1.1110. 1000!
`
`Full Rate
`1'9
`4:3
`41'?
`43th
`
`1:1l
`10
`3
`'t'
`5
`
`Car?
`].75
`m5
`3.00
`L135
`
`FIGS. 3A and 3B illustrate the above-described optimal
`bit assignment strategy for the lower sideband and upper
`sideband, respectively. The notation 60,. 61,. and 62,- refers
`to the ith bit, modulo 4, from the generators g0, g1 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 g2 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.
`
`TABLE 1
`
`Rate—415 CPPC codes that combine to Hagenauer rate—215 code,
`with P = 4.
`
`00
`
`TABLE 4
`
`Puncture Pattern
`(1011, 0100, 1000]
`(1000, 0011, 1100}
`(1011. 01m. 0100:
`
`df
`4
`4
`4
`
`cap'l’ Complementary Pattern
`8.00
`(0100. 1011, 0100}
`9.50
`(11111, 1100, 00001
`21.25
`(0100. 1011.10001
`
`d,
`4
`4
`4
`
`cdp'l’
`2.?5
`0.25
`9.?5
`
`UEEI Sidehand Puncture Pattern for Bit Assiggmenl
`
`USE Pattern
`(101211, 11110. 0001)]
`(100], 0100. 0000}
`
`Full Pattern
`(1111. 1111.. 110101
`(1111, 1101, 0011))
`
`Full Rate
`1'9
`413
`
`dr
`10
`3
`
`Cdp'P
`1.75
`0.715
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 8
`
`Petitioner Sirius XM Radio Inc. - Ex. 1004, p. 8
`
`

`

`US 6,347,122 B1
`
`7
`
`TABLE 4-continued
`
`Lip-Er Sideband Puncture Pattern for Bit Assignment
`
`USB Pattern
`(1001. 01.100, 0000)
`(1000, 0000. 0000]
`
`Full Pattern
`(1111. 1001. 00 101
`(1110. 1001, 0010}
`
`Full Rate
`4,3?
`416
`
`cl,
`7
`5
`
`('de
`2.00
`0.315
`
`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
`fun-bandwidth code may be the full. un-punctured. rate-113
`mother code described above. The half-bandwidth codes,
`which will be referred to as "half-bandwidth+" codes, will
`then each have a rate of 213. TABLE 5 below gives the
`optimal code pairs for two different compatibility con-
`straints. The code pair on the top line of TABLE 5 is the best
`punctured pair overall. The pair on the second line is the best
`pair that is rate-compatible with the optimal rate-415 code
`pair from TABLE 2. The advantage of this second pair is that
`if the additional inner tones were erased by the channel or if
`the receiver were incapable of receiving these inner tones.
`the remaining codes would be the optimal half-bandwidth
`tones previously described.
`
`TABLE 5
`11111111 Half-Bandwidth + Codes. with P - 4.
`
`(
`
`Puncture Pattern
`(0101. 0101.10101
`(0110. 1001.00111
`
`:1,
`6
`5
`
`Carl}, Complementary Pattern
`3.00
`(1010.1010. 0101)
`0.15
`(1001. 0110. 1100)
`
`d,
`6
`S
`
`0.75
`
`R
`
`10
`
`15
`
`r.) U!
`
`30
`
`Another aspect of the invention relates to providing
`unequal error protection (UEP) in a DAB or other commu- ‘
`nication system. In order to configure the above-described
`IBOC system to provide UEP, one would still need an
`average rate of 215 for the fill~bandwidth code and an
`average rate of 415 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 he
`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
`
`40
`
`45
`
`8
`Hagenauer reference. More particularly. the Class 1 bits
`should follow the Class 11 bits. and the unpunctured bits in
`the Class 11 code must be a subset ofthe unpunctured bits in
`the Class I code. TABLES 6 and 7 below show candidate
`punctured convolutional codes for Class 1 and Class 11 bits,
`respectively.
`in the IBOC system. TABLE 6 shows the
`puncture patterns. with a puncture period P-S. for all non-
`equivalent
`rate-4111 codes compatible with an industry-
`standard rate-112 code obtained with the puncture pattern
`(1111, 1111, 1111 1111, 0000 0000). TABLE '1' shows the
`puncture patterns, with P-8. for all non-equivalent rate—419
`codes compatible with the industry-standard rate-1f.) code. It
`should be noted that cyclic shifts of the puncture patterns in
`TABLES 6 and 7 will provide equivalent performance. The
`mother code used to generate the punctured codes in
`TABLES 6 and 7 is the same rate-113 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 Class 11 bits, the average
`rate of the full-bandwidth code is 215 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
`
`(‘ng
`0.350
`12
`(11111111.111111]].111011101
`0.350
`13
`(I111 1111.1111 1111.11101101:
`0.500
`12
`(1111 1111.111111]].11111101'1]
`0.6 25
`13
`(11111111.111111]].111110101
`
`df
`
`TABLE 7
`
`Pull-Bandwidth Code:- for Proleclion of Class 11 Bits in
`DAB System with UEP
`
`Puncture Pattern
`
`(111]1111,111111]],10001000)
`(1111 1111.111111]].10010000}
`(1111 1111.111] 11]]. 1100 1.1000)
`(11111111.111111]].1010 00001
`
`d,
`
`10
`10
`10
`10
`
`Cng
`
`1.750
`3.500
`3.000
`3.115
`
`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-215 (i.e.. 4110) code with a
`puncture pattern of (1111. 1111, 1010), or FFAin hexadeci-
`mal notation. The UEP codes are the best full-bandwidth
`Class I (rate—1111 )and Class II (rate-419) codes taken from
`the top lines of TABLES 6 and 7. respectively. These codes
`in hexadecimal notation may be written as FF FF EE and FF
`PF 88, respectively. It can be seen that the rate-4111 Class 1
`code provides the best BER performance, followed by the
`rate-215 EEP code, with the rate—419 Class 11 code providing
`the worst BER performance of the three full-bandwidth
`codes.
`
`straightforward. and will not he 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 IBOC system. If the
`fraction of Class I bits is f and the fraction of Class II bits
`is l-f. the rates of the codes must satisfy:
`
`
`
`Rn i
`
`[11
`
`where R is the average rate. and R, and R” are the rates of
`the codes for the Class I and Class 11 bits, respectively. For
`example. with R-215 and f-lé. the pair of rates (Ry. R")-
`(4f11, 4.19) satisfies equation (1) above.
`A full-bandwidth code with a set of rates satisfying
`equation (I) can be constructed by puncturing a common
`convolutional mother code. Furthermore, if one wants to
`avoid inserting termination bits between the Class I and
`Class 11 hits, the mother code needs to be punctured in a
`rate-compatible manner. as described in the above-cited .l.
`
`50
`
`60
`
`As in the EEP examples described previously, half-
`bandwidth codes for an IBOC system with UE