队列

队列即FIFO，一言以蔽之就是先进先出。比如入队列的顺序是1,2,3,4，那么出队列的顺序也是1,2,3,4

队列的实现

软件——GO语言实现

除了使用链表和数组实现链表以外，GO语言内置一种新的数据结构叫切片，可以实现类似于动态语言中的list的一些功能（切片和append），用这个数据结构实现队列非常容易

结构体

type fifo struct {
    data   []int
    length int
}

出队列方法

f.data[1:]就是类似于python中的切片操作，表示切掉第一个值，剩下的保留

func (f *fifo) Pop() (int, error) {
    if len(f.data) == 0 {
        return 0, errors.New("empty fifo")
    } else {
        temp := f.data[0]
        f.data = f.data[1:]
        f.length--
        return temp, nil
    }
}

入队列方法

append方法是go语言自带的切片处理方法，第一个参数是要操作的切片，随后的参数都是要插入到切片之后的变量，返回值是完成插入后新的切片

func (f *fifo) Push(din int) {
    f.data = append(f.data, din)
    f.length++
}

构造函数

func New_fifo() *fifo {
    return &fifo{[]int{}, 0}
}

硬件——Verilog实现

fifo由于其不改变数据顺序常用于实现buffer，常用双口ram+控制逻辑的方法实现fifo

端口定义

module fifo_control #(
    parameter WIDTH = 8,
    parameter DEPTH_LOG = 8
)(
    input clk,    // Clock
    input rst_n,  // Asynchronous reset active low

    input fifo_write_req,
    input [WIDTH - 1:0]fifo_write_data,
    output reg fifo_full,

    input fifo_read_req,
    output reg fifo_empty,

    output reg ram_write_req,
    output reg [DEPTH_LOG - 1:0]ram_write_addr,
    output reg [WIDTH - 1:0]ram_write_data,

    output reg [DEPTH_LOG - 1:0]ram_read_addr
);

线网定义

reg [DEPTH_LOG - 1:0]write_point,read_point;
wire almost_full = (write_point == read_point - 1'b1)?1'b1:1'b0;
wire almost_empty = (write_point == read_point + 1'b1)?1'b1:1'b0;

写指针控制

always @(posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        write_point <= 'b0;
        ram_write_req <= 'b0;
    end else if((!fifo_full || fifo_read_req) && fifo_write_req) begin
        write_point <= write_point + 1'b1;
        ram_write_req <= 1'b1;
    end else begin
        ram_write_req <= 'b0;
    end
end

(!fifo_full || fifo_read_req) && fifo_write_req为写执行条件：

fifo不满且写请求
读写同时又请求（不可能溢出）

fifo满信号生成

always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        fifo_full <= 'b0;
    end else if(fifo_read_req && fifo_write_req) begin
        fifo_full <= fifo_full;
    end else if(fifo_read_req) begin
        fifo_full <= 'b0;
    end else if(almost_full && fifo_write_req) begin
        fifo_full <= 'b1;
    end
end

fifo_read_req && fifo_write_req当读写同时进行时，满信号状态不会改变
almost_full && fifo_write_req当写请求有效且只剩一个空位时，满信号置位
fifo_read_req只要读过一次，不可能满

写地址与数据生成

always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        ram_write_data <= 'b0;
        ram_write_addr <= 'b0;
    end else begin
        ram_write_data <= fifo_write_data;
        ram_write_addr <= write_point;
    end
end

读指针/地址控制

always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        read_point <= 'b0;
        ram_read_addr <= 'b0;
    end else if(!fifo_empty && fifo_read_req) begin
        read_point <= read_point + 1'b1;
        ram_read_addr <= read_point;
    end
end

!fifo_empty && fifo_read_req当fifo非空时，读fifo

fifo空信号生成

always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        fifo_empty <= 1'b1;
    end else if(fifo_read_req && fifo_write_req) begin
        fifo_empty <= fifo_empty;
    end else if(fifo_write_req) begin
        fifo_empty <= 1'b0;
    end else if(almost_empty && fifo_read_req) begin
        fifo_empty <= 1'b1;
    end
end