前幾天參加樂鑫的筆試,遇到一道題目,很有價值,分享給大家。
題目要求是將一個串列執行的C語言演算法轉化為單拍完成的並行可綜合verilog。
C語言源碼如下:
unsigned char cal_table_high_first(unsigned char value) { unsigned char i ; unsigned char checksum = value ; for (i=8;i>0;--i) { if (check_sum & 0x80) { check_sum = (check_sum<<1) ^ 0x31; } else { check_sum = (check_sum << 1); } } return check_sum; }
演算法C語言實現:
#include <stdio.h> int main() { unsigned char cal_table_high_first(unsigned char value); unsigned char data; for (unsigned char i = 0; i < 16; ++i) { data = cal_table_high_first(i); printf("value =0x%0x:check_sum =0x%0x ", i, data); } getchar(); }
unsigned char cal_table_high_first(unsigned char value) { unsigned char i; unsigned char check_sum = value; for (i = 8; i > 0; --i) { if (check_sum & 0x80) { check_sum = (check_sum << 1) ^ 0x31; } else { check_sum = (check_sum << 1); } } return check_sum; }
輸出結果:
value =0x0:check_sum =0x0 value =0x1:check_sum =0x31 value =0x2:check_sum =0x62 value =0x3:check_sum =0x53 value =0x4:check_sum =0xc4 value =0x5:check_sum =0xf5 value =0x6:check_sum =0xa6 value =0x7:check_sum =0x97 value =0x8:check_sum =0xb9 value =0x9:check_sum =0x88 value =0xa:check_sum =0xdb value =0xb:check_sum =0xea value =0xc:check_sum =0x7d value =0xd:check_sum =0x4c value =0xe:check_sum =0x1f value =0xf:check_sum =0x2e
C語言作為參考模型,用於後續Verilog的功能模擬。
該演算法邏輯如下,輸入一個8bit的數,首先判斷最高位是否為1,如果為1則左移一位,並且和8『b00110001異或;如果最高位不為1則左移一位。此過程執行8次。
此時我們來看一下異或操作的真值表
我們可以看出:任何數與0異或都等於它本身,即0^x=x。所以我們可以把演算法流程變換為:
『h31 = 』b00110001, 』h00 = 』b00000000,設左移前最高位為M,可以將判斷左移前最高位是否為1的過程省略,直接與 『b00MM000M異或,此時流程圖可以簡化為:
由此,我們可以將循環解開。
根據上述結果,可以用verilog描述。
module loop1( input clk, input rst_n, input [7:0] check_sum, output reg [7:0] check_sum_o ); //reg [7:0] check_sum_o; always @ (posedge clk or negedge rst_n) if (!rst_n) begin check_sum_o <= 8h0; end else begin check_sum_o[7] <= check_sum[3]^check_sum[2]^check_sum[5]; check_sum_o[6] <= check_sum[2]^check_sum[1]^check_sum[4]^check_sum[7]; check_sum_o[5] <= check_sum[1]^check_sum[7]^check_sum[0]^check_sum[3]^check_sum[6]; check_sum_o[4] <= check_sum[7]^check_sum[0]^check_sum[3]^check_sum[6]; check_sum_o[3] <= check_sum[3]^check_sum[7]^check_sum[6]; check_sum_o[2] <= check_sum[2]^check_sum[6]^check_sum[5]; check_sum_o[1] <= check_sum[1]^check_sum[5]^check_sum[4]^check_sum[7]; check_sum_o[0] <= check_sum[0]^check_sum[4]^check_sum[3]^check_sum[6]; end
endmodule
testbench:
module loop1_tb; reg clk; reg rst_n; reg [7:0] check_sum; wire [7:0] check_sum_o; always #1 clk=~clk; initial begin clk = 0; rst_n = 0; #10 rst_n = 1; for (check_sum=0;check_sum<16;check_sum=check_sum+1) begin #2 //check_sum = i; $display ("check_sum = %h", check_sum_o); if (check_sum == 15) $stop; end //$stop; end loop1 loop1_i1( .clk(clk), .rst_n(rst_n), .check_sum(check_sum), .check_sum_o(check_sum_o) ); endmodule
列印結果為:
# check_sum = 00 # check_sum = 31 # check_sum = 62 # check_sum = 53 # check_sum = c4 # check_sum = f5 # check_sum = a6 # check_sum = 97 # check_sum = b9 # check_sum = 88 # check_sum = db # check_sum = ea # check_sum = 7d # check_sum = 4c # check_sum = 1f # check_sum = 2e
loop2.v的實現和loop1.v類似,只是代碼量更少。
module loop2( input clk, input rst_n, input [7:0] check_sum, output reg [7:0] check_sum_o ); integer i; //reg [7:0] check_sum_o; reg [7:0] ccc; always @ (posedge clk or negedge rst_n) if (!rst_n) begin check_sum_o = 8h0; end else begin ccc = check_sum; for(i=0;i<8;i=i+1) begin ccc = {ccc[6:0],1b0}^({8{ccc[7]}} & 8h31); end check_sum_o = ccc; end
其實也可以將C語言函數封裝成Verilog的function,然後在在單周期內進行賦值。
module loop3( input clk, input rst_n, input [7:0] check_sum, output reg [7:0] check_sum_o
);
integer i;
function [7:0] cal_table_high_first; input [7:0] value; reg [7:0] ccc ; reg [7:0] flag ; begin ccc = value; for(i=0;i<8;i=i+1) begin flag = ccc & 8h80 ; if(flag != 0 ) ccc = (ccc <<1) ^ 8h31 ; else ccc = (ccc <<1) ;
end cal_table_high_first = ccc; end
endfunction
always @ (posedge clk or negedge rst_n) if (!rst_n) begin check_sum_o = 8h0; end else begin check_sum_o <= cal_table_high_first(check_sum) ; end
綜上,loop1.v和loop2.v的主要貢獻是解開了演算法實現的if-else判斷。至於loop3.v中將C語言描述的功能封裝成fucntion,直接單周期完成賦值的實現方式在邏輯綜合後是否增加了硬體開銷不在本文討論範圍內。這和設計者施加的時序約束和綜合工具演算法有關。