United States Patent [19J
`Luby et al.
`
`[54]
`
`[75]
`
`IRREGUlARLY GRAPHED ENCODING
`TECHNIQUE
`
`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
`
`Int. Cl? ...................................................... G06F ll/00
`[51]
`[52] U.S. Cl. .............................................................. 714/701
`[58] Field of Search ............................................... 714/701
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,958,348
`5,115,436
`
`9/1990 Berlekamp et a!. ...................... 371/42
`5/1992 McAuley .................................. 371/35
`
`01HER PUBLICATIONS
`
`Zyablov et al., Decoding Complexity of Low-Density
`Codes for Transmission in a Channel with Erasures-val.
`10, No. 1, pp. 10-21, last revision Aug. 20, 1973.
`R. Michael Tanner, A Recursive Approach to Low Com(cid:173)
`plexity Codes-Transactions on Information Theory, vol.
`IT-27, No. 5, Sep. 1981, pp. 533-547.
`Jung-Fu Cheng, On the Construction of Efficient Multilevel
`Coded Modulations-IEEE Inti. Symposium on Informa(cid:173)
`tion Theory, 1997, pp. 1-12.
`MacKay et al., Good Codes based on Very Sparse Matri(cid:173)
`ces-Cavendish Labs, Cambridge, U.K., 7 pages.
`Alan et al., Construction of Asymptotically Good Low-Rate
`Error-Correcting Codes through Pseudo Random Graphs(cid:173)
`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(cid:173)
`nications, Control and Computing, Oct. 4, 1996, pp. 1-10.
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US006081909A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,081,909
`Jun.27,2000
`
`Gelfand et al., On the Complexity of Coding-2nd Inti.
`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(cid:173)
`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.
`ABSTRACT
`[57]
`
`A method of encoding a message including a plurality of
`data items, includes identifying maximum and minimum
`numbers of first edges to be associated with data items. A
`first distribution of different numbers of first edges, ranging
`from the maximum to the minimum number of first edges,
`to be associated with the data items is computed. A first
`associated number of first edges, within the range, is estab(cid:173)
`lished for each data item, the different numbers of first edges
`being associated with the data items according to the com(cid:173)
`puted first distribution. A maximum and minimum number
`of second edges to be associated with redundant data items
`are identified. 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 first distribution and with the
`data items associated with the redundant data items accord(cid:173)
`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
`
`~}0
`
`•
`•
`•
`•
`
`10'
`
`'"{~
`• ~/
`
`•
`•
`•
`•
`•
`•
`•
`10 •
`•
`•
`•
`•
`•
`•
`•
`
`Hughes, Exh. 1016, p. 1
`
`

`
`6,081,909
`Page 2
`
`01HER 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 Spielman, Linear-Time 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 Algorithm(cid:173)
`Motorola, Inc., Mansfield, MA, Oct. 1, 1986, pp. 432-446.
`R. G. Gallager, Low-Density Parity-Check Codes-1963,
`M.I.T. Press, Cambridge, MA, 106 pages.
`Sipser et al., Expander Codes-Journal Version, IEEE IT
`1996, Massachusetts Institute of Technology, pp. 1-28.
`
`Daniel A Spielman, Linear-Tim Encodable and Decodable
`Error-Correcting Codes-Conference Version, STOC 95,
`Massachusetts Institute of Technology, 10 pages.
`Daniel A Spielman, Linear-Tim Encodable and Decodable
`Error-Correcting Codes-Journal Version, IEEE IT 96,
`Massachusetts Institute of Technology, pp. 1-20.
`
`Daniel A Spielman, Computationally Efficient Error-Cor(cid:173)
`recting Codes and Holographic Proofs-Yale University
`(1992), Massachusetts Institute of Technology Jun. 1995,
`pp. 1-147.
`
`Luigi Rizzo-Effective erassure codes for reliable computer
`communication protocols-University of Italy, Jan. 9, 1997,
`pp. 1-10.
`Luigi Rizzo,-A Reliable Multicast data Distribution Pro(cid:173)
`tocol based on software FEC techniques-University of
`Italy, Feb. 20, 1997, pp. 1-6.
`Luigi Rizzo-On the feasibility of software FEC-Univer(cid:173)
`sity of Italy, Jan. 31, 1997, pp. 1-16.
`
`Hughes, Exh. 1016, p. 2
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 1 of 25
`
`6,081,909
`
`•
`•
`•
`-.-- •
`•
`•
`• • •
`•
`•
`•
`•
`•
`•
`•
`•
`•
`•
`
`Q.l
`C'l
`0
`C/)
`C/)
`Q)
`:::::!:
`
`;:::
`
`C'l
`c
`:.0
`0
`u
`c:
`w
`6
`
`•
`•
`•
`•
`• • • •
`•
`•
`•
`•
`•
`
`......
`.--
`
`•
`•
`
`""0
`Q)
`>
`·a:;
`u
`Q)
`0::
`
`~
`
`t_!)
`~
`
`Q.l
`C'l
`0
`C/)
`C/)
`Q)
`:::::!:
`
`;:::
`AI
`
`;:::
`
`Hughes, Exh. 1016, p. 3
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 2 of 25
`
`6,081,909
`
`l 6
`
`Cl.)
`0"1
`0
`(/)
`(/)
`Cl.)
`~
`
`l
`
`l s::: w
`+ --
`
`Cl
`c::::
`"'0
`0
`u
`c:::: w
`
`Hughes, Exh. 1016, p. 4
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 3 of 25
`
`6,081,909
`
`0
`
`'• • 1 • el
`
`,• • y • •,
`
`·a
`...-
`
`t• • • • • • • •,
`
`y
`0 ...-
`
`CrJ
`
`~ r;:
`
`t• • • • • • • • • • • • • • • •,
`
`y
`0
`...-
`
`Hughes, Exh. 1016, p. 5
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 4 of 25
`
`6,081,909
`
`0
`1
`
`0'
`
`...c:::
`Ee
`Ee
`Ee
`Ee
`Ee
`
`Q)
`
`"'C
`
`..0
`
`0'
`
`"'C
`
`Ee
`Ee
`u
`Et)
`..c
`ffi
`
`0
`
`0'
`
`...c:::
`Ee
`Ee
`ffi
`u
`
`Q)
`
`-
`
`Et)
`..c
`Et)
`0
`
`[o
`
`0 0~
`
`0
`
`~
`.
`t;:
`
`(.!)
`
`. -~
`
`0..
`
`-
`
`Q)
`
`y
`0 .....-
`
`Hughes, Exh. 1016, p. 6
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 5 of 25
`
`6,081,909
`
`·a
`,------"1'-----..
`I~ ~ ~ ~~
`:_ :N :_
`:N
`·a o
`·a o
`
`CIJ _.
`:.J..c
`'-c..
`8_o
`·- ....
`CD (.!)
`
`I~~~~
`
`y
`0
`
`2
`:.=;...c
`'-c..
`8_o
`·- ....
`CD (.!)
`
`0
`0
`I~~~~~~~
`y
`0
`
`2
`~...c
`'-c..
`8_o
`·- ....
`CD (.!)
`
`0
`
`N
`0
`
`~ a
`
`0
`
`N
`0
`
`~
`
`0
`
`N
`a
`
`N
`a
`
`~
`
`0
`
`0
`
`N
`0
`
`N
`0
`
`~
`0
`
`0
`
`~~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~. ~
`y
`a
`
`Hughes, Exh. 1016, p. 7
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 6 of 25
`
`6,081,909
`
`0
`
`~-------1--------~
`
`0'
`
`Et>
`..c
`
`..c
`
`~
`
`Et>
`Et>
`
`0'
`
`Q.)
`
`~
`
`0'
`
`Q.)
`
`Et>
`Et>
`Et>
`..c
`
`I
`I
`I
`I
`I
`I
`
`1-J;
`
`10
`
`C'•
`
`u
`
`"'0
`
`-
`
`C'•
`
`y
`
`0
`
`~ '\1_~
`
`N
`
`...-
`
`.. ·•
`
`Hughes, Exh. 1016, p. 8
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 7 of 25
`
`6,081,909
`
`~-------1--------~
`
`..c
`
`... e
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`..c
`
`e
`[o
`
`y
`
`0
`
`Hughes, Exh. 1016, p. 9
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 8 of 25
`
`6,081,909
`
`0
`
`~------~1---------~
`
`.. -~
`
`[o
`
`-
`
`y
`
`0
`
`. -~
`
`Hughes, Exh. 1016, p. 10
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 9 of 25
`
`6,081,909
`
`8
`
`0
`
`0')
`
`~
`
`.
`c.!)
`~
`
`00
`
`Q.)
`Q.)
`\...
`0'
`Q.)
`""0
`r--.. ~
`,.._
`Q.)
`
`tO
`
`l.()
`
`0')
`0
`
`00
`c:i
`
`r--..
`c:i
`
`tO
`0
`
`l.() ~ I"")
`c:i
`c:i
`c:i
`
`N
`c:i
`
`0
`
`0
`
`0' ""0
`c
`0
`""'..c.
`· - Q.)
`0
`\...
`UCl)
`Cl) >
`0
`0
`
`Hughes, Exh. 1016, p. 11
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 10 of 25
`
`6,081,909
`
`+
`Cl
`
`r-
`
`lO
`
`L(')
`
`....,...
`
`N
`
`L(')
`0
`
`....,...
`0
`
`N
`0
`
`0
`
`0
`
`(I'J
`Cl)
`Cl)
`\...
`0"1
`QJ
`0
`
`o+J -Q)
`.....J -0
`
`\...
`
`Q) .c
`E
`:::::s z
`
`c .,.....
`.
`~
`~
`
`Hughes, Exh. 1016, p. 12
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 11 of 25
`
`6,081,909
`
`rn
`Q)
`Q)
`~
`0"1
`Q)
`0
`........
`...s:::::
`0"1
`
`a:: -0
`
`~
`Q)
`..0
`E
`::J z
`
`N
`
`0
`
`CX)
`
`tO
`
`..q-
`
`0
`
`0
`
`N
`c:i
`
`0
`
`CX)
`0
`c:i
`
`tO
`0
`c:i
`
`..q-
`0
`0
`
`N
`q
`0
`
`0
`
`aaJ6aa @ sapoN JO uO!lJDJ .:l
`
`~
`
`~
`
`.
`t..!)
`~
`
`Hughes, Exh. 1016, p. 13
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 12 of 25
`
`6,081,909
`
`Q)
`Q.)
`
`....
`0'
`Q.)
`""0
`
`.......... -Q.)
`
`Q)
`0'
`....
`0
`Q.)
`>
`0
`
`t\2
`.,...._
`
`•
`c.!)
`~
`
`8
`
`N
`
`- 0
`
` -
`
`m
`
`00
`
`1""-o-
`
`c.o
`
`N
`
`N
`0
`
`lJ")
`
`0
`
`..--
`0
`
`0
`
`I.()
`0
`0
`
`lJ")
`!")
`0
`
`!")
`0
`
`lJ")
`N
`0
`0'""0
`c 0
`· - Q)
`""'..s::::::
`0
`....
`(.) Q)
`Q.) >
`0
`0
`
`Hughes, Exh. 1016, p. 14
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 13 of 25
`
`6,081,909
`
`c:
`.Q
`........ u
`
`Q)
`
`0 ,._ -"0
`:..= ·u
`Q) c..
`
`(I)
`c:
`0 ..c.
`........
`,._
`(l)
`0
`E
`"0
`Q)
`Q)
`c:
`........
`0 ..c.
`........
`..!Q
`0
`
`·,:: _.. -0
`
`........
`c:
`(l) u ,._
`(l) a..
`
`~
`
`,._
`0
`::l
`0'1
`Q) a:::
`
`,._
`.2
`::l
`0'1
`,._
`Q)
`,._
`
`.q-
`...-
`
`1-
`
`I")
`0
`
`~
`
`N
`1- 0
`
`(l)
`"0
`0 u
`Q)
`""0
`
`0
`........
`
`""0
`Q)
`"0
`Q)
`Q)
`c:
`0'1
`c:
`:.0
`0
`u
`c:
`Q)
`
`(l)
`..c.
`
`....... -0
`
`c:
`0
`~ u
`,._
`0
`u..
`
`CtJ
`""""'
`.
`~
`~
`
`~
`
`N
`0
`0
`
`Hughes, Exh. 1016, p. 15
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 14 of 25
`
`6,081,909
`
`0
`
`C"'
`C"'
`C"'
`C"'
`C"'
`C"'
`0 00 0 00
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`~JtltlJJ tltltltlJJJJ~
`
`~----------------~y
`
`0
`
`Hughes, Exh. 1016, p. 16
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 15 of 25
`
`6,081,909
`
`in
`
`..
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`C"l
`c
`:.0
`0
`u
`c
`w
`
`0
`
`0
`
`0
`
`0
`
`Q.)
`C"l
`0
`(/)
`(/)
`Q.)
`:::::::!!:
`
`~-
`1.{")
`
`..
`
`1.{")
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`""'0
`Q.)
`>
`·a;
`u
`Q.)
`0:::
`
`..
`
`0
`
`0
`
`0
`
`0
`
`Q.)
`C"l
`0
`(/)
`en
`Q.)
`:::::::!!:
`
`lQ
`,_._
`.
`t.!)
`t;:
`
`Hughes, Exh. 1016, p. 17
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 16 of 25
`
`6,081,909
`
`'• • • .I
`
`·a
`.--
`I
`
`,• • • •,
`
`y
`0 .--
`.--
`
`,• • • • • • • •,
`
`y
`0 .--
`.--
`
`~
`.......
`
`C!)
`~
`
`,• . . . . . . . . . . . . . . •,
`
`y
`0 .-(cid:173)
`.--
`
`Hughes, Exh. 1016, p. 18
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 17 of 25
`
`6,081,909
`
`0
`I
`
`E9
`ffi
`0
`®
`0
`
`®
`Ee
`Ee
`0
`ffi
`Ee
`0
`
`-
`
`®
`.---
`Ee
`0
`ffi
`0
`ffi
`
`-
`
`ffi
`®
`
`.. -~
`
`l."-
`~
`.
`t.!> r;:
`
`l-
`
`0
`
`0
`
`0
`
`y
`
`0
`
`. -~
`
`0
`
`Hughes, Exh. 1016, p. 19
`
`

`
`.___11 a 1 Bipartite
`Graph
`
`.___11a2
`
`.___11 a·, Bipartite
`.___
`, Graph
`11 a 1
`
`11 0"
`
`.___, a2
`
`.___11 a;·
`
`11 o'
`
`.___1102
`
`.___11 a·,
`
`.___11a2
`
`.___11 a·,
`
`.___1102
`
`.___110,
`
`.___110,
`
`.___11a2
`
`.___110,
`
`.___11a2
`
`110-< .___1102
`
`.___11a 1
`
`.___110 1
`
`.___1102
`
`.___1102
`
`.___110, ?I
`
`FIG. 18
`
`110i"_. ~
`110~:~
`
`110'"
`
`\Jl
`
`d .
`.
`~
`~ ......
`~ =
`......
`
`~ = =
`
`N
`~-..J
`
`N c c c
`
`~
`
`'JJ. =-
`~ .....
`'"""'
`00
`0 ......,
`N
`Ul
`
`0\
`
`00
`~ ....
`
`.... =
`\C = \C
`
`Hughes, Exh. 1016, p. 20
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 19 of 25
`
`6,081,909
`
`. •·· ...................••••
`
`2
`:..::;..c:
`,_a.
`8_c
`·- ,_
`C00
`
`~ N
`0
`0
`~ ~
`
`~ - - -
`~ " ................... -~ ~ ~ ~ ~ ~~~~'e
`
`0
`
`~
`
`~
`
`Hughes, Exh. 1016, p. 21
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 20 of 25
`
`6,081,909
`
`~------~1~----------
`
`0
`0
`
`u
`0
`
`••• a.
`
`0
`
`0
`
`Hughes, Exh. 1016, p. 22
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 21 of 25
`
`6,081,909
`
`u
`0
`
`c.
`0
`.....--
`
`1::
`0
`
`-0
`
`.....--
`
`...1::
`0
`
`Ol
`0
`
`0
`0
`
`-o
`0
`.....--
`
`Ol
`0
`
`0
`0
`
`..0
`0
`
`~
`
`C\l
`.
`~
`k:
`
`Hughes, Exh. 1016, p. 23
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 22 of 25
`
`6,081,909
`
`c
`0
`
`Hughes, Exh. 1016, p. 24
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 23 of 25
`
`6,081,909
`
`N
`m
`
`m
`
`IX)
`oc)
`
`L(')
`IX)
`
`N
`IX)
`
`00
`
`IX)
`r--..
`
`<.D
`r--..
`
`...........
`~
`............
`
`Q)
`+J
`
`0 a::::
`
`~
`0
`~
`~
`I..&.J
`
`C¥')
`C\l
`.
`(!)
`[;:
`
`Hughes, Exh. 1016, p. 25
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 24 of 25
`
`6,081,909
`
`(7)
`N
`
`CXJ
`N
`
`f"..
`N
`
`...--
`~ ..._
`
`Q)
`.........
`0 a::
`
`~
`0
`~
`~ w
`
`~
`t\l
`.
`~
`k:
`
`Hughes, Exh. 1016, p. 26
`
`

`
`U.S. Patent
`
`Jun.27,2000
`
`Sheet 25 of 25
`
`6,081,909
`
`.._
`Q)
`>
`·a:;
`u
`(/) c
`0 .._
`1-
`
`1 N
`
`1.{)
`
`-
`
`................
`.._ Q)
`Q)"'O
`-oo
`0 u
`u Q)
`~0
`
`), ,.,..,
`
`1.{)
`
`1.{)
`0
`1.{)
`
`0
`0
`1.{)
`
`'(cid:173)
`Q)
`>
`·a:;
`u
`(/)
`c
`0
`'-
`1-
`
`........_.._
`'- Q)
`Q)"'O
`-oo
`0 u
`u Q)
`~0
`
`Hughes, Exh. 1016, p. 27
`
`

`
`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(cid:173)
`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(cid:173)
`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 40
`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 50
`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. 55
`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(cid:173)
`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(cid:173)
`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
`
`15
`
`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 inefficiency
`must be compensated for by a reduction in the time overhead
`to provide a total efficiency equivalent to or better than those
`techniques having a zero decoding overhead.
`While superior to other loss-resilient techniques, Fourier
`10 transform-based techniques still require a substantial time
`overhead to perform. Hence, even using a Fourier transform(cid:173)
`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
`20 technique is determined by the entropy function of Infor(cid:173)
`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
`25 11% of the data items and redundant items are corrupted by
`errors. Proposed prior art error correction techniques are
`unable to both efficiently 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
`30 data items.
`While the deficiencies of prior art loss-resilient and error
`correcting techniques are generally tolerable for transmis(cid:173)
`sions of relatively short lengths, these deficiencies become
`less acceptable during transmissions of large quantities of
`35 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(cid:173)
`mized. The time performance of conventional techniques is
`generally insufficient to make the necessary recoveries in the
`45 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
`60 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
`65 efficiency.
`It is a further object of the present invention to provide a
`technique for creating encoded messages which, when
`
`Hughes, Exh. 1016, p. 28
`
`

`
`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(cid:173)
`ciated with the data items. Preferably, the minimum number
`of first edges is 2. The numbers are different positive integer
`values. A first distribution of different numbers of first edges,
`ranging from the maximum to the minimum, to be associ(cid:173)
`ated with the plurality of data items is computed. An
`associated number of first edges, within the range, is estab(cid:173)
`lished for each data item. The associated numbers are
`established so that the different numbers of first edges are
`associated with the data items according to the computed
`first distribution.
`The first distribution of numbers of first edges can be
`computed by 2;+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+l. 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.
`In accordance with other aspects of the invention, the
`number of lost data items which are recoverable, expressed
`as a fraction, is designated a and is determined by finding a
`p value satisfying the inequality p(1-aA(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 a. The
`value of A corresponds to the first distribution and the value 55
`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(cid:173)
`ing to a for a fixed A. 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
`
`10
`
`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(cid:173)
`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
`15 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
`20 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
`25 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(cid:173)
`sponding to a number of the data items equal to the asso(cid:173)
`ciated number of second edges. More particularly, the redun-
`30 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
`35 connected by edges.
`A threshold number of potential lost or corrupted data
`items is established. This will typically be the likely maxi(cid:173)
`mum number of data items requiring replacement or cor(cid:173)
`rection in the particular implementation. An encoded mes-
`40 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(cid:173)
`ing to the second distribution, only if the number of data
`items which are determined to be recoverable or correctable
`45 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
`50 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
`60 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(cid:173)
`bers of second edges. Preferably, each second edge is also
`65 randomly connected to a one or more of the first edges so as
`to provide the applicable distributions of first and second
`edges.
`
`Hughes, Exh. 1016, p. 29
`
`

`
`5
`BRIEF DESCRIPTION OF DRAWINGS
`
`6,081,909
`
`6
`BEST MODE FOR CARRYING OUT THE
`INVENTION
`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(cid:173)
`bined with the original data items 1 to form an encoded
`10 :~::~g; t~a~:~~e ar~~:~~ht~:·e!~~d7~;t~~~~{~u~. :r:~~:~
`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 en. 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 en,
`35 then the factor ~=1-(1/c) and the number nodes at 10' is ~n
`and at 10" is ~ 2n. At the last layer, the number of nodes is
`en 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
`40 layer of nodes 10, 10', 10" and 10"' includes an address with
`which the information contained therein is further associ(cid:173)
`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
`60 present invention, for a rate Y2 code, is approximately 0.03.
`This small increase over the decoding overhead of conven(cid:173)
`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/
`
`20
`
`25
`
`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(cid:173)
`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. 15
`FIG. 7 depicts the decoding process in accordance with
`the present invention.
`FIG. 8 is similar to FIG. 4, but reflects regular