# Low Delay Inter-Packet Coding in Vehicular Networks
## 3 Packet Recovering Codes
### Nonbinary Convolutional Codes  
#### 3.2.1 Code Description and Error-Correcting Properties  
The advantage of the binary Wyner-Ash codes is high efficiency under very short decoding delay and extremely simple decoding algorithm. Error-correcting properties can be further improved at the cost of additional decoding complexity if instead of binary digits we consider \(c\)-tuples of bits or even entire packets as message symbols. The corresponding convolutional code will be a code over the Galois field extension GF(2\({}^{c}\)). Generalization of the Wyner-Ash construction to nonbinary alphabets for correcting independent errors and error bursts was presented in [17], where these codes are called \"Reed-Solomon (RS) convolutional codes\". Here, we analyze efficiency of these codes when used for correcting erasures or recovering lost packets in the network. For simplicity, we consider rate \(R=(n-1)/n\) codes with memory \(m=2\). A semi-infinite parity-check matrix of the code has the form of Equation (2), where the main submatrix in Equation (3) is equal to  
\[H^{(m)}= \begin{pmatrix}H_{0}\\ H_{1}\\ H_{2}\end{pmatrix} = \begin{pmatrix}1&1&\cdots&1\\ 1&\alpha&\cdots&\alpha^{n-1}\\ 1&\alpha^{2}&\cdots&\alpha^{2(n-1)}\end{pmatrix}  \tag{12}\]  
and \(\alpha\) denotes a primitive element of the field GF(2\({}^{c}\)). If the parity-check matrix of \(R=(n-1)/n\), \(n\geq 4\) convolutional code over GF(2\({}^{c}\)), \(c>\log_{2}n\), is defined by Equation (2) with submatrices defined by Equation (12), then free distance of the convolutional code is \(d_{\text{free}}=4\). Let \(\mathbf{\
u}=(\
u_{1},\
u_{2},...)\) denote a sequence of numbers of the erased positions on the 1 st, 2 nd, etc. subblocks of length \(n\). It is enough to prove that any erasure pattern such that  
\[\sum_{i=1}^{\infty}\
u_{i}\leq 3\]  
will be recovered using SW decoding, and there exists an uncorrectable erasure pattern of weight 4. To prove the negative statement, consider the sequence \(\mathbf{\
u}=(4,0,0,...)\). Three parity checks of the matrix in Equation (12) will contain four unknown variables and, therefore, a unique decision does not exist. To prove that all erasure patterns of three or fewer erasures will be corrected, we show that the following two statements are true:  
1. Any erasure pattern \(\mathbf{\
u}=(\
u_{1},\
u_{2},...,\
u_{N})\) such that \(\
u_{1}\leq 3\) and \(\
u_{i}=0\), \(i\
eq 1\) for any \(N\) will be corrected. 2. Any erasure pattern \(\mathbf{\
u}=(\
u_{1},\
u_{2},...,\
u_{N})\) such that \(\
u_{i}<3\), \(\sum_{i}\
u_{i}=3\) will be corrected. The first property follows from the fact that the corresponding subblock codes are the RS-codes of length \(n\geq 4\) and \(d_{\min}=4\). The second property follows from the fact that any three columns belonging to different subblocks are linearly independent if \(c>\log_{2}n\) and the Vandermond matrix in Equation (12) is non-degenerate [24]. In other words, for the worst case \(\mathbf{v}=(2,1,0,...)\), the corresponding columns of the parity-check matrix have the form  
\[ \begin{pmatrix}1&1&0\\ \alpha^{i}&\alpha^{j}&1\\ \alpha^{2i}&\alpha^{2j}&\alpha^{h}\\ 0&0&\alpha^{2h}\\ \end{pmatrix} \]  
where \(i<j<n,h<n\). These columns are linearly independent, therefore, correction of such erasure pattern is guaranteed. We already proved that uncorrectable erasure patterns of weight four having their ones in one subblock cannot be corrected. In what follows, we show that if four erasures are located in different subblocks then such erasure patterns can always be corrected. If the parity-check matrix of \(R=(n-1)/n\), \(n\geq 4\) convolutional code over GF(\(2^{c}\)), \(c>2n\), is defined by Equation (2) with submatrices defined by Equation (12), then all erasure patterns of weight four except for the \(\binom{n}{4}\) erasure patterns can be corrected. According to Property 1 of Theorem 1, all correctable erasure patterns of weight four having their ones in one block cannot be corrected. Thus, there are \(\binom{n}{4}\) uncorrectable erasure patterns.