Back to results
US 8,479,082 B2Granted
Packet error correction in networks
AssigneeIndian Institute of Technology Delhi
InventorRanjan Bose
Life of this patent
Estimating the term…
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.
Claims35
In a packet encoding device, a method of encoding packets comprising:
- receiving a message packet;
- subdividing the received message packet into a sequence of k symbols, each of the 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 c1 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.
6 more elements
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 the 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 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;
- 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;
- and
- means for transmitting the sequence of network packets on a network with which the packet encoding device is configured to be communicatively coupled.
6 more elements
A non-transitory 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 the 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;
- and
- transmitting the sequence of network packets on a network to which the encoding device is configured to be communicatively coupled.
6 more elements
A method comprising:
- encoding k symbols into a computed codeword block of n symbols ci, i=[0, . . . , n−1], wherein n>k, each of the k symbols being a symbol in a symbol alphabet defined over GF(q), wherein q is a positive integer,
- 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 α is a positive integer 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;
- and
- packetizing the computed codeword block of n symbols into a sequence of network packets, each network packet in the sequence including an indicator of its position in the sequence.
3 more elements
A packet encoding device programmed to execute instructions to carry out functions comprising:
- encoding k symbols into a computed codeword block of n symbols ci, i=[0, . . . , n−1], wherein n>k, each of the k symbols being a symbol in a symbol alphabet defined over GF(q), wherein q is a positive integer,
- 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 α is a positive integer 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;
- packetizing the computed codeword block of n symbols into a sequence of network packets, each network packet in the sequence including an indicator of its position in the sequence;
- and
- outputting the sequence of network packets.
4 more elements
A non-transitory computer-readable medium having instructions stored thereon that, upon execution by a computing device, cause the computing device to perform functions comprising:
- encoding k symbols into a computed codeword block of n symbols ci, i=[0, . . . , n−1], wherein n>k, each of the k symbols being a symbol in a symbol alphabet defined over GF(q), wherein q is a positive integer,
- 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 α is a positive integer 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;
- and
- packetizing the computed codeword block of n symbols into a sequence of network packets, each network packet in the sequence including an indicator of its position in the sequence.
3 more elements
Dependencies are inferred from the claim text.