[發(fā)明專利]一種迦羅華域乘法器

無效

• 申請(qǐng)?zhí)枺?/td>: 200910142713.0
• 申請(qǐng)日: 2009-05-31
• 公開（公告）號(hào): CN101901127A
• 公開（公告）日: 2010-12-01
• 發(fā)明（設(shè)計(jì)）人: 李宇飛;陸泳;葉光昶;周凡
• 申請(qǐng)（專利權(quán)）人: 國(guó)際商業(yè)機(jī)器公司
• 主分類號(hào): G06F7/72
• 分類號(hào): G06F7/72
• 代理公司: 中國(guó)國(guó)際貿(mào)易促進(jìn)委員會(huì)專利商標(biāo)事務(wù)所 11038
• 代理人: 李鎮(zhèn)江

技術(shù)領(lǐng)域

本發(fā)明涉及通信領(lǐng)域使用的集成電路的設(shè)計(jì)，具體來說，涉及一種迦羅華域乘法器的集成電路設(shè)計(jì)。

背景技術(shù)

迦羅華域乘法器(Galois?field?multiplier)是一類特殊的乘法器，其所有的計(jì)算都是建立在有限域上的，因此也稱有限域乘法器。迦羅華域乘法器在編碼、糾錯(cuò)、加密等通信領(lǐng)域得到了廣泛的應(yīng)用。

有一些處理器可以實(shí)現(xiàn)迦羅華域乘法的功能，采用邏輯模塊也可以進(jìn)行迦羅華域乘法，或者傳統(tǒng)的數(shù)字信號(hào)處理器也可以被用于實(shí)現(xiàn)迦羅華域乘法，但是這些方案上的迦羅華域乘法計(jì)算復(fù)雜，需要消耗大量的時(shí)間。鑒于其應(yīng)用的廣泛性，迦羅華域乘法器目前常常被實(shí)現(xiàn)為一個(gè)電路，一般為微電子集成電路，以期達(dá)到高效處理的目的。作為集成電路本身，設(shè)計(jì)者一般希望設(shè)計(jì)的電路面積越小越好，這樣可以節(jié)省成本。

現(xiàn)有技術(shù)中，迦羅華域乘法器的集成電路設(shè)計(jì)主要包括Bit-serial、digit-serial和Bit?parallel三種方法。

Bit-serial和digit-serial方法指在迦羅華域乘法器輸入乘數(shù)與被乘數(shù)時(shí)，按照位為單位串行輸入。其優(yōu)點(diǎn)為硬件面積、設(shè)計(jì)復(fù)雜度小，當(dāng)計(jì)算GF(2^m)的乘法時(shí)，Bit-serial和digit-serial兩種方法的邏輯面積為O(m)，但Bit-serial方法的乘法輸出結(jié)果的響應(yīng)時(shí)間(latency)較大，為m個(gè)時(shí)鐘周期。

Bit?parallel方法指在Galois域乘法器輸入乘數(shù)與被乘數(shù)時(shí)，按照實(shí)際乘數(shù)與被乘數(shù)位寬并行輸入。其優(yōu)點(diǎn)為乘法輸出結(jié)果的響應(yīng)時(shí)間(latency)較小，僅為1個(gè)時(shí)鐘周期，但硬件面積大，設(shè)計(jì)復(fù)雜度大，當(dāng)計(jì)算GF(2^m)的乘法時(shí)，Bit-Parallel方法的logic面積為O(m²)。但是現(xiàn)有的Bit-parallel一般針對(duì)特定的本原多項(xiàng)式進(jìn)行優(yōu)化，并且很多方案主要集中在三項(xiàng)多項(xiàng)式，即本原多項(xiàng)式，P(x)＝x⁴+x+1，這樣的設(shè)計(jì)缺乏通用性。

因此，需要設(shè)計(jì)一種硬件面積小，設(shè)計(jì)簡(jiǎn)單，響應(yīng)時(shí)間小，并且具有通用性的迦羅華域乘法器。

發(fā)明內(nèi)容

為了克服背景技術(shù)中設(shè)計(jì)的迦羅華域乘法器的不足，本發(fā)明提供了一種迦羅華域乘法器，該迦羅華域乘法器硬件面積小，響應(yīng)時(shí)間小，通用性強(qiáng)。

根據(jù)本發(fā)明的一個(gè)方面，提供了一種迦羅華域乘法器，包括：乘法電路，用于輸入兩個(gè)具有m位的二進(jìn)制乘數(shù)，輸出其乘積，其中，所述乘法電路的輸出包括高位輸出與低位輸出，m為2的整數(shù)次冪；存儲(chǔ)器，用于存儲(chǔ)根據(jù)選擇的迦羅華域本原多項(xiàng)式計(jì)算出的迦羅華域乘法系數(shù)組；第一模塊，用于將所述乘法電路的輸出與所述存儲(chǔ)器存儲(chǔ)的迦羅華域乘法系數(shù)組進(jìn)行運(yùn)算，獲得所述兩個(gè)具有m位的二進(jìn)制乘數(shù)的迦羅華域乘法的結(jié)果。

附圖說明

通過對(duì)附圖中本發(fā)明示例實(shí)施例方式的更詳細(xì)描述，本發(fā)明的上述、以及其它目的、特征和優(yōu)勢(shì)將變得更加明顯，其中，相同的參考標(biāo)號(hào)通常代表本發(fā)明示例實(shí)施例方式中的相同部件。

圖1示意性地示出了一種迦羅華域乘法器的電路；

圖2示意性地示出了一種求取兩個(gè)具有m位的二進(jìn)制乘數(shù)乘積的乘法電路；以及

圖3示意性地示出了圖2中第三模塊的更具體實(shí)施方式。

具體實(shí)施方式

將參照附圖更加詳細(xì)地描述本發(fā)明的優(yōu)選實(shí)施方式，在附圖中顯示了本發(fā)明的優(yōu)選實(shí)施例。然而，本發(fā)明可以以各種形式實(shí)現(xiàn)而不應(yīng)該理解為被這里闡述的實(shí)施例所限制。相反，提供這些實(shí)施例是為了使本發(fā)明更加透徹和完整，并且，完全將本發(fā)明的范圍傳達(dá)給本領(lǐng)域的技術(shù)人員。

為了更好地理解本發(fā)明，這里首先給出一些迦羅華域乘法基本知識(shí)。

迦羅華域GF(x)是一組在其上可進(jìn)行二進(jìn)制運(yùn)算的元素，加法和乘法必須滿足交換律、結(jié)合律和分配律。

迦羅華域上的乘法被定義為：

Mod{AB/P(x)}(1)

其中，A與B為兩個(gè)乘數(shù)，AB表示這兩個(gè)數(shù)相乘，P(x)為迦羅華域的本原多項(xiàng)式。x為迦羅華域的本原元。Mod表示求模計(jì)算。

以下為了敘述方便，所有AB或A·B的形式都表示兩個(gè)數(shù)的傳統(tǒng)乘法，只有Mod{AB/P(x)}才表示迦羅華域上的乘法，本說明書不再逐一解釋。

現(xiàn)有技術(shù)中有若干方法用于實(shí)現(xiàn)迦羅華域乘法，本發(fā)明關(guān)注其電路的實(shí)現(xiàn)。電路實(shí)現(xiàn)的好處在于速度更快，在通信的編碼、加密、糾錯(cuò)等領(lǐng)域需要更快的響應(yīng)速度，只有應(yīng)用電路的實(shí)現(xiàn)才能達(dá)到要求。

如果A與B均為m位的二進(jìn)制數(shù)，并且