I EBB TRANSACTIONS ON COMMUNICATIONS, VOL. 43. NO. 6, JUNE ll)95
`
`2<X)5
`
`Complementary Punctured Convolutional (CPC) Codes and Their Applications
`
`Samir Kallcl
`
`Abstract—We present in this paper a new class of punctured
`convolutions! codes that are complementary (CPC codes). A
`set of punctured convolutional codes derived from the same
`original low rate code are said to be complementary if they
`are equivalent (in terms of their distance properties) and if
`when combined yield at least the original low rate code. Based
`on these CPC codes we propose and analyze a variation of
`the type II hybrid ARQ scheme which we call type III hy­
`brid ARQ scheme. With the type III hybrid ARQ scheme,
`the starting code rate can be chosen to match the channel
`noise requirements, and like with the type II scheme, packets
`that are detected in error are not discarded, but arc combined
`with complementary transmissions provided by the transmitter
`to help recover the transmitted message. The main advantage
`is that any complementary sequence sent for a packet that
`is detected with errors is self decodable. That is the decoder
`does not have to rely on previously received sequences for the
`same data packet for decoding, as is generally the case with
`incremental redundancy ARQ schemes. This feature is desirable
`especially in situations where a transmitted packet can be lost
`or severely damaged as a result of interference. CPC codes
`can find applications in diversity transmissions systems. A novel
`complementary diversity scheme which makes use of CPC codes
`is briefly discussed.
`
`I. INTRODUCTION
`
`IN RECENT years there has been a great interest in con­
`
`volutional codes and their use in modern communication
`
`systems [1], [2], Convolutional codes can be used solely for
`
`forward error correction (FEC), and can be incorporated into
`
`systems using automatic repeat request (ARQ) schemes [1],
`
`A popular scheme is the so-called type II hybrid ARQ. which
`
`uses a rale 1/2 convolutional code [3|, [4], The advent of
`
`high rate punctured convolutional codes has accentuated ihe
`
`interest in convolutional coding even further, as these codes
`
`are readily decodable and yet offer substantial coding gains
`
`without sacrificing much bandwidth [5], Variable coding rate
`
`FEC schemes using a family of punctured convolutional codes
`
`derived from the same low rate code have been suggested 16].
`
`Recently, Hagenauer extended the concept of punctured
`
`convolutional codes to the generation of a family of rate-
`
`compatible punctured convolutional codes (RCPC) [7|. The
`
`rate compatibility condition insures that all coded bits of any
`
`code of the family are used by all lower rate codes. Based
`
`on these RCPC codes, Hagenauer proposed an efficient hybrid
`
`Paper approved by S, G. Wilson. Editor for Coding Theory and Applications
`
`ARQ technique 17]. In the ARQ scheme by Hagenauer, starting
`
`with the higher rate code of the family, incremental code
`
`bits are provided by the transmitter whenever it is necessary.
`
`Later, variations to Hagenauer's construction method of RCPC
`
`codes have been proposed [8] and various ARQ schemes have
`
`been suggested and analyzed [8]-[l 1], We shall refer to these
`
`schemes as incremental redundancy ARQ schemes.
`
`The main drawback of
`
`incremental redundancy ARQ
`
`schemes is that additional incremental code bits sent for a
`
`packet received with errors (or a packet that is lost) are
`
`not in general self decodable. That is the decoder must
`
`rely on both the initially transmitted packet as well as the
`
`additional incremental code bits for decoding. In situations
`
`where a packet can be lost or severely damaged as a result of
`
`interference, such as contention in multiple access protocols, it
`
`is desirable to have a scheme where any additional information
`
`sent is self decodable. Note that the type II hybrid ARQ
`
`scheme possesses this property.
`
`In this paper, we present a new class of punctured con­
`
`volutional codes that are complementary (CPC codes). A
`
`set of punctured convolutional codes derived from the same
`
`original low rate code are said to be complementary if they are
`
`equivalent (in terms of their distance properties) and if when
`
`combined yield at least the original low rate code. Note that the
`
`term complementary is also used to denote convolutional codes
`
`of rate I jV in which the coded bits on two stemming branches
`
`are logical complements of each other, Based on these CPC
`
`codes we propose a variation of the type [1 hybrid ARQ
`
`scheme. With this scheme, the starting code rate can be chosen
`
`to match the channel noise requirements, and like with the type
`
`II scheme, packets that are detecled in error are not discarded,
`
`but are combined with complementary transmissions provided
`
`by the transmitter to help recover the transmitted message.
`
`Since with the proposed scheme there is an additional level
`
`for error correction as compared to the conventional type II
`
`scheme, we choose to call it type III hybrid ARQ scheme.
`
`The main advantage is that any complementary sequence sent
`
`for a packet that is detected with errors is self decodable.
`
`That is the decoder does not have to rely on previously
`
`received sequences for the same data packet for decoding, as is
`
`generally the case with incremental redundancy ARQ schemes.
`
`The performance of the proposed type III hybrid ARQ scheme
`
`is analyzed and compared to that of a conventional type II
`
`ol' the IEEE Communications Society. Manuscript received May 21, 1993;
`
`hybrid ARQ scheme over an additive white Gaussian noise
`
`revised January 15, !'JU4. This work was supported in part by the Natural
`
`Sciences and Engineering Research Council of Canada. This paper was
`
`presented at the IEEE Pacific Rim Conference on Communications, Computers
`
`and Signal Processing, Victoria, B.C. Canada.
`
`The author is wilh the Department of Electrical Engineering, University of
`
`British Columbia, Vancouver, B.C. V6T-IZ4, Canada.
`
`IEEE Log Number 0410444.
`
`(AWGN) channel.
`
`CPC codes can also find applications in frequency, code or
`
`time diversity transmissions schemes. A novel complementary
`
`diversity scheme which makes use of CPC codes is briefly
`
`discussed.
`
`0090-6778/95S<>4.00
`
`1995 IEEE
`
`Petitioner Sirius XM Radio Inc. - Ex. 1007, p. 1
`
`

`

