A $(k+r,k,l)$ binary array code of length $k+r$, dimension $k$, and sub-packetization $l$ is composed of $l\times(k+r)$ matrices over $\mathbb{F}_2$, with every column of the matrix stored on a separate node in the distributed storage system and viewed as a coordinate of the codeword. It is said to be maximum distance separable (MDS) if any $k$ out of $k+r$ coordinates suffice to reconstruct the whole codeword. The repair problem of binary MDS array codes has drawn much attention, particularly for single-node failures. In this paper, given an arbitrary binary MDS array code with sub-packetization $m$ as the base code, we propose two generic approaches (Generic Construction I and II) for constructing binary MDS array codes with optimal access (or repair) bandwidth for single-node failures. For every $s\leq r$, a $(k+r,k,ms^{\lceil \frac{k+r}{s}\rceil})$ code $\mathcal{C}_1$ with optimal access bandwidth can be constructed by Generic Construction I. Repairing a failed node of $\mathcal{C}_1$ requires connecting to $d = k+s-1$ helper nodes, in which $s-1$ helper nodes are designated and $k$ are free to select. $\mathcal{C}_1$ generally achieves smaller sub-packetization and provides greater flexibility in the selection of its coefficient matrices. For even $r\geq4$ and $s=\frac{r}{2}$ such that $s+1$ divides $k+r$, a $(k+r, k,ms^{\frac{k+r}{s+1}})$ code $\mathcal{C}_2$ with optimal repair bandwidth can be constructed by Generic Construction II, with $\frac{s}{s+1}(k+r)$ out of $k+r$ nodes having the optimal access property. To the best of our knowledge, $\mathcal{C}_2$ possesses the smallest sub-packetization among existing binary MDS array codes with optimal repair bandwidth known to date.

Network coding (NC) has proven to offer significant benefits in long-distance and broadcast transmissions, enhancing both throughput and energy efficiency. Recent studies have incorporated partial packet recovery (PPR) into packet-level NC, using syndromes from coded packets to correct bit errors and thereby reduce completion delay. Motivated by recent breakthroughs in deep learning, this paper introduces a novel neural networkbased decoding framework for packet-level NC, referred to as Learned-PPR. The proposed framework incorporates a Bilateral Efficient Self-Attention Network (Bi-ESANet) architecture, which leverages a bilateral network structure to effectively capture both inter- and intra-packet information. Furthermore, we introduce an ESA module to mitigate the GPU memory overhead compared with traditional Transformer attention modules. To handle rateless NC, we propose a “rateless masking” training strategy that enables efficient decoding of rateless codes within the Bi-ESANet framework. Simulation results across various transmission scenarios demonstrate that the proposed approach significantly outperforms existing PPR schemes, achieving lower completion delay. Specifically, compared to existing methods, the proposed approach reduces completion delay by more than 25%. However, the introduced framework incurs higher computational complexity due to the integration of the Bi-ESANet architecture.

Integrated Sensing and Communication (ISAC) is becoming increasingly important in next-generation wireless networks. This paper focuses on an ISAC system supported by a reconfigurable intelligent surface (RIS), where a full-duplex base station (BS) simultaneously performs uplink multi-user communication, downlink multi-user communication, and radar sensing tasks with the assistance of the RIS. To maximize the sum rate of all downlink and uplink users, an optimization problem is formulated, subject to multiple constraints, including target detection signal-to-interference-plus-noise ratio, self-interference, BS transmission power, user transmission power, and unit-modulus constraints of RIS reflection coefficients. To address the complex non-convex optimization problems, efficient solving algorithms are proposed, and their performance is validated through simulations. The results demonstrate that the RIS-assisted full-duplex ISAC (RAFD-ISAC) system significantly enhances both communication and sensing performance. The proposed joint beamforming and reflection design offers a novel solution for the deep integration of sensing and communication in next-generation networks.

In the study of packet-level random linear network coding (RLNC) in wireless broadcast, RLNC over GF(2L) is known to asymptotically achieve the optimal completion delay with increasingL. Effective utilization of guessing random additive noise decoding (GRAND) at the physical layer can help leverage RLNC packets to generate syndromes so as to reduce packet erasure probabilities and thus further improve the completion delay performance. Prior to this work, only a few studies investigated GRAND-assisted RLNC and they restricted to GF(2)-coding. In this paper, we first provide a general framework to formulate the decoding process of GRAND-assisted RLNC over GF(2L) forL≥ 1. Even for GRAND-assisted GF(2)-RLNC, the formulation is more complete than previous considerations in the sense that it takes the a priori information of which packets have errors into consideration. Moreover, we propose a novel GRAND-assisted GF(2L)-RLNC scheme whose computational overhead introduced by GRAND is negligible. In particular, a subset of GF(2L) is carefully designed for random coding coefficient selection. For the novel scheme, we theoretically derive lower bounds on the distribution as well as an upper bound on the expected value of the completion delay. Numerical results demonstrate not only a reduction in average completion delay for the novel scheme, but also the advantage of random coding coefficient selection from the specially designed subset for GRAND-assisted RLNC schemes.

