隊列
隊列即FIFO衫樊，一言以蔽之就是先進先出咬扇。比如入隊列的順序是1,2,3,4喉童，那么出隊列的順序也是1,2,3,4
隊列的實現(xiàn)
軟件——GO語言實現(xiàn)
除了使用鏈表和數(shù)組實現(xiàn)鏈表以外甜刻，GO語言內(nèi)置一種新的數(shù)據(jù)結(jié)構(gòu)叫切片，可以實現(xiàn)類似于動態(tài)語言中的list的一些功能（切片和append）礁芦，用這個數(shù)據(jù)結(jié)構(gòu)實現(xiàn)隊列非常容易
結(jié)構(gòu)體
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語言自帶的切片處理方法宴偿，第一個參數(shù)是要操作的切片湘捎，隨后的參數(shù)都是要插入到切片之后的變量，返回值是完成插入后新的切片
func (f *fifo) Push(din int) {
f.data = append(f.data, din)
f.length++
}
構(gòu)造函數(shù)
func New_fifo() *fifo {
return &fifo{[]int{}, 0}
}
硬件——Verilog實現(xiàn)
fifo由于其不改變數(shù)據(jù)順序常用于實現(xiàn)buffer窄刘，常用雙口ram+控制邏輯的方法實現(xiàn)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
);
線網(wǎng)定義
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為寫執(zhí)行條件：
- 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當讀寫同時進行時窥妇，滿信號狀態(tài)不會改變 -
almost_full && fifo_write_req當寫請求有效且只剩一個空位時，滿信號置位 -
fifo_read_req只要讀過一次娩践，不可能滿
寫地址與數(shù)據(jù)生成
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
