Systems and methods for construction of and network coding using near-maximum distance separable (MDS) linear network codes

1. A method for network coding using a near-maximum distance separable linear network code, comprising:

generating, by a processor, a message matrix wherein each column of the message matrix corresponds to one of K message packets and each element in a column of the message matrix corresponds to one of the symbols of the corresponding message packet;

generating, by the processor, a network code matrix to map the K message packets to N encoded packets, wherein any combination of K+1 columns of the network code contains at least K columns that are linearly independent; and

multiplying, by the processor, the message matrix by the network code matrix to generate a transmission matrix, wherein each column of the transmission matrix corresponds to an encoded packet for wireless transmission;

sending by the processor the resulting encoded packets to a physical layer of a wireless transmitter for transmission using an existing underlying wireless communication protocol without modification.

2. The method of claim 1 wherein the method is performed at a network layer of a wireless transmitter.

3. The method of claim 1 further comprising adding pad symbols to one or more of the message packets such that a resulting length of each message packet is the same.

4. The method of claim 1 wherein the number of message packets and encoded packets are given by a coding rate of a linear network code specified by the network code matrix.

5. The method of claim 1 further comprising: receiving, by the processor, a number of received packets at least equal to K+1, each of the received packets comprising a sequence index that correlates the received packet to one of the encoded packets;

generating, by the processor, a received packet matrix by selecting a number of the received packets equal to K+1, wherein each column of the received packet matrix corresponds to one of the selected received packets;

generating, by the processor, a decoding matrix by forming a sub-matrix by selecting K linearly independent columns of the network code matrix that have indices that are the same as the sequence indices of the selected received packets and inverting the sub-matrix; and multiplying, by the processor, a matrix comprising the columns of the received packet matrix that correspond to the K linearly independent selected columns of the network code matrix by the decoding matrix to generate a recovered matrix, wherein each column of the recovered matrix corresponds to a decoded packet.

6. A non-transitory computer-readable medium containing instructions that, when executed by a processor, cause the processor to:

generate a message matrix wherein each column of the message matrix corresponds to one of K message packets and each element in a column of the message matrix corresponds to one of the symbols of the corresponding message packet;

generate a network code matrix to map the K message packets to N encoded packets, wherein any combination of K+1 columns of the network code contains at least K columns that are linearly independent; and

multiply the message matrix by the network code matrix to generate a transmission matrix, wherein each column of the transmission matrix corresponds to an encoded packet for wireless transmission;

sending by the processor the resulting encoded packets to a physical layer of a wireless transmitter for transmission using an existing underlying wireless communication protocol without modification.

7. The non-transitory computer-readable medium of claim 6 wherein executing the instructions further causes the processor to add pad symbols to one or more of the message packets such that a resulting length of each message packet is the same.

8. The non-transitory computer-readable medium of claim 6 wherein the number of message packets and encoded packets are given by a coding rate of a linear network code specified by the network code matrix.

9. The non-transitory computer-readable medium of claim 6 wherein executing the instructions further causes the processor to: receive a number of received packets at least equal to K+1, each of the received packets comprising a sequence index that correlates the received packet to one of the encoded packets;

generate a received packet matrix by selecting a number of the received packets equal to K+1, wherein each column of the received packet matrix corresponds to one of the selected received packets;

generate a decoding matrix by forming a sub-matrix by selecting K linearly independent columns of the network code matrix that have indices that are the same as the sequence indices of the selected received packets and inverting the sub-matrix; and

multiply a matrix comprising the columns of the received packet matrix that correspond to the K linearly independent selected columns of the network code matrix by the decoding matrix to generate a recovered matrix, wherein each column of the recovered matrix corresponds to a decoded packet.

10. A wireless communication device, comprising: a network encoder to:

generate a message matrix wherein each column of the message matrix corresponds to one of K message packets and each element in a column of the message matrix corresponds to one of the symbols of the corresponding message packet;

generate a network code matrix to map the K message packets to N encoded packets, wherein any combination of K+1 columns of the network code contains at least K columns that are linearly independent; and

multiply the message matrix by the network code matrix to generate a transmission matrix, wherein each column of the transmission matrix corresponds to an encoded packet for wireless transmission; and a physical layer to transmit the encoded packets via a wireless antenna;

sending by the network encoder the resulting encoded packets to the physical layer of the wireless communication device for transmission using an existing underlying wireless communication protocol without modification.

11. The wireless communication device of claim 10 wherein the network encoder comprises a network layer of a wireless transmitter.

12. The wireless communication device of claim 10 wherein the network encoder adds pad symbols to one or more of the message packets such that a length of each message packet is the same.

13. The wireless communication device of claim 10 wherein the number of message packets and encoded packets are given by a coding rate of a linear network code specified by the network code matrix.

14. A method for generating a near-maximum distance separable linear network code having a coding rate of K/N, comprising:

defining, by a processor, a set V that contains all vectors of length K having entries over a finite field and an initially-empty network code set A; if a cardinality of the network code set A is less than K:

continually removing, by the processor, a vector xi from V and inserting xi into the network code set A if xi and A are linearly independent; and

incrementing, by the processor, i; and if the cardinality of the network code set A is greater than or equal to K and the set V is not empty and the cardinality of A is less than N:

continually removing, by the processor, xi from V and inserting xi into the network code set A and incrementing i if all subsets B of the network code set A having a cardinality K contain a subset C of cardinality K−1 that, when combined with xi forms a linearly independent set; and

continually removing, by the processor, xi from V and incrementing i if not all subsets B of the network code set A having a cardinality K contain a subset C of cardinality K−1 that, when combined with xi forms a linearly independent set;

sending by the processor the resulting encoded packets to a physical layer of a wireless transmitter for transmission using an existing underlying wireless communication protocol without modification.