We consider an all-to-all communication problem over a ring network, where N nodes are arranged in a ring topology, and each one wishes to send data to every other node by communicating with its neighbors within a fixed distance. To reduce the communication load, we propose a new coded broadcast scheme that exploits both storage redundancy (i.e., some messages can be stored repeatedly across nodes) and multicast opportunities (i.e., each encoded packet carries multiple messages intended by different nodes). In our schemes, each node transmits each encoded packet based on bits from two messages traveling in opposite directions, and decodes the desired messages based on the local files and priorly recovered messages. Theoretical converse proof shows that our scheme achieves the optimal trade-off between communication load, cache size, and communication distance when N is sufficiently large. The optimality results indicate that in ring-based broadcast, the redundant storage only leads to an additive gain in reducing communication load while the communication distance contributes to a multiplicative gain.

In this work, we introduce a new framework of linear network coding (LNC) schemes called two-dimensional (2D) vector LNC, which subsumes conventional (1D) vector LNC as a special case. The new framework models every data unit as an$L_{1} \times L_{2}$matrix, enabling a new encoding dimension so that data units can be coded along both row and column dimensions. Compared with (1D) vector LNC of block length$L_{1} L_{2}, L_{1} \times L_{2}$2D vector LNC not only reduces the size of local encoding kernels from$L_{1} L_{2} \times L_{1} L_{2}$to$L_{1} \times L_{1}$and$L_{2} \times L_{2}$, but also exhibits greater scalability in the selection of local encoding kernels. In addition, we prove an equivalence between the linear solvability of$L_{1} \times L_{2}$2D vector LNC and (1D) vector LNC of block length$L_{1} L_{2}$. Under the framework of 2D vector LNC, we further formulate 2D circular-shift-based LNC. For distinct odd primes$L_{1}$and$L_{2}$, we prove that a network has a (1D) circular-shift-based linear solution of block length$\left(L_{1}-1\right)\left(L_{2}-1\right)$if and only if it has an$\left(L_{1}-1\right) \times\left(L_{2}-1\right)$2D circular-shift-based linear solution. We also demonstrate through an explicit example that, compared with a (1D) circular-shift-based linear solution of block length 8, a$2 \times 4$2D circular-shift-based linear solution requires 23 % fewer XORs in the coding process at intermediate nodes and 13 % fewer XORs in the decoding process.

Matrix representation of the finite field GF(pm) represents elements in GF(pm) by m × m matrices over GF(p) so that the arithmetic of GF(pm) can be interpreted as the arithmetic among matrices over GF(p). It is a commonly used method to transform a (scalar) linear operation over GF(pm) into a vector linear operation over GF(p)m, and has been practically adopted by several coding libraries to implement maximum distance separable (MDS) codes over GF(pm). Previous construction of matrix representation of GF(pm) stems from the companion matrix of an irreducible polynomial over GF(p). In this paper, we introduce a new approach to construct matrix representation denoted by $\mathcal{B}$ based on the cyclic permutation matrix C, and prove the isomorphism between $\mathcal{B}$ and GF(pm). As every matrix in B can be expressed in the form of Gf (C)H with carefully designed matrices G and H over GF(p) and a polynomial f(x) over GF(p), we further show that the maximum number of nonzero terms in f(x) can be potentially reduced from m. By utilizing this property, we demonstrate that the computational complexity of the linear coding process based on matrix representation $\mathcal{B}$ can be reduced compared with the one based on standard matrix representation, and the reduction rate is up to 13.47% among the instances illustrated in this paper.

Most well-known constructions of (N,n,d) maximum rank distance (MRD) codes rely on the arithmetic of ${\mathbb{F}_{{q^N}}}$, whose increasing computational complexity with larger N hinders parameter selection and practical implementation. In this work, based on circular-shift operations, we present an efficient construction of (J,n,d) MRD codes over ${\mathbb{F}_q}$ with n ≤ mL, where q is prime, L is a positive integer satisfying gcd(q,L) = 1, mLdenotes the multiplicative order of q modulo L and J equals to the Euler’s totient function of L. The proposed construction is performed entirely over ${\mathbb{F}_q}$ and avoids the arithmetic of ${\mathbb{F}_{{q^J}}}$. We prove that under some parameter settings, the constructed MRD codes are equivalent to a generalization of Gabidulin codes obtained by summing and concatenating several (mL,n,d) Gabidulin codes. In this sense, the constructed MRD codes differ from conventional Gabidulin codes. In the special case J = mL, we prove that every (mL,n,d) circular-shift-based MRD code coincides with an (mL,n,d) Gabidulin code. Last, when q = 2, L is prime and n ≤ mL, it is analyzed that generating a codeword of the proposed (L −1, n,d) MRD codes requires O(nkL) XOR operations, while generating a codeword of (L −1, n,d) Gabidulin codes, based on customary construction, requires O(nkL2) XOR operations.

