Hardware Based Sequence Matching: Reviving an FSM Architecture

Mike Markowski, mike.ab3ap@gmail.com

Background

In 1988, after the Dean of Engineering signed the paperwork for my master's degree one pleasant May day, I was officially done! Though I had missed the deadline for spring graduation and had to wait till December, I started a new job developing a projectile tracking radar system, loved it, and never looked back … till retirement.

When I left University of Delaware back then I also left all my files related to my master's degree — .tex files, xfig figures, schematics, source code and results. It was a time when moving data was not as easy as now. Do I buy a 9-track tape, buy a stack of floppies? Then get help from the computer systems folks? I did neither - and honestly never considered either, I was free! - and at some point the valuable pattern of bits representing so much hard work evaporated.

Then retirement rolls round and I spotted my yellowing master's thesis on the shelf. With modern tools available, I used Google OCR to very quickly pull in the text. Then I scanned schematics at 200 dpi — I realize now I should have used higher because my original thesis looks sharper. I can fix it one of these days… With the help of AI, it created a LaTeX class file to mimic the UD 1988 thesis style. As of 2026, my MEE thesis is again digital after nearly, yikes, 4 decades and online for the first time ever!

• Mike Markowski's 1988 master's thesis in electrical engineering.

The Project Then

The timeline of the thesis predates my graduate years. My advisor, the late Prof. Peter Warter, presented the idea in 1979 to IEEE Computer Society, MICRO-DELCON in Newark, Delaware. A University of Delaware master's student, Donald W. Mules, earned his degree in 1983 by fleshing out the idea, and then Jeong-Gyun Shin and I earned our masters in 1988. Jeong designed a custom VLSI solution and Andrew Jacob, an EE senior, and I designed state machines and supporting digital circuitry, and I wrote a C language simulator to help us decide how much hardware a real system needs.

The idea was a hardware solution to fast searches, around 10 ns/char. The character stream simultaneously slides by character matchers that match either a character or character class and their outputs are fed to a string matcher where the real magic happens. Searches are made purely in hardware via an FSM (Finite State Machine) that can make matches while allowing certain errors in spelling; character insertion, deletion, substitution and transposition. The state machine revolves around a truth table, shown below in an example.

The Project Now

While the time has come and gone for such a file searcher, there are cases where an FPGA implementation of this work or something like it still outshine CPUs and GPUs, especially when error tolerance is needed and data cannot be pre-indexed.

DNA Sequencing & Bioinformatics

This is maybe the closest modern equivalent to the thesis. Instruments sequence strings of DNA nucleotides (A, C, T, G) as a massive, continuous stream. Specific gene sequences must be found, but biological data is full of mutations - the same insertions, deletions, transpositions, and substitutions that the EFC deals with.

Wire-Speed Packet Inspection for Network Security

High-speed network firewalls scan incoming packets for malware signatures at 100 Gbps or 400 Gbps speeds without buffering the data. They currently use tools to compile regular expressions directly into massive, pipelined FSM arrays like the EFC matchers and token followers.

Hardware-Accelerated Databases

Enterprise data warehouses use FPGAs to accelerate databases (e.g., AWS Redshift Aqua or specialized NVMe acceleration cards). The FPGA intercepts the data stream and filters the rows using hardcoded FSM arrays before the data even hits the CPU or main memory, saving bus bandwidth.

Rejuvenation

Let's get back to 1988. After returning the thesis to digital form, I could have stopped there. But I decided to go farther and see if my old code in Appendix A would compile and run. It does! I can't exactly reproduce some results, not because of the code but because the simulator assumes a particular prepared version of the Kucera-Francis word usage file exists. My thesis says the file is 12,224 words long and that it ignores words under 4 characters in length and ignores words used less than 10 times in a million. Preparing with those rules, though, I get a wordlist of around 8,000 words, 35% less. Plots are similar in shape and there are no differences that change results in the old thesis. The file format is described here. And here is my python program to prepare the data,

• kfdb.py

Here is the 1988 OCR'd code I revived, though the .h file had to be re-created based on usage in the .c files:

• Makefile
• efc_structs.h
• efc.c
• matcher.c

Running kfdb.py uses the kuceradat-0668.txt file downloaded from the link above to create three subsets named subset1.txt, subset2.txt and subset3.txt which are nothing more than every 10th word starting at the 1st, 4th and 7th, respectively. Finally, the simulator is run on each in turn. A snippet of output is shown,

