使用 Horner’s Rule 霍納規則和定點運算實現多項式（VHDL）

[Kevin_6462]

邏輯主頁

特點

本文涵蓋以下主題：

• 使用霍納規則（Horner’s Rule）在 FPGA 中實現多項式
• 使用定點格式的分數運算
• 與外部處理器介面
• 可擴展的多項式階數和資料寬度
• 使用 MATLAB 進行測試平台和驗證

介紹

在處理器上評估高階多項式可能非常耗時。例如，如果不使用任何技巧，計算 10 階多項式需要 65 次乘法和 10 次加法。這意味著您的處理器至少需要 75 個週期，假設您可以在一個週期內完成每個運算，但事實並非總是如此。本設計使用兩種方法來減少計算時間，所需的時脈數等於多項式的階數加二，或每個所需輸入需要一個週期。首先，霍納規則允許使用較少的乘法進行多項式計算。其次，使用定點而不是浮點也很有用，因為它可以減少乘法運算所需的時間。

背景

霍納規則（Horner’s Rule）

本設計的核心是霍納規則，它是一種簡單且有效率的多項式計算運算。假設我們有一個如下形式的 n 階多項式

f(x) =anxn + an-1xn-1 + … +a1x + a0

直接使用此形式計算，總共需要 n(n +1)/2 次乘法和 n 次加法，因此計算複雜度為 O(n²)。

霍納規則指出，我們可以將其因式分解，並將多項式重寫為：

f(x) =(((anx + an-1)x + an-2)x + an-3)x + … )x +a0.

使用此形式可將所需的運算次數減少為 n 次乘法和 n 次加法。計算複雜度現在降至 O(n) ，這使得高階多項式更易於處理。

定點運算

在本應用中，多項式輸入和系數採用定點格式表示。定點數只是一個普通的二進制整數，在本例中，它被解釋為小數。我們將使用 Qm.n 表示法，其中 m 表示整數位數（不包括符號位元），n 表示小數位元數。最終的資料寬度為 m+n+1。請注意，某些地方會在 m 中包含符號位，使總寬度為 m+n。只要保持一致性，兩種約定均可行。本文將遵循第一種約定。另請注意，這些參數在多項式 VHDL 程式碼中可通用。例如，Q3.4 數的寬度為 8-bit，由 1-bit 符號 + 3-bit（帶符號整數部分）和 4-bit（小數部分）組成。然而，在許多情況下，m 為 0，除符號位外，其他所有位元都分配給小數部分。

與浮點數不同，定點數的小數點是隱含的，設計人員需要在計算過程中追蹤小數點。定點數的動態範圍 [-(2*^m), 2^m* - 2-ⁿ], 也比浮點數小得多。其優點是，由於這些數字是常規整數，因此不需要特殊的硬件，從而縮短了計算時間。定點數的解析度 2^-n 對於動態範圍內的所有數字都保持不變。

由於定點數是整數，其運算本質上與任何二進位補碼相同。需要注意的是，在對 Q 個數進行加減運算時，使用者必須保持小數點對齊。對齊可以透過按小數位的差值進行移位來實現，或者直接在 HDL 中指定要使用的正確位元來實現。此外，在進行加減運算時，必須注意溢位問題。在某些情況下，如果整體系統增益能夠將值保持在允許範圍內，則可以允許溢位。如果中間計算會導致值回傳正確結果，也可以允許溢位。

將 Qm₁.n₁ 數與 Qm₂.n₂ 數相乘，結果為 Q(m₁ + m₂).(n₁ + n₂) 。請注意，最高兩位始終相同，因為它們是符號位元及其一位擴展。乘法也可能發生溢出，但由於一個或兩個運算元通常被規範化為 0 到 1 之間的數值，因此這通常不是問題。

運算

多項式

霍納規則表明，多項式可以透過形式為 a₁x + a₀ 的一階多項式分段計算。因此，本設計最基本的建構區塊是乘法器和加法器。這些組件的 VHDL 程式碼可在 adder.vhd 和 mult.vhd 中找到。

乘法器僅使用內建 VHDL 有符號乘法函數，並帶有寄存輸出。因此，它應該能夠利用 FPGA 內建的乘法器區塊（如果 FPGA 有的話）。加法器採用超前進位元 （Carry Look Ahead）架構，不含寄存輸出。

