一種變步長插值反正切算法的設計與實現

陳文藝, 王子越, 楊 輝

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

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

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

1 插值查找表反正切算法

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

線性插值中點的縱坐標

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

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

圖1 雙端口隨機存取存儲線性內插計算結構

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

圖2 反正切函數

圖3 等間距插值誤差

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

圖4 反正切函數的曲率

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

2 變步長插值反正切算法

2.1 自變量范圍內變步長取點

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

(1) 函數曲率高的范圍內盡量多劃分點。

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

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

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

表1 自變量范圍、其縮放比、規劃點個數

2.2 量化誤差范圍

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

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

圖6 插值誤差示意圖

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

3 變步長插值反正切算法設計與實現

3.1 模塊功能設計

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

圖7 系統結構示意圖

3.1.1 地址映射模塊

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

表2 地址映射細則

3.1.2 線性插值模塊

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

圖8 線性插值硬件結構

在圖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 算法實現

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

圖9 數據流處理及顯示過程

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

圖10 相位解算數據采集調試

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

4 實驗結果及分析

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

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

圖12 系統仿真結果

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

仿真實驗使用quartus15.1軟件且在同一芯片選用Altera自帶的16次迭代cordic IP核作反正切運算。設置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算法的精度由迭代次數與輸出位寬共同決定[12]，由圖13及表3可以得到結論如下。

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

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

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

5 結語

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