0 引言

    在大規模集成電路發展的今天，隨著高精度、便攜式電子器件的進一步發展，傳統的信號處理技術已經逐步被大規模的并行處理技術所取代。剩余數系統以其特有的進位自由和并行運算特性，近年來已經成為高速、大規模數字信號處理的最好選擇。

    剩余數系統應用的意義已經被證明，尤其對于處理密集型加法、減法以及乘法等占有絕對的優勢。然而，其他的運算例如除法、奇偶檢測、比例變化、大小比較和符號檢測等運算由于其運算的復雜性，在剩余數系統就失去了并行性的優勢，這些運算有時不得不將余數轉換成二進制數后再做運算，所以會浪費大量的電路面積和延遲。為了提高此類運算電路的性能，近年來許多研究人員開始對此領域進行研究,但是大部分研究針對比較常用的3模集合{2ⁿ，2ⁿ+1，2ⁿ-1}^[1-4]。

    比例變化是余數系統研究最重要問題之一，比例變化尤其在防止溢出和內部乘積處理方面具有舉足輕重的作用。和反向轉換一樣，比例縮放在剩余數系統實現也涉及到大的延遲和較高的硬件復雜度，涉及在每一個剩余數計算階段。本文針對4模集合{2ⁿ，2²ⁿ+1，2ⁿ+1，2ⁿ-1}，在分析反向轉換和比例縮放算法的基礎上，提出了一個新的基于2ⁿ的比例縮放算法，并基于加法器實現其VLSI結構。

1 算法描述

    基于剩余數系統模集合{m₁，m₂，…，m_n}的整數X，通過一個比例因子k做比例變化，設Y為比例變化的結果，則：

    對于模集合針對4模集合{m₁，m₂，m₃，m₄}其對應于{2ⁿ，2²ⁿ+1，2ⁿ+1，2ⁿ-1}，根據式(3)：

2 電路實現

2.1 y₁的硬件實現

    定理2：若0≤v≤2ⁿ-2，則v2ⁱ模2ⁿ-1的結果相當于將n位寬二進制數v，即v_n-1v_n-2…v₀循環左移i位^[5]。

    定理3：若0≤v≤2ⁿ-2，則(-v)2ⁱ模2ⁿ-1的結果相當于將v乘以2ⁱ模2ⁿ-1的結果按位取反^[5]。

    由前面的分析可知，對于模通道2²ⁿ進行2ⁿ比例變化結果y₁，直接取Y的低n位即可實現。應用定理1和2，通過進一步合并化簡，Y最終轉換為5個4n位操作數相加的形式，即：

    通過3級進位保留加法器（CSA），最終形成兩個4n位寬的S、C，S和C通過模2⁴ⁿ-1加法器得到4n位模加法器的結果Y，如圖1所示。

2.2 y₂的硬件實現

    操作數在進入縮一碼模2²ⁿ+1加法器之前必須分別減1，而縮一碼模2²ⁿ+1加法器在輸出以后必須加1才能得到真正的結果。兩者合并，只要將進位加法器的輸出減1即可。同時，根據定理4，進位保留加法器的最高有效位的進位輸出將被直接取反加到下一級進位保留加法器的最低有效位的同時，需要加上一個補償常數因子2ⁿ。聯合前面縮一碼模2²ⁿ+1加法器的校正因子-1，總的校正項C_j為：

    直接將上面的三項輸入法進位反轉的回轉進位保留加法器，得到進位2n位C和2n位和位S，將C和S直接輸入到縮一碼模2ⁿ+1加法器，該縮一碼模2n+1加法器的輸出即為實際的比例變換結果。

2.3 y₃的硬件實現

    y₃的實現和y₂相似，同樣通過進位保留加法器樹和一個縮一碼模2²ⁿ+1加法器實現。通過化簡式(7)：

    設校正項為C_j，同理，總的校正因子C_j為：

