陳文藝, 王子越, 楊 輝

(1.西安郵電大學(xué) 物聯(lián)網(wǎng)與兩化融合研究院， 陜西 西安 710061； 2. 西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

查找表(look-up-table, LUT)算法在圖像處理和三維測量方面有重要應(yīng)用[1]，其中相位測量輪廓術(shù)(phase measuring profilometry，PMP)是應(yīng)用較為廣泛的一種結(jié)構(gòu)光三維測量技術(shù)[2]，其基本思想是通過計算有一定相位差的多副光柵條紋圖像來得到每個像素的相位值，再根據(jù)相位值計算物體的深度信息。其中相對相位的解算涉及到反正切函數(shù)的求解，而目前應(yīng)用較為廣泛的數(shù)字映射技術(shù)包含數(shù)字循環(huán)技術(shù)、乘法技術(shù)和查找表技術(shù)[3-4]等。其中cordic算法就是典型的數(shù)字循環(huán)技術(shù)，只需進行移位和加法運算就能實現(xiàn)三角函數(shù)的運算[5]。為了提高算法精度，cordic算法需要進行反復(fù)迭代計算或者增加流水線長度，反復(fù)迭代節(jié)省硬件資源但是運算速度慢，增加流水線則會增加運算資源[6]。多項式近似及泰勒展開算法主要是利用邏輯資源和乘法器資源逼近目標函數(shù),優(yōu)點是收斂速度較快，但是會消耗較多的乘法器資源，同時等待時間較長[7]。在高精度計算情況下，查找表尺寸會呈指數(shù)式增長，因此，查找表技術(shù)通常只應(yīng)用于單精度范圍內(nèi)的計算[8-9]。

為了改善基于查找表技術(shù)下高精度要求時資源消耗較多的問題，本文擬在插值查找表基礎(chǔ)上利用matlab工具量化誤差范圍，并劃分插值點個數(shù)，改變步長，從而在保證一定誤差限度下減少資源消耗。

1 插值查找表反正切算法

查找表實質(zhì)是一個存儲元件，能夠根據(jù)任何給定的輸入狀態(tài)組合，查找得到相應(yīng)的函數(shù)值，但使用查找表需要在精度和表的大小之間作出權(quán)衡。對于8-10位的短輸入來說，直接用查找表是最有效的。而對于12-20位的輸入，使用插值查找表是最有效的。插值查找表在實現(xiàn)數(shù)字信號處理功能時，不僅具有查找表所具有的優(yōu)勢，而且無需太多的存儲資源，可以使用較小容量的LUT對其存儲值線性內(nèi)插，以模擬更大容量的LUT，從而達到更高數(shù)值分辨率。插值查找表用計算資源和等待時間的增加換取表尺寸的減小。此外，通過插值查找表只需再增加一小部分邏輯資源和一個乘法器。

線性插值中點的縱坐標

其中，(x0,y0)與(x1,y1)都為已知點坐標，xa為區(qū)間(x0,x1)內(nèi)某一位置點坐標。

如用16位無符號定點數(shù)U16.8作為輸入，用高有效位8 bit作為地址線，低有效位8 bit作為插值位，則自變量x的取值范圍為0≤x≤256，用于插值的步長為2-8，便可以模擬地址線為16位的LUT。雙端口隨機存取存儲線性插值計算結(jié)構(gòu)，如圖1所示。

圖1 雙端口隨機存取存儲線性內(nèi)插計算結(jié)構(gòu)

反正切函數(shù)f(x)=arctanx曲線如圖2所示。對其進行等間距插值誤差，結(jié)果如圖3所示。由圖3可知，在自變量在(0,2)的區(qū)域誤差極大。

圖2 反正切函數(shù)

圖3 等間距插值誤差

對于反正切函數(shù)，當自變量值較小時，其非線性特性明顯(曲率值較大)，反正切函數(shù)的曲率，如圖4所示。

圖4 反正切函數(shù)的曲率

在中低精度要求下，插值查找表很有效，但是，隨著輸入寬度的增加，表的尺寸仍會呈指數(shù)增長。在保證一定誤差前提下，使用插值查找表就要增加用于查找的高有效位位寬，導(dǎo)致資源開銷的增加。針對這一問題，結(jié)合反正切函數(shù)的曲率特征，提出一種變步長插值查找表算法。

2 變步長插值反正切算法

2.1 自變量范圍內(nèi)變步長取點

分析圖4反正切函數(shù)的曲率曲線，可以發(fā)現(xiàn)，其曲率逐漸增加并在x=0.83附近達到最大值，隨后曲率逐漸減小并趨近于0。利用反正切函數(shù)曲率特性，考慮到易于硬件實現(xiàn)和最大化利用存儲資源等劃分原則，劃分自變量x的坐標應(yīng)滿足以下要求[10]。

(1) 函數(shù)曲率高的范圍內(nèi)盡量多劃分點。

(2) 從自變量值到查找表地址的映射以及后續(xù)插值易硬件實現(xiàn)。

(3) 采用劃分方法得到對應(yīng)點的個數(shù)m≤2n，并且點的個數(shù)盡量大。

擬用16位無符號定點數(shù)U16.8輸入映射為8位地址線即最大256個點；輸出結(jié)果為16位無符號定點數(shù)U16.15，按上述要求的自變量范圍、縮放比例、規(guī)劃點的個數(shù)如表1所示。

表1 自變量范圍、其縮放比、規(guī)劃點個數(shù)

2.2 量化誤差范圍

借助Matlab LUT函數(shù)量化誤差需要指定函數(shù)類型為反正切函數(shù)；需要指定分段范圍內(nèi)各自自變量上限、自變量下限、自變量數(shù)據(jù)類型、自變量數(shù)據(jù)步長、因變量數(shù)據(jù)類型、因變量數(shù)據(jù)步長、舍入類型等，確定自變量取點策略；最后將分段量化自變量[0,256)范圍內(nèi)插得到函數(shù)值與32位浮點數(shù)函數(shù)值作比較，其最大絕對誤差1.4×10-4，滿足系統(tǒng)要求。自變量范圍為[0,2)的反正切函數(shù)與線性插值函數(shù)，如圖5所示。采用以2的冪為間隔的自變量取點策略，共得到128個自變量點，對自變量在[0，2)范圍內(nèi)的反正切函數(shù)的插值誤差量化，如圖6所示。

圖5 自變量[0,2)內(nèi)128個插值點插值

圖6 插值誤差示意圖

從圖6可以看出，采用以2的冪為間隔的自變量取點策略，得到的128個自變量點，對自變量在[0，2)范圍內(nèi)的反正切函數(shù)的誤差量化，自變量范圍內(nèi)最大誤差為5.076 7×10-5。

3 變步長插值反正切算法設(shè)計與實現(xiàn)

3.1 模塊功能設(shè)計

將系統(tǒng)劃分為地址映射模塊和插值查找表模塊2個模塊。其中地址映射模塊是重點，其功能是將自變量16位無符號定點數(shù)U16.8按照自變量分段劃分方式映射至8位地址位。系統(tǒng)結(jié)構(gòu)如圖7所示。

圖7 系統(tǒng)結(jié)構(gòu)示意圖

3.1.1 地址映射模塊

地址映射模塊將數(shù)據(jù)預(yù)處理模塊中16位無符號定點數(shù)U16.8數(shù)據(jù)映射成為插值查找表8位地址[11]。采用判定最高有效位及位拼接的方法，自變量范圍為[0,256)的16位數(shù)據(jù)映射規(guī)則由表2給出具體劃分，分別包含數(shù)據(jù)格式、對應(yīng)的8位地址、其映射規(guī)則、插值低有效位及點的個數(shù)。

表2 地址映射細則

3.1.2 線性插值模塊

插值查找表模塊采用雙口隨機存取存儲查找表，讀取輸入的當前地址和下一個地址的數(shù)據(jù)用于插值，線性插值硬件結(jié)構(gòu)，如圖8所示。

圖8 線性插值硬件結(jié)構(gòu)

在圖8中，Y0是8位映射地址(U8.0)，Y1是Y0地址的下一位(U8.0)，用Y1地址讀取到的為B值(U16.15)、Y0地址讀取的為A值(U16.15)，Dx為插值有效位，其位寬隨輸入變化。用B-A的值與插值低有效位Dx相乘即為B1，則A+B1即為得到線性插值后的相位值16位(U16.15)。

3.2 算法實現(xiàn)

采用標準四步相移的正弦光柵數(shù)據(jù)輸入并對其進行相位解算。數(shù)據(jù)流處理及顯示過程，如圖9所示。

圖9 數(shù)據(jù)流處理及顯示過程

使用內(nèi)嵌邏輯分析儀對相位解算進行在線調(diào)試，如圖10所示。軟件、硬件及實時硬件計算結(jié)果VGA顯示，如圖11所示。

圖10 相位解算數(shù)據(jù)采集調(diào)試

圖11 軟件、硬件計算結(jié)果及實時硬件計算結(jié)果VGA顯示

4 實驗結(jié)果及分析

選用Modelsim10.0進行系統(tǒng)仿真。采用流水線結(jié)構(gòu)工作，第一個數(shù)據(jù)輸入后順延10個時鐘得到相位結(jié)果。例如，當輸入為2 913(U16.8)時，10個時鐘周期后輸出的相位值為48 598(U16.15)，對應(yīng)Matlab中32位精度反正切函數(shù)值為1.483 139 …。

反正切值相位的16位無符號定點數(shù)U16.15為48 598，與32位精度的反正切函數(shù)誤差為4.635 8×10-5。系統(tǒng)仿真結(jié)果如圖12所示。

圖12 系統(tǒng)仿真結(jié)果

選用Altera cycloneIV系列的EP4CE30F23C6芯片，在quartus15.1的開發(fā)環(huán)境對代碼進行編譯綜合，其最高時鐘頻率為219.06 MHz共使用311個邏輯單元(Les)，4211個存儲位(Bits)，一個9位乘法器，一個9位除法器。

仿真實驗使用quartus15.1軟件且在同一芯片選用Altera自帶的16次迭代cordic IP核作反正切運算。設(shè)置IP核性能最高頻率目標為219 MHz，綜合后達到206.1 MHz。其最大絕對誤差隨輸出位寬變化，最大值為1.431 2×10-4，如圖13所示。其消耗資源情況，如表3所示。

圖13 不同輸出位寬的最大絕對誤差

算法16位BitsLes17位BitsLes18位BitsLes19位BitsLes20位BitsLes21位BitsLes22位BitsLes23位BitsLescordic算法02 43502 73302 99403 41403 70804 23204 48504 722變步長插值8位地址線4 2113114 3823114 7233114 9793115 2353115 4913115 7473116 003311變步長插值9位地址線8 1923118 7043119 216 3119 72831110 24031110 75231111 26431111 776311

cordic算法的精度由迭代次數(shù)與輸出位寬共同決定[12]，由圖13及表3可以得到結(jié)論如下。

(1) 16次迭代cordic算法的誤差在16位輸出位寬至19位之間變化較為明顯，后續(xù)變化趨于平緩。變步長插值算法的誤差隨輸出位寬變化一直趨于平緩。8位地址線的變步長插值算法在16位位寬時其誤差明顯小于16次迭代cordic算法，其消耗資源也比較接近。

(2) 與cordic算法相比，變步長插值算法適合存儲資源豐富、邏輯資源較少的系統(tǒng)。

變步長插值算法的系統(tǒng)最高頻率基本不會隨位寬的增加而降低，16次迭代cordic算法的系統(tǒng)最高頻率會隨輸出位寬而降低，23位寬時最高頻率192.08 MHz。

5 結(jié)語

結(jié)合插值查找表算法的特點和反正切函數(shù)的曲率特性，使用變步長插值查找表的方法對反正切函數(shù)進行計算，通過Matlab量化誤差確定誤差范圍，再經(jīng)地址映射將數(shù)據(jù)轉(zhuǎn)化為插值地址，通過線性插值完成查找。經(jīng)Modelsim10.0仿真和QuartusII 15.1在EP4CE30F23C6芯片下綜合驗證，結(jié)果表明，該方法與傳統(tǒng)插值查找表和ATLERA CORDIC IP核比較，在同樣的16位位寬輸出下，最大誤差1.431 2 ×10-4，誤差較小；最高工作頻率為219.06 MHz，工作頻率較高；同時，占用資源適中，相較于傳統(tǒng)插值查找表算法可以節(jié)省存儲資源。