Perki~
`Coie
`
`11988 El Camino Real, Suite 200
`
`San Diego, CA 92130-3334
`
`PHONE, 858.y20.5700
`
`FAX, 858.720.5799
`
`www.perkinscoie.corn
`
`March 28, 2011
`
`Attorney Docket No.: 09081-8025.US01/CIT 3220-C-C-C
`
`Commissioner for Patents
`P.O. Box 1450
`Alexandria, VA 22313-1450
`
`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
`
`Assignee: California Institute of Technology
`
`Enclosed are the following papers, including those required to receive a filing date under 37
`C.P.R. § 1.53(b ):
`
`Specification
`Claims
`Abstract
`Declaration
`Drawings
`
`Pages
`13
`3
`1
`To Be Filed Later
`5
`
`Enclosures:
`Small entity statement. See 37 CPR 1.27.
`
`This application is entitled to small entity status.
`
`This application is a continuation (and claims the benefit of priority under 35 U.S.C. § 120) of
`U.S. Application Serial No. 121165,606, filed June 30, 2008, which is a continuation of U.S.
`Application Serial No. 111542,950, filed October 3, 2006, now U.S. Patent No. 7,421,032, which
`is a continuation of U.S. Application Serial No. 09/861,102, filed May 18, 2001, now U.S. Patent
`No. 7,116,710, which claims the priority of U.S. Provisional Application Serial No. 60/205,095,
`
`09081-8025.US01/LEGAL20524194.1
`
`.~. N U-: 0 :~ t'>.. G f
`
`· H f: J: ~J ;:;
`
`· 8!: !. t f V U f
`
`· 8 C•: Sf · C H l C .o. G 0
`
`!) i'.. Ll ,/), :; D:: NV f R · ;_ C 5 .~. N G f l f 5 · !',~AD: S 0 N · f\l i: '.."J
`
`-~, •:) R K
`
`::> .~ ;_ C .~ :_;:;
`
`~ N G t N: X · F 0:-: '( L /..., f'.: n · 5 .~ N [i I f. G 0
`
`· 5 .~ N f X/.\ N CIS L 0
`
`· ·:; C !.., f : !. f:
`
`· S H ,., N G Hr..._:
`
`· 'N ,., S H: N G f (j N, D.C.
`
`Hughes, Exh. 1008, p. 1
`
`
`Coie
`
`11988 El Camino Real, Suite 200
`
`San Diego, CA 92130-3334
`
`PHONE, 858.y20.5700
`
`FAX, 858.720.5799
`
`www.perkinscoie.corn
`
`March 28, 2011
`
`Attorney Docket No.: 09081-8025.US01/CIT 3220-C-C-C
`
`Commissioner for Patents
`P.O. Box 1450
`Alexandria, VA 22313-1450
`
`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
`
`Assignee: California Institute of Technology
`
`Enclosed are the following papers, including those required to receive a filing date under 37
`C.P.R. § 1.53(b ):
`
`Specification
`Claims
`Abstract
`Declaration
`Drawings
`
`Pages
`13
`3
`1
`To Be Filed Later
`5
`
`Enclosures:
`Small entity statement. See 37 CPR 1.27.
`
`This application is entitled to small entity status.
`
`This application is a continuation (and claims the benefit of priority under 35 U.S.C. § 120) of
`U.S. Application Serial No. 121165,606, filed June 30, 2008, which is a continuation of U.S.
`Application Serial No. 111542,950, filed October 3, 2006, now U.S. Patent No. 7,421,032, which
`is a continuation of U.S. Application Serial No. 09/861,102, filed May 18, 2001, now U.S. Patent
`No. 7,116,710, which claims the priority of U.S. Provisional Application Serial No. 60/205,095,
`
`09081-8025.US01/LEGAL20524194.1
`
`.~. N U-: 0 :~ t'>.. G f
`
`· H f: J: ~J ;:;
`
`· 8!: !. t f V U f
`
`· 8 C•: Sf · C H l C .o. G 0
`
`!) i'.. Ll ,/), :; D:: NV f R · ;_ C 5 .~. N G f l f 5 · !',~AD: S 0 N · f\l i: '.."J
`
`-~, •:) R K
`
`::> .~ ;_ C .~ :_;:;
`
`~ N G t N: X · F 0:-: '( L /..., f'.: n · 5 .~ N [i I f. G 0
`
`· 5 .~ N f X/.\ N CIS L 0
`
`· ·:; C !.., f : !. f:
`
`· S H ,., N G Hr..._:
`
`· 'N ,., S H: N G f (j N, D.C.
`
`Hughes, Exh. 1008, p. 1
`
`
`
`U.S. Patent & Trademark Office
`Commissioner for Patents
`Page2
`
`filed May 18, 2000, and is a continuation-in-part of U.S. Application Serial No. 09/922,852, filed
`August 18, 2000, now U.S. Patent No. 7,089,477. The disclosures of 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
`over 20
`Total Claims 14
`Independent Claims 2
`over 3
`Fee for Multiple Dependent claims
`Fee for each additional 50 pages of Specification
`and Drawings over 100
`
`Ox$26
`Ox$110
`
`(X+X-100)/50 = 0 X
`
`Total Filing fee
`
`$0
`$0
`$0
`$0
`$0
`$0
`
`$0
`
`$0
`
`Under 37 C.F.R. §1.53(j), no filing fee is being paid at this time.
`
`If this application is found to be incomplete, or if a telephone conference would otherwise be
`helpful, please call the undersigned at (858) 720-5700.
`
`Kindly acknowledge receipt of this application by returning the enclosed postcard.
`
`Please direct all correspondence to the following:
`
`97075
`PTO Customer Number
`
`Respectfully submitted,
`
`/Hwa C. Lee 59747/
`
`Hwa C. Lee
`Reg. No. 59,747
`
`Enclosures
`HCL/jjc
`
`09081-8025.US01/LEGAL20524194.1
`
`Hughes, Exh. 1008, p. 2
`
`
`
`SERIAL CONCATENATION OF INTERLEAVED
`CONVOLUTIONAL CODES FORMING TURBO-LIKE CODES
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`CROSS-REFERENCE TO RELATED APPLICATIONS
`
`[0001] This application is a continuation of U.S. Application Serial No. 121165,606, filed
`
`June 30, 2008, which is a continuation of U.S. Application Serial No. 111542,950, filed
`
`October 3, 2006, now U.S. Patent No. 7,421,032, which is a continuation of U.S.
`
`Application Serial No. 09/861,102, filed May 18, 2001, now U.S. Patent No. 7,116,710,
`
`which claims the priority of U.S. Provisional Application Serial No. 60/205,095, filed
`
`May 18, 2000, and is a continuation-in-part of U.S. Application Serial No. 09/922,852,
`
`filed August 18, 2000, now U.S. Patent No. 7,089,477. The disclosures of the prior
`
`applications are considered part of (and are incorporated by reference in) the disclosure
`
`of this application.
`
`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.
`
`09081-8025.US01/LEGAL20524229. 1
`
`1
`
`Hughes, Exh. 1008, p. 3
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`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.
`
`[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 channel150: 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 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.
`
`09081-8025.US01/LEGAL20524229. 1
`
`2
`
`Hughes, Exh. 1008, p. 4
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`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-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.
`
`[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 5A illustrates a message from a variable node to a check node on the
`
`Tanner graph of Figure 3.
`
`09081-8025.US01/LEGAL20524229. 1
`
`3
`
`Hughes, Exh. 1008, p. 5
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`[0015] Figure 5B 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.
`
`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 vis v=T0u,
`
`where T 0 is an n x k matrix, and the rate of the coder is kin.
`
`[0020] The rate of the coder may be irregular, that is, the value ofT 0 is not constant, and
`
`may differ for sub-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 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
`
`09081-8025.US01/LEGAL20524229. 1
`
`4
`
`Hughes, Exh. 1008, p. 6
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`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 then-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 50%, 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 11(1 +D). Such
`
`an accumulator may be considered a block coder whose input block [x 1, ... ,xn] and output
`
`block [y1, ... ,yn] are related by the formula
`
`n
`
`where "EB" 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.
`
`09081-8025.US01/LEGAL20524229. 1
`
`5
`
`Hughes, Exh. 1008, p. 7
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`[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, I,Ji = 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 = (ki.dfi)/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 f2
`
`information nodes are connected to two check nodes, corresponding to a repeat of q = 2,
`
`and each of the f3 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)
`
`09081-8025.US01/LEGAL20524229. 1
`
`6
`
`Hughes, Exh. 1008, p. 8
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`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 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 x0=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
`
`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
`
`..
`IS = IS-1 + !'. v(j-1) .. +i.
`i.-1
`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 (u1, ... , uk; x1, ... , Xr).
`
`a
`if.
`
`)
`
`~.i ~
`
`[0029] The rate of the nonsystematic code is
`
`09081-8025.US01/LEGAL20524229. 1
`
`7
`
`Hughes, Exh. 1008, p. 9
`
`
`
`[0030] The rate of the systematic code is
`
`a
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`[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 toR= 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) = I,ipixi- 1 to be the
`
`generating functions of these sequences. The pair (A., p) is called a degree distribution.
`
`[0033] The rate of the systematic IRA code given by the degree distribution is given by
`
`~"
`
`t l
`
`i .l (t) dt I I .l ftl dt
`
`L(x)
`
`}O
`
`•'0
`
`,
`
`')-l
`"-.;;;;'
`(
`t......·· . . · . Pj I J
`Rate = 1 + =.:::....J __ _
`)""' A. I J.
`o.....fj
`]
`
`09081-8025.US01/LEGAL20524229. 1
`
`8
`
`Hughes, Exh. 1008, p. 10
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`[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(l)
`
`satisfying p(O) + p(l) = 1, where p(O) denotes the probability of the bit being 0, p(l) 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 5A and 5B, respectively.
`
`[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
`
`where m0(u) is the log-likelihood message associated with u. If u is a check node, the
`
`. '
`lU}
`
`mh.1--+ v\
`tanh
`,.
`,.
`
`2
`
`corresponding formula is
`
`[0036] Before decoding, the messages m(w -7 u) and m(u -7 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, andy is the output of the channel code bit u, then m0(u) = log(p(u = 0 I y)/p(u =
`II y)). After this initialization, the decoding process may run in a fully parallel and local
`
`09081-8025.US01/LEGAL20524229. 1
`
`9
`
`Hughes, Exh. 1008, p. 11
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`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 -7 u).
`
`[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 { 0, E, 1}, and
`
`[0039] In the BSC, there are two possible inputs (0,1) and two possible outputs (0, 1).
`
`+oo
`m0 (u) = -~
`{
`
`if y = 0
`if y = E
`if y = 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}, and
`
`m0 (u)
`
`1-p
`log - -
`p
`1- p
`- log - -
`p
`
`if y
`
`if y
`
`0
`
`1
`
`[0040] In the A WGN, 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
`
`09081-8025.US01/LEGAL20524229. 1
`
`10
`
`Hughes, Exh. 1008, p. 12
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`is assumed to be no distortion or other effects other than the addition of white Gaussian
`
`noise. In an A WGN with a Binary Phase Shift Keying (BPSK) signaling which maps 0
`
`to the symbol with amplitude ffs and 1 to the symbol with amplitude - ffs , 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 A WGN channel model.
`
`09081-8025.US01/LEGAL20524229. 1
`
`11
`
`Hughes, Exh. 1008, p. 13
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`a
`
`/...2
`
`/...3
`
`/...5
`
`/...6
`
`/...10
`'All
`
`/...12
`
`/...13
`
`/...14
`
`/...16
`
`/...27
`
`/...28
`
`Rate
`
`crGA
`
`cr*
`
`(Eb/NO)*(dB)
`
`S.L. (dB)
`
`TABLE 1
`
`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.1981
`
`0.190
`
`-0.4953
`
`1.2415
`
`1.2607
`
`-0.250
`
`-0.4958
`
`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 113 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 (No) ratio in dB are given. Also listed is the Shannon limit
`
`(S.L.).
`
`09081-8025.US01/LEGAL20524229. 1
`
`12
`
`Hughes, Exh. 1008, p. 14
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`[0043] As the parameter "a" is increased, the performance improves. For example, for a
`
`= 4, the best 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 11(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.
`
`09081-8025.US01/LEGAL20524229. 1
`
`13
`
`Hughes, Exh. 1008, p. 15
`
`
`
`WHAT IS CLAIMED IS:
`
`1.
`
`An apparatus for performing encoding operations, the apparatus comprising:
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`a first set of memory locations to store information bits;
`
`a second set of memory locations to store parity bits;
`
`a permutation module to read a bit from the first set of memory locations
`
`and combine the read bit to a bit in the second set of memory locations based on a
`
`corresponding index of the first set of memory locations and a corresponding
`
`index of the second set of memory locations; and
`
`an accumulator to perform accumulation operations on the bits stored in
`
`the second set of memory locations,
`
`wherein a total number of indices of the first set of memory locations
`
`represents a variable number.
`
`2.
`
`The apparatus of claim 1, wherein the permutation module is configured to
`
`perform the combine operation to include performing mod-2 or exclusive-OR
`
`sum.
`
`3.
`
`The apparatus of claim 2, wherein the permutation module is configured to
`
`perform the combining operation to further include writing the sum to the second
`
`set of memory locations based on a corresponding index.
`
`4.
`
`The apparatus of claim 1, wherein the accumulator is configured to perform the
`
`accumulation operation to include a mod-2 or exclusive-OR sum of the bit stored
`
`in a prior index to a bit stored in a current index based on a corresponding index
`
`of the second set of memory locations.
`
`09081-8025.US01/LEGAL20524229. 1
`
`14
`
`Hughes, Exh. 1008, p. 16
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`5.
`
`The apparatus of claim 4, wherein the accumulator is configured to perform the
`
`accumulation operation to at least 2 consecutive indices of the second set of
`
`memory locations.
`
`6.
`
`The apparatus of claim 1, wherein the permutation module further comprises a
`
`permutation information module to generate pairs of an index of the first set of
`
`memory locations and an index of the second set of memory locations.
`
`7.
`
`The apparatus of claim 6, wherein at least one index of the second set of memory
`
`locations is used twice.
`
`8.
`
`A method of performing encoding operations, the method comprising:
`
`receiving a sequence of information bits from a first set of memory
`
`locations;
`
`performing an encoding operation using the received sequence of
`
`information bits as an input, said encoding operation comprising:
`
`reading a bit from the received sequence of information bits, and
`
`combining the read bit to a bit in a second set of memory locations
`
`based on a corresponding index of the first set of memory locations for the
`
`received sequence of information bits and a corresponding index of the second set
`
`of memory locations; and
`
`accumulating the bits in the second set of memory locations,
`
`wherein a total number of indices of the first set of memory locations
`
`corresponding to the received sequence of information bits is a variable number.
`
`09081-8025.US01/LEGAL20524229. 1
`
`15
`
`Hughes, Exh. 1008, p. 17
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`9.
`
`The method of claim 8, wherein performing the combine operation comprises
`
`performing mod-2 or exclusive-OR sum.
`
`10.
`
`The method of claim 9, wherein performing the combine operation comprises
`
`writing the sum to the second set of memory locations based on a corresponding
`
`index.
`
`11.
`
`The method of claim 8, wherein performing the accumulation operation
`
`comprises performing a mod-2 or exclusive-OR sum of the bit stored in a prior
`
`index to a bit stored in a current index based on a corresponding index of the
`
`second set of memory locations.
`
`12.
`
`The method of claim 8, wherein the accumulation operation is performed to at
`
`least 2 consecutive indices of the second set of memory locations.
`
`13.
`
`The method of claim 8, wherein the combining operation comprises generating
`
`pairs of an index of the first set of memory locations and an index of the second
`
`set of memory locations.
`
`14.
`
`The method of claim 13, wherein at least one index of the second set of memory
`
`locations is used twice.
`
`09081-8025.US01/LEGAL20524229. 1
`
`16
`
`Hughes, Exh. 1008, p. 18
`
`
`
`U.S. Patent Application
`Docket No.: 09081-8025.US01
`
`ABSTRACT OF THE DISCLOSURE
`
`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.
`
`09081-8025.US01/LEGAL20524229. 1
`
`17
`
`Hughes, Exh. 1008, p. 19
`
`
`
`Docket No. 09081-8025.US01
`Applicant: Hui Jin et al.
`SERIAL CONCATENATION OF INTERLEAVED
`CONVOLUTIONAL CODES FORMING TURBO-LIKE CODES
`
`1/5
`
`~ ,.._
`\..
`
`C'J
`UJ
`Cl
`C)
`(..)
`UJ
`Cl
`
`i
`
`C\J
`,.._
`,.._
`\..
`
`""t
`,.._
`C)
`\..
`
`co
`,.._
`C)
`\..
`
`C'J
`UJ
`Cl
`C)
`(..)
`
`a...
`
`\..
`
`.,....--
`UJ
`Cl
`C)
`(..)
`UJ
`Cl
`
`i
`
`\..
`
`l3NNVH8
`
`~
`,.._
`\..
`
`C)
`,.._
`,.._
`\..
`
`.,....--
`UJ
`Cl
`C)
`(..)
`
`~ ~
`
`Hughes, Exh. 1008, p. 20
`
`
`
`Docket No. 09081-8025.US01
`Applicant: Hui Jin et al.
`SERIAL CONCATENATION OF INTERLEAVED
`CONVOLUTIONAL CODES FORMING TURBO-LIKE CODES
`
`2/5
`
`r.
`
`0:::
`UJ z
`z -
`
`"'
`~ 1'5
`
`a...
`
`r.
`
`~ !'>
`
`0:::
`UJ r
`::::::>
`C)
`
`J
`
`_)
`
`,_)
`
`0
`0
`<(
`
`~ "'
`
`:2:
`C!J
`Cl
`_J
`
`~r--.::l
`
`"'
`.::2 i'::l
`
`~r--.
`
`.::2 I'
`
`Hughes, Exh. 1008, p. 21
`
`
`
`Docket No. 09081-8025.US01
`Applicant: Hui Jin et al.
`SERIAL CONCATENATION OF INTERLEAVED
`CONVOLUTIONAL CODES FORMING TURBO-LIKE CODES
`
`3/5
`
`Check Node
`degree a
`
`•
`•
`
`•
`•
`
`----·
`
`----·
`
`Variable Node
`Fraction of nodes
`degree i
`"--,
`,
`'
`I~
`·---t~
`lu1
`I
`e
`e
`
`: . ~
`·-~
`302
`\,_,/
`
`I
`I
`I
`
`I
`I
`I
`
`I
`
`I
`
`3?~~
`: . ~
`
`f2
`
`f3
`
`fj
`
`e
`e
`
`I
`I
`I
`I
`
`I
`I
`I
`I
`
`·---~~
`,
`... _ ....
`'
`• •
`·---t:d6
`: . ~
`·---~·-: ~ \~ \
`
`\
`
`I
`
`I
`
`I
`
`.... _ ....
`,
`'
`
`I
`
`FIG. 3
`
`Hughes, Exh. 1008, p. 22
`
`
`
`Docket No. 09081-8025.US01
`Applicant: Hui Jin et al.
`SERIAL CONCATENATION OF INTERLEAVED
`CONVOLUTIONAL CODES FORMING TURBO-LIKE CODES
`
`4/5
`
`@--------
`
`FIG. 5A
`
`304
`
`w
`
`v
`
`304
`
`FIG. 58
`
`Hughes, Exh. 1008, p. 23
`
`
`
`Docket No. 09081-8025.US01
`Applicant: Hui Jin et al.
`SERIAL CONCATENATION OF INTERLEAVED
`CONVOLUTIONAL CODES FORMING TURBO-LIKE CODES
`
`5/5
`
`~
`
`- - - - - - - - - -
`
`~
`
`Cl
`
`,
`
`Cl
`
`'
`
`\... IJ
`- -------7
`
`C)
`C)
`co
`
`CL
`
`a:
`-
`
`~~
`
`~
`
`- - -
`
`_____ _!_
`!
`
`Cl
`
`{ ' I
`" ./
`
`CL
`
`L ___ - - - - - -
`- - - - - - - - -
`~
`
`Cl
`
`I
`
`{ '
`" ./~
`
`CL
`
`---1------
`
`a:
`-
`
`Hughes, Exh. 1008, p. 24
`
`
`
`Electronic Acknowledgement Receipt
`
`EFSID:
`
`Application Number:
`
`9758168
`
`13073947
`
`International Application Number:
`
`Confirmation Number:
`
`8813
`
`Title of Invention:
`
`SERIAL CONCATENATION OF INTERLEAVED CONVOLUTIONAL CODES
`FORMING TURBO-LIKE CODES
`
`First Named Inventor/Applicant Name:
`
`Hui Jin
`
`Customer Number:
`
`97075
`
`Filer:
`
`Hwa C. Lee/Jennifer Canarelli
`
`Filer Authorized By:
`
`Hwa C. Lee
`
`Attorney Docket Number:
`
`09081-8025.US01
`
`Receipt Date:
`
`28-MAR-2011
`
`Filing Date:
`
`TimeStamp:
`
`21:34:31
`
`Application Type:
`
`Utility under 35 USC 111 (a)
`
`Payment information:
`
`Submitted with Payment
`
`I no
`
`File Listing:
`
`Document
`Number
`
`Document Description
`
`File Name
`
`File Size( Bytes)/
`Message Digest
`
`Multi
`Part /.zip
`
`Pages
`(ifappl.)
`
`401035
`
`1
`
`2011-03-28_Application.pdf
`
`yes
`
`24
`
`4ceec5f48c21 c43a753461 Odac289f3ae 1 b7
`685c
`
`Hughes, Exh. 1008, p. 25
`
`
`
`Multipart Description/PDF files in .zip description
`
`Document Description
`
`Start
`
`End
`
`Transmittal of New Application
`
`Specification
`
`Claims
`
`Abstract
`
`Drawings-only black and white line drawings
`
`1
`
`3
`
`16
`
`19
`
`20
`
`2
`
`15
`
`18
`
`19
`
`24
`
`Warnings:
`
`Information:
`
`Total Files Size (in bytes)
`
`401035
`
`This Acknowledgement Receipt evidences receipt on the noted date by the USPTO of the indicated documents,
`characterized by the applicant, and including page counts, where applicable. It serves as evidence of receipt similar to a
`Post Card, as described in MPEP 503.
`
`New A~~lications Under 35 U.S.C. 111
`If a new application is being filed and the application includes the necessary components for a filing date (see 37 CFR
`1.53(b)-(d) and MPEP 506), a Filing Receipt (37 CFR 1.54) will be issued in due course and the date shown on this
`Acknowledgement Receipt will establish the filing date of the application.
`
`National Stage of an International A~~lication under 35 U.S.C. 371
`If a timely submission to enter the national stage of an international application is compliant with the conditions of 35
`U.S.C. 371 and other applicable requirements a Form PCT/DO/E0/903 indicating acceptance of the application as a
`national stage submission under 35 U.S.C. 371 will be issued in addition to the Filing Receipt, in due course.
`
`New International A~~lication Filed with the USPTO as a Receiving Office
`If a new international application is being filed and the international application includes the necessary components for
`an international filing date (see PCT Article 11 and MPEP 181 0), a Notification of the International Application Number
`and of the International Filing Date (Form PCT/R0/1 OS) will be issued in due course, subject to prescriptions concerning
`national security, and the date shown on this Acknowledgement Receipt will establish the international filing date of
`the application.
`
`Hughes, Exh. 1008, p. 26
`
`
`
`u d
`h p
`n er t e aperwor k R d e uct1on A ct o t 995, no persons are requ1re
`to respon
`PATENT APPLICATION FEE DETERMINATION RECORD
`Substitute for Form PT0-875
`
`PTO/SB/06 (07-06)
`Approved for use through t/3t/2007. OMB 065t -0032
`U.S. Patent and Trademark Office; U.S. DEPARTMENT OF COMMERCE
`II
`f. f
`I
`d'
`I
`I'd OMB
`I
`b
`contra num er.
`to a co ect1on o 1n ormat1on un ess 1t 1sp1ays a va 1
`Application
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
