Information additive code generator and decoder for communication systems

• US 20060087456A1
• Filed: 09/13/2005
• Published: 04/27/2006
• Est. Priority Date: 09/23/1998
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Luby, Michael G.
• Granted Patent: US 7,233,264 B2
• Time in Patent Office: Days
• US Class Current: 341/50
• CPC Class Codes: H03M 13/1191 Codes on graphs other than LDPC codes
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3746 with iterative decoding
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 1/004 by using forward error control H04L1/0618 takes precedence; coding, decoding or code conversion, for error detection or correction H03M13/00
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 12/1836 with heterogeneous network architecture

Abstract

An encoder uses an input file of data and a key to produce an output symbol. An output symbol with key I is generated by determining a weight, W(I), for the output symbol to be generated, selecting W(I) of the input symbols associated with the output symbol according to a function of I, and generating the output symbol'"'"'s value B(I) from a predetermined value function F(I) of the selected W(I) input symbols. An encoder can be called repeatedly to generate multiple output symbols. The output symbols are generally independent of each other, and an unbounded number (subject to the resolution of I) can be generated, if needed. A decoder receives some or all of the output symbols generated. The number of output symbols needed to decode an input file is equal to, or slightly greater than, the number of input symbols comprising the file, assuming that input symbols and output symbols represent the same number of bits of data.

Claims

1-20. -20. (canceled)

21. A method of storing data on a storage medium, the storage medium being such that it is possible that portions of data stored on the storage medium at one time are not recoverable from the storage medium at a later time, the method comprising:

reading input data to be stored;

arranging the input data into an ordered set of input symbols;

generating a plurality of output symbols from the input symbols, wherein the number of possible output symbols is much larger than the number of input symbols, wherein at least one output symbol is generated from more than one input symbol and from less than all of the input symbols in the set of input symbols; and

storing the plurality of output symbols on the storage medium in association with an identifier of the input data, such the ordered set of input symbols can be regenerated from any N of the stored output symbols, where N is an integer greater than one and much less than the number of possible output symbols.

22. The method of claim 21, wherein the input data is ordered in symbol order and arranging comprises identifying symbol boundaries without requiring movement of data among memory locations.

23. The method of claim 21, wherein the input data is a file and the association with an identifier is an association with a file identifier.

24. The method of claim 21, wherein N is slightly larger than the number of input symbols in the ordered set of input symbols.

25. The method of claim 21, wherein the size of each of the input symbols is one byte.

26. The method of claim 21, wherein the size of the each of the output symbols is the size of an input symbol.

27. The method of claim 21, wherein generating a plurality of output symbols includes, for each output symbol:

obtaining a key I for the output symbol, wherein the key I is selected from a key alphabet and the number of possible keys in the key alphabet is much larger than the number of input symbols in the ordered set of input symbols;

calculating, according to a predetermined function of I, a list AL(I) for the output symbol, wherein AL(I) is an indication of W(I) associated input symbols associated with the output symbol; and

generating an output symbol value B(I) from a predetermined function F(I) of the associated input symbols indicated by AL(I).

28. The method of claim 27, wherein F(I) is different for at least two values of I.

29. The method of claim 27, wherein F(I) is the same for all I.

30. The method of claim 29, wherein F(I) is an exclusive OR (XOR) of the input symbols indicated by AL(I).

31. The method of claim 21, wherein the storage medium is a hard disk.

32. The method of claim 21, wherein the storage medium is a CD-ROM.

33. A system for generating an output file including output symbols generated from an input file, wherein the output symbols are used to regenerate the input file, the system comprising:

an encoder capable of receiving a plurality of input symbols generated from an input file, the encoder including an output symbol generator capable of generating a plurality of output symbols from the input symbols, wherein the number of possible output symbols is much larger than the number of input symbols, wherein at least one output symbol is generated from more than one input symbol and from less than all of the input symbols in a set of input symbols, and wherein the output symbols are stored in at least one output file, wherein the at least one output file includes a number of output symbols greater than the number of input symbols, wherein the number of output symbols is sufficient to recover the input file.

34. The system of claim 33, further comprising a key generator, coupled to the encoder, that generates a plurality of keys I, wherein the encoder generates a corresponding output symbol for each of the plurality of keys I.

35. The system of claim 33, wherein the encoder comprises:

an associator that, for each output symbol to be generated, generates a list of associated input symbols; and

a calculator, coupled to the associator, that, for each output symbol to be generated, calculates an output symbol value from the associated input symbols according to a value function.

