FORWARD ERROR CORRECTION FOR BURST AND RANDOM PACKET LOSS FOR REAL-TIME MULTI-MEDIA COMMUNICATION

• US 20090193314A1
• Filed: 01/22/2009
• Published: 07/30/2009
• Est. Priority Date: 01/25/2008
• Status: Active Grant

• Current Assignee: Nevion Europe AS
• Original Assignee: Nevion USA, Inc.
• Inventors: Koh, Chin Chye, Melliar-Smith, Peter Michael, Moser, Louise Elizabeth
• Granted Patent: US 8,230,316 B2
• Time in Patent Office: Days
• US Class Current: 714/755
• 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/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/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/175 Error trapping or Fire codes
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
• CPC Class Codes: H03M 13/2921 wherein error correction coding involves a diagonal direction
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

This invention relates generally to a packet recovery algorithm for real-time (live) multi-media communication over packet-switched networks, such as the Internet. Such multi-media communication includes video, audio, data or any combination thereof. More specifically, the invention comprises a forward error correction (FEC) algorithm that addresses both random and burst packet loss and errors, and that can be adjusted to tradeoff the recoverability of missing packets and the latency incurred. The transmitter calculates parity packets for the rows, columns and diagonals of a block of multi-media data packets using the exclusive or (XOR) operation and communicates the parity packets along with the multi-media data packets to the receiver. The receiver uses the parity packets to recover missing multi-media data packets in the block. The FEC algorithm is designed to be able to recover long bursts of consecutive missing data packets. If some parity packets are missing, they too can be recovered using an extra single parity packet, so that they can be used to recover other missing data packets. The invention applies to both one-way real-time streaming applications and two-way real-time interactive applications, and to both wired and wireless networks. The invention retains backwards compatibility with existing standards governing FEC for professional video over IP networks.

Claims

1. A method for communication of multi-media data comprising the steps of:

arranging multi-media data packets at a transmitter into a two-dimensional block A wherein

block A has D horizontal rows and L vertical columns,

one (1) is less than D is less than or equal to L,

i and j are indices indicating rows and columns respectively of block A,

A[i,j] indicates the entry at the ith row and jth column of the block,

zero (0) is less than or equal to i is less than D,

zero (0) is less than or equal to j is less than L,

block A has a set of diagonals, each with a slant S,

one (1) is less than or equal to S is less than L,

each diagonal includes D entries in block A at A[i, (L−

1−

k−

S×

i) mod L] where

zero (0) is less than or equal to i is less than D, and

the set of diagonals consists of L diagonals;

generating one or more of row parity packets wherein one packet is generated for each row of block A;

generating one or more column parity packets wherein one packet is generated for each column of block A;

generating one or more diagonal parity packets wherein one packet is generated for each diagonal in the set of diagonals;

calculating each parity packet as an exclusive or (XOR) of the packets in the row, column or diagonal for which the parity packet is being calculated;

communicating the data and related parity information from the transmitter to the receiver in a plurality of packets;

the receiver arranging received data packets into a block having the same dimensions D×

L as the block A used by the transmitter;

the receiver identifying missing packets and corrupted packets; and

,

the receiver recovering missing packets and corrupted packets by processing the rows, columns and diagonals with a single missing data packet and iterating until no more missing packets can be recovered.

2. The method of claim 1, further comprising the steps of:

selecting the values of D, L and S to provide recovery of both individual random missing packets and bursts of consecutive missing packets;

selecting the values of D and L such that the multi-media data to be communicated, such as a video or audio frame, can be accommodated in D×

L packets;

selecting the values of L and S such that the maximum anticipated length of a burst of missing packets is less than or equal to 2×

L−

S;

selecting the values of D, L and S such that D×

S and L are relatively prime, i.e., D×

S and L have no common divisor other than 1; and

,

selecting the values of D, L and S such that, for all n, where one (1) is less than or equal to n is less than or equal to D−

1, the value 2×

n×

S is not a multiple of L.

3. The method of claim 2, further comprising the steps of:

the receiver maintaining a Missing Data Packets data structure that records the data packets in said block that it has not received and has not yet recovered;

the receiver determining the number of missing data packets in each row, column and diagonal of said block;

the receiver maintaining a Single Missing Data Packets data structure that records the index of each row, column and diagonal of said block that currently has exactly one missing data packet;

the receiver using, for each row, column and diagonal recorded in said Single Missing Data Packets data structure, the parity packet for that row, column or diagonal to recover said missing data packet;

the receiver inserting the recovered data packet into the block of data packets.

4. The method of claim 3, further comprising the steps of:

as it receives a data packet or recovers a missing data packet that it has not received and inserts said data packet into said block, the receiver determining the number of missing data packets in the row, column and diagonal that contain said data packet;

if the number of missing data packets in said row, column or diagonal now equals one, the receiver inserting the index of said row, column or diagonal with exactly one missing packet into said Single Missing Data Packets data structure; and

,

