Systems, methods, apparatus and computer program products for highly reliable file delivery using compound and braided FEC encoding and decoding

• US 8,726,136 B2
• Filed: 03/07/2013
• Issued: 05/13/2014
• Est. Priority Date: 02/08/2008
• Status: Active Grant

• Current Assignee: KenCast Inc.
• Original Assignee: KenCast Inc.
• Inventors: Fang, Weimin
• Primary Examiner(s): Rizk, Sam
• Application Number:
  US13/789,144
• Publication Number:
  US 20130185613A1
• Time in Patent Office: 432 Days
• Field of Search: 714/755, 714/699, 714/776, 370/231
• US Class Current: 714/776
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/11 using multiple parity bits
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/2909 Product codes
• CPC Class Codes: H03M 13/2921 wherein error correction coding involves a diagonal direction
• CPC Class Codes: H03M 13/2927 Decoding strategies
• CPC Class Codes: H03M 13/293 with erasure setting
• CPC Class Codes: H03M 13/3746 with iterative decoding
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0065 Serial concatenated codes

Abstract

Systems, methods, apparatus and computer program products provide highly reliable file delivery using a combination of packet-level FEC on source data packets which are arranged in matrices, where encoding is performed on both rows and columns or on rows, columns and diagonals.

Claims

1. A method for reconstructing a source file, comprising the steps of:

receiving a plurality of packets, wherein each packet is at least one of a source packet or an FEC packet;

storing each source packet into a corresponding source packet matrix;

storing each FEC packet;

determining, for each row of the source packet matrix, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the row;

recovering a first source packet that has not been received;

updating a status information field of a column and a diagonal associated with the recovered first source packet;

determining, for each column of the source packet matrix, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the column;

recovering a second source packet that has not been received;

updating a status information field of a row and a diagonal associated with the recovered second source packet; and

determining, for each diagonal of the source packet matrix, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the diagonal;

recovering a third source packet that has not been received; and

updating a status information field of a row and a column associated with the recovered third source packet.

2. A non-transitory computer-readable medium having stored thereon sequences of instructions, the sequences of instructions including instructions which, when executed by a computer system, cause the computer system to perform:

receiving a plurality of packets, wherein each packet is at least one of a source packet or an FEC packet;

storing each source packet into a corresponding source packet matrix;

storing each FEC packet;

determining, for each row of the source packet matrix, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the row;

recovering a first source packet that has not been received;

updating a status information field of a column and a diagonal associated with the recovered first source packet;

determining, for each column of the source packet matrix, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the column;

recovering a second source packet that has not been received;

updating a status information field of a row and a diagonal associated with the recovered second source packet; and

determining, for each diagonal of the source packet matrix, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the diagonal;

recovering a third source packet that has not been received; and

updating a status information field of a row and a column associated with the recovered third source packet.

3. An apparatus for reconstructing a source file, comprising:

a receiver configured to receive a plurality of packets, wherein each packet is at least one of a source packet or an FEC packet;

a memory configured to store each source packet into a corresponding source packet matrix and to store each FEC packet;

a processor configured to determine, for each row of the source packet matrix, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the row; and

a decoder configured to recover a first source packet that has not been received and to update a status information field of a column and a diagonal associated with the recovered first source packet,

the processor being further configured to determine, for each column of the source packet matrix, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the column,

the decoder being further configured to recover a second source packet that has not been received and to update a status information field of a row and a diagonal associated with the recovered second source packet,

the processor being further configured to determine, for each diagonal of the source packet matrix, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the diagonal, and

the decoder being further configured to recover a third source packet that has not been received and to update a status information field of a row and a column associated with the recovered third source packet.

4. A method for reconstructing a source file, comprising the steps of:

receiving a plurality of packets, wherein each packet is at least one of a source packet or an FEC packet;

storing each source packet into a corresponding n-dimensional source packet cube, wherein the source packet cube has a plurality of directions, each direction including at least two of the source packets, each of the source packets being included in a plurality of non-parallel directions, and wherein n is an integer greater than or equal to 3;

storing each FEC packet;

determining, for each of the plurality of directions of the source packet cube, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the corresponding direction;

recovering a source packet that has not been received; and

updating a status information field of other directions of the source packet cube that include the recovered source packet.

5. A non-transitory computer-readable medium having stored thereon sequences of instructions, the sequences of instructions including instructions which, when executed by a computer system, cause the computer system to perform:

receiving a plurality of packets, wherein each packet is at least one of a source packet or an FEC packet;

storing each source packet into a corresponding n-dimensional source packet cube, wherein the source packet cube has a plurality of directions, each direction including at least two of the source packets, each of the source packets being included in a plurality of non-parallel directions, and wherein n is an integer greater than or equal to 3;

storing each FEC packet;

determining, for each of the plurality of directions of the source packet cube, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the corresponding direction;

recovering a source packet that has not been received; and

updating a status information field of other directions that include the recovered source packet.

6. An apparatus for reconstructing a source file, comprising:

a receiver configured to receive a plurality of packets, wherein each packet is at least one of a source packet or an FEC packet;

a memory configured to store each source packet into a corresponding n-dimensional source packet cube and to store each FEC packet, wherein the source packet cube has a plurality of directions, each direction including at least two of the source packets, each of the source packets being included in a plurality of non-parallel directions, and wherein n is an integer greater than or equal to 3;

a processor configured to determine, for each of the plurality of directions of the source packet cube, whether at least one of the source packets has not been received and can be recovered based, in part, on a status information field of the corresponding direction; and

a decoder configured to recover a source packet that has not been received and to update a status information field of other directions that include the recovered source packet.