Forward error correction system for packet based data and real time media, using cross-wise parity calculation
First Claim
1. A method of communicating payload through a packet switched telecommunications network, said network including a first node and a second node, said payload defining a sequence of windows of k payload blocks, said sequence including a current window of k payload blocks and a subsequent window of k payload blocks, said method comprising, in combination:
- at said first node, generating p parity blocks by an encoding process comprised of functionally combining together the k payload blocks of the current window, wherein p≧
1, and wherein at least one of said p parity blocks comprises a cross-wise parity block derived as a function of said k payload blocks of said current window taken along an index-shifted path through said k payload blocks of said current window;
piggy-backing said p parity blocks onto a number of payload blocks in the subsequent window;
transmitting into the network the k payload blocks of the current window; and
transmitting into the network the k payload blocks of the subsequent window, whereby the k payload blocks of the subsequent window includes the p parity blocks.
6 Assignments
0 Petitions
Accused Products
Abstract
A computationally simple yet powerful forward error correction code scheme for transmission of real-time media signals, such as digitized voice, video or audio, in a packet switched network, such as the Internet. For each window of k data packets, the invention generates and transmits at least one cross-wise parity packet taken as an index-shifted function over the k data packets. The invention thereby enables a receiving end to recover from packet loss.
-
Citations
29 Claims
-
1. A method of communicating payload through a packet switched telecommunications network, said network including a first node and a second node, said payload defining a sequence of windows of k payload blocks, said sequence including a current window of k payload blocks and a subsequent window of k payload blocks, said method comprising, in combination:
-
at said first node, generating p parity blocks by an encoding process comprised of functionally combining together the k payload blocks of the current window, wherein p≧
1, and wherein at least one of said p parity blocks comprises a cross-wise parity block derived as a function of said k payload blocks of said current window taken along an index-shifted path through said k payload blocks of said current window;
piggy-backing said p parity blocks onto a number of payload blocks in the subsequent window;
transmitting into the network the k payload blocks of the current window; and
transmitting into the network the k payload blocks of the subsequent window, whereby the k payload blocks of the subsequent window includes the p parity blocks. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
subsequently, at said second node, recovering r of said k payload blocks of said current window by employing a decoding process comprised of functionally combining together r of said p parity blocks and k−
r of said k payload blocks of said current window.
-
-
9. A method as claimed in claim 8, wherein functionally combining said r parity blocks and said k−
- r payload blocks comprises index-shifting at least one of said k−
r payload blocks.
- r payload blocks comprises index-shifting at least one of said k−
-
10. A method as claimed in claim 8, wherein functionally combining said r payload blocks and said k−
- r payload blocks comprises computing an XOR sum.
-
11. A method as claimed in claim 8, wherein functionally combining said r parity blocks and said k−
- r payload blocks comprises, for each given one of said r parity blocks, (i) index-shifting each respective one of said k−
r payload blocks to the same extent, if any, that said respective one of said k−
r payload blocks was shifted in said encoding process, and (ii) computing an XOR sum of said k−
r payload blocks and said given one of said r parity blocks.
- r payload blocks comprises, for each given one of said r parity blocks, (i) index-shifting each respective one of said k−
-
12. A method as claimed in claim 8, wherein said decoding process further comprises designating a memory space for recovery of each of said r payload blocks.
-
13. A method of communicating data through a packet switched telecommunications network, said network including a first node and a second node, said data defining a sequence of windows of k data packets, wherein each data packet defines a set of segments and further defines a packet beginning and a packet end, said set of segments including (i) a first segment located at a predetermined location in said data packet, said first segment known to contain a non-zero value, and (ii) a second segment located at said packet end, and wherein said sequence includes a current window of k data packets and a subsequent window of k data packets, said method comprising, in combination:
-
at said first node, generating p parity blocks by an encoding process comprised of swapping said first and second segments in each of said k data packets of said current window and then functionally combining together the k data packets of the current window, wherein p≧
1, and wherein at least one of said p parity blocks comprises a cross-wise parity block derived as a function of said k data packets of said current window taken along an index-shifted path through said k data packets of said current window;
piggy-backing said p parity blocks onto a number of data packets in the subsequent window;
transmitting into the network the k data packets of the current window; and
transmitting into the network the k data packets of the subsequent window, whereby the k data packets of the subsequent window includes the p parity blocks. - View Dependent Claims (14, 15, 16, 17)
subsequently, at said second node, recovering r of said k data packets of said current window by employing a decoding process comprised of functionally combining together r of said p parity blocks and k−
r of said k data packets of said current window.
-
-
17. A method as claimed in claim 16, wherein said decoding process further comprises, after recovering a given data packet, stripping any excess zeros from the recovered data packet, and again swapping said first and second segments.
-
18. A method of communicating payload through a packet switched telecommunications network, said network including a first node and a second node, said payload defining windows of k payload blocks including a first window of k payload blocks and a second window of k payload blocks, said method comprising, in combination, for each of said windows:
-
at said first node, (i) generating p parity packets each based on said k payload blocks of said first window, wherein p≧
1, and wherein at least one of said p parity packets comprises a cross-wise parity packet derived as a first function of said k payload blocks taken along an index-shifted path through said k data payload blocks, (ii) piggy-backing the p parity packets onto a number of payload blocks of said second window, (iii) forwarding into said network said k payload blocks of said first window, and (iv) forwarding into said network said number of payload blocks of said second window on which said p parity packets are piggy-backed; and
at said second node, deriving r of said k payload blocks based on a second function of r of said parity packets and k−
r of said k payload blocks of said first window.- View Dependent Claims (19, 20, 21, 22, 23, 24)
-
-
25. A method of communicating data through a packet switched telecommunications network, said data being divided into a sequence of data blocks, said method comprising, in combination, for each of k data blocks in said sequence:
-
generating p parity blocks based on said k data blocks, wherein p≧
1, and wherein at least one of said p parity blocks is a cross-wise parity block derived as a function of said k data blocks taken along an index-shifted path through said k data blocks;
combining the p parity blocks with a number of subsequent data blocks in said sequence; and
forwarding into said network destined for a receiving end said k data blocks and said number of subsequent data blocks with which p parity blocks are combined. - View Dependent Claims (26, 27)
-
-
28. A method of encoding a sequence of payload blocks in a telecommunications network to enable recovery of lost payload blocks, said method comprising, in combination:
-
deriving p parity blocks from each sequential group of k of said payload blocks, wherein p≧
1, and wherein at least one of said p parity blocks comprises a cross-wise parity block derived as a function of said k payload blocks taken along an index-shifted path through said k payload blocks; and
piggy-backing each of said p parity blocks, respectively, with a payload block in a subsequent sequential group of k of said payload blocks. - View Dependent Claims (29)
-
Specification