United States Patent [19]
`Luby et al.
`
`[54] IRREGULARLY GRAPHED ENCODING
`TECHNIQUE
`
`[75] Inventors: Michael G. Luby, Berkeley, Calif;
`Mohammad Amin Shokrollahi,
`RappWeiler, Germany; Volker
`Stemann, Frankfurt, Germany; Michael
`D. Mitzenmacher, Milpitas, Calif;
`Daniel A. Spielman, Cambridge, Mass.
`
`[73] Assignee: Digital Equipment Corporation,
`Maynard, Mass.
`
`[21] Appl. No.: 08/965,603
`[22] Filed:
`Nov. 6, 1997
`
`[51] Int. Cl.7 .................................................... .. G06F 11/00
`[52] US. Cl. ............................................................ .. 714/701
`[58] Field of Search ............................................. .. 714/701
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,958,348
`
`9/1990 Berlekamp et a1. .................... .. 371/42
`
`5,115,436
`
`5/1992 McAuley . . . . . . . . . . . . .
`
`. . . . .. 371/35
`
`OTHER PUBLICATIONS
`
`Zyablov et al., Decoding Complexity of LoW—Density
`Codes for Transmission in a Channel With Erasures—vol.
`10, No. 1, pp. 10—21, last revision Aug. 20, 1973.
`R. Michael Tanner, A Recursive Approach to LoW Com
`plexity Codes—Transactions on Information Theory, vol.
`IT—27, No. 5, Sep. 1981, pp. 533—547.
`Jung—Fu Cheng, On the Construction of Ef?cient Multilevel
`Coded Modulations—IEEE Intl. Symposium on Informa
`tion Theory, 1997, pp. 1—12.
`MacKay et al., Good Codes based on Very Sparse Matri
`ces—Cavendish Labs, Cambridge, U.K., 7 pages.
`Alon et al., Construction of Asymptotically Good LoW—Rate
`Error—Correcting Codes through Pseudo Random Graphs—
`IEEE Trans. on Information Theory, vol. 38, No. 2, Mar.
`1992, pp. 509—516.
`Cheng et al., Some High—Rate Near Capacity Codes for the
`Gaussian Channel—34th Allerton Conference on Commu
`nications, Control and Computing, Oct. 4, 1996, pp. 1—10.
`
`US006081909A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,081,909
`Jun. 27, 2000
`
`Gelfand et al., On the Complexity of Coding—2nd Intl.
`Symposium on Information Theory, Tsahkadsor Armeia,
`USSR, Sep. 2—8, 1971, pp. 177—184.
`Bassalygo et al., Problems of Complexity in the Theory of
`Correcting Codes—Plenum Publishing Corp., 1978, pp.
`166—175.
`Vvedenskaya et al., Systematic Codes That Can Be Realized
`by Simple Circuits—Plenum Publishing Corp., 1979,
`246—254.
`A. J. McAuley, Reliable Boardband Communication Using
`a Burst Erasure Correcting Code—Computer Communica
`tion Research Group, MorristoWn, NJ, pp. 297—306.
`(List continued on next page.)
`Primary Examiner—Phung M. Chung
`Attorney, Agent, or Firm—Jenkens & Gilchrist,P.C.
`[57]
`ABSTRACT
`
`A method of encoding a message including a plurality of
`data items, includes identifying maximum and minimum
`numbers of ?rst edges to be associated With data items. A
`?rst distribution of different numbers of ?rst edges, ranging
`from the maximum to the minimum number of ?rst edges,
`to be associated With the data items is computed. A ?rst
`associated number of ?rst edges, Within the range, is estab
`lished for each data item, the different numbers of ?rst edges
`being associated With the data items according to the com
`puted ?rst distribution. A maximum and minimum number
`of second edges to be associated With redundant data items
`are identi?ed. A second distribution of numbers of second
`edges, ranging from the maximum to the minimum number
`of second edges, to be associated With the redundant data
`items is computed. An associated number of second edges,
`Within the range, is established for each redundant data item,
`the different numbers of second edges being associated With
`the redundant data items according to the determined second
`distribution. A threshold number of potentially lost/
`corrupted data items is established. An encoded message is
`formed With the redundant data items associated With the
`data items according to the ?rst distribution and With the
`data items associated With the redundant data items accord
`ing to the second distribution only if the number of data
`items Which are recoverable or correctable exceeds the
`threshold.
`
`35 Claims, 25 Drawing Sheets
`
`....
`
`.... 6
`
`6 ........
`
`10* ‘oooooooooooooooo'
`
`CALTECH - EXHIBIT 2003
`Apple Inc. v. California Institute of Technology
`IPR2017-00219
`
`

`

