Forward error correction for burst and random packet loss for real-time multi-media communication
First Claim
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 whereinblock 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, andthe 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;
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 recoveredselecting 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 Assignments
0 Petitions
Accused Products
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.
-
Citations
11 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, andthe 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; 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 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
Specification