We consider broadcasting a block of data packets to multiple users via instantly decodable network coding (IDNC) under the semi-online feedback transmission mode. In this paper, we first introduce a new class of IDNC schemes called lightweight IDNC, tailored for wireless broadcast with stringent computational load at the receiver end. Unlike traditional IDNC that may encode a larger number of original packets together, lightweight IDNC limits each coded packet to a combination of at most two original packets. Explicit lower bounds of the total completion delay as well as the decoding delay are respectively obtained for arbitrary lightweight IDNC schemes. We further investigate the number of transmission rounds as another performance metric, and explicitly characterize its distribution and expectation. The characterizations apply to arbitrary partition-based IDNC schemes, including the lightweight IDNC schemes considered in this paper. A new efficient algorithm is also proposed to construct lightweight IDNC schemes which grants the original packets with lower coding opportunity a higher priority to be encoded. Numerical analyses demonstrate that the lightweight IDNC schemes constructed by the new algorithm not only achieve lower completion and decoding delays in comparison with the ones constructed by the existing algorithm but also adhere closely to theoretical lower bounds, demonstrating their efficiency and practical utility.

Row-Diagonal-Parity (RDP) codes and EVENODD codes are classical systematic array codes and most attention in the literature has been on the generalization of RDP codes. In this work, as generalization of not only RDP codes but also EVENODD codes, we present new construction of$\phi (L)$-dimensional$(k+r, k)$systematic array codes with$r \leq 4$, where L is an odd integer and$\phi (L)$represents the Euler’s totient function of L. We explicitly characterize sufficient conditions on the selection of L to make the codes maximum distance separable (MDS). Compared with EVENODD codes and RDP codes, the largest k that can be supported by the new codes is nearly doubled, and the asymptotic encoding complexity of the new codes is same, that is, asymptotically approaches r XORs per original data bit with increasing L and k. Moreover, for prime L,$r = 2$and$k = 2L-3$, the new code exactly achieves the optimal encoding complexity. For the case$r = 4$, the largest k that can be supported by the new codes is larger than the recently proposed so-called Variants of Extended Shortened Independent-Parity (V-ESIP) systematic array code in a number of code dimension selections, and meanwhile, the obtained explicit conditions on L to guarantee the MDS property of the new codes also apply to classical EVENODD codes and RDP codes, but are more general than well known explicit ones in the literature. The decoding process of the new array codes is also discussed. In particular, the$r\times r$block inverse matrix involved in decoding is explicitly characterized, which applies to all MDS array codes generalized from RDP or EVENODD codes in the literature.

In the study of packet-level random linear network coding (RLNC) in wireless broadcast, RLNC over$\mathbf{GF}(2^{L})$is known to asymptotically achieve the optimal completion delay with increasing$L$. Utilization of guessing random additive noise decoding (GRAND) at physical layer can help leverage RLNC packets to generate syndromes so as to reduce packet erasure probabilities and thus further improve the completion delay performance. Prior to this work, only few studies investigated GRAND-assisted RLNC and they restricted to GF(2)-coding. In this paper, we first provide a general framework to formulate the decoding process of GRAND-assisted RLNC over$\mathbf{GF}(2^{L})$for$L\geq 1$. Even for GRAND-assisted GF(2)-RLNC, the formulation is more complete than previous considerations in the sense that it takes the a priori information of which packets have errors into consideration. In addition, we propose a novel GRAND-assisted$\mathbf{GF}(2^{L})$-RLNC scheme whose computational overhead introduced by GRAND is negligible. We theoretically derive lower bounds on the distribution as well as an upper bound on the expected value of the completion delay of the proposed scheme. Numerical results also demonstrate a reduction in average completion delay for the proposed new GF(28)-RLNC scheme, when compared to existing approaches.

