`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`Apple Inc.,
`Petitioner
`
`v.
`
`California Institute of Technology,
`Patent Owner.
`
`Case TBD
`
`DECLARATION OF JAMES A. DAVIS, PH.D.
`REGARDING U.S. PATENT NO. 7,116,710
`CLAIMS 1-8. 10-17, and 19-33
`
`Apple 1006
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`TABLE OF CONTENTS
`
`Page
`
`II. BACKGROUND ............................................................................................... 1
`III. LEGAL PRINCIPLES ..................................................................................... 4
`IV. OVERVIEW OF THE TECHNOLOGY ......................................................... 6
`A. Error-Correcting Codes in General ......................................................... 6
`B. Coding Rate ............................................................................................. 9
`C. Performance of Error-Correcting Codes ............................................... 10
`D. LDPC Codes, Turbo Codes, and Repeat-Accumulate Codes ............... 11
`E. Mathematical Representations of Error-Correcting Codes ................... 16
`F.
`Irregularity ............................................................................................. 22
`V. Overview Of Primary Prior Art References .................................................... 23
`A. Frey ....................................................................................................... 23
`B. Frey Slides ............................................................................................. 27
`C. Divsalar ................................................................................................. 29
`D. Luby ...................................................................................................... 32
`E. Luby97 ................................................................................................... 35
`F. Pfister Slides .......................................................................................... 36
`VI. PERSON OF ORDINARY SKILL IN THE ART ......................................... 37
`VII. OVERVIEW OF THE ’710 PATENT ......................................................... 37
`VIII. CLAIM CONSTRUCTION ......................................................................... 39
`A. “close to one” (Claims 1 and 3) ............................................................ 39
`IX. THE CHALLENGED CLAIMS ARE INVALID ......................................... 40
`A. Ground 1: Claims 1 and 3 Are Anticipated by Frey ............................. 40
`B. Ground 2: Claims 1-8 and 11-14 Are Obvious over Divsalar in View of
`Frey .................................................................................................... 49
`C. Ground 3: Claims 15-17, 19-22, and 24-33 Are Obvious over Divsalar
`in View of Frey and also in view of Luby97 ..................................... 73
`D. Ground 4: Claim 10 is Obvious in View of Divsalar and Frey, Also in
`View of Pfister ................................................................................... 94
`
`i
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`E. Ground 5: Claim 23 is Obvious in View of Divsalar, Frey, and Luby97,
`Also in View of Pfister ....................................................................... 96
`F. Ground 6: Claims 1 and 3 Are Anticipated by the Frey Slides ............. 96
`G. Ground 7: Claims 1-8 and 11-14 are Obvious over Divsalar in View of
`the Frey Slides .................................................................................. 105
`H. Ground 8: Claims 15-17, 19-22, and 24-33 Are Obvious over Divsalar
`in View of the Frey Slides and also in view of Luby97 ................... 125
`I. Ground 9: Claim 10 is Obvious in View of Divsalar and the Frey Slides,
`Also in View of Pfister ..................................................................... 144
`J. Ground 10: Claim 23 is Obvious in View of Divsalar, the Frey Slides,
`and Luby97, also in View of Pfister ................................................. 146
`K. Ground 11: Claims 1-8 and 11-14 are Obvious over Divsalar in view of
`Luby ................................................................................................. 146
`L. Ground 12: Claims 15-17, 19-22, and 24-33 Are Obvious in view of
`Divsalar and Luby, also in view of Luby97 ..................................... 165
`M. Ground 13: Claim 10 is Obvious Over Divsalar and in View of Luby,
`and Also in View of Pfister .............................................................. 180
`N. Ground 14: Claim 23 is Obvious Over Divsalar, Luby, and Luby97, also
`in View of Pfister ............................................................................. 183
`X. PUBLICATION STATUS OF LUBY97 ...................................................... 183
`XI. AVAILABILITY FOR CROSS-EXAMINATION ..................................... 184
`XII. RIGHT TO SUPPLEMENT ....................................................................... 185
`XIII. JURAT ........................................................................................................ 185
`
`ii
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`I, James A. Davis, Ph.D., declare as follows:
`
`1. My name is James A. Davis.
`
`II. BACKGROUND
`2.
`
`I am a Professor of Mathematics at the University of Richmond in
`
`Richmond, Virginia.
`
`3.
`
`I received a B.S. in Mathematics (with honors) from Lafayette
`
`College in 1983 and an M.S. and Ph.D. in Mathematics from the University of
`
`Virginia in 1985 and 1987, respectively.
`
`4.
`
`After receiving my doctorate, I taught for one year at Lafayette
`
`College before accepting a position at the University of Richmond as an Assistant
`
`Professor of Mathematics in 1988. I became an Associate Professor of
`
`Mathematics in 1994 and a Full Professor of Mathematics in 2001.
`
`5.
`
`Since joining the faculty of the University of Richmond in 1988, I
`
`have been engaged in research in Coding Theory, Algebra, and Combinatorics. My
`
`research has appeared in journals such as IEEE Transactions on Information
`
`Theory, the Journal of Combinatorial Theory Series A, Designs, Codes, and
`
`Cryptography, the Proceedings of the American Mathematical Society, and the
`
`Journal of Algebra.
`
`6.
`
`I have made several major contributions to the field of coding theory
`
`in wireless communication and sequence design. I co-discovered the connection
`
`1
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`between sequences with good power control and Reed-Muller codes, an important
`
`step in making OFDM communication practical. I co-discovered a technique for
`
`constructing difference sets that has been applied to constructions of bent
`
`functions. I co-wrote the paper on the non-existence of Barker arrays.
`
`7.
`
`I was a co-Principal Investigator of a $1.5 million National Science
`
`Foundation grant designed to engage undergraduates in long-term research projects
`
`in mathematics.
`
`8.
`
`I have taught mathematics courses in Calculus, Statistics, Linear
`
`Algebra, Abstract Algebra, Coding Theory, and Cryptography, among others. I
`
`have directed 12 honors projects and 76 summer research experiences for
`
`undergraduates in the general area of Coding Theory and Combinatorics.
`
`9.
`
`I spent two years (academic years 1995-96 and 2000-01) working at
`
`Hewlett-Packard Laboratories in Bristol, England. I was in a communications lab
`
`during this time, an industrial research lab focused on applications of Coding
`
`Theory to wireless communication and storage devices. I am co-inventor on 16
`
`patents based on my work during this time.
`
`10.
`
`I served as Chair of the Department of Mathematics and Computer
`
`Science 1997-2000.
`
`2
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`11.
`
`I have authored or co-authored over 50 peer-reviewed academic
`
`publications in the fields of Coding Theory, Combinatorics, Finite Geometry, and
`
`Algebra..
`
`12. A copy of my curriculum vitae is attached as Appendix A.
`
`13.
`
`I have reviewed the specification and claims of U.S. Patent No.
`
`7,116,710 (the “’710 patent”; Ex. 1001). I have been informed that the ’710 patent
`
`claims priority to a provisional application filed on May 18, 2000, and to U.S.
`
`application Ser. No. 09/922,852, filed on Aug. 18, 2000.
`
`14.
`
`I have also reviewed the following references, all of which I
`
`understand to be prior art to the ’710 patent:
`
`• Frey, B. J. and MacKay, D. J. C., “Irregular Turbocodes,” Proc.
`37th Allerton Conf. on Comm., Control and Computing,
`Monticello, Illinois, published on or before March 20, 2000
`(“Frey”; Ex. 1002.)
`
`• Frey, B. J. and MacKay, D. J. C., “Irregular Turbo-Like Codes,”
`37th Allerton Conf. on Comm., Control and Computing,
`Monticello, Illinois, published on or before September 24, 1999
`(“Frey Slides”; Ex. 1013)
`
`• D. Divsalar, H. Jin, and R. J. McEliece, “Coding theorems for
`“turbo-like” codes,” Proc. 36th Allerton Conf. on Comm., Control
`and Computing, Allerton, Illinois, pp. 201-10, March, 1999
`(“Divsalar”; Ex. 1003.)
`
`• Luby, M. et al., “Analysis of Low Density Codes and Improved
`Designs Using Irregular Graphs,” STOC ‘98, pp. 249-59,
`published in 1998 (“Luby”; Ex. 1004.)
`
`3
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`• Luby, M. et al., “Practical Loss-Resilient Codes,” STOC ‘97, pp.
`150-159, published in 1997 (Ex. 1011)
`
`• Pfister, H. and Siegel, P, “The Serial Concatenation of Rate-1
`Codes Through Uniform Random Interleavers,” 37th Allerton
`Conf. on Comm., Control and Computing, Monticello, Illinois,
`published on or before September 24, 1999 (“Pfister”; Ex. 1005.)
`
`15.
`
`I am being compensated at my normal consulting rate for my work.
`
`16. My compensation is not dependent on and in no way affects the
`
`substance of my statements in this Declaration.
`
`17.
`
`I have no financial interest in Petitioners. I similarly have no financial
`
`interest in the ’710 patent.
`
`III. LEGAL PRINCIPLES
`18.
`
`I have been informed that a claim is invalid as anticipated under Pre-
`
`AIA 35 U.S.C. § 102(a) if “the invention was known or used by others in this
`
`country, or patented or described in a printed publication in this or a foreign
`
`country, before the invention thereof by the applicant for patent.” I have also been
`
`informed that a claim is invalid as anticipated under Pre-AIA 35 U.S.C. § 102(b) if
`
`“the invention was patented or described in a printed publication in this or a
`
`foreign country or in public use or on sale in this country, more than one year prior
`
`to the date of the application for patent in the United States.” Further I have been
`
`informed that a claim is invalid as anticipated under Pre-AIA 35 U.S.C. § 102(e) if
`
`“the invention was described in … an application for patent, published under
`
`4
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`section 122(b), by another filed in the United States before the invention by the
`
`applicant for patent ….” It is my understanding that for a claim to be anticipated,
`
`all of the limitations must be present in a single prior art reference, either expressly
`
`or inherently.
`
`19.
`
`I have been informed that a claim is invalid as obvious under Pre-AIA
`
`35 U.S.C. § 103(a):
`
`
`
`if the differences between the subject matter sought to be patented and
`
`the prior art are such that the subject matter as a whole would have
`
`been obvious at the time the invention was made to a person having
`
`ordinary skill in the art to which [the] subject matter pertains.
`
`20.
`
`I understand that a claimed invention would have been obvious, and
`
`therefore not patentable, if the subject matter claimed would have been considered
`
`obvious to a person of ordinary skill in the art at the time that the invention was
`
`made. I understand that when there are known elements that perform in known
`
`ways and produce predictable results, the combination of those elements is
`
`probably obvious. Further, I understand that when there is a predictable variation
`
`and a person would see the benefit of making that variation, implementing that
`
`predictable variation is probably not patentable. I have also been informed that
`
`obviousness does not require absolute predictability of success, but that what does
`
`5
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`matter is whether the prior art gives direction as to what parameters are critical and
`
`which of many possible choices may be successful.
`
`IV. OVERVIEW OF THE TECHNOLOGY
`
`21. The ’710 patent relates to the field of channel coding and error-
`
`correcting codes. This section provides a brief introduction to channel coding and
`
`error-correcting codes, and highlights a few of the developments in the field that
`
`are relevant to the ’710 patent.
`
`A. Error-Correcting Codes in General
`
`22. Most computing devices and other digital electronics use bits to
`
`represent information. A bit is a binary unit of information that may have one of
`
`two values: 1 or 0. Any type of information, including, for example, text, music,
`
`images and video information, can be represented digitally as a collection of bits.
`
`23. When transmitting binary information over an analog communication
`
`channel, the data bits representing the information to be communicated (also called
`
`“information bits”) are converted into an analog signal that can be transmitted over
`
`the channel. This process is called modulation. The transmitted signal is then
`
`received by a receiving device and converted back into binary form. This process,
`
`in which a received analog waveform is converted into bits, is called
`
`demodulation. The steps of modulation and demodulation are shown in the figure
`
`below:
`
`6
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`
`
`Modulation, Transmission, and Demodulation
`
`24. Transmission over physical channels is rarely 100% reliable. The
`
`transmitted signal can be corrupted during transmission by “noise” caused by, for
`
`example, obstructions in the signal path, interference from other signals, or
`
`electrical/magnetic disturbances. Noise can cause bits to “flip” during
`
`transmission: for example, because of noise, a bit that was transmitted as a 1 can be
`
`corrupted during transmission and demodulated as 0, and vice versa.
`
`25. Error-correcting codes were developed to combat such transmission
`
`errors. Using the bits representing the information to be communicated (called
`
`“information bits”) an error-correcting code generates “parity bits” that allow the
`
`receiver to verify that the bits were transmitted correctly, and to correct
`
`transmission errors that occurred.
`
`26. Bits are encoded by an encoder, which receives a sequence of
`
`information bits as input, generates parity bits based on the information bits
`
`according to a particular encoding algorithm, and outputs a sequence of encoded
`
`7
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`bits (or data elements) called a codeword. The codeword produced by the encoder
`
`is then modulated and transmitted as an analog signal.
`
`27. At the receiver, the signal is received and demodulated, and the
`
`codeword is passed to the decoder, which uses a decoding algorithm to recover the
`
`original information bits.
`
`
`
`Encoding and Decoding
`
`28. Error-correcting codes work by adding redundant information to the
`
`original message. Due to redundancy, the information represented by a given
`
`information bit is spread across multiple bits of the codeword. Thus, even if one of
`
`those bits is flipped during transmission, the original information bit can still be
`
`recovered from the others.
`
`29. As a simple example, consider an encoding scheme, called “repeat-
`
`three,” that outputs three copies of each information bit. In this scheme, the
`
`information bits “1 0 1” would be encoded as “111 000 111.” Upon receipt, the
`
`decoder converts instances of “111” into “1” and instances of “000” into “0” to
`
`produce the decoded bits “1 0 1,” which match the original information bits.
`
`8
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`30. Suppose a bit is flipped during transmission, changing “000” to “010.”
`
`The decoder will be able to detect a transmission error, because “010” is not a
`
`valid “repeat-three” codeword. Using a “majority vote” rule, the decoder can infer
`
`that the original information bit was a 0, correcting the transmission error. Thus,
`
`due to the redundancy incorporated into the codeword, no information was lost due
`
`to the transmission error.
`
`31. Error-correcting codes may be either systematic or non-systematic. In
`
`a systematic code, both the parity bits and the original information bits are
`
`included in the codeword. In a non-systematic code, the encoded data only
`
`includes the parity bits.
`
`32. Systematic and non-systematic codes had been known in the art for
`
`decades prior to May 18, 2000, the claimed priority date of the ’710 patent.
`
`B. Coding Rate
`
`33. Many error-correcting codes encode information bits in groups, or
`
`blocks of fixed length n. An encoder receives a k-bit block of information bits as
`
`input, and produces a corresponding n-bit codeword. The ratio k/n is called the rate
`
`of the code. Because the codeword generally includes redundant information, n is
`
`generally greater than k, and the rate k/n of an error-correcting code is generally
`
`less than one.
`
`9
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`C.
`
`Performance of Error-Correcting Codes
`
`34. The effectiveness of an error-correcting code may be measured using
`
`a variety of metrics.
`
`35. One tool used to assess the performance of a code is its bit-error rate
`
`(BER.) The BER is defined as the number of corrupted information bits divided by
`
`the total number of information bits during a particular time interval. For example,
`
`if a decoder outputs one thousand bits in a given time period, and ten of those bits
`
`are corrupted (meaning they differ from the information bits originally received by
`
`the encoder), then the BER of the code during that time period is (10 bit errors) /
`
`(1000 total bits) = 0.01 or 1%.1
`
`36. The BER of a transmission depends on the amount of noise that is
`
`present in the communication channel and the strength of the transmitted signal
`
`(meaning the power that is used to transmit the modulated waveform). An increase
`
`in noise tends to increase the error rate and an increase in signal strength tends to
`
`decrease the error rate. The ratio of the signal strength to the noise, called the
`
`“signal-to-noise ratio,” is often used to characterize the channel over which the
`
`encoded signal is transmitted. The signal-to-noise ratio can be expressed
`
`
`1 Note that as used herein, BER refers to the information BER, which measures the
`percentage of bits that remain incorrect after decoding. This is different than the
`transmission BER, which measures the percentage of bits that are incorrect when
`received by the decoder, but before the decoding process begins.
`
`10
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`mathematically as Eb/N0, in which Eb is the amount of energy used to transmit each
`
`bit of the signal, and N0 is the density of the noise on the channel. The BER of an
`
`error-correcting code is often measured for multiple values of Eb/N0 to determine
`
`how the code performs under various channel conditions.
`
`37. Error-correcting codes may also be assessed based on their
`
`computational complexity. The complexity of a code is a rough estimate of how
`
`many calculations are required for the encoder to generate the encoded parity bits
`
`and how many calculations are required for the decoder to reconstruct the
`
`information bits from the parity bits. If a code is too complex, it may be
`
`impractical to build encoders/decoders that are fast enough to use it.
`
`D. LDPC Codes, Turbo Codes, and Repeat-Accumulate Codes
`
`38.
`
`In 1963, Robert Gallager described a set of error correcting codes
`
`called Low Density Parity Check (“LDPC”) codes. Gallager described how LDPC
`
`codes provide one method of generating parity bits from information bits using a
`
`matrix populated with mostly 0s and relatively few 1s, as explained in more detail
`
`below. (See Gallager, R., Low-Density Parity-Check Codes, Monograph, M.I.T.
`
`Press, 1963; Ex. 1007.)
`
`39. Gallager’s work was largely ignored over the following decades, as
`
`researchers continued to discover other algorithms for calculating parity bits. These
`
`algorithms included, for example, convolutional encoding with Viterbi decoding
`
`11
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`and cyclic code encoding with bounded distance decoding. In many cases, these
`
`new codes could be decoded using low-complexity decoding algorithms.
`
`40.
`
`In 1993, researchers discovered “turbocodes,” a class of error-
`
`correcting codes capable of transmitting information at a rate close to the so-called
`
`“Shannon Limit” – the maximum rate at which information can be transmitted over
`
`a channel. A standard turbocoder encodes a sequence of information bits using two
`
`“convolutional” coders. The information bits are passed to the first convolutional
`
`coder in their original order. At the same time, a copy of the information bits that
`
`have been reordered by an interleaver is passed to the second convolutional coder.
`
`The figure below shows the structure of a typical turbocoder. See Berrou et al.,
`
`“Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes," ICC
`
`’93, Technical Program, Conference Record 1064, Geneva 1993 (Ex. 1008)
`
`12
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`
`The main drawback of convolutional codes is that they do not perform
`
`41.
`
`well over channels in which errors are clustered tightly together. Turbo codes
`
`overcome this deficiency by encoding the input bits twice. The input bits are fed to
`
`a first convolutional encoder in their normal order to produce a first set of parity
`
`bits. The same input bits are also reordered by an interleaver and then encoded by a
`
`second convolutional encoder to produce a second set of parity bits. The two sets
`
`of parity bits together with the information bits form a single codeword. Using a
`
`turbo code, a small number of errors will not result in loss of information unless
`
`13
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`the errors happen to fall close together in both the original data stream and in the
`
`permuted data stream, which is unlikely.
`
`42.
`
`In 1995, David J. C. MacKay rediscovered Gallager’s work from
`
`1963 relating to low-density parity-check (LDPC) codes, and demonstrated that
`
`they have performance comparable to that of turbocodes. See MacKay, D. J. C, and
`
`Neal, R. M. “Near Shannon Limit Performance of Low Density Parity Check
`
`Codes,” Electronics Letters, vol. 32, pp. 1645-46, 1996 (Ex. 1009.) This
`
`rediscovery was met with wide acclaim. Turbocodes and LDPC codes have some
`
`common characteristics: both codes use pseudo-random permutations to spread out
`
`redundancy, and both use iterative decoding algorithms.
`
`43.
`
`In 1995 and 1996, researchers began to explore “concatenated”
`
`convolutional codes. See Benedetto, S. et al., Serial Concatenation of Block and
`
`Convolutional Codes, 32.10 Electronics Letters 887-8, 1996 (Ex. 1010.) While
`
`turbo codes use two convolutional coders connected in parallel, concatenated
`
`convolutional codes use two convolutional coders connected in series: the
`
`information bits are encoded by a first encoder, the output of the first encoder is
`
`interleaved, and the interleaved sequence is encoded by a second, convolutional
`
`code. In such codes, the first and second encoders are often called the “outer
`
`coder” and the “inner coder,” respectively.
`
`14
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`44.
`
`In 1998, researchers developed “repeat-accumulate,” or “RA codes,”
`
`by simplifying the principles underlying turbocodes. (See Ex. 1003.) In RA codes,
`
`the information bits are first passed to a repeater that repeats (duplicates) the
`
`information bits and outputs a stream of repeated bits (the encoder described above
`
`in the context of the “repeat three” coding scheme is one example of a repeater).
`
`The repeated bits are then optionally reordered by an interleaver, and are then
`
`passed to an accumulator where they are “accumulated” to form the parity bits.
`
`45. Accumulation is a running sum process whereby each input bit is
`
`added to the previous input bits to produce a sequence of running sums, each of
`
`which represents the sum of all input bits yet received. More formally, if an
`
`accumulator receives a sequence of input bits i1, i2, i3, … in, it will produce output
`
`bits o1, o2, o3, … on, such that:
`
`
`Where the ⊕ symbol denotes modulo-2 addition. Accumulators can be
`
`implemented simply, allowing accumulate codes to be encoded quickly and
`
`cheaply.
`
`15
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`46. Repetition and accumulation were well known in the art more than a
`
`year before the earliest claimed priority date of the ’710 patent. (Ex. 1003, pp. 5-
`
`10; Ex. 1002, pp. 2-7; Ex. 1004, pp. 249-50.)
`
`E. Mathematical Representations of Error-Correcting Codes
`
`1. Linear Transformations
`47. Coding theorists often think of error-correcting codes in linear-
`
`algebraic terms. For example, a k-bit block of information bits is a k-dimensional
`
`vector of bits, and an n-bit codeword is an n-dimensional vector of bits (where an
`
`“n dimensional vector” of bits is a sequence of n bits). The encoding process,
`
`which converts blocks of information bits into codewords, is a linear
`
`transformation that maps k-dimensional bit vectors to n-dimensional bit vectors.
`
`This transformation is represented by an n × k matrix G called a generator matrix.
`
`For a vector of information bits u, the corresponding codeword x is given by:
`
`
`The n-dimensional vectors that can be written in the form Gu are valid codewords.
`
`16
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`48. Most n-dimensional vectors are not valid codewords. It is this
`
`property that allows a decoder to determine when there has been an error during
`
`transmission. This determination is made using an (n - k) × n matrix H, called a
`
`parity check matrix. Using a parity check matrix, a given vector x is a valid
`
`codeword if and only if Hx = 0. If the parity check shows that Hx does not equal 0,
`
`then the decoder knows there has been a transmission error (much like the “010”
`
`example in the “repeat three” code above).
`
`49. Each of the n - k rows of the parity-check matrix H represents an
`
`equation that a valid codeword must satisfy. For example, consider a codeword x
`
`and a parity check matrix H given as follows:
`
`
`
`If x is a valid codeword, the product Hx must be equal to 0, so we
`
`50.
`
`have:
`
`
`
`As this equation shows, the first row of H represents the constraint that x3 + x4 = 0,
`
`and the second row of H represents the constraint that x1 + x2 = 0. If the vector x
`
`satisfies both of these constraints, it is a valid codeword. In practice, parity-check
`
`17
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`matrices often have hundreds or thousands of rows, each of which represents an
`
`equation of the form xa + xb + … + xz = 0, similar to those shown in the above
`
`example. These equations are called parity-check equations.
`
`2. Repeating and Permuting as Examples of LDGM Codes
`51. As explained above, the encoding process can be represented using a
`
`matrix called a generator matrix. This is true of all linear codes, including the
`
`“repeat,” “interleave,” and “accumulate” phases of the “repeat-accumulate” codes
`
`discussed above. More specifically, the “repeat” and interleave” phases can be
`
`represented using generator matrices whose entries are mostly zeros, with a
`
`relatively low proportion of 1s. Such generator matrices are called “low-density
`
`generator matrices” (LDGMs). The following is a generator matrix that can be
`
`used to repeat each information bit twice:
`
`
`
`
`
`18
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`52. Using the generator matrix above, encoding a sequence of input bits
`
`“101010101” would result in the encoded sequence “110011001100110011” (the
`
`number of times each input bit is repeated is determined by the number of “1s”
`
`appearing in the column corresponding to that input bit). In the 18×9 matrix above,
`
`11.1% of the entries are 1s, and the rest are 0s. The relative scarcity of 1s means
`
`that GREPEAT2 is a low-density generator matrix (LDGM).
`
`53. Permutation is another linear transform that is represented by a low-
`
`density generator matrix. For example, the matrix below is a permutation matrix
`
`that will output bits in a different order than bits are input:
`
`
`54. Permutation matrices, like GSHUFFLE above, have exactly one 1 per row
`
`and one 1 per column. The order of the output bits is determined by the position of
`
`each of these 1s within its row/column. The matrix above, for example, would
`
`transform input bits i1, i2, i3, i4, i5, i6, i7, i8 into the output sequence i2, i1, i7, i5, i4, i8,
`
`i6, i3. Permutation matrices are square, with dimensions n×n, because the input
`
`19
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`sequence and the output sequence have the same length. Because there is only one
`
`1 per row/column of permutation matrices, the density of 1s is 1/n (GSHUFFLE,
`
`shown above, has a density of 1/8, or 12.5%). In the context of linear codes, which
`
`often operate on blocks of more than a thousand bits at a time, a permutation
`
`matrix might comprise 0.1% 1s or fewer, and are therefore very low-density
`
`generator matrices (LDGMs).2
`
`3. Tanner Graphs
`55. Another popular mathematical representation of error-correcting
`
`codes is the “Tanner Graph.” Tanner graphs are bipartite graphs wherein nodes can
`
`be divided into two groups. Every edge connects a node in one group to a node in
`
`the other (i.e., no two nodes in the same group are connected by an edge). A
`
`bipartite graph is shown below:
`
`
`2 Indeed, for a given n and k, there are no viable codes whose generator matrices
`have a lower density than repeat-codes or permute-codes. Both of these codes have
`matrices with exactly one 1 per row – a matrix with lower density would
`necessarily have at least one row without any 1s at all, which would result in every
`codeword having a 0 in a particular bit position, conveying no information about
`the original message.
`
`20
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`
`56. A Tanner graph includes one group of nodes called variable nodes
`
`that correspond to the information and parity bits, and a second group of nodes
`
`called check nodes that represent constraints that parity and information bits must
`
`satisfy. In particular, when a set of variable nodes are connected to a particular
`
`check node, it means that the information/parity bits corresponding to those
`
`variable nodes must sum to 0.
`
`57. These two mathematical descriptions of linear codes – one using
`
`matrices, one using Tanner graphs – are two different ways of describing the same
`
`thing. Matrices and Tanner graphs are two different ways of describing the same
`
`set of linear codes, in much the same way that “0.5” and “½” are two different
`
`ways of describing the same number. Every generator matrix corresponds to a
`
`Tanner graph, and vice versa.
`
`21
`
`
`
`U.S. Patent 7,116,710
`Declaration of James A. Davis, Ph.D.
`
`F.
`
`Irregularity
`
`58.
`
`Irregular LDPC codes were first introduced in a 1997 paper by Luby.
`
`See Luby, M. et al., “Practical Loss-Resilient Codes,” STOC ’97, 1997 (Ex. 1011).
`
`The paper showed that irregular codes perform better than regular codes on certain
`
`types of noisy channels.
`
`59. Regular codes are codes in which each information bit contributes to
`
`the same number of parity bits, while irregular codes are codes in which different
`
`information bits or groups of information bits contribute to different numbers of
`
`parity bits. This is consistent with the Board’s construction of “irregular” in prior
`
`proceedings. (See, e.g., IPR2015-00060, Paper 18, p. 12.) Irregularity can also be
`
`defined in terms of Tanner graphs. A regular code is one with a Tanner graph in
`
`which each