thereafter, the receiver using the parity packet for said row, column or diagonal inserted into said Single Missing Data Packets data structure to recover said missing data packet and inserting the recovered data packet into said block.

5. The method of claim 4, further comprising the steps of:

when the receiver has received a data packet or recovered a data packet that it did not receive and has inserted said packet into said block, the receiver determining the number of missing data packets in each row, column and diagonal;

the receiver selecting a row, column or diagonal that has exactly one missing data packet;

the receiver using the parity packet for that row, column or diagonal to recover said missing data packet; and

,

the receiver inserting said recovered data packet into said block of data packets.

6. The method of claim 4, further comprising the steps of:

when the receiver has received a data packet or recovered a data packet that it did not receive and has inserted said packet into said block of data packets, the receiver determining the number of missing data packets in said row, column and diagonal that contain said recovered data packet; and

,

if the number of missing data packets in said row, column or diagonal now equals one, the receiver inserting the index of said row, column or diagonal with one missing data packet into said Single Missing Data Packets data structure.

7. The method of claim 4, further comprising the steps of:

the receiver maintaining a Number of Missing Data Packets data structure that records the number of data packets in each row that are currently missing, the number of data packets in each column that are currently missing and the number of data packets in each diagonal that are currently missing;

the receiver initially counting all data packets as missing and the Number of Missing Data Packets data structure indicating the total number of data packets for each row, column and diagonal that are to be received;

when the receiver receives a data packet or recovers a corrupted or lost data packet and inserts said data packet into the block, the receiver decrementing the numbers recorded in said Number of Missing Data Packets data structure for the row, column and diagonal that contain said recovered data packet; and

,

if any of the decremented numbers now equals one, the receiver inserting the index of said row, column or diagonal into said Single Missing Data Packets data structure.

8. The method of claim 2, further comprising the steps of:

selecting a calculation method that when used to calculate a single parity packet from each of plural row parity packets, plural column parity packets and plural diagonal parity packets results in three parity packets, each having the same value; and

,

using any one of the three parity packets to recover a missing parity packet in the set of row parity packets, the set of column parity packets and the set of diagonal parity packets.

9. The method of claim 8, further comprising the steps of:

calculating the single parity packet for all three sets of parity packets at the transmitter;

transmitting the single parity packet for receipt by the receiver;

if the receiver does not receive the single parity packet and the receiver has received all of the parity packets in the set of row parity packets, the receiver using said set of row parity packets to calculate the single parity packet;

if the receiver does not receive the single parity packet and the receiver has received all of the parity packets in the set of column parity packets, the receiver using the set of column parity packets to calculate the single parity packet; and

,

if the receiver does not receive the single parity packet and the receiver has received all of the parity packets in the set of diagonal parity packets, the receiver using the set of diagonal parity packets to calculate the single parity packet and the receiver using the single parity packet to recover one or more of one missing parity packet in a) the set of row parity packets, b) the set of column parity packets and c) the set of diagonal parity packets.

10. The method of claim 8, further comprising the steps of:

if all of the row parity packets are received at the receiver, the receiver calculating the single parity packet for all three sets of parity packets from the set of row parity packets and using the parity packet to recover any of one missing parity packet in the set of column parity packets, one missing parity packet in the set of diagonal parity packets;

if all of the column parity packets are received at the receiver, the receiver calculating the single parity packet for all three sets of parity packets from the set of column parity packets and using the parity packet to recover any of one missing parity packet in the set of row parity packets, one missing parity packet in the set of diagonal parity packets; and

,

if all of the diagonal parity packets are received at the receiver, the receiver calculating the single parity packet for all three sets of parity packets from the set of diagonal parity packets using the parity packet to recover any of one missing parity packet in the set of row parity packets and one missing parity packet in the set of column parity packets.

11. The method of claim 8, further comprising the steps of:

the receiver maintaining a Missing Parity Packets data structure that records the parity packets that it has not received and has not yet recovered;

the receiver determining the number of missing row parity packets, column parity packets and diagonal parity packets; and

,

if there is a single missing row parity packet or a single missing column parity packet or a missing diagonal parity packet, the receiver using the extra single parity packet to recover said single missing parity packet and inserting the recovered parity packet into said set of row parity packets or column parity packets or diagonal parity packets.

12. The method of claim 11, further comprising the steps of:

the receiver maintaining a Number of Missing Parity Packets data structure that records the number of row parity packets that are currently missing, the number of column parity packets that are currently missing, the number of diagonal parity packets that are currently missing, and a number that indicates whether the extra single parity packet is currently missing;

initially counting all parity packets as missing;

the Number of Missing Parity Packets data structure indicating the total numbers of row parity packets, column parity packets, diagonal parity packet and extra single parity packet that are to be received; and

,

the receiver decrementing the number recorded in said Number of Missing Party Packets data structure when the receiver has received or recovered a parity packet that was lost or corrupted and has inserted said parity packet into said set of parity packets.