2.4 y₄的硬件實現

    對于模通道m₄=2ⁿ-1進行2ⁿ比例變化結果y₄，根據式(8)，應用定理2，進一步表示為：

    該模通道比例變化y₄的實現只需要將上面的兩個n位操作數直接通過一個0唯一表示的模2ⁿ-1加法器，即可實現。

    整個基于4模集合{2ⁿ，2²ⁿ+1，2ⁿ+1，2ⁿ-1}的反向轉換以及比例轉化的硬件結構圖如圖1所示。

3 性能評估和比較

    為了進行定性評估，本文與同樣對4模集合2n比例變換文獻[4]的理論模型進行對比。采用文獻[4]提出的門單位計算方法，用近似門單位模型方法計算其硬件以及信號處理延時，即2輸入異或門（XOR）或者同或門（XNOR）的面積和延遲按照2個單位計算，一個全加器（FA）等同于7個單位的面積和4個單位的延遲，非門（NOT）的面積和延遲都以0計算，其他基本的二輸入邏輯門面積和延遲按照1個單元計算。為了更加公平的對比，本研究和文獻[4]所有的模2ⁿ-1加法器均采用目前最優化的0唯一表示的并行前綴模2ⁿ-1加法器^[6]，縮一碼模2ⁿ+1加法器采用文獻[7]提出的模加法器模型。提出的新的比例變換模型各個通道面積理論數據如表1所示，和其他模集合比例轉換器面積和延時對比如表2所示。從中可以看出，本文所提出的4比例變換器模型，在動態范圍大的情況下，在硬件復雜度方面占有絕對的優勢。

4 結論

    余數系統的比例變換是避免在剩余數系統的中間運算過程中發生溢出錯誤的主要方法。基于此，針對4模集合{2ⁿ，2²ⁿ+1，2ⁿ+1，2ⁿ-1}，在分析反向轉換和比例縮放算法的基礎上，提出了一個新的反向轉換和基于2n的比例縮放算法，并基于加法器實現其VLSI結構，使該模集合能夠得到更加廣泛的應用。理論分析結果表明，在具有相同模通道數的同類比例變換器中，本研究的算法更加優化，硬件性能表現更加優異。

參考文獻

[1] ANTONIO G，ANTONIO L.A look-up scheme for scaling in the RNS[J].IEEE Transactions on Computers，1999，48(7)：748-751.

[2] TAY T，CHANG C H，LOW J.Efficient VLSI implementation of 2n scaling of signed integer in RNS{2ⁿ-1，2ⁿ，2ⁿ+1，}[J].IEEE Transactions on Very Large Scale Integration(VLSI) Systems，2013，21(10)：1936-1940.

[3] YE Y，MA S，HU J.An efficient 2n RNS scaler for moduliset{2ⁿ-1，2ⁿ，2ⁿ+1，}[C].IEEE Symp.Inf.Sci.Eng.(ISISE)，Shanghai，China，2008.12：511-515.

[4] SOUSA L.2n RNS Scalers for Extended 4-Moduli Sets[J].IEEE Transactions on Computers，2015，62(12)：1-14.

[5] CAO B，CHANG C H，SRIKANTHAN T.A residue-to-binary converter for a new five-moduli set[J].IEEE Transactions on Circuits and Systems-I，2007，54（5）：1041-1049.

[6] PATEL R A，BENAISSA M，BOUSSAKTA S.Fast parallelprefix architectures for modulo 2n-1 Addition with a single representation of zero[J].IEEE Transactions on Computers，2007，56(11)：1484-1492.

[7] VERGOS H，EFSTATHIOU C，NIKOLOS D.Diminished-one modulo 2n+1 adder design[J].IEEE Transactions on Computers，2002，51(12)：1389-1399.

[8] Wang Yuke.Residue-to-binary converters based on new Chinese remainder theorems[J].IEEE Transactions.on Circuits and Systems-II，2000，47（3）：197-205.