Systems and processes for decoding chain reaction codes through inactivation

• US 6,856,263 B2
• Filed: 06/10/2003
• Issued: 02/15/2005
• Est. Priority Date: 06/11/2002
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Lassen, Soren, Karp, Richard, Shokrollahi, M. Amin
• Primary Examiner(s): WAMSLEY, PATRICK G
• Application Number:
  US10/459,370
• Publication Number:
  US 20040075592A1
• Time in Patent Office: 616 Days
• Field of Search: 341/50, 341/94, 375/295, 714/751, 714/786, 714/746, 714/752, 709/231
• US Class Current: 341/50
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/1191 Codes on graphs other than LDPC codes
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• 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: H03M 13/47 Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37

Abstract

A method for processing a chain reaction codes includes first selecting a source symbol which is associated an output symbol of degree two or higher (i.e., an output symbol which is itself associated with two or more input symbols), and subsequently deactivating the selected source symbol in an attempt to produce an output symbol of degree one. The inactivation process can be repeated either successively until an output symbol of degree one is identified, and/or whenever the decoding process is unable to locate an output symbol of degree one.

Claims

1. In a chain reaction code having a plurality of output symbols and a plurality of source symbols, wherein each output symbol is associated with one or more source symbols, the output symbols associated with one or more source symbols referred to as output symbols of degree one or higher, wherein at least one output symbol is associated with at least two source symbols, the output symbols associated with two or more source symbols referred to as output symbols of degree two or higher, and wherein at least one source symbol is marked as active, a method for processing the chain reaction code, comprising:

(i) selecting one of the active source symbols that is associated with an output symbol of degree two or higher; and

(ii) deactivating the selected source symbol that is associated with the output symbol of degree two or higher.

2. The method of claim 1, wherein (ii) deactivating the selected source symbol produces a deactivated source symbol and one or more recoverable source symbols, wherein each recoverable source symbol is associated with an output symbol of degree one.

3. The method of claim 2, further comprising:

(iii) recovering the values of the one or more deactivated source symbols; and

(iv) determining, based upon the recovered values of the one or more deactivated source symbols, the values of one or more recoverable source symbols.

4. The method of claim 3, further comprising repeating (i)-(iv) one or more times.

5. The method of claim 4, further comprising marking as active, a predetermined number of source symbols.

6. The method of claim 5, wherein marking as active, a predetermined number of source symbols comprises marking as active, all source symbols.

7. The method of claim 5, wherein marking as active, a predetermined number of source symbols comprises marking as active, at least one source symbol.

8. The method of claim 4, wherein repeating (i)-(iv) one or more times comprises repeating (i)-(iv) until no active source symbols remain.

9. The method of claim 3, wherein (iii) recovering the values of one or more of the deactivated source symbol comprises recovering the values of all of the deactivated source symbols.

10. The method of claim 3, wherein (iv) determining the values of one or more source symbols comprises determining the values of all of the source symbols.

11. The method of claim 2, further comprising repeating (i)-(ii) if any source symbols associated with an output symbol of degree two or higher remain in the chain reaction code.

12. The method of claim 11, further comprising:

reactivating the deactivated source symbol if the number of potentially recoverable source symbols does not exceed a predefined number; and

selecting another active source symbol.

13. The method of claim 2, further comprising repeating (i)-(ii) one or more times to produce one or more deactivated source symbols and one or more recoverable source symbols.

14. The method of claim 1, wherein (i) selecting one of the active source symbols comprises selecting an active source symbol associated with a first output symbol, wherein the first output symbol is associated with a first set of two active source symbols.

15. The method of claim 14, wherein at least one of the first set of two source symbols is associated with a second output symbol, the second output symbol being associated with a second set of two active source symbols.

16. The method of claim 15, wherein at least one of the second set of two source symbols is associated with a third output symbol, the third output symbol being associated with a third set of two active source symbols.

17. The method of claim 1, wherein (i) selecting one of the active source symbols associated with an output symbol of degree two or higher comprises:

identifying a source symbol which is associated with an output symbol that is itself associated with a predefined number of active source symbols,

wherein deactivating the selected source symbol comprises deactivating all but one of the active source symbols associated with the identified output symbol, and wherein the remaining active source symbol comprising a non-deactivated source symbol.

18. The method of claim 17, wherein the non-deactivated source symbol is associated with the fewest number of output symbols.

19. The method of claim 1, further comprising:

(iii) identifying at least one output symbol which is associated with only one active source symbol;

(iv) recovering the active source symbol associated with the identified output symbol; and

(v) determining that no output symbol remains which is associated with one active source symbol.

20. The method of claim 19, further comprising repeating (iv)-(v) for each of the identified output symbols associated with only one source symbol.

