二分法查找在實際電路中的應用

1

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

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

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

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

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

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

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

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

這個過程跟求方程(近似)解也非常類似。二進制搜索實現(xiàn)的逐次逼近常常用于需要校準的場景中，比如SAR ADC、DRAM ZQ 校準、儀器校準算法等。因為我們的校準代碼對應的值是線性增加或者減小的，符合二進制搜索法的條件。

2

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

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

SAR code配置DAC模塊得到。

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

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

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

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

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

第3次比較： 設置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ù)也會越來越多。

另外其第3次（最后一位）比較好像也沒有必要，因為你比較完也無法得到一個相等值，可以把最后一位固定成1或者0，最大的誤差就是最后一位代表的權(quán)重1/8 Vref。

2

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

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

每次CLK go high ，走一步

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

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

最低位LSB最終固定為1

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

3

最后給出一個6位二進制搜索SAR logic電路的SPEC：

Input

INCR

RSTB reset信號，負沿有效

CLK

OUTPUT

PUCODE [5:0]

你覺得這個電路是用Verilog代碼實現(xiàn)呢？

還是自己搭電路比較好？