Composite extension finite fields for low overhead network coding
View Patent ↗Described are network coding (NC) systems and techniques which utilize multiple composite extension finite fields to reduce complexity at various nodes in a network and also reduce overhead due to signal coding coefficients. A coding design uses a series of finite fields where increasingly larger fields are based on a previous smaller field. Techniques disclosed herein can be applied to existing systems using Random Linear Network Coding (RLNC) or Fulcrum codes.
1. In a network having at least a first node and a second node, a method comprising:
receiving n source packets;
generating a first coding vector comprising n elements, each element of the first coding vector selected from a corresponding one of a plurality of fields, wherein at least two of the plurality of fields have different sizes;
generating a plurality of encoded packets, each encoded packet corresponding to a linear combination of the source packets according to the first coding vector; and
transmitting the encoded packets from the first node to the second node.
2. The method of claim 1 wherein the plurality of fields comprise a series of composite extension finite fields.
3. The method of claim 2 wherein the series of composite extension finite fields comprise fields of M , M N , and
𝔽
M
N
O
,
where M, N, and O are integers greater than 1.
4. The method of claim 1 wherein generating a first coding vector comprises generating a vector comprising n elements ordered by field size.
5. The method of claim 1 wherein generating an encoded packet comprises:
calculating the sum of the products for each source packet multiplied with a corresponding element in the coding vector,
wherein calculating the sums of the products are performed in at least two fields having different sizes.
6. The method of claim 1 further comprising:
receiving, in the second node, a plurality of encoded packets transmitted from the first node; and
decoding the received encoded packets.
7. The method of claim 6 wherein decoding the received encoded packets comprises decoding the received encoded packets using the first coding vector processed from a smallest field size to a largest field size.
8. The method of claim 6 where decoding the received encoded packets comprises using Gaussian elimination.
9. The method of claim 8 wherein decoding the received encoded packets comprises performing addition and multiplication of elements from fields having different sizes.
10. The method of claim 9 further comprising:
receiving, in the second node, a plurality of encoded packets transmitted from the first node;
recoding the received encoded packets to generate a plurality of recoded packets; and
transmitting the recoded packets to a third node in the network.
11. The method of claim 10 wherein recoding the received encoded packets comprises recoding the received encoded packets using operations in only one of the plurality of fields.
12. The method of claim 11 wherein recoding the received encoded packets comprises recoding the received encoded packets using operations in only a smallest one of the plurality of fields.
13. The method of claim 12 wherein recoding the received encoded packets comprises recoding the received encoded packets using operations in only a largest one of the plurality of fields.
14. The method of claim 11 wherein recoding the received encoded packets comprises recoding the received encoded packets using operations in multiple ones of the plurality of fields.
15. The method of claim 11 further comprising:
selecting a recoding strategy as one of: recoding using operations in only a smallest one of the plurality of fields, recoding using operations in only a largest one of the plurality of fields, or recoding using operations in multiple ones of the plurality of fields,
wherein recoding the received encoded packets comprises recoding the received encoded packets using the selected recoding strategy.
16. The method of claim 15 wherein selecting a recoding strategy comprises selecting a recoding strategy based upon processing resources available within the second node.
17. The method of claim 15 wherein selecting a recoding strategy comprises selecting a recoding strategy based upon requirements for maintaining code structure.
18. The method of claim 15 wherein selecting a recoding strategy comprises selecting a recoding strategy based upon a desired probability that packets received at the third node are linearly independent.
19. The method of claim 15 wherein recoding the received encoded packets to generate a plurality of recoded packets comprises processing the first coding vector from a smallest field size to a largest field size.