FISH & RICHARDSON P.C.
`
`October 3, 2006
`
`W:K. Richardson
`!859-1951
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`Commissioner for Patents
`P.O. Box 1450
`Alexandria, VA 22313-1450
`
`STREET ADDRESS
`12390 EL CAMINO REAL
`SAN DIEGO, CALIFORNIA
`92130
`
`MAIL ADDRESS
`P.O. Box 1022
`MINNEAPOLIS, MINNESOTA
`5544Q-1022
`
`ATLANTA
`
`AUSTIN
`
`BOSTON
`
`DALLAS
`
`l
`
`DELAWARE
`
`NEW YORK
`
`SAN DIEGO
`
`SILICON VALLEY
`
`TWIN CITIES
`
`WASHINGTON, DC
`
`Presented for filing is a new continuation patent application of:
`
`Applicant: HUI JIN, AAMOD KHANDEKAR AND ROBERT J. MCELIECE
`
`Title:
`
`SERIAL CONCATENATION OF INTERLEAVED CONVOLUTIONAL
`CODES FORMING TURBO-LIKE CODES
`
`Enclosed are the following papers, including those required to receive a filing date
`under 37 CFR §1.53(b):
`
`Specification
`Claims
`Abstract
`Declaration
`Drawings
`
`Pages
`16
`6
`1
`4
`5
`
`Enclosures:
`Form PT0-1449, 3 pages, listing documents cited in the parent
`applications. Please confirm that these have been considered in this
`application by returning a copy of the Form PT0-1449 with the examiner's
`initials.
`Statement re Power of Attorney (1 page).
`Rule 63 declaration, copy from a previous application under rule 63(d) for
`continuation or divisional only.
`Small entity statement. This application is entitled to small entity
`status.
`Postcard.
`
`This application is a continuation (and claims the benefit of priority under 35 USC
`120) of U.S. application serial no. 09/861,102, filed May 18, 2001, which claims
`priority to U.S. provisional application serial no. 60/205,095, filed May 18, 2000, and
`to U.S. application serial no. 09/922,852, filed August 18, 2000. The disclosures of
`
`CERTIFICATE OF MAILING BY EXPRESS MAIL
`
`Express Mail Label No. __ _ ~E,wV'-'7-""4""-0 1..,2:.:<.30""2""4""U""'S---
`
`Hughes, Exh. 1004, p. 1
`
`
`
`October 3, 2006
`
`W:K. Richardson
`!859-1951
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`Commissioner for Patents
`P.O. Box 1450
`Alexandria, VA 22313-1450
`
`STREET ADDRESS
`12390 EL CAMINO REAL
`SAN DIEGO, CALIFORNIA
`92130
`
`MAIL ADDRESS
`P.O. Box 1022
`MINNEAPOLIS, MINNESOTA
`5544Q-1022
`
`ATLANTA
`
`AUSTIN
`
`BOSTON
`
`DALLAS
`
`l
`
`DELAWARE
`
`NEW YORK
`
`SAN DIEGO
`
`SILICON VALLEY
`
`TWIN CITIES
`
`WASHINGTON, DC
`
`Presented for filing is a new continuation patent application of:
`
`Applicant: HUI JIN, AAMOD KHANDEKAR AND ROBERT J. MCELIECE
`
`Title:
`
`SERIAL CONCATENATION OF INTERLEAVED CONVOLUTIONAL
`CODES FORMING TURBO-LIKE CODES
`
`Enclosed are the following papers, including those required to receive a filing date
`under 37 CFR §1.53(b):
`
`Specification
`Claims
`Abstract
`Declaration
`Drawings
`
`Pages
`16
`6
`1
`4
`5
`
`Enclosures:
`Form PT0-1449, 3 pages, listing documents cited in the parent
`applications. Please confirm that these have been considered in this
`application by returning a copy of the Form PT0-1449 with the examiner's
`initials.
`Statement re Power of Attorney (1 page).
`Rule 63 declaration, copy from a previous application under rule 63(d) for
`continuation or divisional only.
`Small entity statement. This application is entitled to small entity
`status.
`Postcard.
`
`This application is a continuation (and claims the benefit of priority under 35 USC
`120) of U.S. application serial no. 09/861,102, filed May 18, 2001, which claims
`priority to U.S. provisional application serial no. 60/205,095, filed May 18, 2000, and
`to U.S. application serial no. 09/922,852, filed August 18, 2000. The disclosures of
`
`CERTIFICATE OF MAILING BY EXPRESS MAIL
`
`Express Mail Label No. __ _ ~E,wV'-'7-""4""-0 1..,2:.:<.30""2""4""U""'S---
`
`Hughes, Exh. 1004, p. 1
`
`
`
`,,
`
`FISH & RICHARDSON P.C.
`
`Commissioner for Patents
`October 3, 2006
`Page 2
`
`the prior applications are considered part of (and are incorporated by reference in)
`the disclosure of this application.
`
`Basic Filing Fee
`Search Fee
`Examination Fee
`Total Claims 24
`over20
`over3
`Independent Claims 3
`Fee for Multiple Dependent claims
`Fee for each additional 50 pages of Specification
`and Drawings over 1 00
`(16+5-100)/50 = 0 X
`
`4 x$25
`0 X $100
`
`Total Filing fee
`
`Small Large
`Entity Entity
`150
`300
`500
`250
`200
`100
`25
`50
`100
`200
`180
`360
`
`125
`
`250
`
`$150
`$250
`$100
`$100
`$0
`$0
`
`$0
`
`$600
`
`.,•
`
`A check for the filing fee is enclosed. Please apply any other required fees or any
`credits to deposit account 06-1050, referencing the attorney docket number shown
`above.
`
`If this application is found to be incomplete, or if a telephone conference would
`otherwise be helpful, please call the undersigned at (858) 678-5070.
`
`Kindly acknowledge receipt of this application by returning the enclosed postcard.
`
`Please direct all correspondence to the following:
`
`20985
`PTO Customer Number
`
`Respectfully submitted,
`BY
`~
`JOHN F. CONROY
`Harris
`REG. NO. 45,485
`32,030
`g
`Enclosures
`SCH/jhp
`1 0670991.doc
`
`Hughes, Exh. 1004, p. 2
`
`
`
`FISH & RICHARDSON P.C.
`
`October 3, 2006
`
`W:K. Richardson
`!859-1951
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`Commissioner for Patents
`P.O. Box 1450
`Alexandria, VA 22313-1450
`
`STREET ADDRESS
`12390 EL CAMINO REAL
`SAN DIEGO, CALIFORNIA
`92130
`
`MAIL ADDRESS
`P.O. Box 1022
`MINNEAPOLIS, MINNESOTA
`5544Q-1022
`
`ATLANTA
`
`AUSTIN
`
`BOSTON
`
`DALLAS
`
`l
`
`DELAWARE
`
`NEW YORK
`
`SAN DIEGO
`
`SILICON VALLEY
`
`TWIN CITIES
`
`WASHINGTON, DC
`
`Presented for filing is a new continuation patent application of:
`
`Applicant: HUI JIN, AAMOD KHANDEKAR AND ROBERT J. MCELIECE
`
`Title:
`
`SERIAL CONCATENATION OF INTERLEAVED CONVOLUTIONAL
`CODES FORMING TURBO-LIKE CODES
`
`Enclosed are the following papers, including those required to receive a filing date
`under 37 CFR §1.53(b):
`
`Specification
`Claims
`Abstract
`Declaration
`Drawings
`
`Pages
`16
`6
`1
`4
`5
`
`Enclosures:
`Form PT0-1449, 3 pages, listing documents cited in the parent
`applications. Please confirm that these have been considered in this
`application by returning a copy of the Form PT0-1449 with the examiner's
`initials.
`Statement re Power of Attorney (1 page).
`Rule 63 declaration, copy from a previous application under rule 63(d) for
`continuation or divisional only.
`Small entity statement. This application is entitled to small entity
`status.
`Postcard.
`
`This application is a continuation (and claims the benefit of priority under 35 USC
`120) of U.S. application serial no. 09/861,102, filed May 18, 2001, which claims
`priority to U.S. provisional application serial no. 60/205,095, filed May 18, 2000, and
`to U.S. application serial no. 09/922,852, filed August 18, 2000. The disclosures of
`
`CERTIFICATE OF MAILING BY EXPRESS MAIL
`
`Express Mail Label No. __ _ ~E,wV'-'7-""4""-0 1..,2:.:<.30""2""4""U""'S---
`
`Hughes, Exh. 1004, p. 3
`
`
`
`,,
`
`FISH & RICHARDSON P.C.
`
`Commissioner for Patents
`October 3, 2006
`Page 2
`
`the prior applications are considered part of (and are incorporated by reference in)
`the disclosure of this application.
`
`Basic Filing Fee
`Search Fee
`Examination Fee
`Total Claims 24
`over20
`over3
`Independent Claims 3
`Fee for Multiple Dependent claims
`Fee for each additional 50 pages of Specification
`and Drawings over 1 00
`(16+5-100)/50 = 0 X
`
`4 x$25
`0 X $100
`
`Total Filing fee
`
`Small Large
`Entity Entity
`150
`300
`500
`250
`200
`100
`25
`50
`100
`200
`180
`360
`
`125
`
`250
`
`$150
`$250
`$100
`$100
`$0
`$0
`
`$0
`
`$600
`
`.,•
`
`A check for the filing fee is enclosed. Please apply any other required fees or any
`credits to deposit account 06-1050, referencing the attorney docket number shown
`above.
`
`If this application is found to be incomplete, or if a telephone conference would
`otherwise be helpful, please call the undersigned at (858) 678-5070.
`
`Kindly acknowledge receipt of this application by returning the enclosed postcard.
`
`Please direct all correspondence to the following:
`
`20985
`PTO Customer Number
`
`Respectfully submitted,
`BY
`~
`JOHN F. CONROY
`Harris
`REG. NO. 45,485
`32,030
`g
`Enclosures
`SCH/jhp
`1 0670991.doc
`
`Hughes, Exh. 1004, p. 4
`
`
`
`Attorney's Docket No.: 06618-637002 I CIT3220-C
`
`APPLICATION
`
`FOR
`
`UNITED STATES LETTERS PATENT
`
`TITLE:
`
`SERIAL CONCATENATION OF INTERLEAVED
`CONVOLUTIONAL CODES FORMING TURBO-LIKE
`CODES
`
`APPLICANT:
`
`HUI JIN, AAMOD KHANDEKAR AND ROBERT J.
`MCELIECE
`
`CERTIFICATE OF MAILING BY EXPRESS MAIL
`
`Date of Deposit
`
`October 3 2006
`
`Hughes, Exh. 1004, p. 5
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`SERIAL CONCATENATION OF INTERLEAVED
`CONVOLUTIONAL CODES FORMING TURBO-LIKE
`CODES
`
`CROSS-REFERENCE TO RELATED APPLICATIONS
`
`[0001]
`
`This application is a continuation of U.S.
`
`application serial no. 09/861,102, filed May 18, 2001,
`
`which claims priority to U.S. provisional application
`
`serial no. 60/205,095, filed May 18, 2000, and to U.S.
`
`application serial no. 09/922,852, filed August 18, 2000.
`
`GOVERNMENT LICENSE RIGHTS
`
`[0002]
`
`The U.S. Government has a paid-up license in this
`
`invention and the right in limited circumstances to require
`
`the patent owner to license others on reasonable terms as
`
`provided for by the terms of Grant No. CCR-9804793 awarded
`
`by the National Science Foundation.
`
`BACKGROUND
`
`[0003]
`
`Properties of a channel affect the amount of data
`
`that can be handled by the channel. The so-called "Shannon
`
`limit" defines the theoretical limit of the amount of data
`
`that a channel can carry.
`
`1
`
`Hughes, Exh. 1004, p. 6
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`[0004]
`
`Different techniques have been used to increase
`
`the data rate that can be handled by a channel.
`
`"Near
`
`Shannon Limit Error-Correcting Coding and Decoding: Turbo
`
`Codes," by Berrou et al. ICC, pp 1064-1070, (1993),
`
`described a new "turbo code" technique that has
`
`revolutionized the field of error correcting codes. Turbo
`
`codes have sufficient randomness to allow reliable
`
`communication over the channel at a high data rate near
`
`capacity. However, they still retain sufficient structure
`
`to allow practical encoding and decoding algorithms.
`
`Still, the technique for encoding and decoding turbo codes
`
`can be relatively complex.
`
`[0005]
`
`A standard turbo coder 100 is shown in Figure 1.
`
`A block of k information bits is input directly to a first
`
`coder 102. A k bit interleaver 106 also receives the k
`
`bits and interleaves them prior to applying them'to a
`
`second coder 104. The second coder produces an output that
`
`has more bits than its input, that is, it is a coder with
`
`rate that is less than 1. The coders 102, 104 are
`
`typically recursive convolutional coders.
`
`[0006]
`
`Three different items are sent over the channel
`
`150:
`
`the original k bits, first encoded bits 110, and
`
`second encoded bits 112. At the decoding end, two decoders
`
`are used:
`
`a first constituent decoder 160 and a second
`
`2
`
`Hughes, Exh. 1004, p. 7
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`constituent decoder 162. Each receives both the original k
`
`bits, and one of the encoded portions 110, 112. Each
`
`decoder sends likelihood estimates of the decoded bits to
`
`the other decoders. The estimates are used to decode the
`
`uncoded information bits as corrupted by the noisy channel.
`
`SUMMARY
`
`[0007]
`
`A coding system according to an embodiment is
`
`configured to receive a portion of a signal to be encoded,
`
`for example, a data block including a fixed number of bits.
`
`The coding system includes an outer coder, which repeats
`
`and scrambles bits in the data block. The data block is
`
`apportioned into two or more sub-blocks, and bits in
`
`different sub-blocks are repeated a different number of
`
`times according to a selected degree profile. The outer
`
`coder may include a repeater with a variable rate and an
`
`interleaver. Alternatively, the outer coder may be a low(cid:173)
`
`density generator matrix (LDGM) coder.
`
`[0008]
`
`The repeated and scrambled bits are input to an
`
`inner coder that has a rate substantially close to one.
`
`The inner coder may include one or more accumulators that
`
`perform recursive modulo two addition operations on the
`
`input bit stream.
`
`3
`
`Hughes, Exh. 1004, p. 8
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`[0009]
`
`The encoded data output from the inner coder may
`
`be transmitted on a channel and decoded in linear time at a
`
`destination using iterative decoding techniques. The
`
`decoding techniques may be based on a Tanner graph
`
`representation of the code.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0010]
`
`Figure 1 is a schematic diagram of a prior ~turbo
`
`code" system.
`
`[0011]
`
`Figure 2 is a schematic diagram of a coder
`
`according to an embodiment.
`
`[0012]
`
`Figure 3 is a Tanner graph for an irregular
`
`repeat and accumulate (IRA) coder.
`
`[0013]
`
`Figure 4 is a schematic diagram of an IRA coder
`
`according to an embodiment.
`
`[0014]
`
`Figure SA illustrates a message from a variable
`
`node to a check node on the Tanner graph of Figure 3.
`
`[0015]
`
`Figure SB illustrates a message from a check node
`
`to a variable node on the Tanner graph of Figure 3.
`
`[0016]
`
`Figure 6 is a schematic diagram of a coder
`
`according to an alternate embodiment.
`
`[0017]
`
`Figure 7 is a schematic diagram of a coder
`
`according to another alternate embodiment.
`
`4
`
`Hughes, Exh. 1004, p. 9
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`DETAILED DESCRIPTION
`
`[0018]
`
`Figure 2 illustrates a coder 200 according to an
`
`embodiment. The coder 200 may include an outer coder 202,
`
`an interleaver 204, and inner coder 206. The coder may be
`
`used to format blocks of data for transmission, introducing
`
`redundancy into the stream of data to protect the data from
`
`loss due to transmission errors. The encoded data may then
`
`be decoded at a destination in linear time at rates that
`
`may approach the channel capacity.
`
`[0019]
`
`The outer coder 202 receives the uncoded data.
`
`The data may be partitioned into blocks of fixed size, say
`
`k bits. The outer coder may be an (n,k) binary linear
`
`block coder, where n > k. The coder accepts as input a
`
`block u of k data bits and produces an output block v of n
`
`data bits. The mathematical relationship between u and v
`
`is v=T0u, where T0 is an n x k matrix, and the rate of the
`
`coder is k/n.
`
`[0020]
`
`The rate of the coder may be irregular, that is,
`
`the value of T0 is not constant, and may differ for sub(cid:173)
`
`blocks of bits in the data block.
`
`In an embodiment, the
`
`outer coder 202 is a repeater that repeats the k bits in a
`
`block a number of times q to produce a block with n bits,
`
`where n
`
`qk. Since the repeater has an irregular output,
`
`different bits in the block may be repeated a different
`
`5
`
`Hughes, Exh. 1004, p. 10
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`number of times. For example, a fraction of the bits in
`
`the block may be repeated two times, a fraction of bits may
`
`be repeated three times, and the remainder of bits may be
`
`repeated four times. These fractions define a degree
`
`sequence, or degree profile, of the code.
`
`[0021]
`
`The inner coder 206 may be a linear rate-1 coder,
`
`which means that the n-bit output block x can be written as
`
`x=Trw, where Tr is a nonsingular n x n matrix. The inner
`
`coder 210 can have a rate that is close to 1, e.g., within
`
`SO%, more preferably 10% and perhaps even more preferably
`
`within 1% of 1.
`
`[0022]
`
`In an embodiment, the inner coder 206 is an
`
`accumulator, which produces outputs that are the modulo two
`
`(mod-2) partial sums of its inputs. The accumulator may be
`
`a truncated rate-1 recursive convolutional coder with the
`
`transfer function 1/(1+D). Such an accumulator may be
`
`considered a block coder whose input block [x1 , ••• ,xnl and
`
`output block [y1 , ••• ,ynl are related by the formula
`
`Y2
`
`Y3
`
`x1 ED x2
`
`x1 ED x2 E9 X3
`
`6
`
`Hughes, Exh. 1004, p. 11
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`where "ffi" denotes mod-2, or exclusive-OR (XOR), addition.
`
`An advantage of this system is that only mod-2 addition is
`
`necessary for the accumulator. The accumulator may be
`
`embodied using only XOR gates, which may simplify the
`
`design.
`
`[0023]
`
`The bits output from the outer coder 202 are
`
`scrambled before they are input to the inner coder 206.
`
`This scrambling may be performed by the interleaver 204,
`
`which performs a pseudo-random permutation of an input
`
`block v, yielding an output block w having the same length
`
`as v.
`
`[0024]
`
`The serial concatenation of the interleaved
`
`irregular repeat code and the accumulate code produces an
`
`irregular repeat and accumulate (IRA) code. An IRA code is
`
`a linear code, and as such, may be represented as a set of
`
`parity checks. The set of parity checks may be represented
`
`in a bipartite graph, called the Tanner graph, of the code.
`
`Figure 3 shows a Tanner graph 300 of an IRA code with
`
`parameters ( f1, ... , fj; a) , where fi ;;::: 0, Lifi = 1 and "a"
`
`is a positive integer. The Tanner graph includes two kinds
`
`of nodes: variable nodes (open circles) and check nodes
`
`(filled circles) . There are k variable nodes 302 on the
`
`left, called information nodes. There are r variable nodes
`
`306 on the right, called parity nodes. There are r =
`
`7
`
`Hughes, Exh. 1004, p. 12
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`(kEiifi)/a check nodes 304 connected between the information
`
`nodes and the parity nodes: Each information node 302 is
`
`connected to a number of check nodes 304. The fraction of
`
`information nodes connected to exactly i check nodes is fi.
`
`For example, in the Tanner graph 300, each of the f 2
`
`information nodes are connected to two check nodes,
`
`corresponding to a repeat of q = 2, and each of the f 3
`
`·information nodes are connected to three check nodes,
`
`corresponding to q = 3.
`
`[0025]
`
`Each check node 304 is connected to exactly "a"
`
`information nodes 302.
`
`In Figure 3, a= 3. These
`
`connections can be made in many ways, as indicated by the
`
`arbitrary permutation of the ra edges joining information
`
`nodes 302 and check nodes 304 in permutation block 310.
`
`These connections correspond to the scrambling performed by
`
`the interleaver 204.
`
`[0026]
`
`In an alternate embodiment, the outer coder 202
`
`may be a low-density generator matrix (LDGM) coder that
`
`performs an irregular repeat of the k bits in the block, as
`
`shown in Figure 4. As the name implies, an LDGM code has a
`
`sparse (low-density) generator matrix. The IRA code
`
`produced by the coder 400 is a serial concatenation of the
`
`LDGM code and the accumulator code. The interleaver 204 in
`
`8
`
`Hughes, Exh. 1004, p. 13
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`Figure 2 may be excluded due to the randomness already
`
`present in the structure of the LDGM code.
`
`[0027]
`
`If the permutation performed in permutation block
`
`310 is fixed, the Tanner graph represents a binary linear
`
`block code with k information bits (u1, ... , uk) and r parity
`
`bits (x1, ... ,xr), as follows. Each of the information bits
`
`is associated with one of the information nodes 302, and
`
`each of the parity bits is associated with one of the
`
`parity nodes 306. The value of a parity bit is determined
`
`uniquely by the condition that the mod-2 sum of the values
`
`of the variable nodes connected to each of the check nodes
`
`304 is zero. To see this, set x 0=0. Then if the values of
`
`the bits on the ra edges coming out the permutation box are
`
`(v1, ... , Vra), then we have the recursive formula
`..
`X; = 'X.;-1 + L v(j-1) . .~+.i
`
`.i-1
`
`for j
`
`1, 2, ... , r. This is in effect the encoding
`
`algorithm.
`
`[0028]
`
`Two types of IRA codes are represented in Figure
`
`3, a nonsystematic version and a systematic version. The
`
`nonsystematic version is an (r,k) code, in which the
`
`codeword corresponding to the information bits (u1, ... ,uk)
`
`is (x1, ... , Xr). The systematic version is a (k+r, k) code,
`
`in which the codeword is (ul, ... , Uki x1, ... , Xr).
`
`9
`
`Hughes, Exh. 1004, p. 14
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`[0029]
`
`The rate of the nonsystematic code is
`
`[0030]
`
`The rate of the systematic code is
`
`d + L: ... i~
`
`[0031]
`
`For example, regular repeat and accumulate (RA)
`
`codes can be considered nonsystematic IRA codes with a
`
`1
`
`and exactly one fi equal to 1, say fq = 1, and the rest
`
`zero, in which case Rnsys simplifies to R
`
`1/q.
`
`[0032]
`
`The IRA code may be represented using an
`
`alternate notation. Let Ai be the fraction of edges between
`
`the information nodes 302 and the check nodes 304 that are
`
`adjacent to an information node of degree i, and let Pi be
`
`the fraction of such edges that are adjacent to a check
`
`node of degree i+2 (i.e., one that is adjacent to i
`
`information nodes) . These edge fractions may be used to
`
`represent the IRA code rather than the corresponding node
`
`fractions. Define A (x) = LiAiXi- 1 and p (x) = LiPiXi- 1 to be
`
`the generating functions of these sequences. The pair (A,
`
`p) is called a degree distribution. For L(x) = LifiXi,
`
`10
`
`Hughes, Exh. 1004, p. 15
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`L (x) = r). (t) dt 1 r). (t) dt
`
`[0033]
`
`The rate of the systematic IRA code given by the
`
`degree distribution is given by
`
`L . Pj I jJ-1.
`Rate = 1 + _.;::..3 __ _
`(
`Lj ;.j I j
`
`[0034]
`
`"Belief propagation" on the Tanner Graph
`
`realization may be used to decode IRA codes. Roughly
`
`speaking, the belief propagation decoding technique allows
`
`the messages passed on an edge to represent posterior
`
`densities on the bit associated with the variable node. A
`
`probability density on a bit is a pair of non-negative real
`
`numbers p(O), p(1) satisfying p(O) + p(1)
`
`1, where p ( 0)
`
`denotes the probability of the bit being 0, p(1) the
`
`probability of it being 1. Such a pair can be represented
`
`by its log likelihood ratio, m = log(p(O)/p(l)). The
`
`outgoing message from a variable node u to a check node v
`
`represents information about u, and a message from a check
`
`node u to a variable node v represents information about u,
`
`as shown in Figures SA and SB, respectively.
`
`11
`
`Hughes, Exh. 1004, p. 16
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`[0035]
`
`The outgoing message from a node u to a node v
`
`depends on the incoming messages from all neighbors w of u
`
`except v.
`
`If u is a variable message node, this outgoing
`
`message is
`m (u -7 v) = L m ( w -7 u) + m0 (u)
`...... ,
`where m0 (u) is the log-likelihood message associated
`
`with u.
`
`If u is a check node, the corresponding formula is
`
`m (u -7 v)
`tanh-;:..· __ _.:;..
`2
`
`= fl tanh m (w -7 u)
`..,,...,;
`2
`
`[0036]
`
`Before decoding, the messages m(w ~ u) and m(u ~
`
`v) are initialized to be zero, and m0 (u) is initialized to
`
`be the log-likelihood ratio based on the channel received
`
`information.
`
`If the channel is memoryless, i.e., each
`
`channel output only relies on its input, and y is the
`
`output of the channel code bit u, then m0 (u) = log(p(u
`
`oly)/p(u = lly)). After this initialization, the decoding
`
`process may run in a fully parallel and local manner.
`
`In
`
`each iteration, every variable/check node receives messages
`
`from its neighbors, and sends back updated messages.
`
`Decoding is terminated after a fixed number of iterations
`
`or detecting that all the constraints are satisfied. Upon
`
`termination, the decoder outputs a decoded sequence based
`
`on the messages m(u)
`
`LWm(W ~ u).
`
`12
`
`Hughes, Exh. 1004, p. 17
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`[0037]
`
`Thus, on various channels, iterative decoding
`
`only differs in the initial messages m0 (u). For example,
`
`consider three memoryless channel models:
`
`a binary erasure
`
`channel (BEC) ;
`
`a binary symmetric channel (BSC) ; and an
`
`additive white Gaussian noise (AGWN) channel.
`
`[0038]
`
`In the BEC, there are two inputs and three
`
`outputs. When 0 is transmitted, the receiver can receive
`
`either 0 or an erasure E. An erasure E output means that
`
`the receiver does not know how to demodulate the output.
`
`Similarly, when 1 is transmitted, the receiver can receive
`
`either 1 or E. Thus, for the BEC, y E {o, E, 1}, and
`
`+oo
`ID0 (u) = -~
`{
`
`if y = 0
`if y = E
`if y = 1
`
`[0039]
`
`In the BSC,
`
`there are two possible inputs (0,1)
`
`and two possible outputs (0, 1). The BSC is characterized
`
`by a set of conditional probabilities relating all possible
`
`outputs to possible inputs. Thus, for the BSC y E {0, 1},
`
`if y = 0
`
`if
`
`y = 1
`
`13
`
`l 1- p
`
`log--
`p
`1-p
`-log-P-
`
`m0 (u) =
`
`and
`
`Hughes, Exh. 1004, p. 18
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`[0040]
`
`In the AWGN,
`
`the discrete-time input symbols X
`
`take their values in a finite alphabet while channel output
`
`symbols Y can take any values along the real line. There
`
`is assumed to be no distortion or other effects other than
`
`the addition of white Gaussian noise.
`
`In an AWGN with a
`
`Binary Phase Shift Keying (BPSK) signaling which maps 0 to
`
`the symbol with amplitude ~ and 1 to the symbol with
`
`amplitude -~, output y e R,
`
`then
`
`where N0/2 is the noise power spectral density.
`
`[ 0041]
`
`The selection of a degree profile for use in a
`
`particular transmission channel is a design parameter,
`
`which may be affected by various attributes of the channel.
`
`The criteria for selecting a particular degree profile may
`
`include, for example, the type of channel and the data rate
`
`on the channel. For example, Table 1 shows degree profiles
`
`that have been found to produce good results for an AWGN
`
`channel model.
`
`14
`
`Hughes, Exh. 1004, p. 19
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`a
`
`A.2
`
`A.3
`
`A.5
`
`A.6
`
`A.10
`
`A.11
`
`A-12
`
`A-13
`
`A-14
`
`A-16
`
`A-27
`
`A.2 8
`
`Rate
`
`crGA
`
`cr*
`
`(Eb/NO)*(dB)
`
`S.L.
`
`(dB)
`
`2
`
`0.139025
`
`0.2221555
`
`0.638820
`
`3
`
`0.078194
`
`0.128085
`
`0.160813
`
`0.036178
`
`0.108828
`
`0.487902
`
`0.333364
`
`0.333223
`
`1.1840
`
`1.J,981
`
`0.190
`
`1.2415
`
`1.2607
`
`-0.250
`
`-0.4953
`
`-0.4958
`
`TABLE 1
`
`4
`
`0.054485
`
`0.104315
`
`0.126755
`
`0.229816
`
`0.016484
`
`0.450302
`
`0.017842
`
`0.333218
`
`1.2615
`
`1.2780
`
`0.371
`
`0.4958
`
`[0042]
`
`Table 1 shows degree profiles yielding codes of
`
`rate approximately 1/3 for the AWGN channel and with a = 2,
`
`3, 4. For each sequence, the Gaussian approximation noise
`
`threshold, the actual sum-product decoding threshold and
`
`the corresponding energy per bit (Eb)-noise power (N0 ) ratio
`
`in dB are given. Also listed is the Shannon limit (S.L.).
`
`[0043]
`
`As the parameter "a" is increased, the
`
`performance improves. For example, for a = 4, the best
`
`15
`
`Hughes, Exh. 1004, p. 20
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`code found has an iterative decoding threshold of Eb/N0 =
`
`-
`
`0.371 dB, which is only 0.12 dB above the Shannon limit.
`
`[0044]
`
`The accumulator component of the coder may be
`
`replaced by a "double accumulator" 600 as shown in Figure
`
`6. The double accumulator can be viewed as a truncated
`
`rate 1 convolutional coder with transfer function 1/(1 + D
`
`+ D2) .
`
`[0045]
`
`Alternatively, a pair of accumulators may be the
`
`added, as shown in Figure 7. There are three component
`
`,codes: the "outer" code 700, the "middle" code 702, and the
`
`"inner" code 704. The outer code is an irregular
`
`repetition code, and the middle and inner codes are both
`
`accumulators.
`
`[0046]
`
`IRA codes may be implemented in a variety of
`
`channels, including memoryless channels, such as the BEC,
`
`BSC, and AWGN, as well as channels having non-binary input,
`
`non-symmetric and fading channels, and/or channels with
`
`memory.
`
`[0047]
`
`A number of embodiments have been described.
`
`Nevertheless, it will be understood that various
`
`modifications may be made without departing from the spirit
`
`and scope of the invention. Accordingly, other embodiments
`
`are within the scope of the following claims.
`
`16
`
`Hughes, Exh. 1004, p. 21
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`CLAIMS
`
`1.
`
`A method comprising:
`
`receiving a collection of message bits having a first
`
`sequence in a source data stream;
`
`generating a sequence of parity bits,.wherein each
`
`parity bit "Xj" in the sequence is in accordance with the
`
`formula
`
`where
`
`X; = X;-~ + L: v(.:i-l.)~+.i
`
`~
`
`.i-~
`
`"Xj- 1 " is the value of a parity bit "j-1," and
`a
`" I v(j-l)a+l
`i=l
`randomly chosen irregular repeats of the message bits; and
`
`is the value of a sum of "a"
`
`II
`
`making the sequence of parity bits available for
`
`transmission in a transmission data stream.
`
`2.
`
`The method of claim 1, wherein the sequence of
`
`parity bits is generated is in accordance with "a" being
`
`constant.
`
`3.
`
`The method of claim 1, wherein the sequence of
`
`parity bits is generated is in accordance with "a" varying
`
`for different parity bits.
`
`4.
`
`The method of claim 1, wherein generating the
`
`sequence of parity bits comprises performing recursive
`
`17
`
`Hughes, Exh. 1004, p. 22
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`modulo two addition operations on the random sequence of
`
`bits.
`
`5.
`
`The method of claim 1, wherein generating the
`
`sequence of parity bits comprises:
`
`generating a random sequence of bits that repeats each
`
`of the message bits one or more times with the repeats of
`
`the message bits being distributed in a random sequence,
`
`wherein different fractions of the message bits are each
`
`repeated a different number of times and the number of
`
`repeats for each message bit is irregular; and
`
`XOR summing in linear sequential fashion a predecessor
`
`parity bit and "a" bits of the random sequence of bits.
`
`6.
`
`The method of claim 5, wherein generating the
`
`random sequence of bits comprises coding the collection of
`
`message bits using a low-density generator matrix (LDGM)
`
`coder.
`
`7.
`
`The method of claim 5, wherein generating the
`
`random sequence of bits comprises:
`
`producing a block of data bits, wherein different
`
`message bits are each repeated a different number of times
`
`in a sequence that matches the first sequence; and
`
`randomly permuting the different bits to generate the
`
`random sequence.
`
`18
`
`Hughes, Exh. 1004, p. 23
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`8.
`
`The method of claim 1, further comprising
`
`transmitting the sequence of parity bits.
`
`9.
`
`The method of claim 8, wherein transmitting the
`
`sequence of parity bits comprises transmitting the sequence
`
`of parity bits as part of a nonsystematic code.
`
`10.
`
`The method of claim 8, wherein transmitting the
`
`sequence of parity bits comprises transmitting the sequence
`
`of parity bits as part of a systematic code.
`
`11. A device comprising:
`
`an encoder configured to receive a collection of
`
`message bits and encode the
`
`message bits to generate a collection of parity bits in
`
`accordance with the following Tanner graph:
`
`12.
`
`The device of claim 11, wherein the encoder is
`
`configured to generate the collection of parity bits as if
`
`a number of inputs into nodes Vi was not constant.
`
`19
`
`Hughes, Exh. 1004, p. 24
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`13.
`
`The device of claim 11, wherein the encoder
`
`comprises:
`
`a low-density generator matrix (LDGM) coder configured.
`
`to perform an irregular repeat on message bits having a
`
`first sequence in a source data stream to output a random
`
`sequence of repeats of the message bits; and
`
`an accumulator configured to XOR sum in linear
`
`sequential fashion a predecessor parity bit and "a" bits of
`
`the random sequence of repeats of the message bits.
`
`14.
`
`The device of claim 12, wherein the accumulator
`
`comprises a recursive convolutional coder.
`
`15.
`
`The device of claim 14, wherein the recursive
`
`convolutional coder comprises a truncated rate-1 recursive
`
`convolutional coder.
`
`16.
`
`The device of claim 14, wherein the recursive
`
`convolutional coder has a transfer function of 1/(1+D).
`
`17.
`
`The device of claim 12, further comprising a
`
`second accumulator configured to determine a second
`
`sequence of parity bits that defines a second condition
`
`I
`
`that constrains the random sequence of repeats of the
`
`message bits.
`
`20
`
`Hughes, Exh. 1004, p. 25
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`18. A device comprising:
`
`a message passing decoder configured to decode a
`
`received data stream that includes a collection of parity
`
`bits, the message passing decoder comprising two or more
`
`check/variable nodes operating in parallel to receive
`
`messages from neighboring check/variable nodes and send
`
`updated messages to the neighboring variable/check nodes.
`
`19.
`
`The device of claim 18, wherein the message
`
`passing decoder is configured to decode the received data
`
`stream that includes. the message bits.
`
`20.
`
`The device of claim 18, wherein the message
`
`passing decoder is configured to decode the received data
`
`stream that has been encoded in accordance with the
`
`following Tanner graph:
`
`21
`
`Hughes, Exh. 1004, p. 26
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`21.
`
`The device of claim 20, wherein the message
`
`passing decoder is configured to decode the received data
`
`stream as if a number of inputs into nodes Vi was not
`
`constant.
`
`22.
`
`The device of claim 18, wherein the message
`
`passing decoder is configured to decode in linear time at
`
`rates that approach a capacity of a channel.
`
`23.
`
`The device of claim 18, wherein the message
`
`passing decoder comprises a belief propagation decoder.
`
`24.
`
`The device of claim 18, wherein the message
`
`passing decoder is configured to decode the received data
`
`stream without the message bits.
`
`22
`
`Hughes, Exh. 1004, p. 27
`
`
`
`Attorney Docket No.: 06618-637002/CIT3220-C
`
`ABSTRACT OF THE DISCLOSURE
`
`[0048]
`
`A serial concatenated coder includes an outer
`
`coder and an inner coder. The outer coder irregularly
`
`repeats bits in a data block according to a degree profile
`
`and scrambles the repeated bits. The scrambled and
`
`repeated bits are input to an inner coder, which has a rate
`
`substantially close to one.
`
`10659463.doc
`
`23
`
`Hughes, Exh. 1004, p. 28
`
`
`
`Matter No.: 06618-637002
`Applicant(s): Hui Jin et al.
`SERIAL CONCATENATION OF INTERLEAVED
`CONVOLUTIONAL CODES FORMING TURBO-LIKE CODES
`
`Page 1 of 5
`
`~ .,.._
`\..
`
`N
`w
`Cl
`0
`c..:>
`w
`Cl
`
`\..
`
`or-
`w
`Cl
`0
`c..:>
`w
`Cl
`
`~ t
`
`t ~
`
`.,.._
`C\J
`.,.._
`\..
`
`N
`w
`Cl
`0
`c..:>
`
`c..
`
`\..
`
`13NN'v'H8
`
`~
`.,.._
`\..
`
`c
`.,.._
`.,.._
`·\..
`
`or-
`w
`Cl
`0
`c..:>
`
`"q-c
`.,.._
`\...
`
`(0 c .,.._
`\..
`
`~"
`
`(
`~ ,_
`
`Hughes, Exh. 1004, p. 29
`
`
`
`Matter No.: 06618-637002
`Applicant(s): Hui Jin et al.
`SERIAL CONCATENATION OF INTERLEAVED
`CONVOLUTIONAL CODES FORMING TURBO-LIKE CODES
`
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
