[發(fā)明專利]一種生成伽羅華域乘法器電路的方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 201210525538.5
• 申請(qǐng)日: 2012-12-07
• 公開（公告）號(hào): CN103870239A
• 公開（公告）日: 2014-06-18
• 發(fā)明（設(shè)計(jì)）人: 劉會(huì)娟;蘇志強(qiáng)
• 申請(qǐng)（專利權(quán)）人: 北京兆易創(chuàng)新科技股份有限公司
• 主分類號(hào): G06F7/72
• 分類號(hào): G06F7/72
• 代理公司: 北京安信方達(dá)知識(shí)產(chǎn)權(quán)代理有限公司 11262
• 代理人: 栗若木;曲鵬

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

本發(fā)明涉及電路領(lǐng)域，尤其涉及一種生成伽羅華域乘法器電路的方法及裝置。

背景技術(shù)

伽羅瓦域(GF)中元素的乘法被廣泛應(yīng)用在編碼和解碼系統(tǒng)中。例如通訊系統(tǒng)或存儲(chǔ)系統(tǒng)中的里德-索羅門(RS)編碼和解碼以及BCH(Bose、Ray-Chaudhuri與Hocquenghem的縮寫)的編碼和解碼等。尤其在存儲(chǔ)系統(tǒng)中，需要用硬件電路來(lái)實(shí)現(xiàn)伽羅瓦域乘法器。

在伽羅瓦域中，一個(gè)二元域的擴(kuò)域用GF(2^m)表示。GF(2^m)中的本原元素可設(shè)為α，元素可表示為αⁱ，其中i是大于或等于0的正整數(shù)。當(dāng)i大于或等于m時(shí)，αⁱ可用α⁰～α¹²的線性表達(dá)式來(lái)表示，即表示成多項(xiàng)式的形式，即伽羅瓦域中的元素都可表示為次數(shù)為m-1次的m個(gè)元素相加的多項(xiàng)式形式。例如GF(2⁴)中(m＝4)的元素α²⁰可用多項(xiàng)式形式表示為α²⁰＝0×α³+1×α²+1×α¹+0×α⁰。提取多項(xiàng)式的系數(shù)，表達(dá)為矩陣形式則為：α²⁰＝[0110]，最高次數(shù)為m-1。

根據(jù)以上描述，可知當(dāng)兩個(gè)元素相乘時(shí)，就可表示成兩個(gè)矩陣形式的多項(xiàng)式相乘。伽羅瓦域中的元素相乘分為兩個(gè)步驟，首先將兩個(gè)多項(xiàng)式按照實(shí)數(shù)域中多項(xiàng)式相乘的方式得到一個(gè)乘積，此乘積的多項(xiàng)式的最高次數(shù)小于或等于2(m-1)。其次再根據(jù)轉(zhuǎn)換規(guī)則轉(zhuǎn)換為m-1次的多項(xiàng)式形式。所以在硬件電路實(shí)現(xiàn)時(shí)，伽羅瓦域的乘法器包含兩個(gè)部分，一個(gè)是乘法器部分，一個(gè)是轉(zhuǎn)換器部分，電路比較復(fù)雜，消耗的硬件比較多。

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

本發(fā)明要解決的技術(shù)問(wèn)題是如何生成簡(jiǎn)單的伽羅華域乘法器電路。

為了解決上述問(wèn)題，本發(fā)明提供了一種生成伽羅華域乘法器電路的方法，包括：

將進(jìn)行乘法運(yùn)算的兩個(gè)伽羅瓦域元素分別轉(zhuǎn)換為多項(xiàng)式；對(duì)轉(zhuǎn)換得到的兩個(gè)多項(xiàng)式進(jìn)行實(shí)數(shù)域的多項(xiàng)式乘法，將乘法結(jié)果轉(zhuǎn)換為乘積多項(xiàng)式；

當(dāng)上述兩個(gè)多項(xiàng)式中的一個(gè)已知時(shí)，將該多項(xiàng)式各系數(shù)的值代入所述乘積多項(xiàng)式，將所述乘積多項(xiàng)式轉(zhuǎn)換為另一個(gè)多項(xiàng)式的系數(shù)相加的轉(zhuǎn)換式；

