# FAST-NFA-FPGA

**Repository Path**: liuhunck/fast-nfa-fpga

## Basic Information

- **Project Name**: FAST-NFA-FPGA
- **Description**: 用FPGA来加速判断一个输入是否可以被某个非确定有限状态自动机（NFA）识别
- **Primary Language**: Verilog
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2024-03-19
- **Last Updated**: 2025-04-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# FAST-NFA-FPGA

#### 介绍
用FPGA来加速判断一个输入是否可以被某个非确定有限状态自动机（NFA）识别

#### 软件架构
本项目在Qartus18.1 Standard Edition上开发，运行板为Cyclone IV E：EP4CE10F17C8

此版本为最终版

#### 使用简介

先运行`nfa2v.py`，将NFA转换成相应`Verilog`代码，会生成`top.v, node0.v, node1.v, ... ,nodex.v`

再运行`str2mif.py`，将想判断是否被NFA识别的字符串输入（注意不同字符之间要空格），会生成`input.mif`

最后，将`sm.v pc.v display.v`等文件和之前输出的文件一起经过Quartus编译，选好引脚，下板，按开始键即可

## nfa2v.py

用nfa2v.py可以将任意输入的NFA转换成Verilog语言，并能够被Quartus编译成功

![image-20240323194558424](README.assets/image-20240323194558424.png)

以上是使用方法，很简单，root就是输出文件的目录，不过这样输入是交互型的

`cat mynfa.in | python nfa2v.py --root ./NFA/`这样可以将NFA提前写入mynfa.in文件即可

## str2mif.py

这是一个将输入字符转换成mif文件的脚本，需要读取nfa2v.py生成的config.yaml

它将原本的字符集映射转换成ROM初始化数据，从而写入FPGA板中来判断接受与否

![image-20240324174218088](README.assets/image-20240324174218088.png)

`python str2mif.py -C ./NFA/config.yaml -O ./NFA/input.mif`

如果输入文件不存在会直接退出。

## display.v

为了更方便的观察输入是否被NFA接受，加入了8段数码管的输出功能

加入了写入驱动，通过配置管脚能够在数码管上显示

初始状态为`--------`，接受`7355608`，拒绝`114514`