Packet error correction in networks

• US 8,479,082 B2
• Filed: 06/28/2010
• Issued: 07/02/2013
• Est. Priority Date: 04/07/2010
• Status: Expired due to Fees

• Current Assignee: Indian Institute of Technology Delhi
• Original Assignee: Indian Institute of Technology Delhi
• Inventors: Bose, Ranjan
• Primary Examiner(s): Tabone, Jr., John J
• Application Number:
  US12/824,880
• Publication Number:
  US 20110252292A1
• Time in Patent Office: 1,100 Days
• Field of Search: 714/776, 714/784, 714/780, 714/752
• US Class Current: 714/776
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/134 Non-binary linear block codes not provided for otherwise
• CPC Class Codes: H03M 13/17 Burst error correction, e.g. error trapping, Fire codes
• CPC Class Codes: H03M 13/27 using interleaving techniques
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27
• CPC Class Codes: H04L 1/0084 Formats for payload data

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.

Claims

1. 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 c_i, 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 c₁ 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.

2. The method of claim 1, wherein p is at least a number of bits per symbol needed to define q unique symbols of the symbol alphabet over GF(q).

3. The method of claim 1, wherein encoding the k symbols into the computed codeword block of n symbols comprises determining a value of n sufficiently large to make α

of the n symbols recoverable by the inverse decoding procedure applied to the modified codeword block with x=α

.

4. The method of claim 1, wherein the family of equations is given by

5. The method of claim 1,

wherein encoding the k symbols into the computed codeword block of n symbols comprises arranging the n symbols in a defined sequence within the computed codeword block so that each of the n symbols occupies a known position in the computed codeword block,

and wherein each of the x symbols with an undetermined value occupies a known position in the modified codeword block.

6. The method of claim 1, wherein packetizing the computed codeword block of n symbols into the sequence of m>

1 network packets comprises interleaving the n symbols across the sequence of m>

1 network packets.

7. The method of claim 1, wherein transmitting the sequence of network packets on the network comprises transmitting the sequence of network packets to a packet decoding device that is operable to perform the decoding procedure and is communicatively connected with the packet encoding device by way of the network.

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 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 c_i, 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 c_i 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.

9. The packet encoding device of claim 8, wherein p is at least a number of bits per symbol needed to define q unique symbols of the symbol alphabet over GF(q).

10. The packet encoding device of claim 8, wherein encoding the k symbols into the computed codeword block of n symbols comprises determining a value of n sufficiently large to make α

of the n symbols recoverable by the inverse decoding procedure applied to the modified codeword block with x=α

.

11. The packet encoding device of claim 8, wherein the family of equations is given by

12. The packet encoding device of claim 8, wherein encoding the k symbols into the computed codeword block of n symbols comprises arranging the n symbols in a defined sequence within the computed codeword block so that each of the n symbols occupies a known position in the computed codeword block, and

wherein each of the x symbols with an undetermined value occupies a known position in the modified codeword block.

13. The packet encoding device of claim 8, wherein packetizing the computed codeword block of n symbols into the sequence of m>

1 network packets comprises interleaving the n symbols across the sequence of m>

1 network packets.

14. The packet encoding device of claim 8, wherein transmitting the sequence of network packets on the network comprises transmitting the sequence of network packets to a decoding device that is operable to perform the decoding procedure and to which the packet encoding device is configured to be communicatively connected by way of the network.

15. 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 c_i, 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 c_i 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.

16. The non-transitory computer-readable medium of claim 15, wherein p is at least a number of bits per symbol needed to define q unique symbols of the symbol alphabet over GF(q).

17. The non-transitory computer-readable medium of claim 15, wherein encoding the k symbols into the computed codeword block of n symbols comprises determining a value of n sufficiently large to make α

of the n symbols recoverable by the inverse decoding procedure applied to the modified codeword block with x=α

.

18. The non-transitory computer-readable medium of claim 15, wherein the family of equations is given by

19. The non-transitory computer-readable medium of claim 15,

wherein encoding the k symbols into the computed codeword block of n symbols comprises arranging the n symbols in a defined sequence within the computed codeword block so that each of the n symbols occupies a known position in the computed codeword block,

and wherein each of the x symbols with an undetermined value occupies a known position in the modified codeword block.

20. The non-transitory computer-readable medium of claim 15, wherein packetizing the computed codeword block of n symbols into the sequence of m>

1 network packets comprises interleaving the n symbols across the sequence of m>

1 network packets.

21. A method comprising:

encoding k symbols into a computed codeword block of n symbols c_i, 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 c_i 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.

22. The method of claim 21, wherein encoding the k symbols into the computed codeword block of n symbols comprises determining a value of n sufficiently large to make a of the n symbols recoverable by the inverse decoding procedure applied to the modified codeword block with x=α

.

23. The method of claim 21, wherein the family of equations is given by

24. The method of claim 21,

wherein encoding the k symbols into the computed codeword block of n symbols comprises arranging the n symbols in a defined sequence within the computed codeword block so that each of the n symbols occupies a known position in the computed codeword block, and

wherein each of the x symbols with an undetermined value occupies a known position in the modified codeword block.

25. The method of claim 21, wherein packetizing the computed codeword block comprises:

packetizing the computed codeword block into a sequence of m>

1 network packets, and

interleaving the n symbols across the sequence of m>

1 network packets.

26. A packet encoding device programmed to execute instructions to carry out functions comprising:

encoding k symbols into a computed codeword block of n symbols c_i, 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 c_i 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.

27. The packet encoding device of claim 26, wherein encoding the k symbols into the computed codeword block of n symbols comprises determining a value of n sufficiently large to make a α

the n symbols recoverable by the inverse decoding procedure applied to the modified codeword block with x=α

.

28. The packet encoding device of claim 26, wherein the family of equations is given by

29. The packet encoding device of claim 26,

wherein encoding the k symbols into the computed codeword block of n symbols comprises arranging the n symbols in a defined sequence within the computed codeword block so that each of the n symbols occupies a known position in the computed codeword block,

and wherein each of the x symbols with an undetermined value occupies a known position in the modified codeword block.

30. The packet encoding device of claim 26, wherein packetizing the computed codeword block of n symbols into the sequence of m>

1 network packets comprises interleaving the n symbols across the sequence of m>

1 network packets.

31. 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 c_i, 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 c_i 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.

32. The non-transitory computer-readable medium of claim 31, wherein encoding the k symbols into the computed codeword block of n symbols comprises determining a value of n sufficiently large to make α

of the n symbols recoverable by the inverse decoding procedure applied to the modified codeword block with x=α

.

33. The non-transitory computer-readable medium of claim 31, wherein the family of equations is given by

34. The non-transitory computer-readable medium of claim 31,

wherein encoding the k symbols into the computed codeword block of n symbols comprises arranging the n symbols in a defined sequence within the computed codeword block so that each of the n symbols occupies a known position in the computed codeword block, and

wherein each of the x symbols with an undetermined value occupies a known position in the modified codeword block.

35. The non-transitory computer-readable medium of claim 31, wherein packetizing the computed codeword block of n symbols into the sequence of m>

1 network packets comprises interleaving the n symbols across the sequence of m>

1 network packets.