# High-Throughput Bit-Pattern Matching under Heavy Interference on FPGA
## 4 Pattern-Matching Circuit and Implementation  
By using the cascaded pattern identifier, we performed pattern matching of an input to a set of memory entries. The number of units of the cascaded pattern identifier is the same as the number of memory entries. The input is fed to all of the units, while each memory entry is fed to its respective unit. If we have enough stages, we can minimize the set of output bits of the cascaded identifier to 1 bit for the final level. If the number of units is \(k\), they produce \(k\) bits, each bit indicating whether the input pattern was matched correctly. When a pattern is found, these \(k\) bits contain one \"1\" and \(k-1\) \"0\"s. The place of the 1 is the matched entry in the memory. Different approaches can be adopted to detect the 1. In the current case, a comparator tree was used (Section 2.2). The tree's hardware consumption was extremely small and had no detrimental effect on the operating frequency. The general form of their entire pattern identifier can be seen in Figure 5. The rule set consists of 64 entries. Figure 4: The 3-stage cascaded pattern identifier. The circuit uses the address produced by the comparator tree to output the matched memory entry. The total latency of the circuit is the latency of the cascaded pattern identifier and the latency of the comparator tree at the end, which is 15 + 8 = 23 cycles. In terms of the memory, this was implemented as a very long linear shift register (bits 0 to 1199 are entry 0, bits 1200 to 2399 are entry 1, bits 2400 to 3599 are entry 2, etc., all the way to entry 63), which runs on the same clock as the cascaded identifiers, i.e., 667 MHz) and has a 1-bit input on the first position. If entry \(y\) needs to be outputted, the corresponding bits are in positions \(y\) * 1200 to \((y+1)\) * 1200 \(-\) 1. To update the entire memory, 1200 \(\times\) 64 = 76,800 clock cycles (10\({}^{-4}\) s) are needed (1 bit per clock cycle). To update parts of the memory, a proportional number of clock cycles are needed; however, updates need to be performed in order. Each group of positions (0 to 1199 for entry 0, etc.) is connected as the second input to each one of the 64 3-stage cascaded identifiers (the first input being the 1200-input pattern). The circuit does not support dynamic memory updating. Updating of the memory must be completed before the circuit recommences normal operation. This makes the design reported in [2] better in this area since it supports dynamic updating. As mentioned, we opted for an input pattern that was 1200 bits long, with three stages of cascaded identifiers (bits per symbol were 10, 10, and 12, respectively) and a rule set of 64 rules. The biggest adder used is 4 bits, which can be seen in the operating frequency of the system. The weight of the comparators (value above which the symbol is detected as matched) was set to 6, 6, and 8, respectively, for every level (bits per symbol = 4). This was used to enable the circuit to detect patterns, under the interference of BER = 10\({}^{-1}\). As mentioned, the circuit received the input pattern as an input (along with standard reset and enable signals) and outputs the pattern that matches the closest to an entry in its memory. For its implementation, 205,082 LUTs and 355,013 FFs were used. For only one unit, 3051 LUTs and 5531 FFs (approximately 1/64 th) are necessary. The FPGA evaluation board that was used was the ZCU106 Ultrascale+. Since the biggest adder used was 4 bits, an operating frequency of 667 MHz was achieved, providing a total terminal throughput (with no memory updating) of 1200 \(\times\) 667 = 800.4 Gbps. Compared to other pattern-matching circuits, hardware consumption is on the same magnitude but is slightly higher. In a previous study [7], the pattern-matching circuit of the same size of input \(\times\) entries consumed 29,056 slices on Virtex 6. This translates to 116,224 LUTs and 232,448 FFs [9], which is about half of that for the proposed design in LUTs and two-thirds of that in FFs.