FPGA图像处理_查找表的使用

查找表在计算机科学中，是指用简单的查询操作来替换运行时计算的数组或者associative array这样的数据结构。由于从内存中提取数值经常要比复杂的计算速度快很多，因此这样的到的速度提升是很显著的。在FPGA中，主要是以下两种情况会用到查找表：一种是逻辑的逻辑要求非常高，另一种是计算的复杂度非常高。

使用查找表的首要问题是输入表的构建，首先需要知道输入函数的有效定义域，然后对其进行等分，等分步长需要在计算精度和表的大小之间做一个最佳权衡，随着输入宽度的增加，表的尺寸呈指数倍增长。实用的查找表尺寸需要减小输入的精度，一个简单的方法是删除最低位来实现。没有必要对输入进行舍入，因为表的内容可以根据保留为作用域中的函数的适当值设置来获得最好结果。另外一个减小尺寸的方式是考虑对称性，例如对于对称的正余弦函数，其有效定义域为[0~2π]，在输入查找表之前首先进行象限判断，并保存其象限信息。同时，将其转换到第一象限，查表后根据象限信息恢复实际计算值，将查找表的输入范围缩小到原来的四分之一。

下面是利用查找表来实现正弦函数sinx的实例演示：
1、第一步:查找函数的生成，由于芯片厂商不同，因此需要的生成文件也不同，一般地，Altera的FPGA使用.mif格式，Xilinx的FPGA使用.coe格式，以MATLAB来分别生成.mif文件和.coe文件为例，建立起步长为0.1°，同时将输出值从[0,1]范围扩展到[0,16384]的定义域范围为[0~π/2]的正弦函数查找表，将输出值扩大2的14次方，即左移14位，其MATLAB代码如下：
.mif文件：

clc 
clear 
t = [0:0.1:90]; %输入范围0～90°,步长0.1°
[m,n] = size(t);
x = pi*t/180;
sin_val = sin(x); %取出正弦数组
fid = fopen('sine.mif','wt');
fprintf(fid,'width=14;n'); %转换后的数据位宽14位
fprintf(fid,'depth=1024;n'); %共900个点，深度最少需要1024
fprintf(fid,'address_radix=uns;n'); %地址是无符号类型
fprintf(fid,'data_radix=dec;n'); %数据是十进制类型
fprintf(fid,'content beginn'); 
for j = 1:n
    i = j - 1;
    k = round(sin_val(j)*16384);
    if(k == 16384)
        k = 16383;
    end
    fprintf(fid,'%d:%d;n',i,k);
end
fprintf(fid,'end;n');
fclose(fid);

.coe文件：

clc
clear
t = [0:0.1:90]; %输入范围0～90°,步长0.1°
[m,n] = size(t);
x = pi*t/180;
sin_val = sin(x); %取出正弦数组
fid = fopen('sine.coe','wt');
fprintf(fid,'MEMORY_INITIALIZATION_RADIX=16;n'); %表示ROM内容的数据格式是16进制
fprintf(fid,'MEMORY_INITIALIZATION_VECTOR=  n');
for j = 1:n-1
    i = j - 1;
    k = round(sin_val(j)*16384);
    if(k == 16384)
        k = 16383;
    end
    fprintf(fid,'%x,n',k); %每个数据后面必须要用逗号或者空格或者换行符隔开
end
a = 16383;
fprintf(fid,'%x;',a); %最后一个数据后面加分号
fclose(fid);

2、以Xilinx的FPGA为例，第二步是在FPGA端例化一个ROM来实现查找表的存放：




3、测试模块如下所示：

`timescale 1ns / 1ps

module sin_lut_tb;

reg clk;
reg rst_n;
reg [9:0] addr;
reg [11:0] addr_count;
reg [15:0] data_tmp;
wire [15:0] data;

parameter ADDR_MAX = 900;
parameter ADDR_MAX_ALL = 3600; 
parameter const_half_pi = ADDR_MAX; //90°地址
parameter const_pi = ADDR_MAX*2; //180°地址
parameter const_double_pi = ADDR_MAX*3; //270°地址

initial begin
    rst_n = 1'b0;
    clk = 1'b0;
    #100;
    rst_n = 1'b1;
end

always #5 clk = ~clk;

always @(posedge clk or negedge rst_n) begin
    if(!rst_n)
        addr_count  <= 12'd0;
    else if(addr_count == ADDR_MAX_ALL)
        addr_count  <= 12'd0;  
    else     
        addr_count  <= addr_count + 12'd1;
end

always @(posedge clk or negedge rst_n) begin
    if(!rst_n)
        addr    <= 10'd0;
    else if(addr_count>= 12'd0 && addr_count< const_half_pi) //第一象限
        addr    <= addr_count;
    else if(addr_count>= const_half_pi && addr_count< const_pi) //第二象限
        addr    <= const_pi - addr_count;
    else if(addr_count>= const_pi && addr_count< const_double_pi) //第三象限
        addr    <= addr_count - const_pi;
    else if(addr_count>= const_double_pi && addr_count< ADDR_MAX_ALL) //第四象限
        addr    <= ADDR_MAX_ALL - addr_count;   
end

always @(posedge clk or negedge rst_n) begin
    if(!rst_n)
        data_tmp    <= 16'd0;  
    else if(addr_count>= 12'd0 && addr_count< const_pi) //前两象限，输出大于0
        data_tmp    <= data;
    else if(addr_count>= const_pi && addr_count< ADDR_MAX_ALL) //后两象限，输出小于0
        data_tmp    <= -data;
end

sin_lut sin_lut_inst (
  .clka(clk),    // input wire clka
  .addra(addr),  // input wire [9 : 0] addra
  .douta(data)  // output wire [15 : 0] douta
);
endmodule

仿真结果如下图所示：

以上就是FPGA通过查找表实现正弦函数的全部内容。
参考文献：牟新钢 周晓 郑晓亮《基于FPGA的数字图像处理原理及应用》