PACKET ERROR CORRECTION IN NETWORKS
First Claim
1. In a packet encoding device, a method of encoding packets comprising:
- at the encoding device, receiving a message packet;
subdividing the received message packet into a sequence of k symbols, each of k symbols comprising p>
1 bits and each being a symbol in a symbol alphabet defined over GF(q), wherein q is a positive integer;
encoding the k symbols into a computed codeword block of n symbols ci, i=[0, . . . , n−
1], wherein n>
k,wherein the n symbols of the computed codeword block satisfy a family of equations calculated over GF(q) and having parameters q, α and
β
,wherein each symbol ci is a symbol in the symbol alphabet defined over GF(q),and wherein α and
β
are both positive integers, and a specifies a number x≦
α
of the n symbols that are recoverable by an inverse decoding procedure applied to a modified codeword block that corresponds to the computed codeword block with x of the symbols having undetermined values;
packetizing the computed codeword block of n symbols into a sequence of m>
1 network packets, each network packet in the sequence including an indicator of its position in the sequence; and
transmitting the sequence of network packets on a network communicatively coupled with the packet encoding device.
3 Assignments
0 Petitions
Accused Products
Abstract
An apparatus and a method for packet error correction in packet-switched networks is provided. Message packets to be transmitted on a network are subdivided into k symbols over GF(q), and the symbols are then encoded by a symbol-level encoder into a codeword of n>k symbols over GF(q). The codeword is transmitted on the network in a plurality of network packets to a symbol-level decoder, which recovers any symbols lost or corrupted in transmission. Encoding at the symbol level increases the amount of data that can be recovered in any single correction operation. The efficiency of the decoding is also enhanced because the location of symbol errors can be determined prior to decoding.
24 Citations
20 Claims
-
1. In a packet encoding device, a method of encoding packets comprising:
-
at the encoding device, receiving a message packet; subdividing the received message packet into a sequence of k symbols, each of k symbols comprising p>
1 bits and each being a symbol in a symbol alphabet defined over GF(q), wherein q is a positive integer;encoding the k symbols into a computed codeword block of n symbols ci, i=[0, . . . , n−
1], wherein n>
k,wherein the n symbols of the computed codeword block satisfy a family of equations calculated over GF(q) and having parameters q, α and
β
,wherein each symbol ci is a symbol in the symbol alphabet defined over GF(q), and wherein α and
β
are both positive integers, and a specifies a number x≦
α
of the n symbols that are recoverable by an inverse decoding procedure applied to a modified codeword block that corresponds to the computed codeword block with x of the symbols having undetermined values;packetizing the computed codeword block of n symbols into a sequence of m>
1 network packets, each network packet in the sequence including an indicator of its position in the sequence; andtransmitting the sequence of network packets on a network communicatively coupled with the packet encoding device. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A packet encoding device comprising:
-
means for receiving a message packet; means for subdividing the received message packet into a sequence of k symbols, wherein each of k symbols comprises p>
1 bits and each is a symbol in a symbol alphabet defined over GF(q), wherein q is a positive integer;means for encoding the k symbols into a computed codeword block of n symbols ci, i=[0, . . . , n−
1], wherein n>
k,wherein the n symbols of the computed codeword block satisfy a family of equations calculated over GF(q) and having parameters q, α and
β
,wherein each symbol ci is a symbol in the symbol alphabet defined over GF(q), and wherein α and
β
are both positive integers, and α
specifies a number x≦
α
of the n symbols that are recoverable by an inverse decoding procedure applied to a modified codeword block that corresponds to the computed codeword block with x of the symbols having undetermined values;means for packetizing the computed codeword block of n symbols into a sequence of m>
1 network packets, wherein each network packet in the sequence includes an indicator of its position in the sequence; andmeans for transmitting the sequence of network packets on a network with which the packet encoding device is configured to be communicatively coupled. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A tangible computer-readable medium having instructions stored thereon that, upon execution by a packet encoding device, cause the packet encoding device to carry out functions comprising:
-
receiving a message packet; subdividing the received message packet into a sequence of k symbols, wherein each of k symbols comprises p>
1 bits and each is a symbol in a symbol alphabet defined over GF(q), wherein q is a positive integer;encoding the k symbols into a computed codeword block of n symbols ci, i=[0, . . . , n−
1], wherein n>
k,wherein the n symbols of the computed codeword block satisfy a family of equations calculated over GF(q) and having parameters q, α and
β
,wherein each symbol ci is a symbol in the symbol alphabet defined over GF(q), and wherein α and
β
are both positive integers, and a specifies a number x≦
α
of the n symbols that are recoverable by an inverse decoding procedure applied to a modified codeword block that corresponds to the computed codeword block with x of the symbols having undetermined values;packetizing the computed codeword block of n symbols into a sequence of m>
1 network packets, wherein each network packet in the sequence includes an indicator of its position in the sequence; andtransmitting the sequence of network packets on a network to which the encoding device is configured to be communicatively coupled. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification