# Finding Patterns in Signals Using Lossy Text Compression
## 6 Reverse Engineering Experiments  
We ran experimental results on both synthetic and real data to test Algorithm 2.  
We first ran the following experiment on synthetic data to measure the robustness of the recovery of Algorithm 2; i.e., to get some sense of the signal-to-noise (SNR) ratio. Intuitively, we assume that user [PERSON] sends a periodic string over a known alphabet \(\Sigma[1..4]\) to another user [PERSON], through a noisy channel. [PERSON] then tries to recover the original string from the received noisy string over the alphabet of real numbers \(\Sigma^{\prime}=R\).  
**The input data** was a set \(\mathcal{M}\) of \(48=16\cdot 3\) strings \(\left\{M_{i,k}\ |\ i\in[1..16],k\in[1..3]\right\}\) in \(\Sigma\). Each string \(M\) in this set was constructed as the sum \"\(M=M^{*}+N\)\" of a fixed matrix \(M^{*}\) with additional random noise \(N\) that were defined as follows. Let \(V=S(4^{\prime},12^{\prime},4^{\prime},3^{\prime},3^{\prime},4^{\prime})=121212 123333444\), and let \(M^{*}=V^{3}\) be a string from the alphabet \(\Sigma\). For \(\sigma>0\), let \(N_{\sigma}\) denote a string in \(\Sigma^{\prime}\) of length \(|N|=|M^{*}|\), where \(N[j]\sim\mathcal{N}(0,\sigma^{2})\) is a random variable from a Gaussian distribution with zero mean and variance \(\sigma^{2}\) for every \(j\in[1..|N|]\). To obtain a finite alphabet and Parikh Matrix, we scale and round each letter \(N[j]\) to its nearest integer. We then define \(\sigma_{i}=0.05i\) and \(M_{i}=M^{*}+N_{\sigma_{i}}\); i.e., \(M_{i}[j]=M^{*}[j]+N_{0.05i}[j]\)  
Figure 2: The recording part of our system: Moving a stick of the RC generates an IR (Infra-Red) signal. This signal is received by an IR sensor, which in turn transmits it to the logic analyzer (by Selae LTD). The logic analyzer translates this analog voltage signal into a binary signal. Its frequency is 5 Mhz. The binary signal is then transmitted to the USB port of the laptop and recorded to the hard drive using our software. In the above setting, the micro-processor Arduino is used only as a power supply for the sensor. In a different setup, the expensive logic analyzer was replaced by the Arduino. In this case the thresholds were computed by a software on the laptop.  
for every \(i\in[0..16]\) and \(j\in[1..|N|]\). We repeat this construction of \(M_{i}\) three times to obtain the string \(M_{i,1},M_{i,2},M_{i,3}\), with different random noise \(N_{\sigma_{i}}\) from the same distribution. The result is then the input set \(\mathcal{M}\) of matrices above in the real alphabet \(\Sigma^{\prime}\).  
**The experiment** is a list of \(255=17\times 3\times 5\) calls \(O_{i,j,k}=\textsc{Lossy}(M_{i,k},j)\) to Algorithm 2 with the string \(M_{i,k}\) and \(j\), over every variance level \(i\in[1..17]\), repetition (try) \(k\in[1..3]\), and \(j\in[1..5]\). The cost error for this call is the weighted number of mismatched letters (i.e., dissimilarity or distance) between the output recovered string \(O_{i,j,k}\) and the original de-noised string \(M^{*}\),  
\[\text{error}(i,j,k)=\sum_{z=1}^{|M^{*}|}|M^{*}[z]-O_{i,j,k}[z]|.\]  
**The results** are shown in Figure 3. The \(x\)-axis represents the integer level \(i=\sigma_{i}/0.05\) of the noise variance as defined above. The color of each of the five curves corresponds to different RRLE levels \(j\in[1..5]\) that were used in Algorithm 2. The height \(y\) of the \(j\)th curve in the \(i\)th variance level is the mean error over the 3 errors \((\text{error}(i,j,1)+\text{error}(i,j,2)+\text{error}(i,j,3))/3\), together with its variance.  
**Conclusion.** Figure 3 shows that the algorithm is more robust to noise as the number of the levels in the tree increases.  
Figure 3: Results of Algorithm 2. (**a**) distance in the y-axis, over different number j of words (x-axis). (**b**) average error in the output (y-axis) and its variance, for the values in the x-axis. (**c**) The average Hamming distance compared to the original string.