In this paper we introduce a novel linear networkcoding scheme, namely "rotate-and-add coding", that possesses low encoding complexity and operates fundamentally different from the traditional network codes...
详细信息
ISBN:
(纸本)9781424482641
In this paper we introduce a novel linear networkcoding scheme, namely "rotate-and-add coding", that possesses low encoding complexity and operates fundamentally different from the traditional network codes. This scheme can operate on a small field (e.g. F-2), thereby, it alleviates the computational complexities due to multiplication and addition operations in large finite fields. The key idea is to function on a vector of symbols instead of working with a single symbol of a large field. Each node encodes its received vectors by simply rotationally shifting the vectors and then adding them, i.e., here the addition is done in vector form and the multiplication is replaced by rotation. We verify that the new scheme requires lower computation and overhead than the existing schemes. However, as the cost of reducing the complexity, it provides slightly smaller throughput.
In the algebraic view, the solution to a networkcoding problem is seen as a variety specified by a system of polynomial equations typically derived by using edge-to-edge gains as variables. The output from each sink ...
详细信息
In the algebraic view, the solution to a networkcoding problem is seen as a variety specified by a system of polynomial equations typically derived by using edge-to-edge gains as variables. The output from each sink is equated to its demand to obtain polynomial equations. In this paper, we propose a method to derive the polynomial equations using source-to-sink path gains as the variables. In the path gain formulation, we show that linear and quadratic equations suffice;therefore, networkcoding becomes equivalent to a system of polynomial equations of maximum degree 2. We present algorithms for generating the equations in the path gains and for converting path gain solutions to edge-to-edge gain solutions. Because of the low degree, simplification is readily possible for the system of equations obtained using path gains. Using small-sized networkcoding problems, we show that the path gain approach results in simpler equations and determines solvability of the problem in certain cases. On a larger network (with 87 nodes and 161 edges), we show how the path gain approach continues to provide deterministic solutions to some networkcoding problems.
暂无评论