On Minimizing Decoding Complexity for Binary Linear Network Codes

The typical method adopted in the decoding of linear network codes is Gaussian Elimination (GE), which enjoys extreme low policy complexity in determining actions, i.e., the XORing operation executed upon the decoding matrix and the coded packets. However, the amount of the total required actions is quite large, which makes the overall decoding complexity high. In this paper, we consider the problem of minimizing the decoding complexity of binary linear network codes. We formulate the decoding problem into a special shortest path problem where the weight of each edge consists of: (1) a const weight due to the execution of the action; (2) a variable weight due to the adopted policy in determining the action. The policy is formulated as an optimization problem that minimizes a particular objective function by enumerating over a certain action set. Since finding the optimal policy is intractable, we optimize the policy in dual directions. At one hand, we guarantee the objective function and the action set are similar to the optimal policy that minimizes const weight summation; at the other hand, we guarantee that the objective function have simple structure and the action set is small, so that the variable weight summation is also small. Simulation results demonstrate that our proposed policy can significantly reduce the decoding complexity compared with existing methods.