`6,081,909
`Page 2
`
`OTHER PUBLICATIONS
`
`E. W. Biersack, Performance Evaluation of Forward Error
`Correction in ATM NetWorks—Institut EURECOM, France,
`Aug. 1992, pp. 248—257.
`David J .C. MacKay, Good Error—Correcting Codes based on
`Very Sparse Matrices—Cavendish Labs, U.K. Nov. 2, 1996,
`pp. 1—50.
`Daniel A. Spielrnan, Linear—Tirne Encodable and Decodable
`Error—Correcting Codes—Dept. of Computer Science, U.C.
`Berkeley, Berkeley, CA, pp, 1—20.
`Sipser et al., Expander Codes—Massachusetts Institute of
`Technology, Cambridge, MA,, 12 pages.
`G. David Forney, Jr., The ForWard—BackWard Algorithrn—
`Motorola, Inc., Mans?eld, MA, Oct. 1, 1986, pp. 432—446.
`R. G. Gallager, LoW—Density Parity—Check Codes—1963,
`MIT. Press, Cambridge, MA, 106 pages.
`Sipser et al., EXpander Codes—Journal Version, IEEE IT
`1996, Massachusetts Institute of Technology, pp. 1—28.
`
`Daniel A. Spielrnan, Linear—Tirn Encodable and Decodable
`Error—Correcting Codes—Conference Version, STOC 95,
`Massachusetts Institute of Technology, 10 pages.
`Daniel A. Spielrnan, Linear—Tirn Encodable and Decodable
`Error—Correcting Codes—Journal Version, IEEE IT 96,
`Massachusetts Institute of Technology, pp. 1—20.
`Daniel A. Spielrnan, Cornputationally Efficient Error—Cor
`recting Codes and Holographic Proofs—Yale University
`(1992), Massachusetts Institute of Technology Jun. 1995,
`pp. 1—147.
`
`Luigi RiZZo—Effective erassure codes for reliable cornputer
`cornrnunication protocols—University of Italy, Jan. 9, 1997,
`pp. 1—10.
`Luigi RiZZo,—A Reliable Multicast data Distribution Pro
`tocol based on softWare FEC techniques—University of
`Italy, Feb. 20, 1997, pp. 1—6.
`Luigi RiZZo—On the feasibility of softWare FEC—Univer
`sity of Italy, Jan. 31, 1997, pp. 1—16.
`
`

`

`U.S. Patent
`
`Jun. 27,2000
`
`Sheet 1 0f25
`
`6,081,909
`
`_......_.....
`
`mmumwmz =
`
`@5305 E
`
`-
`
`11
`
`+ 10.‘.
`
`_
`
`828mm =m
`
`$33: =
`
`

`

`U.S. Patent
`
`Jun. 27,2000
`
`Sheet 2 0f25
`
`6,081,909
`
`FIG. 2
`
`
`
`0+2)" __._|
`
`Encoding
`
`Message
`
`

`

`U.S. Patent
`
`Jun. 27,2000
`
`Sheet 3 0f25
`
`6,081,909
`
`l_j___J
`
`lQOOOQQOOJ
`
`FIG. 3
`
`IOOQQQQOCOOOOOOQOJ
`
`

`

`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 4 0f25
`
`6,081,909
`
`0
`
`b
`
`c
`
`J
`
`

`

`U.S. Patent
`
`Jun. 27,2000
`
`Sheet 5 0f25
`
`6,081,909
`
`

`

`U.S. Patent
`
`Jun. 27,2000
`
`Sheet 6 0f25
`
`6,081,909
`
`.91
`
`.UNR
`
`

`

`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 7 0f25
`
`6,081,909
`
`FIG. 7
`
`