21. The method of claim 1, wherein selecting one of the active source symbols comprises selecting the active source symbol which is associated with the greatest number of output symbols.

22. The method of claim 1, wherein selecting one of the active source symbols comprises randomly selecting an active source symbol from a group of active source symbols that are each associated with an output symbol of degree two or higher.

23. The method of claim 1, wherein (i) selecting one of the active source symbols comprises:

(a) identifying an active source symbol;

(b) determining the number of active source symbols which are potentially recoverable if the identified active source symbol is deactivated; and

(c) if the number of potentially recoverable source symbols does not exceed a predefined number, repeating (a) and (b) for another active source symbol.

24. In a chain reaction code having a plurality of output symbols and a plurality of source symbols, wherein each output symbol is associated with one or more source symbols, the output symbols associated with one or more source symbols referred to as output symbols of degree one or higher, wherein at least one output symbol is associate with at least two source symbols, the output symbols associated with two or more source symbols referred to as output symbols of degree two or higher, and wherein at least one source symbol is marked as active, a method for processing the chain reaction code, comprising:

(i) determining that no output symbol within the chain reaction code is associated with only one source symbol;

(ii) selecting one of the active source symbols associated with an output symbol of degree two or higher; and

(iii) deactivating the selected source symbol associated with an output symbol of degree two or higher.

25. The method of claim 24, wherein (iii) deactivating the selected source symbol produces the deactivated source symbol and one or more recoverable source symbols, wherein each recoverable source symbol is associated with an output symbol of degree one.

26. The method of claim 25, further comprising repeating (i)-(iii).

27. In a chain reaction code having a plurality of multi-stage output symbols and a plurality of source symbols, each of the multi-stage output symbols comprising either an output symbol or a check symbol, wherein each of the multi-stage output symbols is associated with one or more source symbols, the multi-stage output symbols associated with one or more source symbols referred to as multi-stage output symbols of degree one or higher, wherein at least one multi-stage output symbol is associated with at least two source symbols, the multi-stage output symbols associated with two or more source symbols referred to as multi-stage output symbols of degree two or higher, and wherein at least one source symbol is marked as active, a method for processing the chain reaction code, comprising:

(i) selecting one of the active source symbols associated with a multi-stage output symbol of degree two or higher; and

(ii) deactivating the selected source symbol associated with a multi-stag output symbol of degree two or higher.

28. The method of claim 27, wherein (ii) deactivating the selected source symbol produces a deactivated source symbol and one or more recoverable source symbols, wherein each recoverable source symbol is associated with an output symbol of degree one or a check symbol of degree one.

29. The method of claim 28, further comprising:

(iii) recovering the values of the one or more deactivated source symbols; and

(iv) determining, based upon the recovered values of the one or more deactivated source symbols, the Values of one or more recoverable source symbols.

30. The method of claim 29, further comprising repeating (i)-(v) one or more times.

31. The method of claim 30, wherein at least one of the multi-stage output symbols comprises an output symbol for (i)-(v), and a check symbol for a subsequent repetition of (i)-(v).

32. The method of claim 30, wherein at least one of the multi-stage output symbols comprises a check symbol for (i)-(v), and an output symbol for a subsequent repetition of(i)-(v).

33. The method of claim 30, wherein at least one of the multi-stage output symbols comprises an output symbol for (i)-(v) until no active source symbol remains, and wherein thereafter, the at least one multi-stage output symbols comprises a check symbol.

34. The method of claim 30, wherein at least one of the multi-stage output symbols comprises a check symbol for (i)-(v) until no active source symbol remains, and wherein thereafter, the at least one multi-stage output symbols comprises an output symbol.

35. The method of claim 29, wherein (iii) recovering the values of one or more of the deactivated source symbol comprises recovering the values of all of the deactivated source symbols.

36. The method of claim 29, wherein (iv) determining the values of one or more source symbols comprises determining the values of all of the source symbols.

37. The method of claim 28, further comprising repeating (i)-(ii) one or more times to produce one or more deactivated source symbols and one or more recoverable source symbols.

38. The method of claim 37, further comprising:

reactivating the deactivated source symbol if the number of potentially recoverable source symbols does not exceed a predefined number; and

selecting another active source symbol.

39. The method of claim 28, further comprising repeating (i)-(ii) if any source symbols associated with a multi-stage output symbol of degree two or higher remain in the chain reaction code.

40. The method of claim 27, wherein (i) selecting one of the active source symbols comprises selecting an active source symbol associated with a first multi-stage output symbol, wherein the first multi-stage output symbol is associated with a first set of two active source symbols.

41. The method of claim 40, wherein at least one of the first set of two source symbols is associated with a second multi-stage output symbol, the second multi-stage output symbol being associated with a second set of two active source symbols.

