# High-Throughput Bit-Pattern Matching under Heavy Interference on FPGA
## 5 Pattern Matching under Interference and Simulations  
### Error-Free and Error-Present Input Generation  
To test the ability of the system to match patterns under heavy interference, simulations for both error-free and error-present inputs were performed. Since the focus of the design is its ability to detect severely altered patterns with very high throughput, all possible sources of misdetection had to be examined. This includes misfires, in other words, if the design detects a pattern when one is not present. For this reason, to create the input, 100,000 patterns were generated by choosing entries from the memory randomly. For example, the sequence could be {entry 0, entry 8, entry 10, entry 44, entry 21, entry 53, etc.}. Another 100,000 patterns were randomly generated 1200-bit patterns (with a 50% chance of 0 and a 50% chance of 1 for each bit) to make absolutely sure that the design did not detect random patterns as part of the 64 memory entries. For the error-free stream, the memory entries could be anything, but for the error-present stream, additional considerations had to be considered. Firstly, the Hamming distance of each memory entry needed to be sufficiently high for the error rate chosen from all other entries, to ensure that they would not be misidentified. Secondly, the error model had to be robust and flexible, in order to simulate realistic error patterns with a high rate of accuracy (BER = 10\({}^{-1}\)). To ensure sufficient Hamming distance, the 64 entries were constructed with a Hamming distance of 400 bits between each other, using the following method. Assuming that an entry of 1200 bits is made up of 100 sub-patterns of 12 bits of \(v_{i}\), it presents the form \(v_{1}v_{2}v_{3}v_{4}\ldots v_{100}\). By performing an exhaustive search on all 12-bit binary numbers it was determined that the biggest set in which all binary numbers have a Hamming distance \begin{table}
\begin{tabular}{c c c} \hline \hline
**Source** & **Hardware** & **Terminal Throughput** \\ \hline
[7] & 116,224 LUTs/232,448 FFs & 256 Gbps \\
[6] & N/A & 358.4 Gbps 1 \\
[2; 3; 4] & Various (not specialized) & <30 Gbps \\ Proposed & 205,082 LUTs/355, 013 FFs & 800.4 Gbps \\ \hline \hline \end{tabular} 1  
\end{table} 
Table 3: A comparison of terminal throughput (with no memory updating) between the different works. of 4 between each other was 128. The memory entries were constructed with this pool of 128 12-bit vectors. Firstly, we aligned the entries vertically. \[\text{entry 1}:\ v_{1}^{1}v_{2}^{1}v_{3}^{1}\ldots v_{100}^{1}\]  
\[\text{entry 2}:\ v_{1}^{2}v_{2}^{2}v_{3}^{2}\ldots v_{100}^{2}\]  
\[\text{entry 64}:\ v_{1}^{64}v_{2}^{64}v_{3}^{64}\ldots v_{100}^{64}\]  
Then, for each column, we shuffled the pool of 128 12-bit vectors and picked 64 at random (no duplicates). These 64 vectors constitute the column \(v_{i}^{j},j\in[1,64]\). All of the vectors have a Hamming distance of 4 between them and, since there are 100 columns, all entries have a distance of 400 between them. The error model used to simulate the channel is the Gilbert-Eliot two-state Markov chain model [10] which has been shown to be a good approximation of wireless communication channels [11]. Figure 6 presents the model. The state of EF (error-free) is the state of the channel where no errors occur in transmission, and the state of EP (error-present) is the state where errors occur with a probability of \(h\). Transition probabilities between the two states are \(P\) and \(r\). Both \(P\) and \(r\) are small while \(1-P\) and \(1-r\) are large. The total percentage of errors is \(h\times\frac{P}{P+r}=P_{E}\). As mentioned, the Hamming distance from one entry to all other entries in the set had to be sufficiently high in order to ensure that the possibility of mistaking one entry for another is inconsequentially low. This model was used to apply a BER of \(10^{-1}\) to the generated input. To summarize the input creation process, first, 64 memory entries with a 400-bit Hamming distance were created.