[發明專利]一種RNS比較器

無效

• 申請號: 201210418373.1
• 申請日: 2012-10-29
• 公開（公告）號: CN102930097A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 李磊;周璐;周婉婷;劉輝華
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 成都宏順專利代理事務所(普通合伙) 51227
• 代理人: 周永宏

技術領域

本發明屬于計算機和集成電路領域，尤其涉及一種余數系統的比較器的設計。

背景技術

在介紹比較器之前，先對余數系統(RNS，Residue?Number?Systems)做一說明。余數系統RNS是一種通過一組兩兩互質余數基的余數來描述數字的數值表征系統。由{m₁,m₂,…,m_L}組成的L個余數基，整數X，0≤X<M，其中M=m₁×m₂×…×m_L，在RNS系統中有唯一的表示方式為X={x₁,x₂,…,x_L}，其中表示X對于模m_i的余數。在余數系統中兩個操作數進行操作，操作符為Θ，可以定義為：

{z₁,z₂,…,z_L}={x₁,x₂,…,x_L}Θ{y₁,y₂,…,y_L}，其中這里Θ可以是模加法，模減法或模乘法。在余數系統中這些算術運算都是并行執行的，而且處理的都是很小的余數而不是一個很大的數。

對于余數基的選擇，{2ⁿ,2ⁿ-1,2ⁿ+1}是非常重要的運算通道，得到了廣泛的應用，因為當考慮area×time²時，它們提供了最有效的電路，并且在余數系統與二進制的互轉過程中也是最有效的。數值之間的比較，是運算系統中經常遇到的問題，因此對于面向{2ⁿ,2ⁿ-1,2ⁿ+1}的RNS比較器的研究是非常有意義的。

比較有效的兩種比較器是參考文獻E.Gholami,R.Farshidi,M.Hosseinzadeh,and?H.Navi,“High?speed?residue?number?system?comparison?for?the?moduli?set{2n,2n-1,2n+1},”J.Commun.Comput.,vol.6,no.3,pp.40–46，March?2009.和S.T.Eivazi,M.Hosseinzadeh,and?O.Mirmotahari,“Fully?parallel?comparator?for?the?moduli?set{2n,2n-1,2n+1},”IEICE?Electronics?Express,vol.8,no.12,pp.897-901,June?2011分別提出的比較器。但是兩種方法都是把需要比較的余數轉化為二進制數進行再比較，從而需要兩個余數系統到二進制系統的轉化器，帶來了耗費資源和速度較低的問題，而且后面的比較過程相對復雜。

發明內容

本發明的目的是為了解決現有的面向{2ⁿ,2ⁿ-1,2ⁿ+1}的RNS比較器耗費資源和速度較低的問題，提出了一種面向{2ⁿ,2ⁿ-1,2ⁿ+1}的RNS比較器。

本發明的技術方案是：一種RNS比較器，包括：第一n位反相器陣列，模2ⁿ加法器，第二n位反相器陣列，模2ⁿ-1加法器，第一n+1位反相器陣列，模2ⁿ+1加法器，第三n位反相器陣列，第二n+1位反相器陣列，二輸入異或門，第一帶循環進位的進位存儲加法器，第二帶循環進位的進位存儲加法器，2n位二進制加法器，第一運算模塊，第二運算模塊，第一1位反相器，第二1位反相器，二輸入與門；

設A和B為所述比較器的輸入，其中，A={a1,a2,a3}，B={b1,b2,b3}，a1、a2、b1、b2為n位，a3、b3為n+1位；(A=B)、(A<B)和(A>B)為所述比較器的輸出；

具體連接關系如下：

所述第一n位反相器陣列的輸入端用于輸入所述RNS比較器的輸入B的對應余數b1，所述第一n位反相器陣列的輸出為