Constructing Forward Error Correction Codes

• US 20100153822A1
• Filed: 12/15/2008
• Published: 06/17/2010
• Est. Priority Date: 12/15/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Astavans, Ruchir, Crinon, Regis J., Li, Jin, Ali, Walid S.I., Mehrotra, Sanjeev, Huang, Cheng, Zuo, Xiping
• Application Number:
  US12/335,496
• Publication Number:
  US 20100153822A1
• Time in Patent Office: Days
• US Class Current: 714/776
• CPC Class Codes: H03M 13/134 Non-binary linear block codes not provided for otherwise
• 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: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

Construction and use of forward error correction codes is provided. A systematic MDS FEC code is obtained having a property wherein any set of contiguous or non-contiguous r packets can be lost during a data transmission of k data packets and r encoded packets and the original k packets can be recovered unambiguously. The systematic MDS FEC code is transformed into a (k+r, k) systematic MDS FEC code that guarantees at least one of the encoded packets is a parity packet. The starting systematic MDS FEC code may be Cauchy-based, and the transformation code derived from the starting Cauchy-based MDS FEC code allows for very efficient initialization, encoding and decoding operations.

Claims

1. A method of providing forward error correction, comprising:

populating an encoder with a forward error correction (FEC) code operable to enable a recovery of a loss of up to all of a set of packets comprising a set of contiguous or non-contiguous n packets, the n packets consisting of k data packets and r encoded packets;

transforming the FEC code such that at least one of the encoded packets in the transformed FEC code is a parity packet, which is the XOR of all k data packets; and

wherein the transformed FEC code is operable to enable a recovery of a loss of up to r packets.

2. The method of claim 1, wherein if the FEC code is used in a data transmission system wherein the original k data packets and the r encoded packets are transmitted over a network;

and

if the original k data packets and the r encoded packets are subjected to network packet losses;

the original k data packets and the r encoded packets are recoverable as long as less than or equal to r packets are lost in the transmission.

3. The method of claim 1, wherein the MDS FEC code may be expressed in matrix terms as a (k+r, k) systematic MDS code and wherein a matrix representing the (k+r, k) systematic MDS code is constructed with k rows by (k+r) columns, wherein a k+1 column represents the parity packet.

4. The method of claim 1, wherein the MDS FEC code is operable to enable a recovery of a loss of up to all r packets comprising a transmitted set of contiguous or non-contiguous n data packets may take the form of a generator matrix of the form

5. The method of claim 4, wherein after transforming the MDS FEC code such that the MDS FEC code is further consist of an additional parity packet, a resulting transformed MDS FEC code may take the form of a transformation matrix of the form

6. The method of claim 1, wherein the MDS FEC code operable to enable a recovery of a loss of up to r packets comprising a transmitted set of contiguous or non-contiguous k data packets is a Cauchy-based MDS FEC code that may take the form of a generator matrix of the form

7. The method of claim 6, wherein after transforming the Cauchy-based MDS FEC code such that the MDS FEC code is further operable to enable encoding of an additional parity packet, a resulting transformed Cauchy-based MDS FEC code may take the form of a transformation matrix of the form

8. The method of claim 1, wherein the forward error correction (FEC) code is extensible such that a first FEC code generator matrix may take a form of (k+r, k) where r is a prescribed number of additional recovery packets and such that a second FEC code generator matrix may take the form of (k+r′

, k) where r′

is a different prescribed number of additional recovery packets.

9. The method of claim 8, wherein the first and second data transmissions have different historical packet loss characteristics.

10. A system for providing forward error correction for data transmitted across a network, comprising:

an encoder including a transformed forward error correction (FEC) code being operable to enable a recovery of a loss of up to r packets comprising a transmitted set of contiguous or non-contiguous k data packets and r encoded packets, and one of the encoded packets being a parity packet.

11. The system of claim 10, wherein the FEC code comprises a maximum distance separable (MDS) FEC code wherein only k+r data and encoded packets must be sent across the network to enable recovery of up to r lost data packets.

12. The system of claim 11, wherein the MDS FEC code may be expressed in matrix terms as a (k+r, k) systematic MDS code and wherein a matrix representing the (k+r, k) systematic MDS code is constructed with k rows by (k+r) columns, wherein a k+1 column represents the parity packet.

13. The system of claim 11, wherein the transformed MDS FEC code operable to enable a recovery of a loss of up to any r packets comprising a transmitted set of contiguous or non-contiguous k+r data and coded packets is derived from an original MDS FEC code of a generator matrix of the form

14. The system of claim 13, wherein the MDS FEC code is a Cauchy-based MDS FEC code that may take the form of a generator matrix of the form

15. The method of claim 14, wherein after transforming the Cauchy-based MDS FEC code such that the MDS FEC code is further operable to enable encoding of an additional parity packet, a resulting transformed Cauchy-based MDS FEC code may take the form of a transformation matrix of the form

16. A computer-readable medium containing computer-executable instructions which when executed by a computer perform a method of providing forward error correction in a data transmission system, comprising:

populating an encoder with a forward error correction (FEC) code operable to enable a recovery of a loss of up to all of a set of packets comprising a set of contiguous or non-contiguous n packets, the n packets consisting of k data packets and r encoded packets;

transforming the FEC code such that at least one of the encoded packets in the transformed FEC code is a parity packet, which is the XOR of all k data packets; and

wherein the transformed FEC code is operable to enable a recovery of a loss of up to r packets.

17. The computer-readable medium of claim 16, wherein the FEC code comprises a maximum distance separable (MDS) FEC code wherein only k+r original and coded data packets must be sent across the network to enable recovery of r lost packets.

18. The computer-readable medium of claim 16, wherein if the FEC code is used in a data transmission system wherein the original k data packets and the r encoded packets are transmitted over a network;

and

if the original k data packets and the r encoded packets are subjected to network packet losses;

the original k data packets and the r encoded packets are recoverable as long as less than or equal to r packets are lost in the transmission.

19. The computer-readable medium of claim 16, wherein the MDS FEC code may be expressed in matrix terms as a (k+r, k) systematic MDS code and wherein a matrix representing the (k+r, k) systematic MDS code is constructed with k rows by (k+r) columns, wherein a k+1 column represents the parity packet.

20. The computer-readable medium of claim 16, wherein the MDS FEC code is operable to enable a recovery of a loss of up to all r packets comprising a transmitted set of contiguous or non-contiguous n data packets may take the form of a generator matrix of the form