42. The method of claim 41, wherein at least one of the second set of two source symbols is associated with a third multi-stage output symbol, the third multi-stage output symbol being associated with a third set of two active source symbols.

43. The method of claim 27, wherein (i) selecting one of the active source symbols comprises:

identifying a source symbol which is associated with a multi-stage output symbol that is itself associated with a predefined number of active source symbols, wherein deactivating the selected source symbol comprises deactivating all but one of the active source symbols associated with the identified multi-stage output symbol, and wherein the remaining active source symbol comprises a non-deactivated source symbol.

44. The method of claim 43, wherein the selected source symbol is associated with the fewest number of multi-stage output symbols.

45. The method of claim 27, wherein at least one of the multi-stage output symbols comprises an output symbol and at least one of the multi-stage output symbols comprises a check symbol.

46. The method of claim 27, wherein (i) selecting one of the active source symbols comprises selecting one the active source symbol which is associated with a multistage output symbol of degree two or higher, the multi-stage output symbol comprising two or more check symbols.

47. The method of claim 27, wherein (i) selecting one of the active source symbols comprises selecting one of the active source symbol which is associate with the greatest number of multi-stage output symbols.

48. The method of claim 27, wherein (i) selecting one of the active source symbols comprises randomly selecting an active source symbol from a group of active source symbols that are each associated with a multi-stage output symbol of degree two or higher.

49. The method of claim 27, wherein (i) selecting one of the active source symbols comprises:

(a) identifying an active source symbol;

(b) determining the number of active source symbols which are potentially recoverable if the identified active source symbol is deactivated; and

(c) if the number of recoverable source symbols does not exceed a number, repeating (a) and (b) for another active source symbol.

50. The method of claim 27, further comprising:

(iii) identifying at least one multi-stage output symbol which is associated with only one active source symbol;

(iv) recovering the active source symbol associated with the identified multi-stage output symbol; and

(v) determining that no multi-stage output symbol remains which is associated with only one active source symbol.

51. A system configured to process a chain reaction code having a plurality of output symbols and a plurality of source symbols, wherein each output symbol associated with one or more source symbols, the output symbols associated with one or more source symbols referred to as output symbols of degree one or higher, wherein at least one output symbol is associated with at least two source symbols, the output symbols associated with two or more source symbols referred to as output symbols of degree two or higher, and wherein at least one source symbol is marked as active, the system comprising:

(i) means for selecting one of the active source symbols associated with output symbol of degree two or higher; and

(ii) means for deactivating the selected source symbol associated with output symbol of degree two or higher.

52. The system of claim 51, wherein (ii) the means for deactivating the selected source symbol produces a deactivated source symbol and one or more recoverable source symbols, wherein each recoverable source symbol is associated with an symbol of degree one.

53. The system of claim 52, further comprising:

(iii) means for recovering the values of one or more deactivated source symbols; and

(iv) means for determining, based upon the recovered values of the deactivated source symbols, the values of one or more recoverable source symbols.

54. The system of claim 51, further comprising

(iii) means for identifying at least one output symbol which is associated with only one active source symbol;

(iv) means for recovering the active source symbol associated with the identified output symbol; and

(v) means for determining that no output symbol remains which is associated with only one active source symbol.

55. The system of claim 54, wherein a computer processor comprises (i)-(iv).

56. A computer program product, on a computer readable storage medium, for processing a chain reaction code having a plurality of output symbols and a plurality of source symbols, wherein each output symbol is associated with one or more source symbols, the output symbols associated with one or more source symbols referred to as output symbols of degree one or higher, wherein at least one output symbol is associated with at least two source symbols, the output symbols associated with two or more source symbols referred to as output symbols of degree two or higher, and wherein at least one source symbol is marked as active, the computer program product comprising:

(i) instruction code to select one of the active source symbols associated with an output symbol of degree two or higher; and

(ii) instruction code to deactivate the selected source symbol associated with the selected output symbol of degree two or higher.

57. The computer program product of claim 56, wherein (ii) the instruction code for deactivating the selected source symbol produces a deactivated source symbol and one or more recoverable source symbols, wherein each recoverable source symbol is associated with an output symbol of degree one.

58. The computer program product of claim 57, further comprising:

(iii) instruction code to identify at least one output symbol which is associated with only one active source symbol;

(iv) instruction code to recover the active source symbol associated with the identified output symbol; and

(v) instruction code to determine whether no output symbol remains which is associated with only one active source symbol.

59. The computer program product of claim 58, further comprising:

(iii) instruction code to recover the values of one or more deactivated source symbols; and

(iv) instruction code to determine, based upon the recovered values of the deactivated source symbols, the values of one or more of the recoverable source symbols.