We consider broadcasting a block of data packets to multiple users via instantly decodable network coding (IDNC) under the semi-online feedback transmission mode. In this paper, we first introduce a new class of IDNC schemes called lightweight IDNC, tailored for wireless broadcast with stringent computational load at the receiver end. Unlike traditional IDNC that may encode a larger number of original packets together, lightweight IDNC limits each coded packet to a combination of at most two original packets. We obtain lower bounds on the total completion delay that apply to arbitrary lightweight IDNC schemes. We further investigate the number of transmission rounds as another performance metric, and explicitly characterize its distribution and expectation. The characterizations apply to arbitrary partition-based IDNC schemes, including the lightweight IDNC schemes considered in this paper. A new efficient algorithm is also proposed to construct lightweight IDNC schemes which grants the original packets with lower coding opportunity a higher priority to be encoded. Numerical analyses demonstrate that the lightweight IDNC schemes constructed by the new algorithm not only achieve lower completion and decoding delays in comparison with the ones constructed by the existing algorithm but also adhere closely to theoretical lower bounds, demonstrating their efficiency and practical utility.

Current data centers rely on failure protection mechanisms to ensure data reliability. However, recent research indicates that failures within the same node or rack are common in data centers that use flash-based solid-state drives (SSDs) as the primary storage medium. Such correlated failures bring challenges for traditional protection mechanisms to achieve high reliability and repair performance. To this end, we propose a product erasure code (PECode) that encodes data blocks in multiple stripes cooperatively to generate intrastripe and interstripe parity blocks. Then, we design a multistripe cooperative repair algorithm (MSCRepair). MSCRepair first creates the failure distribution matrix (FDM) to represent the distribution of failure blocks in nodes and racks, and then conducts FDM-guided repair to minimize cross-rack traffic upon correlated failures. We prove that MSCRepair achieves the least cross-rack repair traffic at the cost of a longer repair time. We further propose a correlated failure repair scheduling algorithm for MSCRepair, which reduces the repair time by balancing the load and delivering data from links with higher bandwidths. We evaluate MSCRepair through both large-scale simulations and real experiments. In the mise-en-scene of its state-of-the-art alternatives, MSCRepair stands out by reducing up to 19.6%–49.9% of cross-rack traffic, while simultaneously reducing 16.2%–51.4% of recovery time of correlated failures.

Given a prime L, we present a new construction of (L−1)-dimensional (k+r,k) systematic array codes with r ≤ 4, and concretely characterize sufficient conditions on the selection of L to guarantee the codes’ MDS property. The largest possible k that can be supported by the new MDS array codes is 2L−4, nearly twice as large as that supported by classical MDS array codes such as EVENODD codes and RDP codes. Moreover, the number of XORs per original data bit required in encoding of the new codes asymptotically approaches r with increasing k and L, same as EVENODD codes and RDP codes. In addition, for the case r = 4, the explicit conditions on L we obtain to guarantee the new codes’ MDS property can also be used to guarantee the MDS property of EVENODD codes and RDP codes, but are more general than the well known ones in the literature.

As the next-generation wireless networks thrive, full-duplex and relay techniques are combined to improve the network performance. Random linear network coding (RLNC) is another popular technique to enhance the efficiency and reliability of wireless communications. In this paper, in order to explore the potential of RLNC in full-duplex relay networks, we investigate two fundamental perfect RLNC schemes and theoretically analyze their completion delay performance. The first scheme is a straightforward application of conventional perfect RLNC studied in wireless broadcast, so it involves no additional process at the relay. Its performance serves as an upper bound for all perfect RLNC schemes. The other scheme allows sufficiently large buffer and unconstrained linear coding at the relay. It attains the optimal performance and serves as a lower bound for all RLNC schemes. For both schemes, closed-form formulae to characterize the expected completion delay at a single receiver as well as for the whole system are derived. Numerical results are also demonstrated to validate the theoretical characterizations, and compare the two fundamental schemes with the existing one.

As the next-generation wireless networks thrive, full-duplex and relaying techniques are combined to improve the network performance. Random linear network coding (RLNC) is another popular technique to enhance the efficiency and reliability in wireless communications. In this paper, in order to explore the potential of RLNC in full-duplex relay networks, we investigate two fundamental perfect RLNC schemes and theoretically analyze their completion delay performance. The first scheme is a straightforward application of conventional perfect RLNC studied in wireless broadcast, so it involves no additional process at the relay. Its performance serves as an upper bound among all perfect RLNC schemes. The other scheme allows sufficiently large buffer and unconstrained linear coding at the relay. It attains the optimal performance and serves as a lower bound among all perfect RLNC schemes. Closed-form formulae for the expected completion delay of both schemes are derived. Numerical results are also demonstrated to verify the theoretical characterization and compare the two new schemes with the existing one.

