# Low Delay Inter-Packet Coding in Vehicular Networks
## 3 Packet Recovering Codes
### Binary Wyner-Ash codes
#### Decoding  
As mentioned above, we study two decoding algorithms: SW-decoding and its simplified version SWBP decoding. A low-complexity modification of SWBP decoding whose error performance tends to that of SW-decoding is suggested. First, we reformulate the problem of decoding over the BEC to the problem of solving a system of linear equations. Consider a BEC with erasure probability \(\epsilon\). Let \(H\) be an \(r_{\text{B}}\times n_{\text{B}}\) parity-check matrix of a binary \((n_{\text{B}},n_{\text{B}}-r_{\text{B}})\) block code, with the minimum Hamming distance \(d_{\min}\). An ML decoder corrects any pattern of \(\
u\) erasures if \(\
u\leq d_{\min}-1\). If \(d_{\min}\leq\
u\leq r_{\text{B}}\), then a unique correct decision can be obtained for some erasure patterns. The number of such correctable patterns depends on the code structure. Let \(\mathbf{y}=(y_{1},y_{2},\ldots,y_{n_{\text{B}}})\) be a received vector, where \(y_{i}\in\{0,1,\phi\}\), and the symbol \(\phi\) represents an erasure. We denote by \(\mathbf{e}=(e_{1},e_{2},\ldots,e_{n_{\text{B}}})\) a binary vector, such that for all \(i=1,2,\ldots,n_{\text{B}},e_{i}=1\) if \(y_{i}=\phi\), and \(e_{i}=0\) if \(y_{i}\in\{0,1\}\). Let \(I(\mathbf{e})\) be the set of nonzero coordinates of \(\mathbf{e}\), \(|I(\mathbf{e})|=\
u(\mathbf{e})\), and let \(\mathbf{z}=(z_{1},z_{2},\ldots,z_{\
u})\) be a vector of unknowns located in positions of \(I(\mathbf{e})\). Consider a system of linear equations \(\mathbf{y}H^{\text{T}}=\mathbf{0}\) which can be reduced to  
\[\mathbf{z}H^{\text{T}}_{I(\mathbf{e})}=\mathbf{s}(\mathbf{e})\, \tag{8}\]  
where the syndrome vector \(\mathbf{s}(\mathbf{e})=\mathbf{y}_{I^{\text{c}}(\mathbf{e})}H^{\text{T}}_{I^{\text{c}}(\mathbf{e})}\) is computed using the nonerased positions of \(\mathbf{y}\) and \(I^{\text{c}}(\mathbf{e})=\{1,2,\ldots,n_{\text{B}}\}\setminus I(\mathbf{e})\). ML decoding over the BEC is reduced to solving Equation (8). Next, we explain SW-decoding of the convolutional code by example of the Wyner-Ash code with memory \(m=2\). \begin{table}
\begin{tabular}{c c c} \hline \hline \(m\) & \(R\) & **Spectrum Coefficients \(g_{3}\),..., \(g_{12}\)** \\ \hline
2 & 3/4 & 6, 23, 80, 290, 1050, 3804, 13782, 49929, 180888, 655334 \\ \hline
3 & 7/8 & 28, 275, 2456, 22468, 205826, 1885187, 17266158, 158138208, 1448368114, 13265417898 \\ \hline
4 & 15/16 & 120, 2644, 52456, 1066592, 21738992, 442834486, 9021091078, 183772934474, 3743704654772, 76264411563598 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Weight enumerators for Wyner–Ash codes. Let \(L\) denote the decoding delay in blocks. At each step of the decoding procedure, the SW-decoder uses a \((W-m)\times Wh\) sized parity-check matrix which determines a ZT convolutional code  
\[H_{\text{ZT}}=\left( \begin{array}{ccccc}H_{2}&H_{1}&H_{0}&\mathbf{0}&\cdots\\ \ddots&\ddots&\ddots&\ddots&\ddots\\ \cdots&\mathbf{0}&H_{2}&H_{1}&\begin{array}{c}H_{0}\\ H_{1}\end{array}&\begin{array}{c}\mathbf{0}&\cdots\\ H_{0}&\mathbf{0}&\cdots\\ H_{1}&H_{0}&\mathbf{0}&\cdots\\ H_{2}\end{array}&\begin{array}{c}\ldots\\ H_{1}&H_{0}&\mathbf{0}&\cdots\\ H_{1}&H_{0}&\mathbf{0}&\cdots\\ H_{1}&H_{0}&\mathbf{0}&\cdots\\ \end{array}\\ \begin{array}{ccccc}&&\ddots&\ddots&\ddots&\ddots\\ &&\cdots&\mathbf{0}&H_{2}&H_{1}&H_{0}\\ \end{array}\end{array} \right), \tag{9}\]  
where \(W=L+m+1\) is the decoding window size in \(n\)-blocks. Let \(\boldsymbol{y}=(y_{1},y_{2},\dots)\) be a semi-infinite input vector of the SW-decoder. Assuming \(m\) first blocks known (for example, all-zero) we start decoding with \((m+1)\)th block. The decision is made about \(W-m\) blocks. After decoding (solving the system of linear equations), the recovered symbols are substituted into input sequence \(\boldsymbol{y}\), the decoder outputs the \((m+1)\)th block and the window slides by one block.