Circular-Shift Linear Network Coding

DOI10.1109/TIT.2018.2832624MaRDI QIDQ4611414zbMATH OpenOpenAlexFDO

Authors Hanqi Tang, Qifu Tyler Sun, Zongpeng Li, Xiao-Long Yang, Keping Long

Publication date 18 January 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.02163

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: We study a class of linear network coding (LNC) schemes, called circular-shift LNC, whose encoding operations consist of only circular-shifts and bit-wise additions (XOR). Formulated as a special vector linear code over GF($2$), an $L$-dimensional circular-shift linear code of degree $delta$ restricts its local encoding kernels to be the summation of at most $delta$ cyclic permutation matrices of size $L$. We show that on a general network, for a certain block length $L$, every scalar linear solution over GF($2^{L-1}$) can induce an $L$-dimensional circular-shift linear solution with 1-bit redundancy per-edge transmission. Consequently, specific to a multicast network, such a circular-shift linear solution of an arbitrary degree $delta$ can be efficiently constructed, which has an interesting complexity tradeoff between encoding and decoding with different choices of $delta$. By further proving that circular-shift LNC is insufficient to achieve the exact capacity of certain multicast networks, we show the optimality of the efficiently constructed circular-shift linear solution in the sense that its 1-bit redundancy is inevitable. Finally, both theoretical and numerical analysis imply that with increasing $L$, a randomly constructed circular-shift linear code has linear solvability behavior comparable to a randomly constructed permutation-based linear code, but has shorter overheads.

Cited in

(2)

• Variable-Rate Linear Network Coding
• Complex Linear Physical-Layer Network Coding

This page was built for publication: Circular-Shift Linear Network Coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4611414)