Permute & Add Network Codes via Group Algebras

A class of network codes have been proposed in the literature where the symbols transmitted on each edge are binary vectors and the coding operation performed in network nodes consists of the application of (possibly several) permutations on each incoming vector and XOR-ing the results to obtain the outgoing vector. These network codes, which we will refer to as permute-and-add network codes, involve simple operations and are known to provide lower complexity solutions than scalar linear codes. The complexity of these codes are determined by their degree which is the number of permutations applied on each incoming vector to compute an outgoing vector. Constructions of permute-and-add network codes of small degree for multicast networks are known. In this paper, we provide a new framework based on group algebras to design permute-and-add network codes for arbitrary (not necessarily multicast) networks. Our framework allows the use of arbitrary group of permutations (including circular shifts, proposed in prior work) and admits a trade-off between coding rate and the degree of the code. Our technique permits elegant recovery and generalizations of the key known results on permute-and-add network codes. The proposed network codes employ low degree permute-and-add operation for encoding as well as decoding.