不說廢話,直接給出verilog代碼for二分法查找

2021-03-02 跟IC君一起學習集成電路

      

上一篇文章IC君介紹了二進位搜索算法（二分法查找）在實際電路中的應用，而且文末也給出了一個電路設計的spec，可惜也沒人給出代碼或者電路，沒辦法只能IC君自己上了

Linux 的創始人 Linus 曾經說過：

Talk is cheap. Show me the code.

下面IC君就給出二進位搜索算法的verilog代碼實現。請注意下面的內容已經進入IC君相對不熟悉領域，很有可能犯錯誤。不過發現錯誤的過程就是成長的過程，所以大家要勇敢的去做，不要怕犯錯。若有錯誤，請大家不吝指教！

首先再寫出6位二進位搜索SAR logic電路的SPEC：

Input 

OUTPUT

看到這張圖和spec很容易就想到用Verilog來實現，具體代碼如下：

`timescale 1ns/10ps

module sar (pucode,clk,incr,rstb);

input clk;

input incr;

input rstb;

output[5:0] pucode;

wire incr;

wire incrb;

reg [2:0] count;

reg [5:0] pucode;

always@(posedge clk or negedge rstb)

    if(!rstb)

begin

//初始轉態

    pucode<=6'b100000;

    end

    else

    begin

        case(count)

        0:

        begin

        pucode[5]<=pucode[5]^~incr;

        pucode[4]<=1'b1;

        end

        1:

        begin

        pucode[4]<=pucode[4]^~incr;

        pucode[3]<=1'b1;

        end

        2:

        begin

        pucode[3]<=pucode[3]^~incr;

        pucode[2]<=1'b1;

        end

        3:

        begin

        pucode[2]<=pucode[2]^~incr;

        pucode[1]<=1'b1;

        end

        4:

        begin

        pucode[1]<=pucode[1]^~incr;

        pucode[0]<=1'b1;

        end

        5:

        begin

        pucode[0]<=1'b1;

        end

        default: pucode<=6'b100000;

    endcase

        end

//6bit的SAR 一共需要走5步，也就是5個CLK周期後就可以得到最後的結果

//所以底下是一個計數為5的計數器

always@(posedge clk or negedge rstb)

        if(!rstb)

        begin

        count<=3'b0;

        end

        else

        begin

        if(count<5)

        count<=count+1'b1;

        end

       

endmodule

在Design Complier下進行邏輯綜合，得到的電路如下

總共用到了97個cell：

一共用到了9個DFF，其中3個是給Counter計數用的，6個是給pucode[5:0]用的，符合我們的預期。但是看起來面積好像有點大，代碼風格也不太像時序狀態機的風格。

接下來我們修改一下代碼，讓它更符合時序狀態機的風格。

`timescale 1ns/10ps

module sar_new (pucode,clk,incr,rstb);

input clk;

input incr;

input rstb;

output[5:0] pucode;

wire incr;

wire incrb;

reg [2:0] count;

reg [5:0] pucode;

reg [5:0] nxt_pucode;

//狀態機的切換

always@(posedge clk or negedge rstb)

    if(!rstb)

    begin

    pucode<=6'b100000;

    end

    else

    pucode<=nxt_pucode;

always@(pucode or incr)

case (pucode)

//窮舉所有可能的code

    6'b100000: nxt_pucode=incr?6'b110000:6'b010000;

    6'b110000: nxt_pucode=incr?6'b111000:6'b101000;

    6'b111000: nxt_pucode=incr?6'b111100:6'b110100;

    6'b111100: nxt_pucode=incr?6'b111110:6'b111010;

    6'b111110: nxt_pucode=incr?6'b111111:6'b111101;

    6'b010000: nxt_pucode=incr?6'b011000:6'b001000;

    6'b011000: nxt_pucode=incr?6'b011100:6'b010100;

    6'b011100: nxt_pucode=incr?6'b011110:6'b011010;

    6'b011110: nxt_pucode=incr?6'b011111:6'b011101;

    6'b001000: nxt_pucode=incr?6'b001100:6'b000100;

    6'b001100: nxt_pucode=incr?6'b001110:6'b001010;

    6'b001110: nxt_pucode=incr?6'b001111:6'b001101;

    6'b000100: nxt_pucode=incr?6'b000110:6'b000010;

    6'b000110: nxt_pucode=incr?6'b000111:6'b000101;

    6'b000010: nxt_pucode=incr?6'b000011:6'b000001;

    //next group

    6'b101000: nxt_pucode=incr?6'b101100:6'b100100;

    6'b101100: nxt_pucode=incr?6'b101110:6'b101010;

    6'b101110: nxt_pucode=incr?6'b101111:6'b101101;

    6'b100100: nxt_pucode=incr?6'b100110:6'b100010;

    6'b100110: nxt_pucode=incr?6'b100111:6'b100101;

    6'b100010: nxt_pucode=incr?6'b100011:6'b100001;

    //next group

    6'b110100: nxt_pucode=incr?6'b110110:6'b110010;

    6'b110110: nxt_pucode=incr?6'b110111:6'b110101;

    6'b110010: nxt_pucode=incr?6'b110011:6'b110001;

    //next group

    6'b111010: nxt_pucode=incr?6'b111011:6'b111001;

    6'b001010: nxt_pucode=incr?6'b001011:6'b001001;

    //next group

    6'b010100: nxt_pucode=incr?6'b010110:6'b010010;

    6'b010110: nxt_pucode=incr?6'b010111:6'b010101;

    6'b010010: nxt_pucode=incr?6'b010011:6'b010001;

    6'b011010: nxt_pucode=incr?6'b011011:6'b011001;

    6'b101010: nxt_pucode=incr?6'b101011:6'b101001;

    //impossible code

    6'b000000: nxt_pucode=6'b000001;

    //the least bit=1 , keep code

    default: nxt_pucode=pucode;

    //6'bxxxxx1: nxt_pucode=pucode;

    endcase