Memory maximum-distance-separable (mMDS) sliding window codes are a type of erasure codes with high erasure-correction capability and low decoding delay. In this paper, we study two types of systematic mMDS sliding window codes over erasure channels, i.e., scalar codes defined over a finite field GF(2L), and vector codes defined over a vector space GF(2)L. We first devise an efficient heuristic algorithm to produce an mMDS sliding window scalar code over relatively small GF(2L). Then, we investigate a special class of mMDS sliding window vector codes whose encoding/decoding are achieved by basic circular-shift and bit-wise XOR operations, and propose a general method to generate such mMDS vector codes. Our complexity analysis shows that the proposed vector codes yield much lower encoding/decoding complexity than the scalar codes. The theoretical and numerical results also demonstrate that mMDS sliding window codes dominate MDS block codes in terms of decoding delay and erasure-correction capability.

In wireless broadcast, random linear network coding (RLNC) over GF(2L) is known to asymptotically achieve the optimal completion delay with increasing L. However, the high decoding complexity hinders the potential applicability of RLNC schemes over large GF(2L). In this paper, a comprehensive analysis of completion delay and decoding complexity is conducted for field-based systematic RLNC schemes in wireless broadcast. In particular, we prove that the RLNC scheme over GF(2) can also asymptotically approach the optimal completion delay per packet when the packet number goes to infinity. Moreover, we introduce a new method, based on circular-shift operations, to design RLNC schemes which avoid multiplications over large GF(2L). The new RLNC schemes turn out to have a much better trade-off between completion delay and decoding complexity. In particular, numerical results demonstrate that the proposed schemes can attain average completion delay just within 5% higher than the optimal one, while the decoding complexity is only about 3 times the one of the RLNC scheme over GF(2).

In wireless broadcast, random linear network coding (RLNC) over GF(2L) is known to asymptotically achieve the optimal completion delay with increasing L. However, the high decoding complexity hinders the potential applicability of RLNC schemes over large GF(2L). In this paper, a comprehensive analysis of completion delay and decoding complexity is conducted for field-based systematic RLNC schemes in wireless broadcast. In particular, we prove that the RLNC scheme over GF(2) can also asymptotically approach the optimal completion delay per packet when the packet number goes to infinity. Moreover, we introduce a new method, based on circular-shift operations, to design RLNC schemes which avoid multiplications over large GF(2L). Based on both theoretical and numerical analyses, the new RLNC schemes turn out to have a much better trade-off between completion delay and decoding complexity. In particular, numerical results demonstrate that the proposed schemes can attain average completion delay just within 5% higher than the optimal one, while the decoding complexity is only about 3 times the one of the RLNC scheme over GF(2).

