Rank deficient decoding of linear network coding
View Patent ↗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; and
using 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; and
collecting a set of solutions to all said sub-problems; and
reconstructing 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; and
forming 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.
2. In a communications network, a method for decoding received rank deficient packets, comprising the steps of:
processing received packets to remove linearly dependent packets;
decomposing into parallel sub-problems, wherein said step of decomposing further comprises 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; and
using 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 comprises the steps of:
identifying a set of potential solutions;
selecting solutions by using additional data properties; and
collecting a set of solutions to all said sub-problems; and
reconstructing transmitted data packets; wherein said step of reconstructing transmitted data packets further comprises the 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; and
forming 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.