姓名：徐铭伟 学号：21011210001 学院：通信工程学院
【嵌牛导读】使用Verilog实现硬件顺序表
【嵌牛鼻子】硬件顺序表的Verilog实现
【嵌牛提问】如何使用Verilog实现硬件顺序表
【嵌牛正文】
引言
数据结构不仅仅是一门软件基础课，同时也是一门硬件基础课，可以说是数字设计的入门课。数据结构里详细介绍了链表、队列、堆栈、哈希等基本底层操作，这些底层操作在一些高级语言中都被封装好了，但是在做硬件设计时都是需要考虑的，如内存分配和存储问题，在硬件设计中是没有编译器来帮我们完成的，都需要一步一步设计来完成。
这里将分几期来演示使用Verilog实现常用数据结构的操作，本文实现Verilog实现顺序线性表的插入操作。
一、顺序线性表
顺序表的定义是用一段地址连续的存储单元一次存储线性表的数据元素，而C语言中的数组本质上也是存储器中的一片地址连续的空间，所以顺序表在C中常用一个一维数组实现（这里指非变长数组）。
描述顺序表需要三个属性：存储空间的首地址、线性表实时长度和存储空间最大容量。
顺序表的 i 位置插入数据的步骤：
1. 从最后一个数据向前遍历到第 i 个位置，将它们一个一个向后移动 1 位。
2. 将要插入的数据插进 i 处。
3. 表长自增 1 。
二、顺序线性表插入操作模块设计
Verilog代码如下：
`timescale 1ns/1ns
module seqlist(
input clk,
input rst_n,
// 顺序表插入操作
input [9:0] wr_addr, // 插入地址
input [7:0] wr_data, // 插入数据
input wr_valid, // 数据有效信号
output reg wr_done, // 插入完成信号
// 顺序表读取操作
input [9:0] rd_addr, // 读地址
input rd_valid, // 读使能
output reg [7:0] rd_data, // 读数据
output [9:0] list_length // 线性表长度
);
// parameter define
localparam IDLE = 2'b01;
localparam SHIFT = 2'b10;
reg [7:0] dram [1023:0]; // 内存空间
reg [9:0] cnt; // 移位计数器
reg [9:0] length; // 线性表长度
reg [1:0] state; // 状态寄存器
assign list_length = length;
// 内存读取
always @(*) begin
if( rd_valid == 1'b1 )
rd_data <= dram[rd_addr];
else
rd_data <= rd_data;
end
// 顺序表插入操作
integer i;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
wr_done <= 1'b0;
cnt <= 10'd256 - 1'b1;
length <= 10'd256; // 线性表初始长度为256
state <= IDLE;
// 内存空间初始化
for( i=0; i<1024; i=i+1 )
dram[i] <= i[7:0];
end
else begin
case( state )
IDLE : begin
wr_done <= 1'b0;
cnt <= length - 1'b1;
if( wr_valid == 1'b1 )
state <= SHIFT;
else
state <= IDLE;
end
SHIFT : begin
if( cnt >= wr_addr ) begin
cnt <= cnt - 1'b1;
dram[cnt+1] <= dram[cnt];
end
else begin
length <= length + 1'b1;
dram[wr_addr] <= wr_data;
state <= IDLE;
wr_done <= 1'b1;
end
end
default : ;
endcase
end
end
endmodule
此模块定义了两个状态：空闲态(IDLE) 和 移位状态(SHIFT)。
1. 在空闲态中，等待插入操作启动信号 wr_valid 有效。此信号有效后进入移位状态。
2. 在移位状态中， 从最后一个数据向前遍历到第 wr_addr 个位置，将它们一个一个向后移动 1 位。wr_addr 就是要插入数据的地址。等待移位过程结束后将待插入数据插入地址 wr_addr 中，表长加一，并且拉高状态信号 wr_done 一个时钟周期，表示插入操作完成。
三、testbench设计
testbench代码如下：
`timescale 1ns/1ns
module seqlist_tb;
// input signal
reg clk;
reg rst_n;
reg [9:0] wr_addr;
reg [7:0] wr_data;
reg wr_valid;
reg [9:0] rd_addr;
reg rd_valid;
// output signal
wire wr_done;
wire [7:0] rd_data;
wire [9:0] list_length;
// reg define
reg [3:0] tb_state;
// 复位
initial begin
rst_n = 1;
#50 rst_n = 0;
#100 rst_n = 1;
end
// 生成时钟
initial begin
clk = 0;
forever #5 clk = ~clk;
end
// 信号初始化 打开dat文件
integer handle;
initial begin
wr_addr = 10'd0;
wr_data = 8'd0;
wr_valid = 0;
rd_addr = 10'd0;
rd_valid = 0;
tb_state = 4'b0001;
// 打开dat文件
handle = $fopen("C:/Users/xumingwei/Desktop/seqlist/sim/data_out.dat");
$fdisplay(handle,"数据 地址 表长\n");
end
// 激励文件状态机
always @(posedge clk or negedge rst_n) begin
if( !rst_n ) begin
wr_addr <= 10'd0;
wr_data <= 8'd0;
wr_valid <= 0;
rd_addr <= 10'd0;
rd_valid <= 0;
tb_state <= 4'b0001;
end
else begin
wr_valid <= 1'b0;
rd_valid <= 1'b0;
case( tb_state )
// 向顺序表中插入数据
4'b0001 : begin
wr_addr <= 10'd5;
wr_data <= 8'd123;
wr_valid <= 1'b1;
tb_state <= 4'b0010;
end
// 等待数据插入完毕
4'b0010 : begin
if( wr_done == 1'b1 ) begin
tb_state <= 4'b0100;
rd_valid <= 1; // 读出地址0的数据
end
else
tb_state <= 4'b0010;
end
// 读出并打印内存空间的数据
4'b0100 : begin
if( rd_addr < 10'd1023 ) begin
rd_addr <= rd_addr + 1'b1;
rd_valid <= 1;
// 将内存空间中的数据写入dat文件中
$fdisplay(handle,"%d %d %d",rd_data,rd_addr,list_length);
end
else if( rd_addr == 10'd1023 ) begin
tb_state <= 4'b1000;
rd_addr <= 10'd0;
$fdisplay(handle,"%d %d %d",rd_data,rd_addr,list_length);
end
end
4'b1000 : ; // 仿真停止
default : ;
endcase
end
end
// top例化
seqlist tb_seqlist(
.clk ( clk ),
.rst_n ( rst_n ),
.wr_addr ( wr_addr ),
.wr_data ( wr_data ),
.wr_valid ( wr_valid ),
.wr_done ( wr_done ),
.rd_addr ( rd_addr ),
.rd_valid ( rd_valid ),
.rd_data ( rd_data ),
.list_length( list_length )
);
endmodule
在 testbench 中操作顺序表模块向表的地址 10'd5 中插入数据 8'd123 ，并将插入后的整个内存空间中的数据打印至文件 data_out.dat 中，便于直观地观察实验结果。
四、仿真结果
编写自动化仿真脚本，在Modelsim中启动仿真，可见写入后的 data_out.dat 文件如下图所示。在地址 5 的位置成功插入了数据 123 ，且表长自增为257(初始表长设为256)
在仿真波形中也可以看到，当 rd_valid (读存储器使能)拉高后，顺序读出存储空间中的新数据，可见在地址 5 处插入了数据 123 。
顺序表的插入和删除需要移动大量数据，此时时间复杂度是O(n)。即使在硬件中可以并行移动所有数据，但也会消耗大量硬件资源，尤其当存储空间很大时。
由此看来，无论硬件软件，顺序表的缺点都是一样的，不适合进行插入和删除操作，会浪费大量时间或硬件面积。
