Circular-shift-based Vector Linear Network Coding and Its Application to Array Codes

Sheng Jin 1 , Zhe Zhai 1 , Qifu Tyler Sun 1 ∗ , Zongpeng Li 2 · 2024

Read Circular-shift-based Vector Linear Network Coding and Its Application to Array Codes by Sheng Jin 1 , Zhe Zhai 1 , Qifu Tyler Sun 1 ∗ , Zongpeng Li 2 (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17067.txt.

Introduction

Sheng Jin, Zhe Zhai, Qifu Tyler Sun, and Zongpeng Li study a form of network coding built on circular shifts. Their paper is from two thousand twenty-four. In network coding, nodes blend data as it moves, and shifts keep the math cheap. The plain shift form, though, cannot reach full network speed, so extra symbols must be sent.

Their new form works over a broad field and can reach full speed. Its set of local rules is closed under its own blends, by design. Costs stay much like the old form, and in some cases they drop. The work also yields new array codes, with bounds on their size and fast ways to encode them.

Catalog record

CREATORSheng Jin 1 , Zhe Zhai 1 , Qifu Tyler Sun 1 ∗ , Zongpeng Li 2
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17067

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Circular-shift-based Vector Linear Network Coding and Its Application to Array Codes Thanks: ∗ {}^{*}~ Q. T. Sun (Email: [email protected]) is the corresponding author. Sheng Jin 1 , Zhe Zhai 1 , Qifu Tyler Sun 1 ∗ , Zongpeng Li 2 Abstract Circular-shift linear network coding (LNC) is a class of vector LNC with local encoding kernels selected from cyclic permutation matrices, so that it has low coding complexities. However, it is insufficient to exactly achieve the capacity of a multicast network, so the data units transmitted along the network need to contain redundant symbols, which affects the transmission efficiency. In this paper, as a variation of circular-shift LNC, we introduce a new class of vector LNC over arbitrary GF( p p ), called circular-shift-based vector LNC, which is shown to be able to exactly achieve the capacity of a multicast network. The set of local encoding kernels in circular-shift-based vector LNC is nontrivially designed such that it is closed under multiplication by elements in itself. It turns out that the coding complexity of circular-shift-based vector LNC is comparable to and, in some cases, even lower than that of circular-shift LNC. The new results in the formulation of circular-shift-based vector LNC further facilitates us to characterize and design Vandermonde circulant maximum distance separable (MDS) array codes, which are built upon the structure of Vandermonde matrices and circular-shift operations. We prove that for r ≥ 2 r\geq 2 , the largest possible k k for an L L -dimensional ( k + r , k ) (k+r,k) Vandermonde circulant p p -ary MDS array code is p m L − 1 p^{m_{L}}-1 , where L L is an integer co-prime with p p , and m L m_{L} represents the multiplicative order of p p modulo L L . For r ∈ { 2 , 3 } r\in\{2,3\} , we introduce two new types of ( k + r , k ) (k+r,k) p p -ary array codes that can achieve the largest k = p m L − 1 k=p^{m_{L}}-1 . For the special case that p = 2 p=2 , we propose scheduling encoding algorithms for the 2 2 new codes, so that the encoding complexity not only asymptotically approaches the optimal 2 2 XORs per original data bit, but also slightly outperforms the encoding complexity of other known Vandermonde circulant MDS array codes with largest k = 2 m L − 1 k=2^{m_{L}}-1 . I Introduction As an extension of conventional scalar linear network coding (LNC), which models data units transmitted along a network over a finite field, vector LNC models data units over a vector space (See, e.g., [ 1 ] - [ 5 ] ). Compared with scalar LNC, vector LNC provides much more candidates of local encoding kernels for coding operations, so that it greatly enhances the flexibility of code design. In the literature, various classical networks have been designed to demonstrate the advantage of vector LNC. For instance, in the M-network constructed in [ 6 ] , the network capacity can be simply achieved by a 2 -dimensional vector linear network code, but cannot be achieved by scalar LNC over any finite field. Specific to (single-source) multicast networks, various instances have been constructed to demonstrate that the size of data units required by vector LNC to achieve the multicast capacity can be smaller than that required by scalar LNC (See, e.g., [ 2 ] - [ 4 ] ). Circular-shift LNC is a special class of vector LNC and it was introduced in [ 7 ] , with the aim to reduce the coding complexity. In an L -dimensional circular-shift linear network code on a network, the local encoding kernel \mathbf{K}_{d,e} of every adjacent pair (d,e) of edges is selected from L\times L cyclic permutation matrices over GF( 2 ), so that the encoding operations of circular-shift LNC only contains circular-shifts and bit-wise additions. On a binary sequence of length L , compared with bit-wise additions, circular-shift operations theoretically incurs negligible computational complexities, so circular-shift LNC has lower encoding and decoding complexities compared with scalar LNC over the extension field GF( 2^{L} ). Circular-shift LNC was first formulated in [ 7 ] under the assumption that L is a prime with primitive root 2 , and was extended to be applicable to arbitrary odd dimension L in [ 8 ] . In particular, over an arbitrary multicast network, under the assumption that \frac{m_{L}}{\phi(L)}2^{m_{L}} is larger than the number of receivers, where m_{L} and \phi(L) respectively represent the multiplicative order of 2 modulo L and the Euler’s totient function of L , an L -dimensional circular-shift linear solution at rate \phi(L)/L can be efficiently constructed by the algorithm designed in [ 8 ] . Herein, an L -dimensional linear solution at rate \phi(L)/L<1 refers to an L -dimensional circular-shift linear network code equipped with a \phi(L)\times L matrix \mathbf{G} over GF( 2 ) subject to: a) every source data unit is a vector of dimension \phi(L) instead of L , and the outgoing data units of the source are L -dimensional vectors generated via multiplying source data units by \mathbf{G} ; b) every receiver is able to recover all \phi(L) -dimensional source data units based on its incoming L -dimensional data units. For a circular-shift linear solution at rate \phi(L)/L , Ref. [ 9 ] formulated a general rule to construct the \phi(L)\times L matrix \mathbf{G} , and explicitly characterized the decoding process at a receiver, which involves an L\times\phi(L) matrix \mathbf{H} over GF( 2 ) to transform incoming L -dimensional data units into \phi(L) -dimensional vectors. Random circular-shift LNC was studied in [ 10 ] in the context of wireless broadcast networks. In [ 11 ] , it was proved that even though circular-shift LNC can asymptotically approach the capacity of every multicast network, it is insufficient to exactly achieve the capacity of a multicast network. It was further proved in [ 12 ] that even more generalized permutation-based LNC, i.e. , vector LNC with local encoding kernels selected from permutation matrices, is not sufficient to exactly achieve the capacity of a multicast network either. Consider an L -dimensional circular-shift linear solution at rate \phi(L)/L , together with the \phi(L)\times L matrix \mathbf{G} used at the source and the L\times\phi(L) matrix \mathbf{H} used at a receiver. Based on the local encoding kernels \mathbf{K}_{d,e} of the considered circular-shift linear network code, a new \phi(L) -dimensional vector linear network code with local encoding kernels \mathbf{G}\mathbf{K}_{d,e}\mathbf{H} can be naturally induced. If the induced code qualifies as a linear solution, then its rate is 1 and the capacity of a multicast network can be exactly achieved by a variation of circular-shift LNC. However, justification of whether the induced code is a linear solution is nontrivial and intractable at the first glance. In the present work, we first investigate how to formulate a variation of circular-shift LNC that can exactly achieve the capacity of a multicast network, and then apply the new formulation to the design of array codes, which are widely adopted in storage systems to enhance data reliability, such as in Redundant Arrays of Inexpensive Disks (RAID) [ 13 ] . Different from previous study of circular-shift LNC

Read the complete text