`

`U.S. Patent
`
`Jun. 27,2000
`
`Sheet 8 0f25
`
`6,081,909
`
`I
`
`1
`
`FIG. 8
`
`

`

`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 9 0f25
`
`6,081,909
`
`8 Q I o_ m m N m n ¢ n N
`
`85% :2
`
`I Yo
`
`I nd
`
`I Nd
`
`I _..o
`
`I o
`
`IP
`
`I Q0
`
`I wd
`
`I 50
`
`I @o
`
`I m.o
`
`@8508
`@5808
`
`

`

`6,081,909
`
`Q
`B
`
`.
`L5
`N
`k.
`
`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 10 0f25
`
`D+1
`
`w
`
`8 "2
`g
`Q
`:
`L03
`0.
`0
`L
`L03
`E
`:1
`Z
`
`IIIIII%
`
`06-1
`
`05
`
`0.4
`
`03
`
`02
`
`0.1
`
`aaJbaq @ sapoN 4o uonomj
`
`

`

`U.S. Patent
`
`Jun. 27,2000
`
`Sheet 11 0f25
`
`6,081,909
`
`3
`
`.1
`
`NF
`
`0? 0 0
`
`8230 20E 3 63:52
`
`“ \ 6.0%
`
`2.0
`
`3.0
`
`N_.0
`
`To
`
`00.0
`
`00.0
`
`+0.0
`
`No.0
`
`991690 @ sapoN 40 uoppmj
`
`

`

`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 12 0f25
`
`6,081,909
`
`85% :2 2.666
`
`N \ 65%
`
`I We
`
`I 3.0
`
`I Nd
`
`I mNo
`
`@8530
`0588a
`
`

`

`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 13 0f25
`
`6,081,909
`
`
`
`5:8: 858% :05 20E now: 65 22: 3 E351
`
`
`
`
`
`
`
`653m 539::
`
`_ - _
`
`260% 8 88m: @685 m5 3 5:08;
`
`m.“ 6?‘
`
`f f N09
`
`3... no; No; 00;
`
`

`

`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 14 0f25
`
`6,081,909
`
`EL
`
`670 870
`
`67. 870
`
`670 ST‘
`
`67G 87.
`
`67. 870
`
`670 87d
`
`‘1 65%
`
`

`

`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 15 0f25
`
`6,081,909
`
`

`

`U.S. Patent
`
`Jun. 27,2000
`
`Sheet 16 0f25
`
`6,081,909
`
`110'+:
`
`lQQOQOQOOJ
`
`FIG. 16
`
`lQQQOQOQOOOOIOQQOJ
`
`

`

`U.S. Patent
`
`Jun. 27, 2000
`
`Sheet 17 0f25
`
`6,081,909
`
`

`

`U.S. Patent
`
`Jun. 27,2000
`
`Sheet 18 0f25
`
`6,081,909
`
`50:
`
`Ye:
`
`

`

`
`
`US. PatentUS. Patent
`
`
`
`Jun. 27, 2000Jun. 27, 2000
`
`
`
`Sheet 19 0f 25Sheet 19 0f 25
`
`
`
`6,081,9096,081,909
`
`
`
`
`
`

`

`US. Patent
`
`Jun. 27, 2000
`
`Sheet 20 0f 25
`
`6,081,909
`
`.o_—
`
`POFF
`
`POFF
`
`FOFF
`
`POFF
`
`oo—_-no:
`
`00——
`
`Q.5:
`
`uo—_
`
`oo—_
`
`OF—
`
`ON65%
`
`

`

`US. Patent
`
`Jun.27,2000
`
`Sheet2170f25
`
`6,081,909
`
`co:
`
`ob:
`
`Po:0.02
`
`8:.5:
`
`5:
`
`,5:8:co:8:8:8:8:
`
`“N65%
`
`

`

`
`
`US. PatentUS. Patent
`
`
`
`Jun. 27, 2000Jun. 27, 2000
`
`
`
`Sheet 22 0f 25Sheet 22 0f 25
`
`
`
`6,081,9096,081,909
`
`
`
`11001100
`
`
`
`110'b110'b
`
`
`
`110'0110'0
`
`110'c 22110'c 22
`
`
`
`
`
`FIG.FIG.
`
`
`_:_:
`
`O,_O,_
`
`._._
`
`