$ efc subset1.txt
.
.
.
4 letter target string:

  0.01454131 mismatches.

  0.54677671 used 2 tokens.
  0.14491482 used 3 tokens.
  0.29606897 used 4 tokens.
  0.01051783 used 5 tokens.
  0.00171464 used 6 tokens.
  0.00000515 used 7 tokens.
  0.00000183 used 8 tokens.

  0.69956189 of matching tokens had 0 errors.
  0.05579220 of matching tokens had 1 errors.
  0.23420753 of matching tokens had 2 errors.
  0.01043844 of matching tokens had 3 errors.

 Average: 2.77550149 tokens per 4-letter word.
.
.
.

Evolution

There is an old joke of sorts that PhD grads spend their careers re-doing their dissertations. Now that I have my old master's code OCR'd and running, let's take a look and, yes, re-do it. Well, yikes, there are bugs. Probabilities are calculated from subset files rather than the entire Kucera-Francis database of about a million words. Worse, I simulated 16 token followers to see how many should be built in hardware. Perusing the code ... I never store results for 16 character words and should have. They are all correctly reported as zero because, well, I never recorded anything. Please don't take my degree away. :-D Wait, no one but me is reading this page so I'm safe! Still, it's never too late to do it right.

At the time, I was unaware of object oriented programming and this project begs for it. That prompted a python rewrite whose source you can find here in efc.py. It is much clearer conceptually, but also turns out to be very slow compared to C! (For the ease of sharing, the one file contains several classes.)

Python output was used to create the plots in Chapter 2. Here is an example of an original plot and its equivalent now. While the prepared data in 1988 contained 12,224 words, the file I have now is 7,947 words. I hope I can figure out the discrepancy, but the file I used in grad school was provided by my advisor and I know nothing about how it came to be. With a 35% reduction in data we must expect differences. Results below are plotted from data files generated by, for example,

efc.py -1988 subset1.txt
efc.py -1988 subset2.txt
efc.py -1988 subset3.txt

and then using a gnuplot file like mm.gnu, err1.gnu, etc. The -1988 flag ensures, for better or worse, that bugs in my 1988 thesis are reproduced. :-)

Left: original 1988 plot  ·  Right: 2026 reproduction

Left: original 1988 plot  ·  Right: 2026 reproduction

Left: original 1988 plot  ·  Right: 2026 reproduction

Left: original 1988 plot  ·  Right: 2026 reproduction

Example

The logic revolves around this truth table from Mules' 1983 thesis

The output columns are the actions under each state name in the FSM below. The transitions are the input columns from the truth table. Refer to the truth table legend to understand the bit functions. This FSM is expanded from 4 states by Mules to 7 here to accommodate various actions upon state transition.

For a concrete example, picture loading a target string RADIO into a string matcher. Pretend now that entering the EFC is a misspelled character stream RAIDO with a transposition error.

When the first character arrives, a token follower is activated and the FSM is entered at State 2. The actions proceed from here as follows. The string '==?' asks does the string matcher's indexed character matcher value on the left matche the incoming character on the right.

Tok 1:
    Fsm state 2:
        Actions:    00 0000 (no actions)
        Ptr: 0
        i:   R ==? R    1       CHAR MATCH!
        i+1: A ==? R    0
        i-2:            0
        Transition: 111 00 -> state 5

Tok 1:
    Fsm state 5:
        Actions:    00 1000 (ptr += 1)
        Ptr: 1
        i:   A ==? A    1       CHAR MATCH!
        i+1: D ==? A    0
        i-2:            0
        Transition: 111 00 -> state 5

Tok 1:
    Fsm state 5:
        Actions:    00 1000 (ptr += 1)
        D ==? I
        Ptr: 2
        i:   D ==? I    0
        i+1: I ==? I    1       DELETION/TRANSPOSITION
        i-2: R ==? I    0
        Transition: 010 00 -> state 3

Tok 1:
    Fsm state 3:
        Actions:    01 0110 (set ef, ptr += 2, err += 1)
        Ptr: 4
        Err: 1
        ef: 1
        i:   I ==? D    0       NO MATCH
        i+1: O ==? D    0
        i-2: A ==? D    0
        Transition: 000 01 -> state 2

Tok 1:
    Fsm state 2:
        Actions:    00 0000 (do nothing)
        Ptr: 4
        Err: 1
        ef: 0
        O ==? O     1           CHAR MATCH!
        O ==? A     0
        Transition: 111 00 -> state 5

Tok 1:
    Fsm state 5:
        Actions:    00 1000 (ptr += 1)
        Ptr: 5
    ==> Match (tok pointer moves beyond target) with 1 error!

Full Circle

Now that code written by 25 year old me is revived, I'm working on rebooting myself as 25 years old. It's proving difficult. :-)