On GRAND-Assisted Vector Random Linear Network Coding in Wireless Broadcasts

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.