Rank deficient decoding of linear network coding

摘要

Rank deficient decoding for linear network coding. The decoding problem is first decomposed into multiple parallel sub-problems. A determination is made whether the decoding problem is or is not rank deficient. If rank deficient, and for each sub-problem, a rank deficient decoder is applied to obtain a solution.

主权项

1. In a communications network, a decoder for decoding received rank deficient packets, comprising:
computer; and a software program, wherein said computer further comprises means to communicate input and output packet data with said communications system; and wherein said software program further comprises a set of computer-implementable instructions stored on a non-transitory media, which, when executed by said computer cause said computer to perform the following steps:
processing received packets to remove linearly dependent packets;decomposing into parallel sub-problems, wherein said step of decomposing further causes said computer to perform the steps of:
determining whether the decoding problem is rank deficient;decomposing the decoding problem into N sub-problems when the decoding problem is rank deficient; andusing a full rank decoder to obtain transmitted data packets when the decoding problem is not rank deficient.solving the sub-problems in parallel, wherein said step of solving sub-problems in parallel further causes said computer to perform the steps of:
identifying a set of potential solutions;selecting solutions by using additional data properties; andcollecting a set of solutions to all said sub-problems; andreconstructing transmitted data packets. wherein said step of reconstructing transmitted data packets further causes said computer to perform the following steps of;
determining whether all sub-problems have unique solutions;collecting all unique solutions to obtain said transmitted data packets when all said sub-problems have unique solutions; andforming a set of possible data packets and then select transmitted data packets using additional data properties when all said sub-problems do not have unique solutions.