Packet error correction in networks
View Patent ↗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.
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 1 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
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
calculated
over
GF
(
q
)
and corresponds to α equations
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
-
1
c
i
=
0
⋮
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
c
i
=
0
,
each calculated modulo q,
and wherein encoding the k symbols into the computed codeword block of n symbols comprises determining all of the n symbols so that the family of equations is satisfied.
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
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
calculated
over
GF
(
q
)
and corresponds to α equations
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
-
1
c
i
=
0
⋮
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
c
i
=
0
,
each calculated modulo q,
and wherein encoding the k symbols into the computed codeword block of n symbols comprises determining all of the n symbols so that the family of equations is satisfied.
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
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
calculated
over
GF
(
q
)
and corresponds to a equations
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
-
1
c
i
=
0
⋮
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
c
i
=
0
,
each calculated modulo q,
and wherein encoding the k symbols into the computed codeword block of n symbols comprises determining all of the n symbols so that the family of equations is satisfied.
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
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
calculated
over
GF
(
q
)
and corresponds to α equations
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
-
1
c
i
=
0
⋮
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
c
i
=
0
,
each calculated modulo q,
wherein β is a positive integer, and wherein encoding the k symbols into the computed codeword block of n symbols comprises determining all of the n symbols so that the family of equations is satisfied.
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
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
calculated
over
GF
(
q
)
and corresponds to a equations
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
-
1
c
i
=
0
⋮
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
c
i
=
0
,
each calculated modulo q,
and wherein encoding the k symbols into the computed codeword block of n symbols comprises determining all of the n symbols so that the family of equations is satisfied.
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
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
calculated
over
GF
(
q
)
and corresponds to α equations
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
c
i
=
0
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
α
-
1
c
i
=
0
⋮
∑
i
=
0
n
-
1
(
(
q
-
β
)
-
i
)
c
i
=
0
,
each calculated modulo q,
and wherein encoding the k symbols into the computed codeword block of n symbols comprises determining all of the n symbols so that the family of equations is satisfied.
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.