endmodule

 最終綜合出來的電路如下：

總共用到了44個cell：

最終只用了5個DFF，總共只用了44個cell, 總面積是146；

而前一個代碼總共用了97個cell，總面積283，新代碼綜合出來的面積幾乎是前一個代碼的一半。

通過比較可以發現，不同的verilog代碼風格綜合出來的電路有著巨大的差異。數字前端工程師應該花更多的時間思考自己的代碼是不是可以用其它方式來實現，有沒有更好的風格。當然我在這方面也是初學者，希望大家多多指教。

下一篇文章預告：

如何驗證上面2個版本的verilog代碼，敬請繼續關注！

相關焦點

  • Verilog代碼轉VHDL代碼經驗總結
    代碼轉換為VHDL代碼。，再轉換回verilog後與原代碼對比的圖，可以看出，一些注釋之類的信息都沒有了，原來的代碼規範和風格也發生了變化。在轉換的過程，該軟體對代碼中的漢語注釋不支持，如果出現漢字就無法轉換。筆者之前就曾試著寫過Verilog轉VHDL代碼的工具，見：Verilog HDL代碼轉VHDL代碼，無奈因為不是軟體開發出身，寫出來的東西通用性和完善性很差。
  • 二分法題型小結
    學好算法沒有捷徑，最好的捷徑就是多刷題，並且跳出舒適區，每道題都要尋找最優解，也不能老是做那些你自己比較擅長的題，不定期更新 Leetcode 的題，每道題都會給出多種解法以及最優解在刷題的過程中，二分法用的還是挺多的，有時候超時了往往是你沒有用上二分法，今天我就來稍微總結下用的最多的三種二分法搜索。
  • 二分法其實很簡單,為什麼老是寫不對!!
    作者丨代碼隨想錄 來源丨代碼隨想錄 （code_thinking）相信很多人對二分法是又愛又恨，愛是在於它思想簡單
  • 使用Python和C語言實現二分法查找(折半查找)
    二分查找 叫折半查找，它對要查找的序列有兩個要求，一是該序列必須是有序的，二是該序列必須是順序存儲的。二分法查找算法的原理如下：1、 如果待查對象為空返回-1，表示查找不到目標元素2、 如果待查序列不為空，則將中間元素與要查找的目標元素進行匹配看是否相等，如果相等表示 查找成功，返回該中間元素的索引如果不相等再比較這兩個元素的大小
  • 懂Excel輕鬆入門Python數據分析包pandas(二十八):二分法查找
    後來才發現，原來不是 Python 數據處理厲害，而是他有數據分析神器—— pandas前言Excel 中的 vlookup 函數有一個模糊查找選項，其內在原理為二分法查找，在 pandas 中同樣有一樣功能的方法。
  • 漫畫:二分法深度剖析(第二講)
    所以我們的問題轉化為在 [0,x/2] 中找一個特定值，滿足二分查找的條件。（當然，如果沒有想到使用 x/2 作為 Right 而 直接使用 x ，其實也是可以的）剩下的邏輯就很簡單了，我們不停縮小mid的範圍，如果最終平方大於x就放回它前面一個值，否則就正常返回，直到兩邊的邊界完全收斂。
  • 算法競賽小專題系列(1):二分法、三分法
    清華大學出版社二分法和三分法是算法競賽中常見的算法思路，本文介紹了它們的理論背景、模板代碼、典型題目。1. 二分法的理論背景在《計算方法》教材中，關於非線性方程的求根問題，有一種是二分法。整數二分模板2.1 基本形式  先看一個簡單問題：在有序數列a[]中查找某個數x；如果數列中沒有x，找它的後繼。通過這個問題，給出二分法的基本代碼。　　如果有x，找第一個x的位置；如果沒有x，找比x大的第一個數的位置。
  • 面試向算法 - 二分法專題(一)
    因此，我期望將這些知識給帶出來，就引申出了本系列文章和視頻。二分法是一種隨處可見卻又非常精妙的算法，我們最熟知的用法是在一個有序數組中查找某個 target 是否存在。初學二分法的同學可能會被各種邊界情況、不同寫法、是開區間還是閉區間等細節弄糊塗，以至於捨本逐末。其實並不需要如此，我們只需要記住一種最方便的寫法並理解它即可。
  • 算法入門——二分查找法
    二分查找法      假設我們要在一個電話簿中查找一個名字為g名字開頭的人，我們可以從頭開始翻頁
  • excel查找函數：如何對合併單元格進行查找
    VLOOKUP坐字法專做單元格合併查找》中作者推薦使用VLOOKUP「坐」字法。很多夥伴對這個「坐」字法非常感興趣，想了解其中的原理。苦等64個夜晚，今天「坐」字法背後的秘密終於浮出了水面。1月23日發布的教程中VLOOKUP裡出現了一個「坐」字，大家紛紛表示想了解這個「坐」字到底是何意，今天就為大家解釋這個公式的原理。
  • 面試手撕算法系列:二分法
    最近春招開始了，面試面著面著一言不合就開始手撕代碼手撕就手撕，接下來我打算寫幾個專題講講面試中手撕的常見題目 這些都是LeetCode上有的題目 手撕無非就是 樹、鍊表、二分、字符串這些常用的數據結構二分法查找，也稱為折半法，是一種在有序數組中查找特定元素的搜索算法。
  • ​verilog相關基礎知識
    對於verilog基礎知識，這裡做簡單的介紹，對於已經熟悉verilog語言的讀者可以省略不看此部分。
  • 二分法
    二分法是什麼呢？百度上的定義是：「對於區間[a,b]上連續不斷且f(a)·f(b)<0的函數y=f(x)，通過不斷地把函數f(x)的零點所在的區間一分為二，使區間的兩個端點逐步逼近零點，進而得到零點近似值的方法叫二分法。」        這個定義比較複雜，我們把它分成幾部分來看。
  • 關於學習verilog
    這樣做乍看起來很花時間，但是從整個項目過程來看，絕對要比一上來就寫代碼要節約時間，且這種做法可以使項目處於可控、可實現的狀態。　 2.代碼規範。　 a.設計要參數化。這樣做可以讓綜合器綜合出更優的結果。　　　5) 儘量在底層模塊上做邏輯，在高層儘量做例化，頂層模塊只能做例化，禁止出現任何膠連邏輯（glue logic），哪怕僅僅是對某個信號取反。理由同上。　　　6) 在FPGA的設計上禁止用純組合邏輯產生latch，帶D觸發器的latch的是允許的，比如配置寄存器就是這種類型。
  • Verilog 最全經驗總結(建議收藏)
    verilog與VHDL相比的優點二者的關係仿佛C與FORTRAN,具體而言:1 verilog的代碼效率更高:比較明顯的對比:VHDL在描述一個實體時採用entity/architecture模式,verilog在描述一個實體時只需用一個"module/edumodule"語句塊.
  • 通過點燈的邏輯體驗FPGA的編程流程以及Verilog語法基礎
    作為「寒假在家一起練」的第二次直播講座，我們今天就基於1個LED做了1個多小時的分享，從創建第一個FPGA項目、寫下第一句Verilog代碼，到調用FPGA的IP Cores，體驗了FPGA的設計流程以及Verilog的基本語法規範。
  • HDLBits:在線學習Verilog(七 · Problem 30-34)
    下面給出了一個基本的if語句和其綜合出來的電路。解答與分析// synthesis verilog_input_version verilog_2001module top_module( input a, input b, input sel_b1, input sel_b2, output wire out_assign,
  • SystemVerilog中的多維數組
    在網絡研討會的後半部分，你將了解導入包的最佳位置，以及如何編寫代碼，來避免在多個包中有重名定義的問題。例如，為什麼以下代碼不編譯，RED 和 GREEN 名稱的 Bug 是什麼？調試並找出答案。有很多很棒的問題，在這裡（https://verificationacademy.com/sessions/taking-systemverilog-arrays-to-the-next-dimension/questions-and-answers）我已經回答了很多。「SystemVerilog數組」是一個大話題，我不得不省略許多想法。
  • 利用VBA代碼實現多重查找、模糊查找、清除值的方案
    大家好，今日內容仍是和大家分享VBA編程中常用的簡單「積木」過程代碼，第NO.111-NO.113則，內容是：利用FindNext完成多重查找、利用ClearContents完成清除值的操作、利用FIND完成模糊查找等內容。
  • 遍歷,二分法:排序,紅黑樹,斯特拉森算法
    幾個「最」，說明人對極值更敏感:(電腦一般情況下，要麼從頭到尾遍歷，要麼使用二分法。電腦算法的優化，很多就是把遍歷算法變成二分法的遞歸。歸併排序，則是典型的二分法。16個數，一分為二每組8個，二分為4每組4個，三分為8每組2個，四分為16每組1個。每組1個的時候也就無所謂順序了。然後把它們兩兩一組的合併起來，只需要一次比較，小的在前，大的在後，也就排好了。