二分法查找在實(shí)際電路中的應(yīng)用

1

首先問(wèn)大家一個(gè)問(wèn)題，如果有一堆有序的數(shù)據(jù)

1,2,3,4,5,6,7,8,9,10,11,...100

如果想要找出55，你要怎么實(shí)現(xiàn)呢？

最直觀的是用線性查找，從頭開始一個(gè)個(gè)的查找，需要55次才能找到目標(biāo)數(shù)值。

如果大家學(xué)過(guò)C或者C++，應(yīng)該有二分法查找的概念，先把這堆數(shù)分成2堆，把第一堆的最后一個(gè)數(shù)跟55比較，發(fā)現(xiàn)55比它大，所以55應(yīng)該在第2堆。再重復(fù)這個(gè)過(guò)程，大概需要7次就可以確定55的位置。

二分法查找效率顯而易見(jiàn)，它的時(shí)間復(fù)雜度T(n)=O(log(2)n)，遠(yuǎn)遠(yuǎn)小于線性查找的T(n)=O（n）。

但二分法要求數(shù)據(jù)必須是有序排列的，這在實(shí)際電路世界里面往往是滿足的。

利用二進(jìn)制搜索（二分法查找）實(shí)現(xiàn)的逐次逼近算法，每次都是選取比較范圍內(nèi)的中間點(diǎn)來(lái)跟參考值進(jìn)行比較，通過(guò)比較結(jié)果來(lái)繼續(xù)縮小比較范圍，一直迭代直至找到最接近比較值的解。

這個(gè)過(guò)程跟求方程(近似)解也非常類似。二進(jìn)制搜索實(shí)現(xiàn)的逐次逼近常常用于需要校準(zhǔn)的場(chǎng)景中，比如SAR ADC、DRAM ZQ 校準(zhǔn)、儀器校準(zhǔn)算法等。因?yàn)槲覀兊男?zhǔn)代碼對(duì)應(yīng)的值是線性增加或者減小的，符合二進(jìn)制搜索法的條件。

2

下圖是一個(gè)SAR ADC的基本架構(gòu)：

電路的目標(biāo)就是得到一個(gè)最接近Vin的VDAC，可以通過(guò)調(diào)整

SAR code配置DAC模塊得到。

假設(shè)我們的SAR（逐次逼近寄存器）的位數(shù)是3位，初始狀態(tài)設(shè)為SAR[2:0]=3'b100，也就是處于000-111的中間位置。

如果SAR的使能clock 開始toggle，比較過(guò)程就開始了：

如上圖所示，X軸表示時(shí)間，Y軸表示DAC輸出電壓VDAC：

第1次比較： 設(shè)置SAR[2:0]=3'b100，VDAC=1/2 Vref < Vin , 所以SAR[2]保持1，SAR[2:0]=3'b100；

第2次比較： 設(shè)置SAR[2:0]=3'b110，VDAC=(1/2 Vref + 1/4 Vref)> Vin , 所以SAR[1]最終取0，SAR[2:0]=3'b100；

第3次比較： 設(shè)置SAR[2:0]=3'b101，VDAC=(1/2 Vref + 1/8 Vref)> Vin , 所以SAR[0]最終取0，SAR[2:0]=3'b100；

最終我們可以得到與輸入電壓Vin最接近的VDAC，可以看出SAR的位數(shù)越多，精度越高，但是比較周期數(shù)也會(huì)越來(lái)越多。

另外其第3次（最后一位）比較好像也沒(méi)有必要，因?yàn)槟惚容^完也無(wú)法得到一個(gè)相等值，可以把最后一位固定成1或者0，最大的誤差就是最后一位代表的權(quán)重1/8 Vref。

2

前面是具體的SAR ADC的例子，我們可以進(jìn)一步把二進(jìn)制搜索SAR的過(guò)程畫成流程圖的形式，方便后續(xù)電路或者Verilog代碼的實(shí)現(xiàn)：

初始化SAR的MSB=1， 其它bit為0 （比如4bit 4'b1000）

每次CLK go high ，走一步

如果INCR=1， 走圖中實(shí)線箭頭方向；

如果INCR=0， 走圖中虛線箭頭方向；

最低位LSB最終固定為1

4bit的SAR 一共需要走3步，也就是3個(gè)CLK周期后就可以得到最后的結(jié)果。

3

最后給出一個(gè)6位二進(jìn)制搜索SAR logic電路的SPEC：

Input

INCR

RSTB reset信號(hào)，負(fù)沿有效

CLK

OUTPUT

PUCODE [5:0]

你覺(jué)得這個(gè)電路是用Verilog代碼實(shí)現(xiàn)呢？

還是自己搭電路比較好？