這兩個構建區塊組合成一個更高層級的區塊，用於 mult_add.vhd 中的單一乘加運算。此單元實作函數 a₁x + a₀，其中 a_i 和 x 均為 Qm.n 數，用於霍納規則的每個階段。因此，一個 n 階多項式需要該區塊的 n 個實例。

假設系數、輸入 x 或兩者都被歸一化為 0 到 1 之間的數值，這樣乘法結果就可以儲存回相同的資料大小，因為整數位元不會溢位。在此應用中，乘法結果被簡單地截斷，取符號位、小數點左側最接近的 m 位以及小數點後的前 n 位。

這是整數和小數長度首次發揮作用的地方，因為結果需要在正確的位置截斷以保持正確的格式。各個乘法器和加法器只處理整數，而不關心小數點。

圖 1. 多項式 RTL 視圖。

在多項式層級，乘加區塊串接，以便一個區塊的結果饋入下一個區塊的輸入。圖 1 上圖展示了一個三階多項式的 RTL 視圖。此層級也為 x 和每個系數新增了一個暫存器。這樣，所有輸入都可以使用一條匯流排。在每個時脈上升緣，內部訊號都會移位，以將輸入載入到各自的暫存器中。資料必須依照 x、 a_n, a_n-1, …, a₀ 的順序排列。最終結果在 n+2 個時脈週期加上加法器的傳播延遲後生效。

介面

以上就是實際多項式區塊的內部運作原理。然而，該設計最初的想法是將其用作主機微控制器的共處理器。這種設計在系統單晶片（SoC）中使用時效果顯著，因為處理器和 FPGA 結構可以透過記憶體對應暫存器共享資料。但這只是一份通用指南，適用於您現有的任何硬體。

外部 MCU 可以使用平行介面直接與多項式區塊連接，但這會佔用大量引腳。串列介面可能更實用，因為幾乎所有 MCU 都內建了串列介面。本範例使用基於此處提供的 SPI 從屬介面。頂層測試平台也包含此處提供的 SPI 主介面。雖然 SPI 是常用串列介面中速度最快的，但任何串列介面都會造成嚴重的瓶頸，尤其是在處理高階多項式和大資料位元寬時。如果您需要快速獲得結果，這會帶來問題。我們鼓勵使用者開發自己的介面（例如上面提到的記憶體對應），以滿足自身需求，並將其與多項式區塊結合使用。

圖 2. 頂層 RTL 視圖。

圖 2 顯示了包含 SPI 介面的頂層設計。使用此 SPI 接口，從屬選擇訊號用作多項式單元的時脈，在傳輸完成時閂鎖數據，以便數據能夠以最快的速度處理。計數器追蹤傳輸數量，並在最終計算完成後透過置位「done」輸出向主機發出訊號。然後，主機在下一個 SPI 傳輸開始時向「請求」線發出脈衝，在此期間結果將被閂鎖並傳送回主機。然後，從屬將等待下一個 x 值以在相同傳輸中啟動新的計算。請注意，此應用程式僅使用 SPI 模式 3。

模擬與測試

本設計在 ModelSim Altera Starter Edition v10.4b 中進行了模擬。測試資料使用 Matlab 的 fi 函數建立。Matlab 腳本運行相同的演算法，並給出預期結果以供比較。第一次模擬僅測試多項式單元。測試資料為 7 階多項式，資料格式為 Q7.24，因此取值範圍為 -128 至 128-2^-24。但是，為了避免溢出，取值範圍為 -64 至 64-2^-24。

圖 3. ModelSim 中的多項式區塊模擬。

第二個模擬包含 SPI 接口，並使用更典型的 Q0.15 資料格式計算三階多項式。

圖 4. ModelSim 中的頂層設計模擬

Matlab 腳本和測試平台檔案包含在下載檔案中。請注意，根據 Matlab 中使用的捨入方法，模擬結果可能會略有不同。本應用程式中使用的直接截斷相當於 Matlab 的「下整數（Floor）」舍入方法。

結論

本設計實現了霍納規則，用於計算階數、資料寬度以及整數和小數長度可變的定點運算中的多項式。如果需要，使用者可以輕鬆地用其首選晶片供應商的 IP 替換提供的乘法器和加法器組件。本範例使用 SPI 介面與主機微控制器通訊，但這並不理想，鼓勵使用者根據應用需求自行設計通訊介面。

下載

Polynomial.zip (17.2 KB)

該 zip 壓縮檔案包括所有 VHDL 檔案、2 個測試台、2 個用於模擬的 DO 檔案以及 Matlab 模擬腳本。