SYSTEMATIC ENCODING AND DECODING OF CHAIN REACTION CODES

• US 20090189792A1
• Filed: 04/03/2009
• Published: 07/30/2009
• Est. Priority Date: 10/05/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Luby, Michael G., Shokrollahi, M. Amin
• Granted Patent: US 9,236,885 B2
• Time in Patent Office: Days
• US Class Current: 341/51
• 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/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 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04L 1/00 Arrangements for detecting or preventing errors in the information received correcting synchronisation H04L7/00

Abstract

A method of encoding data into a chain reaction code includes generating a set of input symbols from input data. Subsequently, one or more non-systematic output symbols is generated from the set of input symbols, each of the one or more non-systematic output symbols being selected from an alphabet of non-systematic output symbols, and each non-systematic output symbol generated as a function of one or more of the input symbols. As a result of this encoding process, any subset of the set of input symbols is recoverable from (i) a predetermined number of non-systematic output symbols, or (ii) a combination of (a) input symbols which are not included in the subset of input symbols that are to be recovered, and (b) one or more of the non-systematic output symbols.

Claims

1. A method of encoding data into a chain reaction code having systematic output symbols and non-systematic output symbols, the method comprising:

generating, from the data, a set of input symbols, the input symbols comprising systematic output symbols; and

generating, from the set of input symbols, one or more non-systematic output symbols, wherein each of the one or more non-systematic output symbols is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols,

wherein any subset of the set of input symbols is recoverable from (i) a predetermined number of non-systematic output symbols, or (ii) a combination of (a) input symbols which are not included in the subset of input symbols that are to be recovered and (b) one or more of the non-systematic output symbols.

2. The method of claim 1, wherein generating one or more non-systematic output symbols comprises:

generating a plurality of intermediate input symbols from the set of input symbols; and

encoding the plurality of intermediate input symbols into one or more non-systematic output symbols, wherein one or more intermediate input symbols are encoded into one non-systematic output symbol.

3. The method of claim 2, wherein generating the plurality of intermediate input symbols comprises:

computing systematic keys for the plurality of input symbols; and

generating, from the plurality of input symbols and corresponding systematic keys, a plurality of intermediate input symbols.