`

`US. Patent
`
`Jun.27,2000
`
`Sheet23 0f25
`
`6,081,909
`
`Nd
`
`m
`
`w
`
`w.wOmNd
`
`ARV20mLotm
`
`MN65%
`
`(z) 9103 GJNIEDJ
`
`

`

`US. Patent
`
`Jun. 27, 2000
`
`Sheet 24 0f 25
`
`6,081,909
`
`F]G.24
`
`
`
`ErrorRate(7..)
`
`(z) 9103 aJnuoj
`
`

`

`US. Patent
`
`Jun.27,2000
`
`Sheet25 0f25
`
`6,081,909
`
`mFm
`
`omm
`
`o_m
`
`Lm>_momco‘_._.
`
`Lm>_womchH
`
`\Louoocm
`
`hmuoooo
`
`0mm
`
`oom
`
`\Louoocm
`
`Louoomo
`
`mm65%
`
`
`
`

`

`6,081,909
`
`1
`IRREGULARLY GRAPHED ENCODING
`TECHNIQUE
`
`TECHNICAL FIELD
`
`The present invention relates to loss resilient and error
`correcting codes and, more particularly, to a technique for
`creating loss resilient and error correcting codes having
`irregular graphing between the message data and the redun-
`dant data.
`
`BACKGROUND ART
`
`In downloading data from storage or communicating data,
`for example over a communications network such as the
`INTERNET, data is transmitted in streams of message
`packets. Typically, the message packets each contain a word
`of, for example, 16, 32 or 64 bits. The packets are combined
`into a message or message segment for transmission.
`During transmission of the message, various transmission
`related factors can result in message packets being lost or the
`data contained therein being altered so as to be in error,
`causing the communication to be corrupted at the receiving
`end. Stored data may also be lost or suffer error due to, for
`instance, static electrical charges in the environment or other
`factors. Numerous techniques are in use or have been
`proposed for replacing lost packets of information and
`correcting erroneous message data after the communication
`has been received. Such conventional techniques include
`Fourier transform-based techniques such as BCH and Reed-
`Solomon codes.
`
`Conventional techniques for protecting information from
`loss or errors involve encoding the information before it is
`transmitted in such a way that, even if it is partially lost or
`corrupted during transmission, the original information can
`be recovered. The encoding process necessarily involves the
`addition of extra, redundant data to the information. This
`redundant information is gathered together with the original
`information to form the message that is transmitted. The
`process of determining the original information, given the
`received corrupted message, i.e. a message with either losses
`or errors, is called decoding. Two criteria by which these
`techniques are evaluated are: how much additional data must
`be added to achieve reliable communications given a certain
`expected amount of loss or corruption, and how long it takes
`to perform the processes of encoding and decoding.
`The original information is represented by data items,
`which are also commonly referred to as message symbols.
`The data items could for example be message packets or data
`bits. The redundant data that is also transmitted with the
`
`information is represented by redundant data items, which
`are commonly referred to as check symbols. The redundant
`data items are of the same type as the data items. For
`example, if the data items are packets, then the redundant
`data items are also packets. The collection of data items and
`redundant data items that is transmitted is called a codeword.
`
`In the field of Coding Theory, each corruption of a data item
`is either called a loss, often referred to as an erasure, or an
`error. When trying to ascertain the information, the receiver
`will only have access to a corrupted version of the code-
`word.
`
`The decoding overhead of a loss-resilient technique at a
`particular stretch factor is given by that stretch factor
`divided by the least stretch factor of any code that can
`reliably recover from the maximum number of losses reli-
`ably recoverable by the technique at the particular stretch
`factor, less 1. Using Reed-Solomon techniques, the decoding
`overhead is zero. Loss resilient techniques with a decoding
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`overhead of zero are judged by their time overheads, i.e. the
`time required to encode and decode expressed as a multiple
`of the total number of data items and redundant data items.
`To the extent the use of any technique would result in a
`decoding overhead greater than zero, this added inefliciency
`must be compensated for by a reduction in the time overhead
`to provide a total efliciency equivalent to or better than those
`techniques having a zero decoding overhead.
`While superior to other loss-resilient techniques, Fourier
`transform-based techniques still require a substantial time
`overhead to perform. Hence, even using a Fourier transform-
`based technique, there can be a bottleneck at the receiving
`end due to the time required to replace lost packets. For
`example, if the number of packets being communicated is
`100,000, the time overhead will typically exceed 1,000. The
`more packets requiring replacement
`the higher the time
`overhead.
`
`The situation is similar for error correcting techniques.
`However,
`the decoding overhead of an error correcting
`technique is determined by the entropy function of Infor-
`mation Theory. For example, if the number of redundant
`data items is to be equal to the number of data items, and
`those data items and redundant data items are bits, then no
`technique can reliably recover all data items if more than
`11% of the data items and redundant items are corrupted by
`errors. Proposed prior art error correction techniques are
`unable to both efliciently and reliably recover from a full
`11% error rate, but are generally capable of recovering from
`errors in approximately 8% of the data items and redundant
`data items.
`
`While the deficiencies of prior art loss-resilient and error
`correcting techniques are generally tolerable for transmis-
`sions of relatively short lengths, these deficiencies become
`less acceptable during transmissions of large quantities of
`data. In applications requiring transmission of messages
`having large quantities of data items, such as video signal
`transmission, the probability that all corrupted data items
`can be recovered is at best low using conventional tech-
`niques.
`Further, where large blocks of data are being transmitted
`at high speed, for example, in video distribution, the time
`required to recover any corrupted data needs to be mini-
`mized. The time performance of conventional techniques is
`generally insufficient to make the necessary recoveries in the
`required real time periods, unless specialized hardware is
`provided.
`Accordingly, a need exists for data recovery techniques
`which can be utilized for quickly recovering corrupted data
`items where large blocks of data items must be transmitted.
`OBJECTIVES OF THE INVENTION
`
`Accordingly, it is an objective of the present invention to
`provide a technique for creating loss resilient and error
`correcting codes which substantially reduce the time
`required to encode and decode messages.
`It is another object of the present invention to provide a
`technique for creating encoded messages which, when
`decoded, facilitate recovery and/or correcting of message
`data which has been lost or corrupted during transmission or
`storage.
`It is yet another objective of the present invention to
`provide a technique for creating encoded messages which,
`when decoded, facilitate recovery and/or correction of a
`large number of lost or corrupted data items with improved
`efliciency.
`It is a further object of the present invention to provide a
`technique for creating encoded messages which, when
`
`

`