`2006
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 43, NO. 6, JUNE I99S
`
`II. COMPLEMENTARY PUNCTURED
`CONVOLUTIONAL (CPC) CODES
`
`A. Punctured and Repetition Convolutional Codes
`
`C. Complementary Punctured Convolutional Codes
`
`Let Ci,i = 1, 2, • • • ,p, be p equivalent codes of the same
`
`rate b/V, all obtained from the same original rate 1/Vo code,
`where p = |"6y°]. Let Pi denote the perforation matrix of
`
`A rate b/V punctured convolutional code can be obtained
`
`code Cj. Define the matrix P as
`
`from a rate l/Vo,(V0 < V), code by deleting (hVo - V) bits
`from every bV0 coded bits corresponding to the encoding of
`
`b information bits by the original rate l/Vb code, according
`to a perforation pattern [5], The perforation pattern is usually
`
`represented by a "perforation matrix." The perforation matrix
`yielding a rate b/V code has V0 rows and b columns. Each
`row corresponds to one of the Vq encoded bits at the output
`of the rate 1/Vo encoder, and each column is associated to
`
`one encoding cycle. The elements of a perforation matrix are
`
`only zero's and one's, corresponding to deleting or keeping
`
`the coded bit at the output of the original rate 1/Vo encoder.
`
`For example, the perforation matrix P0 of a rate 7/8 punctured
`convolutional code of memory m = 6, obtained from a rate
`
`1/2 code is given [6] by
`
`(4)
`
`The p codes C;, i = 1,2, • • • ,p, are said to be complementary
`
`if every element of matrix P is greater or equal than one. This
`means that when complementary codes are combined together
`
`according to (4), the code obtained contains the original rate
`1/Vo code. For the case V0 = V, we have p = b, and the
`
`combined code is of rate 6/6VQ = 1/Vo, which is the original
`
`rate 1/Vo code, viewed b information bits at a time. For
`the case V0 < V, if the p matrices are chosen to satisfy (4),
`
`then some elements of P would be greater than one, and the
`
`combined code would correspond to a repetition code of rate
`
`b/pV.
`
`Pq
`
`1
`1
`1
`1
`0
` 1
`0
`1 0 0 0 1 0 1
`
`
`
`As an example, consider the rate 5/6 punctured code ob­
`
`( 1 )
`
`tained from a rate 1/2 code with perforation matrix Px given
`
`A low rate b/{bV0 + I), I > 1, repetition code can be obtained
`form a rate \/Va code by repeating I bits among every bV0
`coded bits which result from the encoding of each group of 6
`
`information bits [8]. The I bits that are repeated are determined
`
`by a well-selected repetition pattern. The repetition pattern
`is usually represented by a "repetition matrix" which has Vq
`rows and b columns. In contrast to the perforation matrix,
`
`each element of a repetition matrix is greater than or equal to
`
`one and indicates the number of repeats of the corresponding
`
`by (3). From this code, four equivalent codes, including the
`
`two with perforation matrices P2 and P.3 given by (3) can be
`constructed, as described above. Here, we have p — 2; that is
`
`two codes among all five can be combined to get a code that
`
`contains the original rate 1/2 code, but not any two such codes
`
`can serve the purpose. Take for example the two codes with
`
`perforation matrices Pi and P2. With these two codes P is
`
`P = P1 + P2 = 12 2 10
`2 10 12
`
`(5)
`
`coded bit. For example, the repetition matrix Qi of a rate 7/17
`
`Since matrix P contains some zero's, then the two codes with
`
`repetition convolutional code of memory rn = 8, obtained
`
`from a rate 1/2 code is given [8] by
`
`perforation matrices Pi and P2 do not satisfy the comple­
`mentarity criterion. However, the two codes with perforation
`
`matrices Pi and P3 are complementary as
`
`2
`
` 1
`
`1
`
`2
`
` 1
`
`1
`
`1
`
`
`
`Q i
`
`(2)
`
` 1
`
`1
`
`
`
`1
`
`1
`
`1
`
`1
`
`2
`
` 1
`
`1
`
`
`
`P = Pi + P3 •
`
`1
`
`2
`
`1
`
` 1
`
`2
`
`1
`
`1
`
`1
`
`
`
`(6)
`
`B. Equivalent Punctured and Repetition Convolutional Codes
`
`does not have any zero elements. The combined code cor­
`
`Let C'i and C2 denote two punctured or repetition codes of
`
`responding to this matrix P is a repetition code of rate 5/12.
`
`the same rate obtained from the same original rate 1/Vo code.
`
`Obviously this code is better than the former one, as it contains
`
`Ci and C2 are said to be equivalent if the b columns of the
`
`the original rate 1/2 code which was used to obtain the rate
`
`perforation or repetition matrix of one code are shifted versions
`of the b columns of the perforation or repetition matrix of
`the other code [12]. For example the three rate 5/6 codes of
`
`perforation matrices
`
`5/6 punctured code.
`
`D. Construction of a Family of Complementary
`
`Punctured Convolutional (CPC) Codes
`
`"1
`
`1
`
`1 0 0'
`
`1 0 0 1
`
`1
`
`Pi ••
`
`0
`
`1
`
` 1
`
`1
`
`1
`
`0
`
`1
`
` 0
`
`0
`
`
`
` 1
`
`
`
`The construction of a family of rate b/V CPC codes from
`
`a rate 1/Vo code is as follows:
`
`Pi =
`
`ft =
`
`0 0 1 1 r
`
`1 1 1 0 0
`
`(3)
`
`are equivalent. Equivalent codes have the same distance prop­
`
`erties and they hence yield the same error correction per­
`
`1) Select a perforation pattern Pi that yields the best non-
`
`catastrophic rate b/V code. The selection criterion is
`based on maximal free distance (diTex.) and minimal
`number of incorrect paths at (ifree-
`2) Obtain from P\ the b equivalent perforation patterns
`
`formance [12]. With a perforation or repetition matrix of b
`
`columns, one can construct at most b distinct codes that are
`equivalent.
`
`Pi,i = 1,2,3,• • • b.
`3) Select p =
`among the b equivalent codes found
`above that satisfy the complementarity criterion. If 110
`
`Petitioner Sirius XM Radio Inc. - Ex. 1007, p. 2
`
`

`

`IEEK TRANSACTIONS ON COMMUNICATIONS, VOL.. 43, NO. 6. JUNE 1995
`
`2007
`
`TABLH 1
`
`RATE 2/3 PUNCTURED CONVOLUTIONAL
`
`CODES DIARIVKD FROM BLST RATE 1/3 CODE
`
`TABLH II
`
`RATI-: 3/4 PUNCIURKD CONVOLU CIONAI.
`
`CODES DERIVED FROM BP.ST RATE 1/3 CODE
`
`Original Code ( R = 1/J)
`G,
`G,
`Cn
`
`i
`
`7
`
`4
`
`25
`
`33
`
`37
`
`133
`
`145
`
`175
`
`V
`
`1
`
`u
`
`0 1
`
`U
`
`I
`
`.1
`
`P "
`i»
`i
`
`Li
`
`U
`
`X4t>8, 2-1752)
`
`jl. 10, 54. 226, 856, 3072
`
`1 >647,
`
`35vva, i I947t«, nvoyiM;
`
`(2. -1. 17. 7S, 256, $57, 3560. 131-1'),
`
`4R72(')
`
`|6. 12. 1(14. 555, 2500, i P JO.
`
`49)86. 208733, 872l72j
`
`6
`
`II, 12. 54, 197. 763 287<> 1<I752
`
`40992 154909)
`
`131. 47, 4114, 16-13. 7875. 3'454
`
`143148 6(196X4 2546KM
`
`Punctured Code (R = 2/3)
`<1,
`
`Original Code. { R = J/3)
`o3
`a i
`M
`0,
`
`Punctured Code (R = 1/4)
`(if
`
`[cn,« =
`
`(1. 4, |4. 40, | I#,. .139, 9'!|. !K'>7
`
`2
`
`25
`
`33
`
`37
`
`1
`
`0
`
`0
`
`1
`
`10 0
`
`ri
`
`ii
`
`n
`
`jo 0
`
`1
`
`[l 1 0.
`
`|6, 23, HO. 284, 1027, 3 724. 13480,
`
`4K76B. 176445, 638422)
`
`|15, 104, 540. 2536. H302, 48638,
`
`203998. 839392, 3403522.
`
`13640568]
`
`(5. 33. 137. 674. 3377, 16517,
`
`8)1152. 1986.33, 1958670, 9622756)
`
`fJ9, 180. 1130, 7026, 42350,
`
`244915. 1333836, 7693698.
`
`42190352, 228R358K9I
`
`133
`
`145
`
`175
`
`1
`
`0 0
`
`5
`
`(H. :»4, 158, 83R, 4384, 22630)
`
`'
`
`)
`
`1 0
`
`3555141
`
`[36. 214, 1385, 9287, 58644,
`
`such p codes can be constructed, discard perforation
`
`pattern I\ and repeat from 1.
`
`Property: To insure that p complementary matrices using
`
`cyclic shifts of the ft columns of matrix P( can be constructed,
`a necessary condition is that the number of one's in each row
`
`of /'] must at least be equal to
`Proof: Take any row of matrix P\, and denote the
`
`number of one's in this row by x. The number of elements
`
`greater than one in the same row of matrix P, which is obtained
`
`by combining p cyclic shifts of Pi according to (4), is less or
`
`equal than xp. Thus, if x< [M, then xp < b, which means
`
`that some elements of matrix P are zero's, and this of course
`
`violates the complementarity criterion.
`
`The choice for b,V, V'o, and hence p depends on the ap­
`
`plication where these CPC codes are to be used. Moreover,
`
`in certain applications, codes obtained from combining only a
`subset /)o, 1 < pa <p, of the p complementary codes may be
`
`used. For these applications, it is important to insure that such
`
`codes are also good.
`
`TABLH III
`
`RATH 5/6 PUNCTURF.D CONVOLUTIONAL
`
`COOKS DFKIVKD FROM BKST RATE 1/3 Com-;
`
`Original Code ( K = 1/3)
`0,
`0,
`
`M
`
`Pnnciurcd Cixle (K * 5/h)
`'if
`
`<0„,M
`
`J'
`
`[c.„ H R <f/, d/.»|,
`
`.)
`
`|
`
`2
`
`5
`
`7
`
`7
`
`2
`
`12, 26. 13), 657, 3423, 17776,
`
`0 0 "J
`1*1 0 1
`ID
`i o 0
`i (
`[l 0 0 1 oj
`
`4
`
`25
`
`33
`
`37
`
`6
`
`133
`
`145
`
`175
`
`a a"
`o
`i
`p
`0 0 0 1
`1
`[o
`)
`i
`u
`a
`
`"2215, 47B560. 2483454)
`|(>. 121. 1032, 7360. 48709.
`
`507321. 1877873. 11214275,
`65819387)
`
`It. 6. 5K. 42). 2951. 20986,
`1.19369, 1062318. 7554050.
`S3721670)
`|4, 52, 518, 5143, 46507,
`398520, 3327020, 27160749.
`217991733. 1727002951]
`
`(1. 12. 12li. 905. 7099.5625))
`['). 105. 1141. 13684. 132529.
`
`1248007]
`
`way as described in [8]. As an example, consider the two
`
`complementary matrices Pi and P:s given by (3). Starting
`with Pi, the zero's of matrix Pj are substituted by the
`
`Lemma: It is not possible to construct CPC codes from rate
`
`one's of matrix P-i,//. at a time, yielding RCC codes of rates
`
`b/V codes which are derived from rate 1 /Vo if
`
`• Vn > V.
`
`5/(6 + ih),i = 1,2, • • • . If h = 3. we get the family of RCC
`
`Proof: The proof of this lemma falls from the property
`
`codes given by matrices
`
`above. Since the number of one's per row must at least be
`
`equal to [jj], and there are Vo rows, then [£] • Vo cannot
`exceed V. As an example, CPC codes of rate 4/5 cannot
`
`be obtained from a rate 1/3 code, as here p = .'i, and
`
`FJL - V'O = « >V = 5.
`
`It should be pointed out however thaL this restriction is
`
`not quite severe, and a variety of CPC codes can indeed
`
`be constructed. We have verified that from most best known
`punctured convolutional codes of rate (2 + i)/(3 + i).i —
`0,1,2, which are derived from best-known rate 1/2 codes,
`
`complementary codes can be readily found. Using a computer
`
`' search procedure, we have found best rate 2/3, 3/4 and 5/6
`punctured codes of memory m - 2.4. and 6, obtained from
`
`( i t _
`Pi
`
`1
`
`[>(3)
`1 1
`
`(7)
`
`Lower rate compatible codes can be obtained by adding to
`
`matrix Pj'1' the elements one of yet another equivalent matrix,
`
`h at a time.
`
`III. TYPE HI HYBRID ARQ SCHEME
`
`best known rate 1/3 codes, from which CPC codes can be
`readily obtained. Results are given in Tables I, II, and III,
`
`Let Pj,i = 1,2, •••,?, denote the perforation patterns of
`
`p CPC codes of rate b/V obtained from a rate 1/Vo code,
`
`for rate 2/3, 3/4, and 5/6 codes, respectively. Best CPC codes
`
`as described above. We refer to the code with perforation
`
`derived from rate 1/4 codes, and from lower rate codes, can
`
`be readily found in the same way.
`Note that intermediate rate compatible convolutional (RCC)
`codes can be added to the set of CPC codes in the same
`
`pattern Pj as C,. The code obtained by combining j CPC
`has perforation (or repetition) matrix
`codes Citi — 1,2, • • •
`p0') = Px + P2 + • • • + Pj, and we shall refer to it by
`fOperations of the type III hybrid ARQ scheme are
`
`Petitioner Sirius XM Radio Inc. - Ex. 1007, p. 3
`
`

`

`2008
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 43, NO. 6, JUNE 1995
`
`now described. To each fc-bit
`
`information packet B to be
`
`packet is given by
`
`transmitted are appended np parity bits for error detection and
`
`m known tail bits corresponding to the memory of the encoder.
`
`The transmission State of each data packet B is described by
`a level. Each packet of n = (k+np + m) bits is encoded with
`
`the rate 1/Vo code and transmitted according to the following
`procedure.
`
`Level 1: Initially, only coded bits in Ci are sent to the re­
`
`ceiver. At the receiver end, Viterbi decoding using perforation
`
`pattern P% is applied on the received sequence. The decoded
`
`sequence, which corresponds to the information and parity
`check bits, is then examined by the error detection decoder.
`
`If this sequence is declared error-free, transmission of B is
`
`complete. Otherwise, that sequence is saved for subsequent
`
`decoding attempts and B moves to the next level.
`Level i,2 < i < p: Coded bits in C\ are sent to the receiver.
`
`Viterbi decoding is first applied on the received sequence,
`
`using perforation pattern Pj. If the decoded sequence is
`
`declared error free, transmission of B is complete. Otherwise
`
`Viterbi decoding is applied once again, but on the combination
`
`of the i sequences received up to this level, using the combined
`code CW which has perforation pattern PM = Pi + P2 +
`• • • -f 1^. If now decoding is successful, transmission of B is
`
`complete. Otherwise, the t sequences received so far are saved
`
`and B moves to the next level.
`
`Level p: Coded bits in (7,, are sent to the receiver. The same
`
`decoding process as above is performed. That is, first using
`
`only the sequence received at this level, then, if this decoding
`
`is not successful, using all received sequences available at
`the receiver. At this level, all codes have been used. Should
`
`77 = 1 4- Pr {F' 1'} + Pr {F^1', F^2'}
`+ Pr {F(1\F<2>,F<3>} + ...
`
`+ Pr{F ( l\F ( 2 ),F ( 3 ),-.-,FW} + •
`
`(8)
`
`Event F^ is equivalent to the joint event {Dd(l), Dd(i)}
`
`for i < p, and to the joint event {Dd{l),Dd{p)} for i > p.
`
`Due to the statistical dependency among the joint events
`
`{Dd(l), Dd(i)}, the exact evaluation of (8) is difficult. How­
`
`ever, we can bound each term in (8) as
`
`Pr{F(1),F(2>,...,F(i)}
`
`' P r { D d ( i ) h
`i < p
`Pr {Dd(p)}j,
`i=jp, j = 1, 2 , - -
`Pr {AKZOF Pr {Dd(jp - «)}.
`jp<i<(j + l)p,
`j = 1,2,• - • .
`
`(9)
`
`Substituting (9) into (8) and rearranging terms, we obtain
`
`w ^ ( • 1 + £Pr {^(0)) IEPr
`
`1
`
`1 = 1
`
`0
`
`p - 1
`= l + £Pr{A,(t)} r
`
`1
`
`(10)
`
`Pr{Ai(p)}'
`
`The probability Pr {Dd(i)} in (10) can be upperbounded as in
`
`decoding still fail, the received sequence in Ci is discarded
`
`[8], and thus a lower bound on the throughput can be obtained.
`
`and B moves to the next level.
`
`l^evel (p + j), j — 1,3. • • •: Coded bits in C, are sent to the
`
`receiver. If decoding in Cj is successful transmission of B is
`complete. Otherwise, decoding resumes using all p sequences
`
`available at the receiver.
`In the event that decoding is still not
`successful, the sequence received at level (j + 1) in Cj+1 is
`
`discarded and B moves to the next level.
`
`Assuming antipodal signaling over an AWGN chaiinel, we
`
`have computed the throughput of the type III hybrid ARQ
`scheme using CPC codes of rates 2/3, 3/4, and 5/6, of memory
`TO = 6, all derived from the best known rate 1/2 code. Results
`are shown on Fig. 1. The throughput curve of the conventional
`
`type II hybrid ARQ scheme is also shown on the figure. As
`
`expected, the throughput of the type III hybrid ARQ scheme is
`
`We note that the above type III scheme can be viewed as
`
`higher than that of a conventional type II hybrid ARQ scheme,
`
`the generalized type D scheme in [8j, where the number of
`
`except over a small range of SNR values.
`
`incremental code bits sent at each level per every b infor­
`
`Fig. 2 compares the throughputs of our scheme using CPC
`
`mation bits is equal to V here, with of course the additional
`
`codes of rate 3/4 and memory in = 6, derived from best known
`
`requirement that these additional bits must emanate from an
`
`rates 1/2, 1/3 and 1/4 codes. It can be seen that for low SNR
`
`equivalent and complementary code to the one used for the
`
`values, the throughput with CPC codes obtained from a low
`
`initial transmission. This makes any additional sequence sent
`
`rate code is higher than that with CPC codes obtained from
`
`for the same data packet self decodable, in the same way as
`
`with the type II hybrid ARQ scheme.
`
`A. Throughput Evaluation
`
`a higher rate code. This is due to the fact that the combined
`
`code from CPC codes derived from a lower rate code is better
`
`than from those derived from a higher rate code.
`
`The type III hybrid ARQ scheme is quite flexible,
`
`and
`
`offers many variations. The starting code rate can be chosen '
`
`The throughput ?j is defined as R/N where R is the code
`
`to overcome the nominal noise always present on the channel,
`
`rate and N is the average number of packets transmitted per
`correctly decoded packet. Let F'*' denote the event {decoding
`
`and as the channel degrades, a useful throughput is maintained
`due to the transmission of complementary coded sequences.
`
`failure at level i of the ARQ scheme, i.e., after receiving i
`
`For time varying channels, the code rate used with the type III
`
`sequences for a given data packet}. Let Dd(j),j = 1,2,3, • • •,
`
`hybrid ARQ scheme can be made adaptive accordingly to the
`
`denote the event {decoded sequence in C^\ obtained by
`
`channel conditions. That is during good channel conditions, a
`
`combining j equivalent codes, is detected with errors}. The
`average number of packets transmitted per correctly decoded
`
`high code rate can be used, and as the channel degrades, the
`code rate can be lowered accordingly.
`
`Petitioner Sirius XM Radio Inc. - Ex. 1007, p. 4
`
`

`

`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 43, NO. 6, JUNE 1995
`
`2009
`
`terms of their distance properties) and if when combined yield
`
`at least the original low rate code. Based on these CPC codes
`
`we have proposed and analyzed a so called type III hybrid
`ARQ scheme. With the type III hybrid ARQ scheme, the
`
`starting code rate can be chosen to match the channel noise
`requirements, and like with the type II scheme, packets that
`are detected in error are not discarded, but are combined with
`
`complementary transmissions provided by the transmitter to
`
`help recover the transmitted message. The main advantage
`
`is that any complementary sequence sent for a packet that
`is detected with errors is self-decodable. That is the decoder
`
`does not have to rely on previously received sequences for
`
`the same data packet for decoding, as is generally the case
`
`with incremental redundancy ARQ schemes. This feature is
`
`desirable especially in situations where a transmitted packet
`can be lost or severely damaged as a result of interference.
`
`The code rate used with the type III hybrid ARQ scheme can
`
`be made adaptive according to the channel conditions. That is
`
`during good channel conditions, a high code rate can be used,
`
`and as the channel degrades, the code rate can be lowered
`
`accordingly.
`
`CPC codes can find applications in diversity transmissions
`systems. Assume that t channels are available for frequency,
`
`code or time diversity transmissions. In conventional diversity
`
`transmissions techniques the same packet (encoded or not) is
`
`sent over t channels, and a combining scheme is applied on
`the t received sequences for that packet. In what we call a
`
`complementary diversity (CD) scheme, t CPC codes of rate
`
`bjV are used, one code per channel. At the receiver end the t
`
`received sequences are combined and decoded using a Viterbi
`
`algorithm based on the combined code of rate b/tV.
`
`REFERENCES
`
`[1] S. Lin and D. J. Costello, Error Control Coding: Fundamentals and
`
`Applications, Englewood Cliffs, NJ: Prentice-Hal], 1985.
`
`[2] W. Wu, D. Haccoun, R. Peile, and Y, Hirata, "Coding for satellite
`
`communications," IEEE J. Select. Areas Commun., vol. JSAC-5, pp.
`
`724-748, May 1987.
`
`'
`
`[3] Y. M. Wang and S. Lin, "A modified selective type II hybrid ARQ
`
`system and its performance analysis," IEEE Trans. Commun., vol, COM-
`
`31, pp, 593-608, May 1983.
`[4] S. Kallel, "Analysis of a type II hybrid ARQ scheme with code
`
`combining," IEEE Trans. Commun., vol. 38, pp. 1133-1137, Aug. 1990.
`
`[5] J. B, Cain, G. C. Clark, and J. M. Geist, "Punctured convolutional codes
`
`of rate (n — 1 ){n and simplified maximum likelihood decoding," IEEE
`
`Trans. Inform. Theory, vol. IT-24, pp. 97-100, Jan. 1979,
`
`[6] Y. Yasuda, K. Kashiki, and Y. Hirata, "High rate punctured convolu­
`
`tional codes for soft decision Viterbi decoding," IEEE Trans. Commun.,
`
`vol. COM-32, pp. 315-319, Mar. 1984.
`
`[7] J. Hagenauer, "Rate-compatible punctured convolutional codes (RCPC
`
`codes) and their applications," IEEE Trans. Commun., vol. 36, pp.
`
`389-400, Apr. 1988.
`
`Fig. 1. Throughput of type III hybrid ARQ scheme with CPC codes derived
`from rate 1/2 codes.
`
`Type 111 from Rate-IM Code ••
`Type ID Awn Rate- i/3 Code -
`Type ID from Raie-J/2 Code -
`
`g
`S 0.6
`
`•5.0
`
`-4.0
`
`-3.0
`
`-2.0
`
`-1.0
`
`0.0
`
`1.0
`
`10
`
`3.0
`
`4.0
`
`S.O
`
`[8] S. Kallel and D. Haccoun, "Generalized type II hybrid ARQ scheme
`
`using punctured convolutional coding," IEEE Trans. Commun., vol, 38,
`
`Es/No [dbj
`
`pp. 1938-1946, Nov. 1990.
`
`Fig. 2. Throughput of type 111 hybrid ARQ scheme with rate 3/4 CPC Codes
`
`derived from rate 1/4, 1/3, and 1/2 codes.
`
`IV. CONCLUSIONS
`
`We have proposed in this paper a new class of punctured
`
`convolutional codes called CPC codes. A set of punctured
`convolutional codes derived from the same original low rate
`
`[9] S. Kallel, "Sequential decoding with an efficient incremental redundancy
`
`ARQ scheme," IEEE Trans. Commun., vol, 40, pp. 1588-1593, Oct.
`
`1992.
`110) S. Kallel and C. Leung, "An adaptive incremental redundancy selective-
`
`repeat ARQ scheme for finite buffer receivers," in Proc. INFOCOM
`1991, Miami, FL, May 1991, pp. 720-725.
`•
`[11] S. Kallcd, "Efficient hybrid ARQ protocols with adaptive forward error
`
`correction," IEEE Trans. Commun. vol. 42, pp. 281-289, Feb. 1994.
`
`[12] G, Begin and D. Haccoun, "High-rate punctured convolutional codes:
`
`Structure properties and construction techniques," IEEE Trans. Com•
`
`code are said to be complementary if they are equivalent (in
`
`rnun., vol. 37, pp. 1381-1385, Dec. 1989,
`
`Petitioner Sirius XM Radio Inc. - Ex. 1007, p. 5
`
`