36. The system of claim 35, wherein the associator calculates, according to a predetermined function of I, a list AL(I) for an output symbol corresponding to the keys I, wherein AL(I) is an indication of W(I) associated input symbols associated with the output symbol corresponding to the keys I, and wherein weights W are positive integers that vary between at least two values, and wherein at least one of the weights W is greater than 1 and less than the number of input symbols in the input file.

37. The system of claim 33, further comprising an input symbol generator coupled to the encoder, wherein the input symbol generator is capable of outputting the input symbols as an ordered set of input symbols.

38. The system of claim 33, wherein the input file comprises at least one stream of data or file.

39. The system of claim 33, wherein the output file comprises a plurality of distinct output files, wherein at least a portion of each distinct output file is capable of providing a portion of the number of output symbols required to recover the input file.

40. A system for reading data transmitted via a storage channel, the system comprising:

a receive module coupled to the storage channel for receiving output symbols transmitted via the storage channel, wherein each output symbol is generated from at least one input symbol in an ordered set of input symbols, wherein each input symbol is generated from an input file, wherein at least one output symbol is generated from more than one input symbol and less than all of the input symbols in the set of input symbols, wherein the number of possible output symbols is much larger than the number of input symbols in the set of input symbols;

a decoder coupled to the receive module, the decoder configured to allow storing an number N of the output symbols received in at least one output file, wherein N is an integer greater than one and much less than the number of possible output symbols, wherein the decoder is capable of regenerating the ordered set of input symbols from the N number of output symbols; and

an input file reassembler coupled to the decoder, wherein the reassembler is capable of regenerating the input file from the regenerated ordered set of input symbols.

41. The system of claim 40, further comprising a key regenerator coupled to the decoder that generates a key corresponding to the output symbol for each received output symbol.

42. The system of claim 40, wherein the decoder comprises an associator, wherein for each received output symbol, the associator generates an indication of input symbols associated with the output symbol.

43. The system of claim 42, wherein the decoder further comprises:

an output symbol buffer that stores information about each of the received output symbols; and

a weight selector coupled to the output symbol buffer that, for each received output symbol, generates a positive integer W that indicates the number of input symbols associated with the output symbol and stores the positive integer W in the output symbol buffer.

44. A method of processing encoded data stored on a storage medium to generate an input file associated with the encoded data, the method comprising:

reading an N number of output symbols from a storage medium, wherein the output symbols are generated from an ordered set of input symbols derived from an input file, wherein the number of possible output symbols is much larger than the number of input symbols, wherein at least one output symbol is generated from more than one input symbol and from less than all of the input symbols in the ordered set of input symbols;

reading a plurality of keys I from the storage medium corresponding to the output symbols;

upon reading any N number of the output symbols and corresponding keys I, regenerating the ordered set of input symbols from the N output symbols and respective keys I, wherein N is an integer greater than 1 and much less than the number of possible output symbols; and

regenerating the input file from the ordered set of input symbols.

45. The method of claim 44, wherein regenerating the ordered set of input symbols comprises:

processing each received output symbol by determining which of the input symbols are associated with that output symbol;

determining if enough information has been received to decode any input symbols; and

decoding input symbols that can be decoded from the information received.

46. The method of claim 45, wherein processing each received output symbol includes:

determining a key I for the output symbol;

determining a weight W(I) for the output symbol; and

determining W(I) associated input symbols for the output symbol.

47. The method of claim 45, wherein processing each received output symbol further includes determining a value function F(I) for that output symbol, wherein the output symbol is the function F(I) of the associated input symbols.

48. The method of claim 44, wherein some of the output symbols are read from a first storage medium and wherein some of the output symbols are received from a second storage medium.

49. The method of claim 48, wherein at least some of the output symbols are read from at least the first storage medium and the second storeage medium to obtain a sufficent quantity of output symbols to recover the input file.

50. The method of claim 44, wherein the plurality of keys I are stored on a separate storage medium from the storage medium used to store the output symbols.

51. A computer data signal stored in a computer readable medium, the computer data signal comprising:

a plurality of output symbols, wherein the plurality of output symbols represent symbols generated from input symbols, wherein the number of possible output symbols is much larger than the number of input symbols, wherein at least one output symbol represents a symbol generated from more than one input symbol and less than all of the input symbols in the set of input symbols, wherein a reader of the data signal can regenerate the ordered set of input symbols from any N of the output symbols, wherein N is an integer greater than one and much less than the number of possible output symbols.

52. A rateless encoder, comprising:

an encoder that generates output symbols selected from a set of possible output symbols wherein the number of possible output symbols is independent of the number of input symbols.