On GRAND-Assisted Vector Random Linear Network Coding in Wireless Broadcasts Authors: Rina Su, Chengji Zhao, Qifu Sun, Linqi Song Published: 2026 ABSTRACT Recent works have combined random linear network coding (RLNC) with guessing random additive noise decoding (GRAND) to leverage RLNC packets to partially correct bit errors prior to RLNC decoding, so as to reduce the packet erasure rates in wireless broadcast networks. However, existing schemes are restricted to scalar RLNC over the finite field GF(2L). In this paper, we first formulate a general GRAND-assisted decoding framework for vector RLNC over the vector space GF(2)L, and further propose a design rule for vector RLNC schemes such that estimated error vectors can be efficiently obtained without incurring any additional computational overhead. Necessary and sufficient conditions for the correctness of every efficiently obtained estimated error vector are characterized. Two explicit vector RLNC schemes satisfying the proposed design rule are constructed. The first scheme is designed based on the matrix representation of GF(2L), and analytical results show that it achieves the same completion delay performance as the counterpart scalar RLNC scheme over GF(2L), while achieving up to a 37.3% reduction in coding computational complexity compared with the scalar one. The second scheme is designed based on sparse coding coefficient matrices. It further reduces computational complexity by up to 33.6% compared with the first scheme, at the cost of a slight degradation in completion delay performance. 1. Introduction In wireless broadcast networks with packet erasures, maintaining timely information delivery is a key challenge. Metrics such as transmission delay have therefore attracted increasing attention. Network coding has emerged as an effective technique to address these challenges, as it allows multiple packets to be jointly encoded and transmitted, thereby reducing the number of transmissions. Scalar linear network coding (LNC) treats every data symbol, which is a binary sequence of length L, as an element in the finite field GF(2L), and performs linear combinations over GF(2L), with coding coefficients selected from the same field. Vector LNC [1,2] generalizes this framework by representing data symbols in the vector space GF(2)L and applying coding coefficients in the form of L×L matrices over GF(2) to generate coded packets. While scalar LNC provides 2L possible coding coefficients, vector LNC enlarges the set of available coefficients to 2L2, offering substantially greater coding flexibility. The advantages of vector LNC over scalar LNC have been demonstrated in various wireline network settings. In particular, there exist networks whose capacity can be achieved by vector LNC but not by scalar LNC [1,3,4,5]. Moreover, for single-source multicast networks, explicit instances have been designed to demonstrate that the code dimension L required by vector LNC to achieve the multicast capacity can be much smaller compared with (that by) scalar LNC [6,7,8,9,10]. In addition, in the practical implementation of MDS codes over GF 2m for data storage systems, several coding libraries have adopted the vector linear code versions based on matrix representation of GF2m, such as Jerasure Library [11] and Intel Intelligent Storage Acceleration Library [12] (ISA-L) for Reed–Solomon codes and Longhair library [13] for Cauchy Reed–Solomon codes. Random LNC (RLNC) [14] is a widely studied LNC technique that can significantly improve the completion delay performance, a key metric of transmission efficiency in wireless networks with packet erasures [15,16,17,18,19,20,21,22]. Even though most attention has been focused on scalar RLNC, vector RLNC with properly designed coding coefficient sets has been shown to offer lower computational complexity [18,23]. In recent years, in the context of wireless broadcast networks, a series of works [24,25,26] investigated the joint design of RLNC with an interesting guessing–decoding principle, i.e., guessing random additive noise decoding (GRAND) [27,28,29], to exploit RLNC packets to partially correct certain bit errors in a packet before RLNC decoding, so that the packet erasure rate is reduced and thus completion delay performance is improved. However, these GRAND-assisted RLNC schemes only apply to scalar RLNC. In particular, the works in [24,25] investigated GRAND-assisted RLNC over GF(2), while [26] extended the study to GF(2L). To the best of our knowledge, no previous research has investigated GRAND-assisted vector RLNC schemes. This paper aims to bridge this gap. Compared with prior scalar GRAND-assisted RLNC schemes, the proposed vector RLNC framework enables comparable completion delay performance under appropriate design, while offering better design flexibility of coding coefficients so as to further reduce the coding complexity. The main contributions of this paper are enumerated as follows. We formulate a general framework of the GRAND-assisted decoding process of vector RLNC over GF(2)L in wireless broadcasts. We formulate a general framework of the GRAND-assisted decoding process of vector RLNC over GF(2)L in wireless broadcasts. Building on this framework, we further establish a general design rule for vector RLNC schemes such that the estimated error vectors can be directly obtained without incurring any additional computational overhead. We further theoretically characterize necessary and sufficient conditions for the correctness of every efficiently obtained estimated error vector. Building on this framework, we further establish a general design rule for vector RLNC schemes such that the estimated error vectors can be directly obtained without incurring any additional computational overhead. We further theoretically characterize necessary and sufficient conditions for the correctness of every efficiently obtained estimated error vector. Two explicit vector RLNC schemes satisfying the proposed design rule are deliberately constructed. The coding coefficient matrices in the first scheme are constructed by leveraging the matrix representation of GF(2L), while the second scheme employs sparse coding coefficient matrices. Two explicit vector RLNC schemes satisfying the proposed design rule are deliberately constructed. The coding coefficient matrices in the first scheme are constructed by leveraging the matrix representation of GF(2L), while the second scheme employs sparse coding coefficient matrices. The first proposed scheme with the efficient GRAND process to obtain estimated error vectors is proved to have the same completion delay performance as the counterpart scalar RLNC scheme investigated in [26], while reducing coding computational complexity by up to 37.3%. Moreover, analytical and numerical results demonstrate that the second proposed vector RLNC scheme can further reduce computational complexity by up to 33.6% compared with the first one, at the cost of a slight degradation in completion delay performance. The first proposed scheme with the efficient GRAND process to obtain estimated error vectors is proved to have the same completion delay performance as the counterpart scalar RLNC scheme investigated in [26], while reducing coding computational complexity by up to 37.3%. Moreover, analytical and numerical results demonstrate that the second proposed vector RLNC scheme can further reduce computational complexity by up to 33.6% compared with the first one, at the cost of a slight degradation in completion delay performance. The organization of this paper is as follows. Section 2 describes the network model, followed by Section 3 which establishes a general framework for GRAND-assisted vector RLNC. Section 4 proposes a design rule for the coding coefficient set of vector RLNC so that estimated error vectors can be efficiently obtained while avoiding any additional computational overhead. Explicit design examples subject to the rule are also presented. Section 5 numerically compares the two design examples. Section 6 concludes the paper. 2. Network Model Consider a single-hop broadcast scenario with no feedback, where a single sender serves R receivers by transmitting P original packets. Every packet consists of M bits. Packet transmissions take place in discrete timeslots, with one packet broadcast in each slot. The sender-to-receiver links are independently modeled as memoryless packet erasure channels; in particular, the erasure probability for receiver r is 1−pr. The task of every receiver is to recover all P original packets successfully. Following the settings in [15,16,18,19,21,22], this paper considers systematic RLNC transmission. In the first phase, the sender broadcasts the P original packets sequentially. After this systematic phase, coded transmissions begin, where each transmitted packet is generated as a random linear combination of the P original packets. The transmission proceeds until every receiver successfully recovers all P packets. To evaluate the throughput performance, we adopt completion delay as the primary metric, defined as the total number of coded packets transmitted by the sender. We consider vector RLNC schemes defined over the L-dimensional vector space GF(2)L. Each packet mj containing M bits is represented as a row vector [mj,1,mj,2,…,mj,M/L], which consists of M/L symbols. Each symbol mj,i is viewed as an L-bit row vector over GF(2). Given an L×L matrix K over GF(2), the vector coding operation K∘mj is defined symbol-wise as(1)K∘mj=[mj,1K,mj,2K,…,mj,M/LK]. For d≥1, the dth coded packet mP+d randomly produced by the sender in the second phase can be represented as(2)mP+d=∑j=1PKd,j∘mj=[∑j=1Pmj,1Kd,j,…,∑j=1Pmj,M/LKd,j]. where the coding coefficient matrices Kd,j are randomly selected, according to certain defined rules, from L×L matrices over GF(2). The global encoding kernel of a packet is defined as a PL×L matrix over GF(2), which can also be interpreted as a P×1 block matrix where each block entry is an L×L coding coefficient matrix. For each original packet mj (1≤j≤P), its global encoding kernel Fj is structured such that the jth block entry is the identity matrix IL, and all other block entries are L×L zero matrices. By construction, the concatenation of these kernels satisfies [Fj]1≤j≤P=IPL. For a coded packet mP+d=∑j=1PKd,j∘mj, the corresponding global encoding kernel FP+d is formulated as FP+d=[Kd,1TKd,2T…Kd,PT]T. Denote by I the index set of packets successfully received by a receiver. In vector RLNC, the receiver can reconstruct all P original packets provided that the column-wise concatenation [Fj]j∈I of the |I| global encoding kernels forms a PL×|I|L matrix over GF(2) of rank PL. 3. A General Framework for GRAND-Assisted GF(2)L-RLNC Decoding In most previous studies of RLNC in wireless broadcasts, only the successfully received packets will be utilized by a receiver. In these studies, receivers are assumed to discard the packets that are corrupted even for 1 bit, and to utilize only error-free packets for RLNC decoding. However, it has been advocated in [24,25,26] that both error-free and erroneous packets can be jointly utilized to generate syndromes so that some erroneous packets can be corrected following the principle of GRAND, and hence the actual packet erasure probability can be reduced. In [24,25,26], the GRAND-assisted decoding process is investigated in the context of scalar RLNC; that is, RLNC over GF(2) or GF(2L). In this section, we shall formulate, for the first time in the literature, the framework of GRAND-assisted RLNC decoding that applies to vector RLNC over GF(2)L. To ease the ensuing presentation, unless otherwise specified, a fixed receiver r is assumed, so that r will not be reflected in notations. For every packet mj=[mj,1,…,mj,M/L], let m^j=[m^j,1,…,m^j,M/L] denote the packet received by receiver r, and let ej=[ej,1,…,ej,M/L] denote the error vector m^j+mj, where every ej,i is called an error symbol. We have Pr{ej=0}=Pr{mj=m^j}=pr. Following a similar assumption adopted in [24], we consider that upon receiving a packet m^j, every receiver can categorize the packet as either error-free or erroneous by using an error detection mechanism such as cyclic redundancy check (CRC), and the global encoding kernel of the packet is identified at the receiver in an error-free manner. When all P original packets are correctly received by receiver r then the transmission completes at r. Otherwise, let I⊆{1,…,P} denote the index set of the correctly received original packets and J={1,…,P}∖I denote the index set of the erroneously received original packets; that is, I={1≤j≤P:mj=m^j}, J={1≤j≤P:mj≠m^j}. Receiver r repeatedly performs the following routine every time a coded packet m^P+d is received, till all P original packets can be recovered; that is, rank([Fj]j∈I)=PL. Upon receiving a new coded packet m^P+d=∑j=1PKd,j∘mj+eP+d, d≥1, if mP+d=m^P+d, then receiver r updates the correct packet set I=I∪{P+d}; otherwise, receiver r updates the erroneous packet set J=J∪{P+d}. Upon receiving a new coded packet m^P+d=∑j=1PKd,j∘mj+eP+d, d≥1, if mP+d=m^P+d, then receiver r updates the correct packet set I=I∪{P+d}; otherwise, receiver r updates the erroneous packet set J=J∪{P+d}. A syndrome sd=[sd,1,…,sd,M/L] is computed as(3)sd=∑j=1PKd,j∘m^j+m^P+d, in which every symbol sd,i, 1≤i≤M/L is equal to ∑j=1Pm^j,iKd,j+m^P+d,i. It can be readily checked that(4)sd=∑j=1PKd,j∘ej+eP+d,sd,i=∑j=1Pej,iKd,j+eP+d,i. A syndrome sd=[sd,1,…,sd,M/L] is computed as(3)sd=∑j=1PKd,j∘m^j+m^P+d, in which every symbol sd,i, 1≤i≤M/L is equal to ∑j=1Pm^j,iKd,j+m^P+d,i. It can be readily checked that(4)sd=∑j=1PKd,j∘ej+eP+d,sd,i=∑j=1Pej,iKd,j+eP+d,i. Based on d syndromes s1,…,sd, receiver r attempts to obtain an estimated error vector e˜j for every (nonzero) ej, j∈J. According to the principle of GRAND,(5)[e˜j]j∈J=argmax[wj]j∈JPr{ej=wj,∀j∈J}subjectto(6)wP+i+∑1≤j≤P,j∈JKi,j∘wj=si∀1≤i≤d(7)wj≠0∀j∈J,wP+i=0∀P+i∉J Based on d syndromes s1,…,sd, receiver r attempts to obtain an estimated error vector e˜j for every (nonzero) ej, j∈J. According to the principle of GRAND,(5)[e˜j]j∈J=argmax[wj]j∈JPr{ej=wj,∀j∈J}subjectto(6)wP+i+∑1≤j≤P,j∈JKi,j∘wj=si∀1≤i≤d(7)wj≠0∀j∈J,wP+i=0∀P+i∉J For each j∈J, check whether e˜j+m^j is equal to mj by another round of CRC. If so, then receiver r successfully corrects ej and recovers packet mj, removes j from J, puts j into I, sets ej=0, and performs the following steps. If j is no larger than P, then update every syndrome si, 1≤i≤d as si+Ki,j∘e˜j; otherwise, update the syndrome sj−P as sj−P+e˜j. For each j∈J, check whether e˜j+m^j is equal to mj by another round of CRC. If so, then receiver r successfully corrects ej and recovers packet mj, removes j from J, puts j into I, sets ej=0, and performs the following steps. If j is no larger than P, then update every syndrome si, 1≤i≤d as si+Ki,j∘e˜j; otherwise, update the syndrome sj−P as sj−P+e˜j. Based on the |I|=P+d−|J| correctly obtained packets, full recovery of all P original packets is possible when rank([Fj]j∈I)=PL. Otherwise, receiver r will receive a new coded packet m^P+d+1, with the above routine being repeated. Based on the |I|=P+d−|J| correctly obtained packets, full recovery of all P original packets is possible when rank([Fj]j∈I)=PL. Otherwise, receiver r will receive a new coded packet m^P+d+1, with the above routine being repeated. In the above formulation, estimated error vectors e˜j, j∈J, are obtained based on the probability Pr{ej=wj} in (5), which is related to the underlying channel modeling for bit-level transmission. In previous studies of GRAND-assisted RLNC, memoryless binary symmetric channels (BSCs) were considered in [25,26], and Gilbert–Elliott channels were considered in [24]. Different channel models lead to different relationships between packet erasure rate 1−pr and bit error rate in a packet, and thus lead to different Pr{e˜j=ej}. 4. Efficient GRAND-Assisted Vector RLNC As indicated by the formulation in (5)–(7) in Section 3, the computational complexity to obtain estimated error vectors e˜j, j∈J, is excessively high. In the context of scalar RLNC, a novel scheme over GF(2L) was proposed in [26] so that estimated error vectors could be guessed with negligible computational overhead from syndromes. Motivated by this scalar scheme, in this section, we shall first introduce a general rule to design vector RLNC schemes over GF(2)L for L>1, so that estimated error vectors can be obtained from syndromes without introducing any computational overhead. Subsequently, in Section 4.2 and Section 4.3, we explicitly design two vector RLNC schemes satisfying the general rule. The two concrete design instances exhibit different complexity and performance characteristics. 4.1. Design Rule of Vector RLNC and Efficient Estimate of e˜j In an error vector ej=[ej,1,…,ej,S] consisting of S error symbols, if an error symbol ej,i contains exactly 1-bit error, it means that ej,i∈GF(2)L represents a unit vector of size L. Let E denote the set of all unit (row) vectors of size L, i.e.,(8)E=e∈GF(2)L∣wt(e)=1, where wt(e) represents the Hamming weight of vector e. We aim at guessing out those error symbols belonging to E. In the design of vector RLNC, for every coded packet mP+d=∑j=1PKd,j∘mj, d≥1, we need to impose the following conditions on the random coding coefficient matrices. (∗)All rows in Kd,j, 1≤j≤P, are distinct nonzero vectors, and none of them is a unit vector; that is,(9)|⋃u∈Kd,j,1≤j≤P{u}|=PL,{⋃u∈Kd,j,1≤j≤P{u}∩E}=ϕ, where u∈Kd,j traverses all the rows in the coding coefficient matrix Kd,j. All rows in Kd,j, 1≤j≤P, are distinct nonzero vectors, and none of them is a unit vector; that is,(9)|⋃u∈Kd,j,1≤j≤P{u}|=PL,{⋃u∈Kd,j,1≤j≤P{u}∩E}=ϕ, where u∈Kd,j traverses all the rows in the coding coefficient matrix Kd,j. Since the global encoding kernel FP+d for coded packet mP+d is FP+d=Kd,1TKd,2T…Kd,PTT, condition (∗) equivalently states that all row vectors in FP+d are distinct, and not equal to any unit vector. The primary motivation for choosing the coding coefficient matrices subject to (∗) is that all eKd,j, 1≤j≤P and e∈E, constitute PL distinct row vectors. As a consequence, compared with estimating error vectors e˜j, j∈J through the general formulation in (5)–(7), the syndrome sd obtained from received coded packet m^P+d=∑j=1PKd,j∘mj+eP+d subject to (∗) offers a far more efficient alternative, as elaborated below. Efficient estimate of e˜j. Consider a vector RLNC scheme over GF(2)L subject to condition (∗), equipped with the GRAND-assisted decoding routine formulated in the previous section. Upon receiving a new packet m^P+d, instead of solving (5)–(7), receiver r performs the following concise procedure to obtain e˜j=[e˜j,1,…,e˜j,S], j∈J, based on the syndrome sd=[sd,1,…,sd,S]:As initialization, set estimated error symbol e˜j,i=0 for all j∈J and 1≤i≤S.For every nonzero symbol sd,i in sd, 1≤i≤S, perform the next two steps.If sd,i is a unit vector, then set e˜(P+d),i=e;Otherwise, check whether sd,i is identical to a row vector u in Kd,j, j∈J. If there exists such u, say in Kd,j′ with j′∈J, then set e˜j,i=e.When the above two steps are performed for all nonzero sd,i, 1≤i≤S, we obtain estimated error vectors e˜j, j∈J. As initialization, set estimated error symbol e˜j,i=0 for all j∈J and 1≤i≤S. As initialization, set estimated error symbol e˜j,i=0 for all j∈J and 1≤i≤S. For every nonzero symbol sd,i in sd, 1≤i≤S, perform the next two steps. For every nonzero symbol sd,i in sd, 1≤i≤S, perform the next two steps. If sd,i is a unit vector, then set e˜(P+d),i=e; If sd,i is a unit vector, then set e˜(P+d),i=e; Otherwise, check whether sd,i is identical to a row vector u in Kd,j, j∈J. If there exists such u, say in Kd,j′ with j′∈J, then set e˜j,i=e. Otherwise, check whether sd,i is identical to a row vector u in Kd,j, j∈J. If there exists such u, say in Kd,j′ with j′∈J, then set e˜j,i=e. When the above two steps are performed for all nonzero sd,i, 1≤i≤S, we obtain estimated error vectors e˜j, j∈J. When the above two steps are performed for all nonzero sd,i, 1≤i≤S, we obtain estimated error vectors e˜j, j∈J. The above process to obtain e˜j only involves the injective mapping from every sd,i to a vector in Kd,j, j∈J upon existence, so it is considered to take negligible computational overhead. It is worth noticing that e˜j, j∈J obtained by the above process do not necessarily satisfy (5), but (6) and (7) always hold. We next analyze the scenario where the efficiently estimated e˜j, j∈J, from a syndrome sd is equal to ej. As every syndrome sd is exploited independently in the efficient estimate, and according to Equation (3), syndrome sd does not contain any information of coded packets m^P+1,…,m^P+d−1. Hence, only those ej with j∈{1,2,…,P}∪{P+d} are possible to correct (i.e., e˜j=ej) based on syndrome sd. Notice that e˜j=ej if and only if e˜j,i=ej,i at every symbol location 1≤i≤S. For every 1≤i≤S with ej,i≠0, e˜j,i=ej,i holds if and only if(10)ej,i∈E,ej′,i=0∀j′∈J∖{j,P+1,…,P+d−1}. For every 1≤i≤S with ej,i=0, we need e˜j,i=0. Even though e˜j,i is set to 0 as initialization, it will be set to a nonzero vector e in E if eKd,j=sd,i. In this case, some nonzero error symbols at symbol location i are erroneously estimated to the 1-bit error symbol e˜j,i∈E, so that e˜j,i≠ej,i=0 and e˜j≠ej. It turns out that e˜j,i=0 whenever ej,i=0 if and only if(11)eKd,j≠sd,i∀e∈E, where Kd,j is assumed to be IL when j=P+d. Condition (11) is equivalent to stating that sd,i is not identical to any row vector of Kd,j. The above-characterized necessary and sufficient conditions for e˜j=ej are summarized in the following proposition. Consider a vector RLNC scheme subject to condition (∗). When e˜j, j∈J is obtained by the efficient estimate process based on sd, a receiver is able to correct nonzero ej; that is, e˜j=ej, if and only if the following holds. j∉{P+1,…,P+d−1}. For every symbol location 1≤i≤S with ej,i≠0, condition (10) holds. For every symbol location 1≤i≤S with ej,i=0, condition (11) holds. Since condition (10) only involves error symbols and is not related to the design of coding coefficient matrices Kd,j, Pr{e˜j,i=ej,i|ej,i≠0} keeps the same for all vector RLNC schemes subject to (∗). j∉{P+1,…,P+d−1}. j∉{P+1,…,P+d−1}. For every symbol location 1≤i≤S with ej,i≠0, condition (10) holds. For every symbol location 1≤i≤S with ej,i≠0, condition (10) holds. For every symbol location 1≤i≤S with ej,i=0, condition (11) holds. For every symbol location 1≤i≤S with ej,i=0, condition (11) holds. Based on Proposition 1, the probability Pr{e˜j=ej} for a receiver to correctly guess ej can be explicitly characterized, as long as the underlying channel model that determines the distribution of ej is given. In particular, when the memoryless BSC is considered, the sparse error pattern represented by Equation (10) occurs with high probability, so that Pr{e˜j=ej} is also high. As we do not focus on any particular channel model in the design of efficient estimate of e˜j, the theoretical analysis of Pr{e˜j=ej} is beyond the scope of this paper. To support the efficient estimation of e˜j, condition (∗) must be satisfied by the coding coefficient matrices in vector RLNC. Compared with the scalar RLNC scheme with efficient GRAND-assisted decoding proposed in [26], condition (∗), formulated within the more general vector RLNC framework, provides greater design flexibility. Different choices of Kd,j subject to (∗) may result in different coding complexities and distinct linear independence structures among global encoding kernels, thereby leading to different completion delay performances. Therefore, the design of vector RLNC schemes subject to (∗) warrants further investigation. In the following two subsections, we present two design instances with different features. 4.2. The First Design Instance of Vector RLNC Scheme Subject to (∗) In this subsection, based on the matrix representation of finite field GF(2L) (see, e.g., [23,30]), we introduce the first explicit design instance of vector RLNC subject to condition (∗). Let p(x)=xL+aL−1xL−1+…+a1x+1 be a primitive polynomial of degree L over GF(2), and α∈GF(2L) be a root of p(x). Consequently, α1,α2,…,α2L−1(=1) constitute 2L−1 distinct nonzero elements in GF(2L). Denote by A the following L×L companion matrix over GF(2) of p(x):(12)A=p1IL−10, where p=[aL−1,aL−2,…,a1]. Then, the set(13)M={0,A,A2,…,A2L−2(=IL)} forms a matrix representation of GF(2L), where A plays the same role as α. Specifically, if A(αj) represents the matrix representation of αj with A(α)=A, we have(14)A(αj)=Aj,∀j≥0. Define the following set K of L×L matrices(15)K={AL,A2L,…,A(⌊2L−1L⌋−1)L}. Let C1 denote the vector RLNC scheme with Kd,1,…,Kd,P randomly and independently selected from K for each d≥1. For every coded packet, it takes P(L−⌊log2L⌋) bits to store the information of P coding coefficient matrices. Condition (∗) holds for the vector RLNC scheme C1. For 0≤j≤2L−2, denote by pj=[aj,L−1,aj,L−2,…,aj,0] the (unique) polynomial representation of αj; that is, αj=∑l=0L−1aj,lαl. In this way, all pj, 0≤j≤2L−2, constitute the 2L−1 distinct nonzero vectors in GF(2)L. It is known (see, e.g., [23]) that(16)Aj=[pjT,pj+1T,…,pj+L−1T]T, where pj+l represents pj+l+1−2L whenever j+L≥2L−1. This implies that all rows in all matrices given by (∗) are distinct. Since p0,p1,…,pL−1 are the L unit vectors in GF(2)L, (16) further implies that only Aj, 0≤j≤L−1 and 2L−L−1≤j≤2L−2 contain rows equal to unit vectors. As these Aj do not belong to K, there is not any row in any matrix in K equal to a unit vector. We can now conclude that for each d≥1, the P random coding coefficient matrices Kd,1,…,Kd,P satisfy condition (∗). □ Based on Proposition 2, as long as the code dimension L is set to satisfy ⌊2L−1L⌋>P, the efficient process to estimate e˜j applies to the vector RLNC scheme C1. Under the same L, let C1′ denote the scalar RLNC scheme over GF(2L) with the coding coefficients kd,1,…,kd,P∈GF(2L) for every coded packet mP+d=∑j=1Pkd,jmj randomly and distinctively from the following set(17)K′={αL,α2L,…,α(⌊2L−1L⌋−1)L}. As every Aj=A(αj) in K is the matrix representation of αj in K′, a d×P matrix [ki,j]1≤i≤d,1≤j≤P over GF(2L) with ki,j∈K′ is full rank if and only if the dL×PL matrix [A(ki,j)]1≤i≤d,1≤j≤P with A(ki,j)∈K over GF(2) is full rank. It turns out that both the vector RLNC scheme C1 and the scalar RLNC scheme C1′ have the same distribution of completion delay. The scalar RLNC scheme C1′ over GF(2L) can be equipped with the efficient GRAND-assisted decoding procedure proposed in [26], so that estimated error vectors, denoted by e˜j′, j∈J can be guessed with negligible computational overhead from syndromes. Even though the necessary and sufficient conditions for e˜j′ equal to ej were not explicitly given in [26], we remark here that the conditions in Proposition 1 apply to e˜j′ as well. Consequently, we have the following proposition. For the vector RLNC scheme C1 and the counterpart scalar RLNC scheme C1′, they have the same distribution of completion delay. When C1 and C1′ are equipped with the efficient GRAND-assisted decoding procedure respectively proposed in the previous subsection and in [26], C1 and C1′ also have the same distribution of completion delay, regardless of the channel modeling for bit-level transmission. Although the completion delay performance of the efficient GRAND-assisted vector RLNC scheme C1 is identical to that of the counterpart scalar RLNC scheme C1′, our design yields a clear advantage in coding computational complexity. It has been theoretically analyzed in [23] that the theoretical coding complexity of vector RLNC over GF(2)L with nonzero coding coefficient matrices randomly selected from M in (13) can be halved compared with scalar RLNC with nonzero coding coefficients randomly selected from GF(2L). For brevity, assume every packet consists of 1 symbol; that is, it consists of L-bits. Given a binary row vector mj=[mj,L−1,…,mj,0] of length L, let mj=∑l=0L−1mj,lαl denote the corresponding element in GF(2L), where α denotes the same primitive element as in (17). By adopting a similar argument to [23], we theoretically compare the average number of exclusive OR (XOR) operations involved in generating a vector RLNC packet mP+d=∑j=1PmjKd,j and in generating a scalar RLNC packet mP+d=∑j=1Pmjkd,j, with Kd,1,…,Kd,P randomly and distinctively selected from K in (15), and kd,1,…,kd,P randomly and distinctively selected from K′ in (17). Same as in the proof of Proposition 2, for element αi∈GF(2L), 0≤i≤2L−2, denote by pi=[ai,L−1,ai,L−2,…,ai,0] its unique polynomial representation; that is, αi=∑l=0L−1ai,lαl. For the vector RLNC scheme C1 to generate mP+d=∑j=1PmjKd,j, it takes N1−L XORs, where N1 denotes the total number of nonzero entries in the corresponding global encoding kernel FP+d=[Kd,1T…Kd,PT]T. Since the P coding coefficient matrices Kd,1,…,Kd,P satisfy condition (∗), based on the characterization of Aj in (16), it can be deduced that the expected value of N1 is(18)E[N1]=P⌊2L−1L⌋−1∑i=L⌊2L−1L⌋L−1wt(pi)=P⌊2L−1L⌋−1(L2L−1−L−∑i=⌊2L−1L⌋L2L−2wt(pi)) We now consider the case of scalar coding over GF(2L). As α is a root of the defined primitive polynomial p(x)=xL+aL−1xL−1+…a1x+1,(19)αL=1+∑l=1L−1alαl. Thus, for i≥0, it takes iη XORs to compute mjαi, where η denotes the number of nonzero coefficients in {a1,…,aL−1}. Moreover, notice that in computing m(αi+αi+i′) with i,i′>0, it is equivalent to compute mαi+(mαi)αi′, so it takes (i+i′)η+L XORs. Consequently, for a coefficient αi=∑l=0L−1ai,lαl∈GF(2L) with the unique polynomial representation pi=[ai,L−1,ai,L−2,…,ai,0], it takes li,maxη+(wt(pi)−1)L XORs to compute mjαi, where li,max represents the largest degree in αi=∑l=0L−1ai,lαl with a nonzero coefficient; that is,(20)li,max=maxai,l′≠0l′. Let N1′ denote the total number of XORs involved in generating mP+d=∑j=1Pmjkd,j based on the previously analyzed arithmetic. When kd,1,…,kd,P are randomly and distinctively selected from K′ in (17),(21)E[N1′]=(P−1)L+P⌊2L−1L⌋−1∑i=1⌊2L−1L⌋−1liL,maxη+(wt(piL)−1)L. As an explicit comparison based on (18) and (21), for the case P=10, L=8 and α8+α4+α3+α2+1=0, it takes 512 XORs on average to generate mP+d=∑j=1Pmjkd,j, with kd,1,…,kd,P randomly and distinctively selected from K′ in (17). It takes 321 XORs on average to generate mP+d=∑j=1PmjKd,j, with Kd,1,…,Kd,P satisfying (∗), which yields a 37.3% reduction in coding computational complexity. 4.3. The Second Design Instance of Vector RLNC Scheme Subject to (∗) In addition to the one presented in the previous subsection, we next present another design instance of vector RLNC subject to condition (∗). Let 2