`6,081,909
`
`3
`decoded, facilitate recovery of corrupted data items with
`high probability.
`Additional objects, advantages, novel features of the
`present invention will become apparent to those skilled in
`the art from this disclosure, including the following detailed
`description, as well as by practice of the invention. While the
`invention is described below with reference to preferred
`embodiment(s), it should be understood that the invention is
`not limited thereto. Those of ordinary skill in the art having
`access to the teachings herein will recognize additional
`implementations, modifications, and embodiments, as well
`as other fields of use, which are within the scope of the
`invention as disclosed and claimed herein and with respect
`to which the invention could be of significant utility.
`SUMMARY DISCLOSURE OF THE INVENTION
`
`In accordance with the present invention, a method is
`provided for encoding a message having a plurality of data
`items, e.g. message packets or data bits, by identifying a
`maximum and minimum number of first edges to be asso-
`ciated with the data items. Preferably, the minimum number
`of first edges is 2. The numbers are different positive integer
`values. Afirst distribution of different numbers of first edges,
`ranging from the maximum to the minimum, to be associ-
`ated with the plurality of data items is computed. An
`associated number of first edges, within the range, is estab-
`lished for each data item. The associated numbers are
`
`10
`
`15
`
`20
`
`25
`
`established so that the different numbers of first edges are
`associated with the data items according to the computed
`first distribution.
`
`30
`
`The first distribution of numbers of first edges can be
`computed by 2i+1, where i is a number of first edges within
`the range of different numbers of first edges. For example,
`the different numbers of first edges might include 3, 5, 9, 17
`and 33. Alternatively, the different numbers of first edges
`could be distributed equally. In a still further and most
`preferred alternative, the maximum number of first edges is
`set equal to D+1. A constant N is set equal to 1+1/D. The
`distribution of numbers of first edges is computed by N/i
`(i—1).
`Preferably, prior to creating the encoded message, those
`data items to which each of the redundant data items will
`
`correspond are randomly selected. The encoded message
`will preferably include multiple levels of redundant data
`items. Preferably, the number of data items will exceed the
`number of redundant data items which are edged directly to
`the data items.
`
`the
`In accordance with other aspects of the invention,
`number of lost data items which are recoverable, expressed
`as a fraction, is designated 0L and is determined by finding a
`p value satisfying the inequality p(1—(1)\.(1—X))>X for all
`xe[0,1]. It will be recognized that in practice the number of
`lost redundant data items will also correspond to 0L. The
`value of )t corresponds to the first distribution and the value
`of p corresponds to the second distribution. The computation
`of p is performed using a standard binary search for a using
`linear programming to determine if there is a p correspond-
`ing to 0L for a fixed )L. The computation of p can be limited
`to a selected range of different numbers of second edges or
`to a selected number of different numbers of second edges,
`if it desired to reduce the processing overhead. If desired, p
`could initially be roughly computed using a first number of
`x values, and then refined by recomputation using a greater
`number of more closely spaced x values.
`The maximum number of first edges can be changed
`causing each data item to be associated with one of the
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`different numbers of first edges which are within a new
`range bounded by the changed maximum. These modified
`numbers of first edge are associated with the data items
`according to a third distribution, which is different than the
`first distribution. Each redundant data item is associated
`with a one of the different numbers of second edges which
`are based on the change in the maximum number of first
`edges. These modified numbers of second edges are asso-
`ciated with the redundant data items according to a fourth
`distribution, which is different than the second distribution.
`A maximum and minimum number of second edges to be
`associated with redundant data items is also identified.
`Beneficially, the minimum number of second edges is 1.
`These maximum and minimum numbers are also different
`positive integer values. A second distribution of different
`numbers of second edges, ranging from the maximum to the
`minimum, to be associated with the redundant data items is
`computed. A number of second edges, within the range, is
`established for each redundant data item. The different
`numbers of second edges are associated with the redundant
`data items according to the second distribution. This second
`distribution may, for example be a Poisson distribution. The
`second distribution is determined such that a maximum
`number of data items are recoverable.
`A determination is made of the number of the data items
`which are recoverable if lost or correctable if corrupted, in
`an encoded message formed of the data items and redundant
`data items, with each of the redundant data items corre-
`sponding to a number of the data items equal to the asso-
`ciated number of second edges. More particularly, the redun-
`dant data items are formed such that each of the redundant
`
`data items represents those of the data items to which it is
`connected by first and second edges. For example, each
`redundant data item may be formed to equal an exclusive-or
`of the those data items to which the redundant data item is
`
`connected by edges.
`A threshold number of potential lost or corrupted data
`items is established. This will typically be the likely maxi-
`mum number of data items requiring replacement or cor-
`rection in the particular implementation. An encoded mes-
`sage is formed, with the redundant data items associated
`with the data items according to the first distribution and the
`data items associated with the redundant data items accord-
`
`ing to the second distribution, only if the number of data
`items which are determined to be recoverable or correctable
`exceeds the threshold.
`A determination is made as to whether or not the number
`of data items which are recoverable or correctable from an
`
`encoded message formed with each of the redundant data
`items corresponding to a number of the data items equal to
`one of the modified numbers of second edges, exceeds the
`threshold. If so, an encoded message with the redundant data
`items associated with the data items according to the third
`distribution and data items associated with the redundant
`
`data items according to the fourth distribution is formed.
`In accordance with other aspects of the invention, the
`associated number of first edges for each data item is
`established by random assignment of each of the different
`numbers of first edges so as to provide the appropriate
`distribution of the different numbers of first edges. The
`associated number of second edges for each redundant data
`item is also established by random assignment of each of the
`different numbers of second edges so as to provide the
`appropriate, e.g. Poisson, distribution of the different num-
`bers of second edges. Preferably, each second edge is also
`randomly connected to a one or more of the first edges so as
`to provide the applicable distributions of first and second
`edges.
`
`

`

