Reduced complexity sum-product algorithm for decoding nonlinear network codes and in-network function computation

Abstract

While the capacity, feasibility, and methods to obtain codes for network coding problems are well studied, the decoding procedure and complexity have not garnered much attention. In this paper, we pose the decoding problem at a sink node in a network as a marginalize product function (MPF) problem over the Boolean semiring and use the sum product (SP) algorithm on a suitably constructed factor graph to perform iterative decoding. The number of operations required to perform SP decoding is reduced using traceback. The number of operations required to perform SP decoding with and without traceback is obtained. For nonlinear network codes, we define fast decodability of a network code at sinks demanding all the messages and identify a sufficient condition for the same. Next, we consider the network function computation problem wherein the sink nodes demand a function of the messages. We present an MPF formulation for function computation at the sink nodes and use the SP algorithm to obtain the value of the demanded function. Though the proposed method can be used for decoding both linear and nonlinear network codes, it is advantageous only for the case of nonlinear network codes.