Method and apparatus for forward error correction in packet networks

• US 6,141,788 A
• Filed: 10/13/1998
• Issued: 10/31/2000
• Est. Priority Date: 03/13/1998
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Schulszrinne, Henning Gunther, Rosenberg, Jonathan David
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US09/170,596
• Time in Patent Office: 749 Days
• Field of Search: 714/746, 714/774, 714/776
• US Class Current: 714/774
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/03 Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words

Abstract

A method for applying forward error correction in a transmission network includes the steps of choosing one of a plurality of possible error correction codes, using an appropriate field to encode a complete forward-error-correcting (FEC) code algorithm in each FEC packet to be transmitted. The packet stream, consisting of media packets and FEC packets can be sent to both FEC-capable and FEC-incapable receivers. Decoding methods are independent of the forward-error-correcting code transmitted. The sender can adapt the forward-error-correction code algorithm and the degree of error correction provided on a one-time basis or even more dynamically. Decoding and recovery at the receiver require no prior notification from the sender. Applying the FEC code algorithm to decode includes interrogating the bits in an offset bit mask in each FEC packet to yield links with media packets, and applying other fields of the FEC header to obtain instructions to recover lost data in one of the media packets. Based thereon, reiterative decoding of media packets ensures that lost data recoverable with combinations of media packets and FEC packets are recovered.

Claims

1. A method for applying forward error correction to media packets in a transmission network, comprising the steps of

choosing an error correcting code at a transmitter;

generating a set of FEC packets, each FEC packet containing an offset bitmask associating the FEC packet with a media packet and containing a field sufficient to impart the chosen error-correcting code to at least one FEC-capable receiver;

sending the packet stream, consisting of media packets and FEC packets, to the FEC-capable receiver; and

decoding the packet stream at the FEC-capable receiver, generating media packets as a result.

2. The method according to claim 1, wherein the step of generating the set of FEC packets includes the step of generating an FEC packet header, including the steps of:

generating a sequence number base;

generating the offset bit mask with data of offsets from said sequence number base indicating which media packets are associated with said FEC packet.

3. The method according to claim 2, wherein the step of generating the sequence number base comprises the steps of:

computing the minimum sequence number of all media packets associated with said FEC packet; and

setting said sequence number base to said minimum sequence number.

4. The method according to claim 3, wherein the step of generating the offset bitmask comprises the step of:

setting bit I in said bitmask if the media packet with sequence number K+I is associated with said FEC packet, the value of K being equal to said sequence number base.

5. The method according to claim 1, wherein the step of decoding comprises the steps of:

receiving a media packet;

linking each FEC packet received with those media packets associated with it;

checking whether sufficient media packets have been received to allow an FEC packet to be used to recover a missing media packet;

recovering said missing media packet should such checking succeed.

6. The method according to claim 5, wherein the step of linking comprises the steps of:

constructing an array;

setting the Kth entry of said array to point to said FEC packet if said FEC is associated with media packet with sequence number K;

further setting the Kth entry of said array to point to said media packet if said media packet is received, otherwise further setting said array to point to an empty object.

7. The method according to claim 6, wherein the step of linking further comprises the steps of:

associating a number with said FEC packet, said number having a value equal to the number of media packets that have been received that are associated with said FEC packet;

incrementing said number when another media packet is received that is associated with said FEC packet.

8. The method according to claim 6, wherein the step of checking further comprises the steps of:

associating array entry K with a received media packet, where K is also the sequence number of the received media packet;

traversing a list of FEC packets pointed to by array entry K;

for each FEC packet, counting the number of array entries associated with said FEC packet, which array entries are also associated with a media packet;

declaring said check to succeed if said counted number of array entries is equal to the number of array entries associated with said FEC packet, minus one.

9. The method of claim 7, wherein the step of checking further comprises the steps of:

associating array entry K with said media packet, where K is also the sequence number of said media packet as received;

traversing a list of FEC packets pointed to by array entry K;

for each FEC packet, increasing said number associated with said FEC packet by one;

declaring said check to succeed for any FEC packet if a count of said list is equal to said number of array entries associated with said FEC packet, minus one.

10. The method of claim 5, wherein the step of recovering further comprises the step of performing the exclusive or of the content of those media packets associated with said FEC packet, which media packets have been received with content of said FEC packet.

11. Apparatus for providing forward error correction in a transmission network for data packets transmitted therein, comprising:

apparatus for providing media data packets for transmission;

a transmission interface with the network;

a forward-error-correcting code generator for preparing the media data packets and separable forward-error-correcting packets for transmission through said transmission interface into said network, said forward-error-correcting code generator being capable of operating with a plurality of algorithms for forward error corrections;

an algorithm inserter for inserting one of the plurality of algorithms into said forward-error-correcting code generator;

a bitmask source for providing to said forward-error-correcting code generator an offset bitmask for insertion in the protocol header, the offset bitmask associating a forward-error-correction packet with at least one media packet;

a reception interface with said network; and

apparatus for providing an error-corrected version of the media data packets received from the network through the reception interface, including a decoder capable of acquiring and using any of a plurality of algorithms for forward-error-correction received through the interface from the network.

12. Apparatus according to claim 11, wherein the algorithm inserter comprises a first logic apparatus for inserting the one algorithm into a payload type header of each FEC packet.

13. Apparatus according to claim 12, wherein the bitmask source comprises a second logic apparatus controllable by the first logic apparatus for associating the forward-error-correcting packet with the at least one media packet.