`5
`BRIEF DESCRIPTION OF DRAWINGS
`
`6,081,909
`
`6
`BEST MODE FOR CARRYING OUT THE
`INVENTION
`
`FIG. 1 is a simplified depiction of the steps performed in
`encoding and decoding a message.
`FIG. 2 depicts parameters of encoding and decoding.
`FIG. 3 depicts a cascading encoding structure in accor-
`dance with the present invention.
`FIG. 4 depicts a graph of a partial set of irregularly
`graphed edges between node layers of the FIG. 3 encoding
`in accordance with the present invention.
`FIG. 5 depicts a received corrupted version of a codeword
`in accordance with the present invention.
`FIG. 6 is a partial depiction of the edges between nodes
`of the FIG. 3 encoding at the receiving end of a transmission.
`FIG. 7 depicts the decoding process in accordance with
`the present invention.
`FIG. 8 is similar to FIG. 4, but reflects regular rather than
`irregular graphing of edges between nodes.
`FIG. 9 is a graph of the decoding overhead with the left
`nodes having regularly graphed degrees.
`FIG. 10 graphs the fractional portions of nodes at different
`degrees in a good left degree sequence having a cascading
`series with a truncated heavy tail in accordance with the
`present invention.
`FIG. 11 depicts a distribution of right node edges for the
`left edge distribution depicted in FIG. 10 in accordance with
`the present invention.
`FIG. 12 is a graph of the decoding overhead with the left
`nodes having irregularly graphed degrees.
`FIG. 13 is a graph of the fraction of data items and
`redundant data items that need to be received to decode a
`
`message using irregular and regular graphing of the edges
`between nodes in accordance with the present invention.
`FIG. 14 depicts an induced graph of the received cor-
`rupted version of the codeword after all redundant data items
`at the right nodes have been recovered in accordance with
`the present invention.
`FIG. 15 is a simplified depiction of the process of encod-
`ing and decoding a message with an error correcting code.
`FIG. 16 depicts an error correcting cascading encoding
`structure in accordance with the present invention.
`FIG. 17 depicts an irregular graphing of the edges
`between node layers in the FIG. 16 encoding structure in
`accordance with the present invention.
`FIG. 18 depicts a received encoded message which has an
`encoding structure as shown in FIG. 16.
`FIG. 19 depicts the decoding process for the error cor-
`rection code in accordance with the present invention.
`FIG. 20 depicts the graphing of the edges between nodes
`of the layers shown in FIG. 19 at the receiving end of a
`transmission in accordance with the present invention.
`FIG. 21 depicts one level of belief propagation for a node
`depicted in FIG. 20.
`FIG. 22 depicts a further extension of the belief propa-
`gation shown in FIG. 21.
`FIG. 23 graphs the failure rate versus the error rate
`utilizing the error correcting code in accordance with the
`present invention.
`FIG. 24 is similar to FIG. 23 but reflects a different
`
`redundancy ratio.
`FIG. 25 depicts a simplified communication link over
`which messages encoded in accordance with the present
`invention can be transmitted and decoded.
`
`FIG. 1 provides a simplified depiction of the process of
`encoding and decoding messages for loss resilience. As
`shown, a message 1 having n data items is encoded by an
`encoding algorithm prior to transmission. The encoding
`algorithm creates redundant data items 1' which are com-
`bined with the original data items 1 to form an encoded
`message having a length cn. The number 1/c is commonly
`referred to as the rate of the encoding technique. As shown,
`the original information contains six data items 1, to which
`six redundant data items 1' are attached to form a codeword.
`
`Accordingly, the stretch value c is 2 in the example shown.
`The corrupted version of the codeword which is received
`after transmission contains only three of the original data
`items which are designated 11 and four of the redundant data
`items designated 1'1. The properly received redundant data
`items 1'1 are utilized to recreate the full original message
`having data items 1, using the decoding algorithm.
`FIG. 2 depicts the parameters of the technique. As shown,
`the message has a length of n data items. With the redundant
`data items added, the encoded message has a length cn. The
`decoding overhead can be represented by a value e. As
`indicated by the lower bar in FIG. 2, the number of data
`items and redundant data items required to decode the
`received encoded message can be described by the equation
`(1+e)n.
`FIG. 3 depicts a cascading series loss resilient encoding
`structure in accordance with the present
`invention. As
`depicted, a message 10 includes data items associated with
`nodes 1—n. Redundant data items are associated with nodes
`
`formed in cascading levels or layers of nodes 10', 10" and
`10'”. Assuming that the message is stretched to a length cn,
`then the factor [3=1—(1/c) and the number nodes at 10' is [3n
`and at 10" is [3%. At the last layer, the number of nodes is
`cn less the number of nodes at all other layers. Each pair of
`adjacent levels of nodes forms a bipartite graph. Each of the
`data items and redundant data items associated with each
`
`layer of nodes 10, 10', 10" and 10'” includes an address with
`which the information contained therein is further associ-
`ated. Each of the redundant data items associated with the
`
`respective cascading layers of nodes 10', 10" and 10'”
`includes an amount of information identical to that con-
`
`tained in the corresponding data items associated with a
`node or nodes in layer 10. However, the information in each
`of the redundant data items associated with the node layers
`10', 10" and 10'” is, as will be described in detail below,
`different from that in the data items associated with the
`
`corresponding node(s) in the node layer 10.
`The number of redundant data items in the node layers
`10', 10" and 10'” will depend on the desired length of the
`codeword, which in turn depends upon the expected number
`of losses in the data items and redundant data items during
`transmission. Preferably,
`the cascading of the redundant
`nodes is restrained to a limited number of levels, most
`preferably 3, in order to minimize both the time overhead
`and decoding overhead while maintaining high reliability.
`A typical decoding overhead,
`in accordance with the
`present invention, for a rate 1/2 code, is approximately 0.03.
`This small increase over the decoding overhead of conven-
`tional techniques is offset by a time overhead which is
`substantially less than that required to encode and to replace
`lost data items using conventional techniques.
`More particularly, the time overhead required to encode
`and decode, expressed as a multiple of the total number of
`data items and redundant data items, is approximately ln(3/
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`6,081,909
`
`7
`
`for a
`e), e being the decoding overhead. Accordingly,
`decoding overhead of 0.03, the resulting time overhead is
`4.5. This compares with a time overhead which will typi-
`cally be well in excess of 1,000 using conventional tech-
`niques.
`Inherently, it will be a random portion of a codeword
`which is received at the receiving end of a transmission. That
`is, whatever amount of the codeword is received is deter-
`mined by which data items and redundant data are lost. The
`portion of the data items and redundant data items that are
`received will, in fact, be a portion that is independent of the
`contents of those items. Preferably,
`the data items and
`redundant data items are sent in a randomly interleaved
`order. The decoding depends upon receiving approximately
`the same fraction of those items from each layer. Because of
`the random ordering of those items, a random portion of
`those items will be received. This randomness ensures the
`
`necessary random portion of the codeword is received
`notwithstanding the arbitrariness of the data item and redun-
`dant data item contents. Thus, data items and redundant data
`items are randomized so that there is a high probability of
`proper decoding and decoding overheads are minimized. It
`will be understood that, as used herein, the term “random”
`should be construed to include pseudo randomness, biased
`randomness and other types of randomness.
`Referring again to FIG. 3, if the encoding structure is to
`be stretched, for example, by a factor of 2, then the total
`number of redundant data items associated with the node
`
`layers 10', 10" and 10'” will equal the number of data items
`in the node layer 10,
`i.e., n. In general,
`the number of
`redundant data items and, hence, nodes at each cascading
`level is reduced by a constant factor [3 such that the total
`number of data items and redundant data items will equal the
`total number of data items n multiplied by the stretch factor
`c. Accordingly, [3=1—1/c, with c being the stretch factor, in
`this example, 2.
`In FIG. 3, the total number of data items associated with
`the node layer 10 is 16, i.e., n, equals 16, and the stretch
`factor, i.e., c, equals 2. The number of redundant data items
`at each consecutive level of the cascading series is reduced
`or shrunk by a factor of 2. Hence, the number of redundant
`data items in series 10' is 8 (i.e., 0.5x16). The number of
`redund