Forward error correction method
First Claim
Patent Images
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, indexed by k, 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] wherezero (0) is less than or equal to i is less than D, andthe set of diagonals consists of L diagonals;
generating one or more 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 a 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 Assignments
0 Petitions
Accused Products
Abstract
This invention concerns packet recovery for real-time (live) multi-media communication over packet-switched networks like the Internet. Such communication includes video, audio, data or any combination thereof. The invention comprises forward error correction (FEC) algorithms addressing both random and burst packet loss and errors, and that can be adjusted to tradeoff the recoverability of missing packets and the latency incurred.
-
Citations
7 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, indexed by k, 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] wherezero (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 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 a 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. - View Dependent Claims (4, 5)
-
-
2. A method for communication of multi-media data comprising the steps of:
-
providing a transmitter and a receiver in a packet switched network; arranging multi-media data packets at the 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, indexed by k, 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] wherezero (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 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; for each row parity packet, calculating the packet as an exclusive or (XOR) of the packets in the row; for each column parity packet, calculating the packet as an exclusive or (XOR) of the packets in the column; for each diagonal parity packet, calculating the packet as an exclusive or (XOR) of the packets in the diagonal; 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.
-
-
3. 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 consists of the multi-media data packets, 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, indexed by k, 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] wherezero (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 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; for each row parity packet, calculating the packet as an exclusive or (XOR) of the packets in the row; for each column parity packet, calculating the packet as an exclusive or (XOR) of the packets in the column; for each diagonal parity packet, calculating the packet as an exclusive or (XOR) of the packets in the diagonal; communicating the data and related parity information from the transmitter to a 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.
-
-
6. 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 (l) 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 j is less than L, block A has a set of diagonals, indexed by k, each with a slant S, one (l) is less than or equal to S is less than L, and each diagonal includes D entries in block A at A[i, (L−
l−
k−
S×
i) mod L] wherezero (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 row parity packets wherein only a single packet is generated for each row of block A; generating one or more column parity packets wherein only a single packet is generated for each column of block A; generating one or more diagonal parity packets wherein only a single 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 a 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.
-
-
7. A method for communication of multi-media data without the use of Reed Solomon syndromes, the method 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 (l) 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 j is less than L, block A has a set of diagonals, indexed by k, each with a slant S, one (l) is less than or equal to S is less than L, and each diagonal includes D entries in block A at A[i, (L−
l−
k−
S×
i) mod L] wherezero (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 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 a 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.
-
Specification