根據(jù)該轉(zhuǎn)換式生成邏輯電路，具體包括：為所述轉(zhuǎn)換式中的多項(xiàng)式的系數(shù)各設(shè)立一個(gè)輸入端；為所述轉(zhuǎn)換式中的加運(yùn)算各設(shè)立一個(gè)對(duì)應(yīng)的門電路，各門電路的輸出端用于輸出該門電路兩個(gè)輸入端信號(hào)的加運(yùn)算結(jié)果，將各門電路的兩個(gè)輸入端分別連接到該門電路所對(duì)應(yīng)的加運(yùn)算的加數(shù)和被加數(shù)。

進(jìn)一步地，將門電路的兩個(gè)輸入端分別連接到該門電路所對(duì)應(yīng)的加運(yùn)算的加數(shù)和被加數(shù)是指：

當(dāng)該門電路所對(duì)應(yīng)的加運(yùn)算的加數(shù)/被加數(shù)為多項(xiàng)式的系數(shù)時(shí)，將門電路的相應(yīng)輸入端連接到為該多項(xiàng)式的系數(shù)設(shè)立的輸入端；當(dāng)該門電路所對(duì)應(yīng)的加運(yùn)算的加數(shù)/被加數(shù)為另一加運(yùn)算的結(jié)果，將門電路的相應(yīng)輸入端連接到為該另一加運(yùn)算設(shè)立的門電路的輸出端。

進(jìn)一步地，在根據(jù)該轉(zhuǎn)換式生成邏輯電路的步驟后，還包括：將該邏輯電路轉(zhuǎn)換為硬件電路。

進(jìn)一步地，所述門電路為異或門。

本發(fā)明還提供了一種生成伽羅華域乘法器電路的裝置，包括：

乘運(yùn)算模塊，用于將進(jìn)行乘法運(yùn)算的兩個(gè)伽羅瓦域元素分別轉(zhuǎn)換為多項(xiàng)式；對(duì)轉(zhuǎn)換得到的兩個(gè)多項(xiàng)式進(jìn)行實(shí)數(shù)域的多項(xiàng)式乘法，將乘法結(jié)果轉(zhuǎn)換為乘積多項(xiàng)式；

轉(zhuǎn)換模塊，用于當(dāng)上述兩個(gè)多項(xiàng)式中的一個(gè)已知時(shí)，將該多項(xiàng)式各系數(shù)的值代入所述乘積多項(xiàng)式，將所述乘積多項(xiàng)式轉(zhuǎn)換為另一個(gè)多項(xiàng)式的系數(shù)相加的轉(zhuǎn)換式；

邏輯電路生成模塊，用于根據(jù)該轉(zhuǎn)換式生成邏輯電路，具體包括：為所述轉(zhuǎn)換式中的多項(xiàng)式的系數(shù)各設(shè)立一個(gè)輸入端；為所述轉(zhuǎn)換式中的加運(yùn)算各設(shè)立一個(gè)對(duì)應(yīng)的門電路，各門電路的輸出端用于輸出該門電路兩個(gè)輸入端信號(hào)的加運(yùn)算結(jié)果，將各門電路的兩個(gè)輸入端分別連接到該門電路所對(duì)應(yīng)的加運(yùn)算的加數(shù)和被加數(shù)。

進(jìn)一步地，所述邏輯電路生成模塊將門電路的兩個(gè)輸入端分別連接到該門電路所對(duì)應(yīng)的加運(yùn)算的加數(shù)和被加數(shù)是指：

所述邏輯電路生成模塊當(dāng)該門電路所對(duì)應(yīng)的加運(yùn)算的加數(shù)/被加數(shù)為多項(xiàng)式的系數(shù)時(shí)，將門電路的相應(yīng)輸入端連接到為該多項(xiàng)式的系數(shù)設(shè)立的輸入端；當(dāng)該門電路所對(duì)應(yīng)的加運(yùn)算的加數(shù)/被加數(shù)為另一加運(yùn)算的結(jié)果，將門電路的相應(yīng)輸入端連接到為該另一加運(yùn)算設(shè)立的門電路的輸出端。

進(jìn)一步地，所述的裝置還包括：