# High-Throughput Bit-Pattern Matching under Heavy Interference on FPGA
## 3 Core Circuit Description
### Cascaded Pattern Identifier  
The cascaded pattern identifier is a circuit with multiple stages. Each stage comprises a lesser pattern identifier (see Section 3.1) where the comparator outputs are fed to the identifier of the next stage. Figure 3 presents the circuit of a cascaded pattern identifier. The number of input bits is kept low in the example, in order to plot the entire circuit clearly. This version has 2 stages. The first stage (stage 1) comprises 30 bits, organized as 5 bits per symbol for 6 symbols. In the second stage, the inputs drop from 30 to 6. They are organized in 2 symbols of 3 bits each. The last 2 bits indicate if the entire pattern of 30 bits was detected. We can see that the weights of the comparators are now higher than or equal to 4 for the first stage and higher than or equal to 2 for the second stage. This means that there is a margin for error. Additionally, the pattern that needs to be detected only appears in the symbols of the first stage. For stage 2, all symbols are replaced with combination 111 since subsequent stages are used to determine how well the first stage detected the pattern. As we can see, only a part of the pattern was detected based on the weights used by the comparators and there is no match. The latency of the circuit is represented by \(\mathrm{ceil(log_{2}5)+1+ceil(log_{2}3)+1=7}\) clock cycles. The term 1 + 1 represents the clock cycles needed by the comparators. To conserve hardware, comparators can be implemented as combinatorial circuits so they do not consume clock cycles. The log terms are a product of the adders. In general, for a circuit of \(t\) stages, the clock cycles needed by the circuit are \(Cycles=t+\left[\sum_{i=1}^{t}\mathrm{ceil(log_{2}\,b_{i})}\right]\), where \(b_{i}\) represents the bits per symbol for each stage.  
By constructing the pattern identifier in this way, we have achieved two important things. Firstly, for large patterns, adders do not need to scale indefinitely. We can use more stages and steadily decrease the number of bits to keep the bits per symbol low. This means that the size of the pattern, in bits, has no effect on the critical path (and as a result of the operating frequency and throughput). Secondly, by manipulating the weights of the comparators, we can adjust the detecting ability of the circuit (it resembles a neural network, where comparators are neurons). As an example, we offer the implemented version of the circuit with 1200 input bits and 3 stages. The general form can be seen in Figure 4. This method can be scaled to any pattern length and any combination of adder-size, and the levels can be constructed and tested to maximize the detection capability.  
Figure 2: The lesser pattern identifier.  
In the first stage (lesser identifier 1) the 1200 bits are broken down to 120 symbols of 10 bits. Following the logic of Figure 2, we use 120 adder trees, divided into 10 bits each. The results of these trees are fed to 120 comparators, which have a predetermined weight. The results of the comparators are now fed to the next lesser pattern identifier (2). This identifier has an input of 120 bits, which is broken down into 12 symbols of 10 bits. The same process is applied, then the outputs of the second identifier (14 bits) are fed to the last identifier (3), where they are broken down into 1 symbol of 12 bits. The output of the last identifier is 1 bit. This bit vector is used to determine the detection of a pattern. If the bit output is 1, the pattern was detected. As mentioned, the key pattern of the first lesser identifier is the pattern being searched. For the second and third stages, the key pattern is the all-1 vector. This is because the second- and third-stage identifiers act as confirmation that the pattern in the previous stage was indeed detected. The clock cycles for 1200 bits are \(Cycles=3+2\times\mathrm{ceil}(\log_{2}10)+\mathrm{ceil}(\log_{2}12)=15\). The largest adder used is of 4 bits.  
Figure 3: The 2-stage cascaded pattern identifier.