Circular-shift linear network coding (LNC) is a class of vector LNC with low encoding and decoding complexities, and with local encoding kernels chosen from cyclic permutation matrices. When L is a prime with primitive root 2, it was recently shown that a scalar linear solution over GF(2L-1) induces an L-dimensional circular-shift linear solution at rate (L-1)/L. In this paper, we prove that for arbitrary odd L, every scalar linear solution over GF(2mL), where mL refers to the multiplicative order of 2 modulo L, can induce an L-dimensional circular-shift linear solution at a certain rate. Based on the generalized connection, we further prove that for such L with mL beyond a threshold, every multicast network has an L-dimensional circular-shift linear solution at rate φ(L)/L, where φ(L) is the Euler's totient function of L. An efficient algorithm for constructing such a solution is designed. Finally, we prove that every multicast network is asymptotically circular-shift linearly solvable.

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. Formulated as a special vector linear code over GF(2), an L-dimensional circular-shift linear code of degree δ restricts its local encoding kernels to be the summation of at most δ 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(2L-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 δ can be efficiently constructed, which has an interesting complexity tradeoff between encoding and decoding with different choices of δ. 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.

Circular-shift linear network coding (LNC) is a class of vector LNC with low encoding and decoding complexities, with local encoding kernels chosen from cyclic permutation matrices. When L is a prime with primitive root 2, it was recently shown that a scalar linear solution over GF(2L-1) induces an Ldimensional circular-shift linear solution at rate (L-1)/L. In this work, we prove that for an arbitrary odd L, every scalar linear solution over GF(2(m)L), where mLrefers to the multiplicative order of 2 modulo L, can induce an L-dimensional circularshift linear solution at a certain rate. Based on the generalized connection, we further prove that every multicast network has an L-dimensional circular-shift linear solution at rate φ(L)/L, where φ(L) is the Euler's totient function of L and (m)Lis beyond a threshold. Stemming from this, we last prove that every multicast network is asymptotically circular-shift linearly solvable.

We design classes of quantum low-density paritycheck (LDPC) codes, called quasi-cyclic stabilizer (QCS) codes, from conventional QC-LDPC codes. The proposed QCS codes belong to the family of non-Calderbank-Shor-Steane stabilizer codes. The QC-LDPC codes are self-orthogonal with respect to the symplectic inner product (SIP) and are constructed from submatrices of nonorthogonal Latin squares via array dispersion. The Latin squares are constructed using quadratic (non)-residue sets of prime modulus p, where p = 4n ± 1. For p = 4n - 1, two constructions, namely, Type-I-A and Type-I-B QCS codes, are proposed based on matrix superposition and matrix concatenation, respectively. For p = 4n +1, Type-II QCS codes are proposed based on permutations of a base matrix. We show that the parity-check matrix for Type-I-B and Type-II QCS codes is self-orthogonal with respect to the SIP for all orders of circulant permutation matrix. This resulting in ensembles of QCS codes characterized by a single base matrix. We show that the minimum distance of Type-II QCS codes can be lower bounded by the minimum distance of the QC-LDPC codes. Simulation results show that the proposed QCS codes outperform some codes in the literature with a noteworthy low-error floor, below 10-7, over quantum depolarizing channels.

We study a class of linear network coding (LNC) schemes, called circular-shift LNC, whose encoding operations at intermediate nodes consist of only circular-shifts and bitwise addition (XOR). Departing from existing literature, we systematically formulate circular-shift LNC as a special type of vector LNC, where the local encoding kernels of an L-dimensional circular-shift linear code of degree δ are summation of at most δ cyclic-permutation matrices of size L. Under this framework, an intrinsic connection between scalar LNC and circular-shift LNC is established. In consequence, for some block lengths L, an (L - 1, L)-fractional circular-shift linear solution of arbitrary degree δ can be efficiently constructed on a multicast network. With different δ, the constructed solution has an interesting encoding-decoding complexity tradeoff, and when δ = (L - 1)/2, it requires fewer binary operations for both encoding and decoding processes compared with scalar LNC. While the constructed (L - 1, L)-fractional solution has one-bit redundancy per edge transmission, we show that this is inevitable, and that circular-shift LNC is insufficient to achieve the exact capacity of multicast networks.

Vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L-dimensional vector of data symbols over a base field GF(q). Vector LNC enriches the choices of coding operations at intermediate nodes, and there is a popular conjecture on the benefit of vector LNC over scalar LNC in terms of alphabet size of data units: there exist (singlesource) multicast networks that are vector linearly solvable of dimension L over GF(q) but not scalar linearly solvable over any field of size q' qL. This paper introduces a systematic way to construct such multicast networks, and subsequently establish explicit instances to affirm the positive answer of this conjecture for infinitely many alphabet sizes pL with respect to an arbitrary prime p. On the other hand, this paper also presents explicit instances with the special property that they do not have a vector linear solution of dimension L over GF(2) but have scalar linear solutions over GF(q') for someq'L, where q' can be odd or even. This discovery also unveils that over a given base field, a multicast network that has a vector linear solution of dimension L does not necessarily have a vector linear solution of dimension L' > L.

