# Pattern-Based Decoding for Wi-Fi Backscatter Communication of Passive Sensors
## 5 Pattern-Based Decoding Algorithm  
Based on the observations made in the previous section, we developed a pattern-based decoding algorithm. The pseudocode of the algorithm is given in Algorithm 1. ```
1:for all slot \(n\)do
2:\(\text{slope}[n]=\text{GetSlope}([\tau_{n}-T/2,\tau_{n}+T/2-1])\)
3:if\(\text{slope}[n]>0\)then
4:\(\text{bitPair}[n]=(0,1)\)
5:elseif\(\text{slope}[n]<0\)then
6:\(\text{bitPair}[n]=(1,0)\)
7:endif
8:\(\text{bit}[n]=\text{bitPair}[n][2]\)
9:if\(|\text{slope}[n]|\geq|\text{slope}[n-1]|\)then
10:\(\text{bit}[n-1]=\text{bitPair}[n][1]\)
11:endif
12:endfor
```  
**Algorithm 1** Pattern-based decoding algorithm. In order to decode the bit of slot \(n\), we designed the algorithm to identify the pattern of samples in \([\tau_{n}-T/2,\tau_{n}+T/2-1]\), i.e., \(T/2\) samples from slot \(n-1\) and the other \(T/2\) samples from slot \(n\), not in \([\tau_{n},\tau_{n}+T-1]\), due to the following reasons (\(\tau_{n}\) is the first sample of slot \(n\)):  
* When signal smoothing of Equation (2) is applied, the sample pattern in \([\tau_{n}-T/2,\tau_{n}+T/2-1]\) monotonically increases and decreases if the transmitted signal at \(\tau_{n}\) corresponds to rising and falling edges, respectively, according to Proposition 1, thus being identified as positive and negative slopes, respectively, according to Proposition 3. * It does not identify a single bit value, but the transition of two adjacent bits at once. This means that we decode the value of a bit twice, once with the previous bit and the second time with the next bit. Therefore, decoding becomes more robust against sudden unstable noisy samples. The algorithm calculates slope of samples \([\tau_{n}-T/2,\tau_{n}+T/2-1]\) (denoted by \(\text{slope}[n]\)) via linear curve fitting, which is derived from Equation (4) as (the details of the derivation are given in Appendix A):  
\[\text{slope}[n]=\frac{12}{T(T^{2}-1)}\sum_{i=\tau_{n}-T/2}^{\tau_{n}+T/2-1} \left(i-\tau_{n}+\frac{1}{2}\right)\bar{y}[i] \tag{5}\]  
If the slope is positive (inclining pattern), the algorithm assumes that the samples correspond to bit pair \((0,1)\); otherwise, to bit pair \((1,0)\). Since the first \(T/2\) samples of pattern detection are from the previous slot \(n-1\), the algorithm identifies the second value of the resulting bit pair (\(\text{bitPair}[n][2]\)) as the bit of slot \(n\) (\(\text{bit}[n]\)). Finally, the algorithm compares \(\text{slope}[n]\) obtained for slot \(n\) with that for the previous slot (\(\text{slope}[n-1]\)). If \(\text{slope}[n]\) is larger than the previous one, the algorithm assumes that the detected bit pair from \(\text{slope}[n]\) (\(\text{bitPair}[n]\)) is more confident and modifies the bit value of the previous slot (\(\text{bit}[n-1]\)) as the first value of this bit pair (\(\text{bitPair}[n][1]\)). In the algorithm, for both bit pairs (1, 1) and (0, 0), the slope is ideally obtained as zero. Then, the corresponding bit value is judged from the samples of the next slot because the samples of the next slot are either (1, 0) or (0, 1), having a nonzero slope (no consecutive bit pairs of either (1, 1) or (0, 0) appear in FM0 coding). In reality, for both bit pairs (1, 1) and (0, 0), the slope may be obtained as a nonzero value, but its absolute value is probably smaller than the one for the next slot. Therefore, from the comparison between the slopes for two consecutive slots, the algorithm is likely to pick the bit value judged from the samples for the next slot. Figure 5 illustrates the operation of the algorithm. The transmitted bits are the FM0-coded ones for the data of alternating one and zero. Suppose that bit[1] is decoded as data one, and slope[1] is positive. In order to decode bit[2], the algorithm calculates slope[2], which is obtained small but positive, and judges bit[2] as data one. The previous slope[1] is for bit pair (0, 1) and larger than slope[2]; thus, the algorithm keeps the decision of bit[1]. The algorithm obtains slope[3] as a negative since it is for bit pair (1, 0), and judges bit[3] as data zero.