# Finding Patterns in Signals Using Lossy Text Compression
## 6 Reverse Engineering Experiments
### De-Noising Level III  
In Level III, we are given the semantic package of \"\(0\)\" and \"\(1\)\" and need to split it into semantic words as in (1).  
**In the first experiment** we repeated the experiment from the previous section, where in the package \(P\) we used different values of _throttle_. That is, the \"throttle\" stick on the RC was pushed to random levels, from 1% to 100%, which ideally produces a repetitions of the semantic package \(L=S(\operatorname{package}(throttle,50,50,0))\) where the value of _throttle_ is then a random integer in \([0..127]\). The checksum field in \(L\) was also changed in each package. Let \(M=L_{1}L_{2},\cdots\) denote the concatenation of these semantic packages.  
Our goal was to identify the bits in \(M\) that correspond to the throttle field. To that end, we ran Algorithm 2 with the Parikh matrix for the string \(M\) with an additional row matrix that corresponded to a wildcard letter: \"\(2\)\". Each entry in this row will have a (cost) value of \(1/2\). The reason is that this wildcard will be used only on the variable \"throttle\" bits. The other bits are expected to be almost periodic and the cost of using wildcard on them will be too expensive.  
Ideally, the algorithm will output the input string \(M\) where the \"throttle\" bits are replaced by wildcards. We repeat this experiment where \"throttle\" was replaced by \"role\" and \"pitch\".  
**The results** are shown in Table 1. The first 4 lines of Table 1 correspond to 4 semantic packages \(M=L_{1}L_{2}L_{3}L_{4}\) while the throttle is changed and the pitch/roll sticks remain unchanged. The fourth column of the \(i\)th row shows \(L_{i}\) for \(i\in[1.4]\). The \"throttle\" bits were marked manually (by us) in bold. The first row in the fifth column contains the output of Algorithm 2 on \(M\), where the throttle field, as well as the checksum, were indeed identified by wildcards.  
To recover the complete protocol of IR-UFO, we scanned the two sticks over 20 positions, where each position was recorded for roughly a second. Our system plotted the desired Level III words as defined in (1) after a couple of hours. We expect that using core-sets the running time will reduce to minutes; see Section 4.  
**In the second experiment** the goal was to see how Algorithm 2 is robust to noise that may occur in previous levels. To this end, we added synthetic noise to the input (column 4 from the left in Table 1) for the string \(M\) with the variable \"throttle\" field above. For each \(x\in[1..250]\) we changed \(x\) bits in \(M\) to obtain \(M_{x}\) and run Algorithm 2 with \(M_{x}\) as described in the previous experiment. We then define \(y(x)\) to be the wrong letters in the output, compared to the desired string (rightmost column of first row in Table 1) over 100 experiments. Figure 3 describes the average error \(y\) in the output (\(y\)-axis) and its variance, for the values of \(x\) (in the \(x\)-axis).  
**Conclusions:** Figure 3 shows that roughly 90% of the noisy bits in the input were recovered. When the input string is completely noisy, the output string consists of only wild cards, which is correct for few bits but wrong for the other (approximately 20) bits.