For a (single-source) multicast network, the size of a base field is the most known and studied algebraic identity that is involved in characterizing its linear solvability over the base field. In this paper, we design a new class N of multicast networks and obtain an explicit formula for the linear solvability of these networks, which involves the associated coset numbers of a multiplicative subgroup in a base field. The concise formula turns out to be the first that matches the topological structure of a multicast network and algebraic identities of a field other than size. It further facilitates us to unveil infinitely many new multicast networks linearly solvable over GF(q) but not over GF(q') with q2k) but not over GF(22k+1) and 2) for arbitrary distinct primes p and p', there are infinitely many k and k' such that an instance in N can be found linearly solvable over GF(pk) but not over GF(p'k') with pkk'.

In the literature of network coding, vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L-dimensional vector of data symbols over a base field GF(q). A scalar linear code over GF(q) is simply a vector linear code of dimension 1 over GF(q), and a general network has a scalar linear solution over GF(qL) only if it has a vector linear solution of dimension L over GF(q). Though vector LNC is more powerful in enabling a higher coding diversity, this work will present explicit multicast networks, for the first time in the literature, with the special property that they do not have a vector linear solution of dimension L over GF(2) but have scalar linear solutions over GF(q'), for some q'L. This reveals the fact that although vector LNC can outperform scalar LNC in terms of yielding a solution for a general network, scalar LNC can also outperform vector LNC of dimension larger than 1 in terms of using a smaller alphabet to yield a solution for a multicast network.

Vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L-dimensional vector of data symbols over a base field GF(q). There are classical exemplifying multi-source networks that have simple vector linear solutions but no scalar linear solutions over any field. For (single-source) multicast networks, a popular conjecture characterizes the following benefit of vector LNC over scalar LNC in terms of alphabet size of data units: there exist multicast networks that are vector linearly solvable of dimension L over GF(q) but not scalar linearly solvable over any field of size q' ≤ qL. This paper introduces a general method to construct such a network, and subsequently constructs the first examples to affirm the positive answer of this conjecture. Moreover, among these exemplifying networks vector linearly solvable of dimension L over GF(q), there are instances with the additional property that even for some extremely large q' > qL, they are still not scalar linearly solvable over GF(q').

A distributed multiple-input-multiple-output (MIMO) system consists of M users served by L distributed base stations (BSs), where the BSs are connected to a central unit (CU) via L independent backhaul (BH) links. In this paper, we consider the design of an uplink distributed MIMO system where 1) the channel state information is not available at the transmitters and 2) the BH links are rate constrained. We propose a new linear network coding (LNC)-based protocol: the M users transmit simultaneously. Each BS generates N linear functions of the M users' messages, based on a preassigned LNC coefficient matrix. The CU collects N · L linear functions from the L BSs and recovers all M users' messages by solving these linear functions. The decoding becomes successful if the linear functions has full rank M and fails if the linear functions are rank deficient. We derive the preassigned LNC coefficient matrix that minimizes the probability of rank deficiency. We then analyze the outage probability (OP) of the proposed scheme over a Rayleigh fading channel. We analytically show that as long as the BH rate is greater than the individual data rate of one user, the OP of the proposed scheme decays like 1/SNRLat high SNR. This is in contrast to the existing scheme whose OP decays like 1/SNR. As the BH rate constraint approaches M times the data rate of one user, the performance of the proposed scheme is 10/L log10(L!) dB away from that of the full MIMO scenario at high SNR. We also develop a structured way to efficiently construct the preassigned LNC coefficient matrix that yields the optimized OP performance. Numerical results show that the proposed scheme has significantly improved performance over existing schemes.

In an acyclic multicast network, it is well known that a linear network coding solution over GF(q) exists when q is sufficiently large. In particular, for each prime power q no smaller than the number of receivers, a linear solution over GF(q) can be efficiently constructed. In this paper, we reveal that a linear solution over a given finite field does not necessarily imply the existence of a linear solution over all larger finite fields. In particular, we prove by construction that: 1) for every ω ≥ 3, there is a multicast network with source outdegree ω linearly solvable over GF(7) but not over GF(8), and another multicast network linearly solvable over GF(16) but not over GF(17); 2) there is a multicast network linearly solvable over GF(5) but not over such GF(q) that q > 5 is a Mersenne prime plus 1, which can be extremely large; 3) a multicast network linearly solvable over GF(qm1) and over GF(qm2) is not necessarily linearly solvable over GF(qm1+m2); and 4) there exists a class of multicast networks with a set T of receivers such that the minimum field size qminfor a linear solution over GF(qmin) is lower bounded by O(√|T|), but not every larger field than GF(qmin) suffices to yield a linear solution. The insight brought from this paper is that not only the field size but also the order of subgroups in the multiplicative group of a finite field affects the linear solvability of a multicast network.

In an acyclic multicast network, it is well known that a linear network coding solution over GF(q) exists when q is sufficiently large. In particular, for each prime power q no smaller than the number of receivers, a linear solution over GF(q) can be efficiently constructed. In this work, we reveal that a linear solution over a given finite field does not necessarily imply the existence of a linear solution over all larger finite fields. Specifically, we prove by construction that: (i) For every source dimension no smaller than 3, there is a multicast network linearly solvable over GF(7) but not over GF(8), and there is another multicast network linearly solvable over GF(16) but not over GF(17); (ii) There is a multicast network linearly solvable over GF(5) but not over such GF(q) that q > 5 is a Mersenne prime plus 1, which can be extremely large.

In this paper, we propose a novel opportunistic pair-wise transmission scheme in a multi-way relay channel (MWRC), in which multiple users exchange information via a common relay. We investigate pair-wise compute-and-forward for MWRCs by exploiting the multi-user fading channels. Conventionally, a pair-wise physical-layer network coding scheme with binary phase shift keying modulation was studied for a MWRC. In this paper, the proposed opportunistic pair-wise compute-and-forward employs high level modulation with nested lattice codes to improve the sum-rate of multi-user transmission. We demonstrate that this novel opportunistic pair-wise transmission has a 2 bits/s/Hz improvement in the sum-rate performance at signal-to-noise ratio of 30 dB for a 4-user MWRC. For the same MWRC, up to 4.5 dB gain or 2.5 dB gain can be achieved for an uncoded or a channel-coded system, respectively, at the frame error probability of 10-2.

A combinatorial notion of flow is identified for time-invariant linear coding over non-layered deterministic linear networks that may contain cycles, broadcast and interference links. It reveals the matroidal structure for efficient code construction, and enables a seamless extension of the classical network coding results. In particular, the flow can be decomposed efficiently into disjoint information flow paths to support a maximum unicast rate up to the cut-set bound.

