System, method and apparatus for FEC encoding and decoding

• US 20060064626A1
• Filed: 09/22/2005
• Published: 03/23/2006
• Est. Priority Date: 09/22/2004
• Status: Active Grant

• Current Assignee: KenCast Inc.
• Original Assignee: KenCast Inc.
• Inventors: Fang, Weimin, Wolfgang, H. Lewis, Fischer, Michael J.
• Granted Patent: US 7,533,324 B2
• Time in Patent Office: Days
• US Class Current: 714/776
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0083 Formatting with frames or packets; Protocol or part of protocol for error control

Abstract

A system, method and apparatus are provided for encoding and decoding a source file. The source file is encoded by dividing it into a plurality of shares comprised of a plurality of packets. A bit vector is generated. For at least one share, an FEC packet is generated by XOR'"'"'ing a subset of packets from the plurality of packets in the share in accordance with the bit vector. The process of encoding continues until terminated. Once the FEC encoded packets are received, each of the plurality of packets which is not a linear combination of previously received packets is stored into a file. A sequence of XOR operations to perform in-place on the file to reconstruct the source file are generated and performed on the file.

Claims

1. A method for encoding a source file to be transmitted to a receiver, comprising the steps of:

(a) dividing the source file into a plurality of shares comprised of a plurality of packets;

(b) generating a bit vector;

(c) for at least one share, generating an FEC packet by XOR'"'"'ing a subset of packets from the plurality of packets in the share in accordance with the bit vector; and

(d) repeating steps (b) and (c).

2. The method according to claim 1, wherein the bit vector is at least one of a random bit vector and a pseudorandom bit vector.

3. The method according to claim 1, wherein for two or more shares processed in step (c), the shares are processed in a round-robin fashion and a starting share is randomly selected.

4. The method according to claim 1, wherein step (d) is repeated for a predetermined time.

5. The method according to claim 1, wherein step (d) is repeated for a predetermined number of rounds.

6. The method according to claim 1, wherein step (d) is repeated until a user defined trigger is set.

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

receiving a plurality of packets;

storing each of the plurality of packets which is not a linear combination of previously received packets into a file;

generating a sequence of XOR operations; and

performing the sequence of XOR operations in-place on the file to reconstruct the source file.

8. The method according to claim 7,

wherein the file comprises a plurality of independent shares, and the method further comprises:

performing on each independent share the sequence of XOR operations, wherein the sequence of XOR operations comprises a plurality of XOR operations constructed using a Gaussian elimination technique on a matrix of bit vectors associated with the stored packets, wherein each bit vector in the matrix represents a plurality of source packets which were XOR'"'"'ed to generate the associated stored packet.

9. The method according to claim 8, wherein for each stored packet, the associated bit vector is received along with the data for the stored packet.

10. The method according to claim 8, wherein the bit vector associated with each stored packet is constructed using a pseudorandom number generator and a seed value received along with the stored packet.

11. An FEC encoder for encoding a source file to be transmitted to a receiver, comprising:

a packetizer operable to divide the source file into a plurality of shares comprised of a plurality of packets;

a bit vector generator operable to generate a bit vector; and

an encoder operable to, for at least one share, generate an FEC packet by XOR'"'"'ing a subset of packets from the plurality of packets in the share in accordance with the bit vector.

12. The FEC encoder according to claim 11, wherein the bit vector is at least one of a random bit vector and a pseudorandom bit vector.

13. The FEC encoder according to claim 11, wherein for two or more shares, the encoder processes the shares in a round-robin fashion and a starting share is randomly selected.

14. The FEC encoder according to claim 11, further comprising:

a timer operable to control how long FEC packets are generated.

15. The FEC encoder according to claim 11, further comprising:

a counter operable to control how many FEC packets are generated.

16. The FEC encoder according to claim 11, further comprising:

a triggering unit operable to control how many FEC packets are generated in accordance with a user defined triggering event.

17. An FEC decoder for reconstructing a source file, comprising:

a packet receiver operable to receive a plurality of packets and store each of the plurality of packets which is not a linear combination of previously received packets into a file; and

a decoder operable to generate a sequence of XOR operations to perform in-place on the file to reconstruct the source file.

18. The FEC decoder according to claim 17,

wherein the file comprises a plurality of independent shares, and

wherein the decoder performs on each independent share the sequence of XOR operations, wherein the sequence of XOR operations comprises a plurality of XOR operations constructed using a Gaussian elimination technique on a matrix of bit vectors associated with the stored packets, wherein each bit vector in the matrix represents a plurality of source packets which were XOR'"'"'ed to generate the associated stored packet.

19. The FEC decoder according to claim 18, wherein for each stored packet, the associated bit vector is received along with the data for the stored packet.

20. The FEC decoder according to claim 18, wherein the bit vector associated with each stored packet is constructed using a pseudorandom number generator and a seed value received along with the stored packet.

21. An apparatus for encoding a source file to be transmitted to a receiver, comprising:

means for dividing the source file into a plurality of shares comprised of a plurality of packets;

means for generating a bit vector;

means for generating, from at least one share, an FEC packet by XOR'"'"'ing a subset of packets from the plurality of packets in the share in accordance with the bit vector; and

means for controlling how long FEC packets are generated.

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

means for receiving a plurality of packets;

means for storing each of the plurality of packets which is not a linear combination of previously received packets into a file;

means for generating a sequence of XOR operations; and

means for performing the sequence of XOR operations in-place on the file to reconstruct the source file.

23. A computer program product comprising a computer usable medium having control logic stored therein for causing a computer to encode a source file to be transmitted to a receiver, said control logic comprising:

first computer readable program code for causing the computer to divide the source file into a plurality of shares comprised of a plurality of packets;

second computer readable program code for causing the computer to generate a bit vector;

third computer readable program code for causing the computer to, for at least one share, generate an FEC packet by XOR'"'"'ing a subset of packets from the plurality of packets in the share in accordance with the bit vector; and

fourth computer readable program code for causing the computer to repeat the second and third computer readable program code.

24. The computer program product of claim 23, wherein the bit vector is at least one of a random bit vector and a pseudorandom bit vector.

25. The computer program product of claim 23, wherein for two or more shares processed by the third computer readable program code, the third computer readable program code processes the shares in a round-robin fashion and randomly selects a starting share.

26. The computer program product of claim 23, further comprising:

fifth computer readable program code for causing the computer to repeat the fourth computer readable program code for a predetermined time.

27. The computer program product of claim 23, further comprising:

fifth computer readable program code for causing the computer to repeat the fourth computer readable program code for a predetermined number of rounds.

28. The computer program product of claim 23, further comprising:

fifth computer readable program code for causing the computer to repeat the fourth computer readable program code until a user defined trigger is set.

29. A computer program product comprising a computer usable medium having control logic stored therein for causing a computer to reconstruct a source file, said control logic comprising:

first computer readable program code for causing the computer to receive a plurality of packets;

second computer readable program code for causing the computer to store each of the plurality of packets which is not a linear combination of previously received packets into a file;

third computer readable program code for causing the computer to generate a sequence of XOR operations; and

fourth computer readable program code for causing the computer to perform the sequence of XOR operations in-place on the file to reconstruct the source file.

30. The computer program product of claim 29,

wherein the file comprises a plurality of independent shares, and

wherein the third computer readable program code further causes the computer to perform on each independent share the sequence of XOR operations, wherein the sequence of XOR operations comprises a plurality of XOR operations constructed using a Gaussian elimination technique on a matrix of bit vectors associated with the stored packets, and wherein each bit vector in the matrix represents a plurality of source packets which were XOR'"'"'ed to generate the associated stored packet.

31. The computer program product of claim 30, wherein for each stored packet, the associated bit vector is received along with the data for the stored packet.

32. The computer program product of claim 30, wherein the bit vector associated with each stored packet is constructed using a pseudorandom number generator and a seed value received along with the stored packet.