`
`USUUGEHISSB]
`
`(12) United States Patent
`US 6,247,158 B1
`(10) Patent N0.:
`Smallcomb
`{45) Date of Patent:
`Jun. 12, 2001
`
`(54)
`
`DIGITAL BROADCASTING SYSTEM AND
`METHOD
`
`(75)
`
`Inventor:
`
`Joseph Smallcomh, Herndon, VA (US)
`
`(73)
`
`Assignee:
`
`IT'I‘ Manufacturing Enterprises. Inc..
`Wilmington. DE (US)
`
`OTHER PUBLICA'I'I ONS
`
`German Patent Document. entitled Apparatus and Method
`for Transmitting Information and Apparatus and Method for
`Receiving information. Schoppe & Zimmemtann, pp. 1—35,
`undated.
`
`4‘ cited by examiner
`
`V)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`Prirttary Emmt'rter—Phung M. Chung
`(74) Attornev. Agent. or Finn—Jim Zegeer
`
`(57}
`
`ABSTRACT
`
`(31)
`
`Appl. No.: 09f222,836
`
`Filed:
`
`Dec. 30, 1998
`
`(so)
`
`(51)
`(53)
`(58)
`
`(56)
`
`Related U.S. Application Data
`Provisional application No. ()(I.tlltl_.258.
`liled on Nov. 3ft.
`1998
`
`Inl.C|.T ..
`GllfiF llr'li]
`U.S. CI.
`714fl86
`Field of Search ..................................... 714,“?90. 746,
`7 l4r786; 370.1464, 542
`
`References Cited
`
`U.S. PATENF DOCUMENTS
`
`3.-’l980
`4.5”.3]? "
`2mm
`5,283,?80
`5,907,582 ' Sr'tuw
`Samara - harm
`5,010,085 * mow:
`0,023.402 *
`2..-'20m
`(1.049.506 '
`4r20ttt
`
`............................ 37l.);‘5t|2
`Chu ct al.
`...... 37050
`Schuchman ct al.
`
`.........................
`.. ”5:259
`‘t’i
`Kttwahara cl al.
`“[1380
`
`Yi
`.............
`315;?“ I
`
`Norman ...........
`“5:341
`Saunders ct al.
`375,522“
`
`Apparatus and method of achieving diversity in reception of
`plural digital broadcast signals. A stream of a complete set
`of code bits is generated from one or more sources of data
`bits. A first Critical Subset of code bits is chosen or selected
`for a first channel (cg. a specified puncturing pattern is
`applied to the stream of a complete set of code sets). A
`second (cg. alternative) Critical Subset of code bits is
`chosen or selected for a second channel (eg. a second or
`alternative puncturing pattern is chosen for the second
`channel}. Further alternative Critical Subsets may be chosen
`for any additional channels. All
`the channels are
`transmitters, some can incorporate time delay to achieve
`temporal diversity. Moreover. the order of transmitting the
`code bits on each channel can be it different (for example.
`the interleaving depths can he dillerent). At the receiver. the
`stream of Critical Subsets oi‘code hits for all of the channels
`are simultaneously received and a reconstruction of a com-
`plete set of code bits accomplished and the reconstructed
`code and may be inserted into a single Viterbi decoder.
`Various weighting functions and reconstruction algorithms
`are disclosed.
`
`21 Claims, 8 Drawing Sheets
`
`Intaneavers
`
`
`
`Code Bit
`Decom-
`position
`
`504B
`
`
`
`Channels Channel A
`Spatiaiiy Diverse
`
`Code Bit
`
`Fteeomgosition
`
`
`Recovered
`
`Combining
`Source Bits
`
`
`
`
`Deintedeavers
`
`
`
`
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 1
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 1
`
`
`
`US. Patent
`
`Jun. 12, 2001
`
`Sheet 1 of 8
`
`US 6,247,158 B1
`
`mo_.
`
`m.2ch
`
`46520
`
`For
`
`FMIDOE
`
`$3@3530
`
`an:4"
`
`
`4|'4
`.9,J
`
`555as...
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 2
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 2
`
`
`
`
`
`
`US. Patent
`
`U
`
`2
`
`lB8s
`
`19nm"mamgoonmggoumm
`6.,mm.mammagnum.”bmgmzoommmmEcEEoo
`
`m53:ch93:20.----------1----------------------------------------Sn
`
`
`2,"mEmmEmmcfioocmM."EmuHmuccmE.mam830m.
`flmccmcom528mMmagniamcmqmm.
`
`mcfioomo
`"row
`IIIIIIIIIIIIIIIIIIIIIIIIIlllllllllllllll|lllll|llIII
`
`BEEmcE...
`
`
`
`C5.coin:NMIDOE
`
`vow
`
`mammboo
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 3
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 3
`
`
`
`US. Patent
`
`Jun. 12, 2001
`
`Sheet 3 of 8
`
`US 6,247,158 B1
`
`FIGURE 3
`(PRIOR ART)
`
`x(n)
`
`
`
`
`%?:‘é’°"—“"n:
`\—’
`SR/ lag» y(n)
`
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 4
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 4
`
`
`
`US. Patent
`
`4
`
`lB
`
`fl.omE.
`
`
`m58:2092:20
`S"VOWGOV
`
`8:05..|2_mEmmEmMu4EMU\gucmhtInt/COOmammbhaomwm.82."mammUOUmvow
`,.9282.”.
`
`BEEmcE...
`
`.1IIIIllllllIIllIIllllllll|l|lllllllllllllllIlllll
`
`0dmfi
`
`$3:ch"528mmmamemxamfiumSum
`
`.no
`
`U
`
`%...........................................................lumvmv
`6.,"mmmv
`
`nmmvmummnoo3838mm
`_a.330Smammagnum.UnEBMynaggoomm
`
`
`.w938:3"9..com
`
`vMEDOE
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 5
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 5
`
`
`
`
`US. Patent
`
`Jun. 12, 2001
`
`Sheet 5 of 8
`
`US 6,247,158 B1
`
`9.32ch
`
`<.2520m.EccmcomEmEQkamnmqm.
`
`
`
`mommummfiQO“‘0mammaam.
`
`gm$8
`
`mm.
`
`FEamomm
`
`-----...---- --_------..l
`
`20333:.
`
`vam
`
`FIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII||
`
`mMEDOE
`
`
`
`
`
`mammboo.6<333m.mummuoU55:6ch
`
`‘
`
`-Eoomo
`
`H53
`
`9E...:oEmoa
`momFomE
`mummgaom
`
`coamonEoomm@5330
`
`
`
`voEoDEmEFmEEMEoobmgmgumm
`
`
`
`32mm
`
`mammaaom
`
`mvmm
`
`90>wo=2£mo
`
`
`
`
`
`mmmmmmmummuoobmhmsoomt
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 6
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 6
`
`
`
`
`
`
`
`US. Patent
`
`lB
`
`
`
`savage...1"55:09.830n."E<Eoummo”mmm.QBuEm"Emummboo"«vow
`
`
`
`
`1_3memEgan.m.9.2...Sagan.mcfiogmM“ESE...
`
`
`
`9985:.
`
`wmmDOE
`
`
`
`“nmccw“..........---------------:-.-.-..----------..-----b<_com..3350".vowmomSe
`
`.m@935Aamcmnm."mmemo
`
`.8$3:ch"Eamomm
`
`
`.rU.>m_mo0
`_EHI.w
`.a..83uM.60mcfioomo
`0:5.mammoSom."EEmEFm9:3998mm
`
`
`
`mmhm>mmtm§mDW_(wmmmmmammoammo$5«$00beggoomm
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 7
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 7
`
`
`
`
`US. Patent
`
`Jun. 12, 2001
`
`Sheet 7 of 8
`
`US 6,247,158 B1
`
`FIGURE 7
`
`
`
`FIGURE 8
`
`Channel A
`
`804
`
`Channel B
`
`
`
`
` Calculate:
`
`“SN FLA
`'SNFLB
`*0: and [3
`
`
`
`803
`
`Ouantizer
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 8
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 8
`
`
`
`US. Patent
`
`Jun. 12, 2001
`
`Sheet 8 of 3
`
`US 6,247,158 B1
`
`FIGURE 9
`
`Channel A
`
`x n
`(
`)A
`
`
`
`
` 904 Calculate:
`
`*SNR_A
`
`*SNFLB
`
`*0: and B
`
` Channel B
`I,
`
`x(n+1)I3
`
`FIGURE 10
`
`.0om
`
`AverageDistancemetric PPPJ:-O'JCO-I|-
`
`SNR (dB)
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 9
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 9
`
`
`
`US 6,247,158 B1
`
`1
`DIGITAL BROADCASTING SYSTEM AND
`METHOD
`
`REFERENCE TO RELATED APPLICATION
`
`R
`
`This application includes the subject matter of provisional
`application Ser. No. “#110,258 filed Nov. 30. 1998 and
`entitled DUAL CHANNEL DIVERSITY SYSTEM.
`
`The present invention relates to digital broadcasting sys-
`tems and methods which achieve multi-channel code diver-
`
`ID
`
`sity by way of decomposition of a single forward error
`corrected code (FEC).
`
`BACKGROUND OF THE INVENTION
`Introduction
`
`15
`
`2
`
`compensating for this with a comparable Tittle Delay (253)
`at the receiver. The diversity receiver has two demodulators
`(Demod—254) to receive the signals on Channel A and B
`simultaneously. Finally. the diversity receiver implements
`Combining (252) of the bits received on Channels A and B
`and Decoding (251) of the recovered code bits.
`Note that in the implementation of diversity illustrated in
`FIG. 2. encodes the data stream and places identical coded
`data streams on both A and B channels. In this case. the
`diversity receiver captures the same coded bits from each
`channel and then implements a combining scheme to come
`up with a "best" estimate for each received code bit. Such
`combining may involve ongoing calculation of a quality
`metric for data on channelsA and B and selecting the coded
`bits that are carried on the best channel at any point in time.
`Alternatively, combining may be more sophisticated in
`which the quality metric is used to generate weights for the
`code bits arriving on channels A and B and thereby con-
`structing a summed estimate that maximizes the signal to
`noise composite signal. Such an approach is referred to as
`maximum ratio combining (MRC).
`A widely used implementation of an encoder is a convo-
`lutional code. The typical construction of a convolutional
`code is illustrated in FIG. 3. The source bits are input into
`a digital shift register from the left, and the coded bits are
`constructed by a sum of the current and 6 most recent input
`source bits as weighted by a generator polynomial over a
`Galois Field. This implementation generates a rate 11‘: code
`because it outpuLs 2 code hits (s and y) for every input
`source bit.
`
`less redundant codes from
`It is customary to construct
`such a code by puncturing (deleting) output code bits in a
`particular pattern. Table I
`illustrates the construction of a
`rate 3/3 code from a rate ‘2‘». code. Three source bits are input
`and the output is 6 code bits: {x(i), yti),i-1. 3}. ”No code
`bits. x(2) and ytl) are deleted, leaving 4 output code bits for
`3 input code biLs. thus making a rate 36 code.
`
`40
`
`TABLE 1
`
`A general strategy for sending digital data reliably
`through a communications channel of varying quality is to
`send redundant information so that a stream of transmitted
`source bits can be recovered without error at a receiver even
`
`though the communications channel may be erratic. This is
`particularly important for one-way broadcasts of audio and
`multimedia that must be received in real-time with a low
`
`error rate. In such cases, a low error rate is achieved partly
`through the use of forward error correction (FEC) code.
`The mobile satellite broadcast channel is such an erratic
`
`the
`channel since. particularly at lower elevations angle.
`line-of—sight (LOS) between a mobile vehicle and the sat-
`ellite is often obstructed by trees, buildings, signs, utility
`poles and wires. Such obstructions attenuate and distort a
`communications waveform. thereby causing high error rates
`for brief and longer periods of time. A common approach to
`reliable satellite broadcasting is to implement spatial diver-
`sity by broadcasting duplicate signals from satellites at two
`different orbital locations.
`In addition. temporal diversity
`may also be used by delaying one signal by a fixed amount
`of time. Indeed, some satellite systems also rely upon
`terrestrial
`repeating of the satellite signal which is yet
`another source of diversity. FIG.
`1
`illustrates a satellite
`broadcasting system that has dual diversity from 2 satellites
`(101 and 102) and is augmented by terrestrial repeating
`(104), thereby providing 3-fold diversity. The origin of the
`satellite broadcasts is the hub station (103). Both of the
`satellites and the terrestrial repeaters broadcast the same
`source data. but the channels that the data travels over are
`different so that diversity is provided. A diversity radio in the
`vehicle (104) would in general
`receive all
`the signals
`(satellite and terrestrial) and use this to reconstruct
`the
`source data as faithful as possible based upon the reception
`from the multiple wurces.
`
`45
`
`50
`
`Current State of the Art for Diversity
`
`FIG. 2 illustrates a generic implementation of diversity
`using two channels A and B. Although the discussion here is
`limited to two channels (A and B), all of the concepts put
`forth are applicable to 3 or more diverse channels. For a .
`broadcast satellite application, signalsAand B would be sent
`by two different satellites, and the channels for those signals
`are denoted also denoted as A and B. At the outset, each
`individual channel has some diversity due to the fact that
`Encoding (201) adds redundancy to a single data stream so
`that the source bits can be recovered without error even
`
`00
`
`though limited numbers coded bits may be lost over the
`channel. Also, additional diversity (spatial) is used that
`involves modulating (Mod 204) duplicate streams of data
`over independent channels A and B. Finally. as illustrated in
`FIG. 2,1ime diversity is also used by implementing a fixed
`Time Delay (203) on signal B at
`the transmitter, and
`
`Construction of a Rate 3M Code by Puncturirtg a Rate 1"! Code
`Code Bits
`Code Bits
`Pre-punctu ring
`Post-pu nctu ring
`
`Polynomial
`
`g]
`a?
`
`x(3,t
`.vt3t
`
`xtl:
`313:
`
`1(1)
`.vtlt
`
`x(3t
`5'0!
`
`P
`at?!
`
`xttt
`P
`
`Table 2 illustrates the use ofthis rate $6 code in a standard
`implementation in which the puncturing for both A and B
`channels is identical. Therefore the coded bits on both
`channel A and B are also identical.
`
`TABLE 2
`
`Standard Implementation of a Single
`Rate 3'4 Code on Diverse Channels
`
`Channel
`
`Polynomial
`
`Code Bits
`Prat—puncturing
`
`Code Bits
`Post—puncturing
`
`A
`B
`A
`B
`
`g1
`3.1
`g2
`g2
`
`x(l:
`P
`x(3t
`x(lt
`KC!)
`x(3}
`same for Channel A same for Channel A
`H3)
`i'tlt
`,vtlt
`H31
`ytlt
`P
`same for Channel A same for Channel A
`
`The standard implementation of a punctured convolu-
`tional code implemented in the context of spatial and
`temporal diversity with dual channels is illustrated in FIG.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 10
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 10
`
`
`
`US 6,247,158 B1
`
`3
`the Convolutional Encoder (401)
`the transmitter,
`4. At
`generates the code bits from input source bits. Some of the
`code bits are deleted by the Puncture element (402) prior to
`modulation by the Mod element
`(404). The diversity
`receiver again has two demodulators {Demods—454) to
`simultaneously receive the broadcasts on both Channel A
`and B. The retrieved code bits from both A and B are input
`to the Combining element (452b) which aligns, weights and
`combines redundant information about a received bit on the
`
`two channels. The intent of most combining algorithms is to
`maximize the signal to noise ratio of the combined signal.
`After combining, the stream of recovered code bits are input
`to the De-puncture element (4520) which inserts the erasures
`into the slots of the code bits that were deleted in the
`
`Puncture element (402) of the transmitter.
`
`THE PRESENT INVENTION
`
`JD
`
`15
`
`An object of the invention is to provide an improved
`digital
`information broadcasting system and method.
`Another object of the invention is to provide code diversity
`in a digital broadcast system. Another object of the invention
`is to provide an apparatus and method of achieving diversity
`in reception of plural digital broadcast signals.
`Briefly. according to the invention a stream of a complete
`set ofcode bits is generated from one or more sources ofdata
`bits. A first Critical Subset of code bits is chosen or selected
`
`for a first channel (eg. a specified puncturing paltem is
`applied to the stream of a complete set of code sets). A
`second or alternative Critical Subset of code bits is chosen
`or selected for a second channel (e. g. a second or alternative
`puncturing pattern is chosen for the second channel}. Further
`alternative Critical Subsets maybe chosen for any additional
`channels. All the channels are transmitters, some can incor-
`poratc time delay to achieve temporal diversity. Moreover.
`the order of transmitting the code bits on each channel can ‘
`he difi'crent (for example.
`the interleaving depths can be
`dilIerent). At the receiver, the stream of Critical Subsets of
`code bits for all of the channels are simultaneously received
`and a reconstruction of a complete set of code bits accom-
`plished and the reconstructed code is inserted into a decoder.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`40
`
`4
`FIG. 9 illustrates weighting of adjacent bits x(l) and x(2)
`received on different channels, and
`
`FIG. 10 is a graph of simulation results of average
`distance metric vs. SN'R.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`FIG. 5 illustrates a generic example of the invention. At
`the transmitter, the source bits enter a single Encoder (501)
`in which a set of output code bits are generated from a set
`of input source bits. For explanation purposes, the whole set
`of output code bits will be referred to as the Complete Set.
`The Encoder sends the Complete Set
`to the Code Bil
`Decomposition (CBD) functional element (502}. The CBD
`decomposes the Complete Set into two Critical Subsets A
`and B. The Subsets are called critical, because even if the
`receiver faithfully captures only one of the subsets, this is
`sufiicient to regenerate the original source bits. The Subsets
`Aand B may be totally disjoint (i.e.. share no common code
`bits of the Complete Set) or may contain some common
`elements of the Complete Set. Note that the critical difi'er-
`ence between the transmitter system in FIG. 5 vs.
`that of
`FIG. 2 is that the code bits sent on Channels A and B are not
`identical.
`
`the receiver, the each stream of code bits on both
`At
`Channels A and B are captured and input to the Code Bit
`Recomposition and Combining (CBRC) element (552). The
`CBRC faithfully assembles the Complete Set to the maxi-
`mum extent possible via a process of weighting and com-
`bining received information. The CBRC then sends the
`recovered code bits to Decoding element (551). For each
`transmitted code bit there are 3 alternative outcomes at the
`receiver. Table 3 explains the causes and receiver behavior
`for each alternative:
`
`The scope of the invention illustrated in FIG. 5 includes
`the following concepts at the transmitter:
`
`generation of a stream of a Complete Set of code bits from
`source data bits
`
`choosing a Critical Subset ofcode bits for channel A(e.g..
`specified puncturing pattern)
`choosing an alternative Critical Subset of code bits for
`channel B (e.g., alternative puncturing pattern), and
`similarly for additional channels
`the order of transmission ofthe code bits on each channel
`can be different (e.g., dilferent interleaving depths).
`The scope of the invention includes the following con-
`cepts at the receiver:
`simultaneous reception of a stream of code bits on chan-
`nelsA and B and additional channels if present,
`reconstruction of the Complete Set of code bits in general
`accord with the logic of Tables 3 and 4 and using
`specific algorithms described below,
`insertion of reconstructed code set into a single Viterbi
`decoder.
`
`The above and other objects. advantages and features of
`the invention will become more clear when considered with
`
`the following specification and accompanying drawings
`wherein:
`
`FIG. 1 is a pictorial illustration of diversity broadcasting
`System.
`FIG. 2 illustrates a generic diversity Implementation with
`current state of the art,
`FIG. 3 illustrates a typical construction of a constraint
`length 7. rate V: convolution code,
`FIG. 4 is an illustration of diversity implementation with
`punctured convolutional code.
`FIG. 5 is an illustration ofan embodiment of the invention
`
`implementing diversity on dual channels by selecting dif-
`ferent subset of code bits for channels A and B,
`FIG. 6 is an illustration ofan embodiment of the invention
`
`implementing diversity on dual channels by selecting dif-
`ferent puncturing patterns of a single convolutional code for
`Channels A and B.
`
`FIG. 7 illustrates a pre-Viterbi diversity combining
`receiver block diagram.
`FIG. 8 illustrates weighting of bit x{l) received on both A
`and B channels,
`
`45
`
`50
`
`55
`
`00
`
`Table 4 lists the general types of combiningt’depuncturing
`and their weighting scheme that corresponds to the out-
`- comes of Table 3 above. The weighting type is a function of
`the code diversity technique used and whether a code bit was
`received on multiple channels.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 11
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 11
`
`
`
`US 6,247,158 Bl
`
`TABLE 3
`ReceiverAlternative Outcomes and Behavior of n Diversit
`
`
`
`Alternative
`
`Causes
`
`Receiver Behavior
`
`1.
`
`I.
`
`3.
`
`the code bit
`is captured
`by both
`channel
`demodulators
`
`the code bit
`is captured
`by only one
`channel
`demodulator
`
`the code bit
`is captured
`by neither
`channel
`demodulator:
`
`code bit is transmitted in both Receiver constructs a "best" estimate of
`A and B Subsets and is
`the code bit from A + B based upon
`successfully received on both
`quality indicators on each channel;
`channels
`Receiver constructs new code bit by
`combining (e.g._. adding} the recovered
`oode bits from Channel A and B. The
`recovered code bils could be weighted
`based upon quality indicators from each
`Demodulator
`code bit is transmitted in both Receiver uses the estimate of the code
`A and B Subsets but is
`bit from the single channel and weights
`successfully received on only
`is with a quality indicator for the
`one channel
`channel: Receiver uses the recovered
`code bit is in transmitted only code bit from the single channel. The
`one channel subset and is
`recovered code bits could be weighted
`successfully received on that
`based upon quality indicators from each
`channel
`Demodulator
`code bit is transmitted in both Receiver treats this code bit as a
`A and B Subsets but is not
`puncture
`successfully received on either
`channel
`code bit is transmitted in only
`one channel subset and is
`successfully received on that
`channel
`code bit is not pan of either
`subset
`
`TABLE 4
`
`WW
`
`Alternative Weighted Output Weighting Approach
`
`
`1. Received on
`a‘tth + fi‘xfina
`Channels A and B Weight the hits received on A and B wim
`0. and [5, respectively: each is n fiJnction of
`the SNR on both Channels A and B
`2A RcCeivcd on Weight the bits received on A with o: o is
`Channel A Only
`a function of the SNR on both Channels A
`and B
`ll. is
`2.13 Received on Weight the bits received on B with I}:
`Channel B Only
`a function of the SNR on both Channels A
`and B
`3. Received on
`Treat hits as Punctures
`fl
`neither Channel A
`nor B
`
`n'tt(ntA
`
`[l‘xmB
`
`It is important to note in Alternatives 2A and 2.3 of Table 50
`4 that, even though a code bit
`is received on only one
`channel,
`its weight
`is determined by the SNR on both
`channels. This is an important feature of the invention and
`yields a significant performance gain.
`
`55
`
`illustration (If an Embodiment 0f the Invention
`Umng a Convolutional Code
`
`Puncture element. The critical difference between the system
`in FIG. 6 versus that of FIG. 4 is that the puncture patterns
`on Channels A and B are dilferent.
`
`Table 5 gives an example of suitable subsets for Channel
`A and B based upon difierent puncturing of a common rate
`56 code that constructs a rate 3K: code on each channel. Note
`that the code bits for both Channel A and B are the same
`
`prior to puncturing. However. aftcr puncturing. the Channel
`FIG. 6 illustrates the invention usin a convolutional code
`at the transmitter. At the transmitter. i'IG. 6 shows a single so Acode bli subset ‘5 {x(3). Kll)‘ y{3), 542)} and the Channel
`Convolutional Encoder (601) that generates a Complete Set
`B 51]le '3 {x{3). ’12). Vizl- y(l)}. Note then that in mm
`of code bits from inputsource bits.At this point, the transmit
`example 1”} 0f the code his, “3) and 3(2), are carried by
`stream is broken into pathsA and B which undergo difierent
`both channels, while T3,“ 1)! “2)“ fl 1) and 313)! are carried
`processing. Path A. destined for Channel Ais punctured with as by only a single channel. Analysis has shown that the benefit
`of this type ofcodc diversity can improve performance by up
`a pattern (A) in the Puncture element (602) and Path B is
`to 2 dB.
`punctured with a dilferent pattern (B) by another copy of the.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 12
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 12
`
`
`
`US 6,247,158 B1
`
`7
`
`TABLE 5
`
`Example of Transmitting Difi'erent Subsets of Code Bits
`Selected for Channels A and B
`
`Channel
`
`Polynomial
`
`A
`B
`A
`B
`
`g]
`g]
`s?-
`32
`
`Code Bits
`Pte-puncturing
`
`Code Bits
`Post-puncturing
`
`x(3_]
`x(lt
`x[2j
`x(.’-J
`same as Channel A x(3_]
`5'(3t
`ytEJ
`.vtlt
`313!
`same as Channel A
`P
`
`l’
`x(2_]
`slit
`y(21
`
`x(ll
`P
`P
`y(l_]
`
`While the transmitter creates different code bit subsets
`
`and transmits them on different channels, the receiver cap-
`tures these bits and processes them in a combined process.
`Note that since the receiver may receive x(3) on both
`channel A and B, its estimate of x{3) is determined from
`X(3)A and x(3)3. Alternatively, its estimate of x(2) is based
`only on 30(2)fl since it is only received on that channel.
`However, in both cases. the weighting factors for the esti-
`mates are determined by SNR metrics for both Channel A
`and B. This is described in the next section.
`
`ID
`
`15
`
`TABLE 6
`
`Receiver Processing of Received Code Bits on Channel A and B
`to Derive Best Comrgsite Signal
`
`Channel
`
`Code Bits Post-puncturing
`
`P
`,vtl-t
`YO!
`x0:
`P
`xEBJ
`A
`_v(1 J
`y(2t
`P
`P
`s(".-.t
`KB!
`B
`v0)
`select best
`y(3)
`KO)
`x(2)
`select best
`A + B
`
`
`
`
`
`or MRC“via A‘via A“via 3‘or MRC" via B“
`
`‘Wcighted with coefficiean determined from both A and B quality metrics
`
`.
`
`DESCRIPTION OF COMBINING ALGORITHMS
`
`General Approach
`The pre-viterbi code diversity combining receiver is illus-
`trated in FIG. 7 for OPSK waveforms that are convolution-
`
`40
`
`45
`
`50
`
`involves taking the QPSK
`it
`In general,
`ally encoded.
`symbols from the Demods {754} of the difi'erent channels (A
`and B). calculating a quality (e.g.. MRC) metric, weighting
`the symbols based on this quality metric and combining the
`two signals. The calculation of the quality metric and
`weighting coemcients is carried out
`in the MRC weight
`Calculation (MWC‘) element (752%)). In general, the MWC
`calculates the quality metric and the Weights {u and B}
`based upon the input sampled code bits {XA and X3} as well
`as signal lock indicators {LA and LB} for each demodulator.
`The Combiner & Depuncture (C&D) element (752:?) uses
`the a and [3 inputs and constructs an optimum estimate for
`each code bit. The function of the C&D also includes _
`appropriate quantization of the code bit esLim ate for input of
`soft decisions into the Viterbi Decoder (751). This is an
`important
`factor because the weighting coefficient deter-
`mines the distribution of received code samples over the
`chosen quantization which in turn determines the influence
`that the input code bits have on the Viterbi metric that drives
`the decision on source bits that are the outputs of the Viterbi
`Decoder. FIGS. 8 and 9 show additional detail of the
`
`00
`
`includes quantization. FIG. 8 is
`Diversity Combiner that
`applicable to a case in which a single bit is received on both
`A and B channels. The bit stream of both A and B enter the
`
`—
`
`8
`Calculate element (804) which calculates the SNR (which is
`the quality metric for each channel). The weighting coeffi-
`cients are then calculated from the SNRs and are used to
`scale the current bit. The two resultant
`terms are then
`
`summed (803) and the sum is input to the Quantizer (802).
`The output of the Quantizer is a soft decision variable {SDV}
`that is required by the Viterbi Decoder (801). Note that a low
`weight applied to the SDV forces most of the out put values
`of Quantiaer to be in the bins closest to zero and in this way.
`the influence on the “term metric is felt and drives the
`
`decoding of source bits.
`FIG. 9 is applicable to a case in which a single bit is
`received on only one channel.
`In this example. x{n)A is
`received on Channel A and x(n+l)3, an adjacent bit. is
`received on Channel B. AS in the Combiner in FIG. 8, the
`Calculate element (904) calculates the SNR of each channel
`based upon the input bit stream. The weighting coefficients
`are again calculated from the SNRs and are used to scale the
`current bit.
`In contrast with the case in FIG. 8. after
`weighting.
`the bits are then serially put into a Quantizer
`{902). Note that the effect of a low weight is to drive the
`quantizer to the levels closest to 0 so that the impact on the
`metric of the Viterbi Decoder (901) is minimized. This is the
`way that the weighting has its impact on the decoded source
`bits even though the weightng is applied to different
`(adjacent and nearby) bits rather than the same bits as in the
`system in FIG. 8.
`The detailed weighting algorithm (and its calculation) can
`be performed in several different ways. The approach given
`is described below is based on a Maximal Ratio Combining
`(MRC) algorithm. Let SNR,‘ and SNRB represent the Signal
`to Noise Ratio of the A and B Channels. respectively.
`Assuming that the OPSK symbols are normalized. the MRC
`weight for the early channel. (1.. is the following.
`
`1
`awn,
`a 3 sum ”may 2 I ”Norway
`
`It can be shown that in this case. the MRC weight for the
`late channel, B. is simply
`[int—u.
`
`Algorithm Background
`Soft Decision Variable
`
`The QPSK Demodulator uses 2’s complement format or
`equivalent in most of calculations. The output of the QPSK
`Demodulalor may be quantized to a 4 bit Soft Decision
`Variable (SDV) to minimize the memory requirements. The
`optimum method of quantizing (for the Viterbi Decoder) is
`to represent it symmetrically about the null value. so that
`there are equal number of levels representing "ones" and
`“zeros". A typically representation for SUV is odd integer
`which is illustrated in Table 7. It is also optimum to clip the
`Viterbi Decoder input signal at the AGC level. However, for
`proper weighting of and SDV clipping should be imple-
`mented after the MRC weighting. Therefore, the output of
`the QPSK Demod should be clipped at twice the AGC level.
`Distance Metric
`The distance metric. d. is a measurement of the distance
`from the “hard decisions" (i.e. +f—AGC level). Table 7
`illustrates the distance metric relationship to the SDV,
`assuming it is clipped to twice the AGC level:
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 13
`
`Petitioner Sirius XM Radio Inc. - Ex. 1003, p. 13
`
`
`
`US 6,247,158 B1
`
`10
`
`TABLE 7
`
`Binary Formats
`
`Binary Ofi'set
`Soft Dec. “11'.
`Distance
`
`I}
`-]5
`3
`
`l
`-13
`2
`
`2
`-11
`1
`
`3
`-‘J
`[J
`
`"F
`o
`5
`4
`-? -S -3 -1
`U
`l
`2
`3
`
`1
`l
`3
`
`9
`3
`2
`
`1E]
`
`l]
`'l'
`U
`
`12
`9
`D
`
`13
`l]
`J
`
`14
`13
`3
`
`15
`15
`4
`
`Let the variable, ma, be the mean distance metric of a Soft
`Decision Variables (SDV). For high SNR, d is approxi-
`mately a Rayleigh random variable with one degree of
`freedom. It can be shown that under this case. the relation-
`ship between d and SNR is:
`
`,1
`SNR = 1 '1
`“mo.
`
`For an arbitrary value of X, let SNR-X3
`Then the relationship between g and md for the case of high
`SNR is
`
`s-tosrzm-etogrno
`
`The above calculation shows the basic relationship
`between g and mi, but
`it does not take into account the
`effects of a) clipping and quantizing of the SDV or b)
`non-Rayeigh {and non-trivial) Distribution at
`low SNRs.
`Therefore, for a more accurate relationship, empirical analy-
`sis is required over the SNR range of interest. For the
`above-mentioned algorithm and over the SNR range of —3 to
`15 dB. the analysis shows that relationship between g and d
`is close to linear and monotonic (see FIG. 10). This implies
`that a simple Look Up Table (LUT) is suitable for the
`conversion from n't(I to g.
`Computing MRC Weighting factors
`'lhe calculation of the MRC Weighting factors {oand [3)
`are based primary from SNR variables (gA and g3) described
`in previous sections. FIG. 7 illustrates a possible use of the
`Lock indicators in this computation. The lock indicator
`would override the SNR variable by setting it to the mini-
`mum value (e.g.. g -logJ(SNRm,.,,} } and cause the equivalent
`of an erasure.
`The key assumption to this algorithm discussion is that
`each QPSK Demodulator has a coherent digital automatic
`
`15
`
`JD gain control (AGC). This is primarily required for optimum
`QPSK Demodulator and Viterbi Decoder performance. It
`also has the added benefit of normalizing the desired signal
`power. This allows the MRC weight to be based on the SNR
`(i.e., liq: or mci’o2) rather than to in: metric.
`Columns 1—3 of Table 8 demonstrate several approaches
`ot'generating weighting factors based on SNR. The selection
`of the best method depends primarily on a) the possible
`weighting approaches described in Table 4, b) the SDV
`format and c) the implementation of the Viterbi decoder.
`Method 1 employs a relative [to SNR] weighting scheme
`that normalizes the combined output symbol. It is best suited
`to cases when a code bit is present on both channel A and B.
`Method 2 is similar to Method 1 except
`that
`it always
`weights the channel with the highest SNR by a factor of 1.
`This method is best suited for case when the code bit is only
`present on a single channel (i.e., only Channel A or B).
`Method 3 weights the code bits of a given channel based
`only on the SNR of that channel. To simply the calculation,
`an arbitrary upper limit
`(SNRMM)
`is used to limit
`the
`weighting factor values. Typically. SNR“... is set at a level
`where diversity is not required (i.e., the decoder is virtually
`error free with code bits from a single channel). This method
`has the advantage of applying the weights immediately and
`therefore not requiring memory if time diversity is used (see
`FIG. 6).
`Table 8 (Column 4) also illllslt'ales efiicient formulas for
`calculating the MRC Weighting factors to. and [3) from SNR
`variables (g, and g3) for each ofthe methods. Each formula
`is based on the difference between 3“ and gs. Again a simple
`LUT can be used instead of direct calculation.
`
`‘
`
`40
`
`TABLE 8
`
`Alter-n ative weighting factors
`
`Method Description
`
`General Algorithm
`
`Etficient Formula
`
`1
`
`[J
`
`Normalized Relative
`“13h“
`
`SNRA
`“ 2 sum + SNR];
`
`1
`" = 1 + Kan—mt
`
`Relative Weights
`
`SNRB
`B _
`' SNRA +SNRB
`
`n E J _ (l
`
`For SNRA é SNRB
`tr - SNRAISN'RB Ii - 1
`For SNRA a SNRB
`a = 1 [1 = SNRBISNRA
`
`For g 5 $5
`rr - X“*"‘3 {it - 1
`For g...
`:- SB
`n=1|1=xgfi'3*
`
`Absolute Weights
`
`
`SN'RA
`" = 3m“,
`
`a _
`
`xta—fmu
`