# Low Delay Inter-Packet Coding in Vehicular Networks
## 3 Packet Recovering Codes
### Binary Wyner-Ash codes
#### Decoding
At the \(i\)th step of the decoding procedure the decoder decides about \(\boldsymbol{y}_{\text{W}}\)  
\[\boldsymbol{y}_{\text{W}}=\left(y_{(m+i-1)n}\ \...\ \ y_{(i-1+W)n}\right)\]  
bits and outputs bits \((y_{(m+i-1)n},...,y_{(m+i)n})\). **Example 1**. : _Let \(L=2\). Then, a parity-check matrix of the ZT code has the form_  
\[H_{\text{ZT}}= \begin{pmatrix}1100&1010&1111\\ &1100&1010&1111\\ &&1100&1010&1111\\ \end{pmatrix} . \tag{10}\]  
_Let \(\boldsymbol{v}=(110\ 110\ 001\ 000\ 101\...)\) be the information sequence. By using the generator matrix in Equation (7) we obtain the corresponding codeword \(\boldsymbol{u}=(1100\ 1101\ 0010\ 0001\ 1010\...)\). Assume that the received sequence is \(\boldsymbol{y}=\left(1100\ 1\phi 001\phi\ 0001\ 1010\...\right)\)._  
_The SW-decoder starts decoding with the sequence \(\boldsymbol{y}_{\text{W}}=\left(0000\ 0000\ 1100\ 1\phi\ 0\phi\ 001\phi\right)\)._  
_The goal is to find codeword bits \([z_{1},z_{2},z_{3}]\) at the erased positions._  
**Step 1. **: _Compute syndrome. The syndrome is equal to [0 0 1]. From Equation (8) follows_  
\[ \begin{pmatrix}0&0&0\\ 1&1&0\\ 0&0&1\end{pmatrix}\begin{pmatrix}z_{1}\\ z_{2}\\ z_{3}\end{pmatrix} = \begin{pmatrix}0\\ 0\\ 1\end{pmatrix} .\]  
_The number of unknowns is larger than the rank of the system which is equal to 2, that is, a unique solution does not exists. The decoder outputs only the information part of the first erasure-free block [1 1 0 0], i.e., output bits at this step are [1 1 0]._
**Step 2. **: _Shift the window. Input now is \(\boldsymbol{y}_{\text{W}}=\left(0000\ 1100\ 1\phi 0\phi\ 001\phi\ 0001\right)\).__The syndrome is equal to [0 0 1]. From Equation (8) follows_  
\[ \begin{pmatrix}1&1&0\\ 0&0&1\\ 1&0&0\end{pmatrix}\begin{pmatrix}z_{1}\\ z_{2}\\ z_{3}\end{pmatrix} = \begin{pmatrix}0\\ 0\\ 1\end{pmatrix} .\]  
_The unique solution is \([z_{1},z_{2},z_{3}]\) = [1 1 0]. The decoder decision is [1 1 0 1] and the output is [1 1 0]. At the next step the decoder will recover block [0 0 1 0] and the output bits are [0 0 1]._  
Notice that, in general, we have to perform Gaussian elimination to solve the system of linear equations. However, in our example it was not necessary. The variable \(z_{1}\) is the only variable of the third equation and we found immediately that \(z_{1}=1\). Similarly, from the second equation, we have \(z_{3}=0\). Excluding known variable from the first equation, we obtain \(z_{2}=0\). This algorithm coincides with BP decoding used for decoding LDPC codes over the BEC. The formal description of the decoding procedure is given below as Algorithm 1. When applying Algorithm 1 to a sliding window, we obtain SWBP decoding. Next, we modify the SWBP algorithm in order to increase its erasure-correcting capability while keeping its low complexity. ```
while there exist parity checks with only one erased symbol do  Assign to the erased symbol the modulo-2 sum of all nonerased symbols participating in the same parity check. endwhile
```  
**Algorithm 1** BP-BEC. Since the free distance of the convolutional code is \(d_{\text{free}}=3\), not every combination of three erasures can be corrected by ML decoding. Thus, not every combination of three erasures can be corrected by the SW or SWBP decoding procedures. When the decoding delay \(L\) grows, the performance of SW decoder tends to the performance of the ML decoder. It means that any erasure pattern which is not a codeword and does not cover any codeword can be corrected by the SW decoder. This is not true for SWBP decoding even if \(L\) tends to infinity. An erasure pattern cannot be corrected if it is a stopping set or it covers a stopping set [27]. The stopping set is defined as a subset of indices of columns in its parity-check matrix, such that a matrix constructed from these columns does not have a row of weight one. The size of the smallest stopping set is called stopping distance \(d_{\text{stop}}\). In general, \(d_{\text{stop}}\leq d_{\text{min}}\), for the Wyner-Ash convolutional code \(d_{\text{stop}}=d_{\text{free}}\).