# High-Throughput Bit-Pattern Matching under Heavy Interference on FPGA
## 1 Introduction  
Bit-vector pattern matching is an important function of modern hardware systems and has a strong presence in many fields. Notable examples include packet header classification [1], string matching (in the field of network intrusion systems) [2; 3; 4], and many others, including biology, image processing, and text search [5]. In essence, bit-vector pattern matching concerns the identification of an input pattern of a specific size to a known pattern that resides in the memory of the system performing the operation [6]. Since the size of the patterns is typically greater than 1000 bits, the main method used by state-of-the-art solutions is to break down the input pattern into smaller sub-patterns and then use small and efficient processing elements to perform pattern matching at maximum throughput [6]. In this paper, we will present a different approach to pattern matching that focuses on matching under heavy interference. Contemporary methods are very efficient in pattern matching; however, there is a critical disadvantage connected to their use, in that they cannot perform pattern matching when the pattern is significantly altered. While there are many solutions for pattern matching that are very proficient [6; 7] and employ advanced methods to maximize operating frequency and the optimal use of memory blocks, there is little to no provision for performing pattern matching at the same data rates (gigabits) under interference. Since digital data can be manipulated easily and can take any form, being able to distinguish between very large patterns that have undergone significant alternation can prove to be very important in fields such as image recognition [8]. The circuit presented in this article aims to solve this problem by changing the philosophy behind the process of pattern matching. Instead of breaking down the pattern into smaller sub-patterns, the entire pattern is directly compared with as many memory elements as possible in every clock cycle. To achieve this end with few resources, the comparison procedure was augmented with pipelined adder trees. The intention behind this choice is to sever the connection between the size of the pattern and the operating frequency. In other words, the circuit is able to handle large patterns without suffering losses in operating frequency and throughput. The architecture used is minimalistic and can be implemented very easily on all types of hardware platforms. The circuit can handle bit-error rates (BER) of up to \(10^{-1}\) with high accuracy, as a result of its nature. Detection via adder trees and the comparators of large bit patterns is resistant to bit errors, regardless of the error pattern. This article is, first and foremost, an introductory presentation of the novel treatment of pattern matching that is described above. It is not meant to be a conclusive survey of every single possible configuration of the architecture of the proposed circuit but is, rather, a proof of concept. It presents evidence that there is, in fact, merit in pursuing this type of approach to pattern matching since it displays multiple advantages that are not present in other schemes. The circuit itself is a kernel implementation. Certain aspects of it (e.g., memory) were implemented without particular attention being paid to their efficiency, as a means to an end, and other aspects (I/O circuitry) are left to the user. Since these functions are already widely researched, future plans include the integration of optimized memory and an I/O circuitry module, as well as a thorough survey of all the parameters connected to the design. This article consists of 6 sections. The second section houses the presentation of a set of fundamentals regarding the function of pattern matching itself, as well as the philosophy behind using adder trees instead of only comparators. This will become the basis of our approach. The third section presents the fundamental pattern-matching circuit upon which the general design is based.