In this paper, we investigate lattice network codes (LNCs) constructed from Eisenstein integer based lattices. Quantization and encoding algorithms over Eisenstein integers are first introduced. Then, a union bound estimation (UBE) of the decoding error probability is derived when the shaping region of the LNC is a product of regular hexagons. Next, the Gaussian reduction algorithm is generalized to be applicable to complex lattices over Eisenstein integers such that an optimal coefficient vector can be found in the two-transmitter single-relay system. Based on the UBE, design criteria for optimal LNCs with minimum decoding error probability are formulated and applied to construct both Gaussian integer and Eisenstein integer based good LNCs from rate-1/2 feed-forward convolutional codes by Complex Construction A. The constructed codes provide up to 7.65 dB nominal coding gains over Rayleigh fading channels. Furthermore, we introduce the construction of LNCs from linear codes by Complex Construction B. The nominal coding gains and error performance of the LNCs thus constructed are explicitly analyzed. Examples show that the LNCs constructed by Complex Construction B provide a better tradeoff between code rate and nominal coding gain.

In this paper, we investigate lattice network codes (LNCs) constructed from lattices over the ring of Eisenstein integers. Quantization and encoding algorithms over Eisenstein integers are first introduced. Then, a union bound estimation (UBE) of the decoding error probability is derived when the shaping region of the LNC is a product of regular hexagons. We show that the UBE is in the same form as the one for hypercube shaped LNCs, such as in the Gaussian integer case. We also demonstrate that in the Eisenstein integer case, the nominal coding gain and the shaping gain of a baseline LNC are, respectively, 0.625 dB and 0.167 dB, in contrast to the Gaussian integer case, where both gains are 0 dB. This is consistent with the simulation results comparing the performance of decoding error probability of baseline LNCs.

In this work, we define delay invariant convolutional network codes which guarantee multicast communication at asymptotically optimal rates in networks with arbitrary delay patterns. We show the existence of such a code over every symbol field. Moreover, the code can be constructed with high probability when coding coefficients are independently and uniformly chosen from a sufficiently large set of coding operations. On the other hand, if the symbol field is no smaller than the number of receivers, we devise a method to efficiently construct a delay invariant convolutional network code with scalar coding coefficients.

Network coding is a new paradigm in data transport that combines coding with data propagation over a network. Theory of linear network coding (LNC) adopts a linear coding scheme at every node of the network and promises the optimal data transmission rate from the source to all receivers. Linearity enhances the theoretic elegance and engineering simplicity, which leads to wide applicability. This paper reviews the basic theory of LNC and construction algorithms for optimal linear network codes. Exemplifying applications are presented, including random LNC. The fundamental theorem of LNC applies to only acyclic networks, but practical applications actually ignore the acyclic restriction. The theoretic justification for this involves convolutional network coding (CNC), which, however, incurs the difficulty of precise synchronization. The problem can be alleviated when CNC is generalized by selecting an appropriate structure in commutative algebra for data units. This paper tries to present the necessary algebraic concepts as much as possible in engineering language.

The fundamental result of linear network coding asserts the existence of an optimal code on an acyclic single-source multicast network when the symbol field is sufficiently large. The restriction to acyclic networks turns out to stem from the customary structure of the symbol alphabet as a field. Adopting data units belonging to a discrete valuation ring (DVR), that is, a PID with a unique maximal ideal, much of the network coding theory extends to cyclic single-source multicast networks. Convolutional network coding is the instance of DVR-based network coding when the DVR consists of rational power series over the symbol field. Meanwhile, a field can be regarded as a degenerate DVR since it is a PID with the maximal ideal 0. Thus the conventional field-based network coding theory becomes a degenerate version of the DVR-based theory. This paper also delves into the issue of constructing optimal network codes on cyclic networks. Inspired by matroid duality theory, a novel method is devised to take advantage of all existing acyclic algorithms for network code construction. It associates every cyclic network with a quadratically large acyclic network so that essentially every optimal code on the acyclic network directly induces one on the cyclic network.

This paper deals with matroids on the edge set of a network. Through the structure of edge-disjoint paths, a single-source network is associated with a network matroid, which turns out to be representable. A linear network code on an acyclic network assigns a coding vector to every edge. The linear independence among coding vectors naturally induces a matroid. It is shown that every independent set in the matroid so induced is also independent in the network matroid. Moreover, the two matroids coincide with each other if and only if the linear network code is a generic one. Furthermore, every representation for the network matroid of an acyclic network induces a generic linear network code. This offers a new characterization of generic linear network codes. For the network matroid of a cyclic network, an algorithm for finding a representation is also derived through the association with an acyclic network.