[發明專利]一種基于多級查表的壓縮伽羅華域的執行方法及系統

有效

• 申請號: 200810100117.1
• 申請日: 2008-05-22
• 公開（公告）號: CN101587433A
• 公開（公告）日: 2009-11-25
• 發明（設計）人: 程作仁
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: G06F7/72
• 分類號: G06F7/72;G06F1/035
• 代理公司: 北京安信方達知識產權代理有限公司
• 代理人: 龍 洪;霍育棟

技術領域

本發明涉及集成電路設計領域、FPGA(現場可編程門陣列)設計領域以及通訊領域，尤其涉及一種基于多級查表的壓縮伽羅華域的執行方法及系統。

背景技術

通訊系統中進行RS(里德-所羅門)編碼和高級加密都廣泛采用了伽羅華域中的具有系數的多項式乘法。傳統方法采用采用先乘后取模的方式或者單級乘取模的方式實現，傳統方法占用周期較多且實現較復雜，為了避免傳統方法的這種缺點，專利CN200580045323.1提出一種利用查找表代替求模的方法，可以大幅減少運算周期，但是其查找表會隨著伽羅華域的增大而指數級增大，例如對于伽羅華域GF(2⁸)來說，所需查找表空間為2⁷＝128，而對于伽羅華域GF(2¹⁶)來說，其查找表空間將達到2¹⁵＝32768，該專利的方法在伽羅華域空間較大時使用將會受限，因此需要一種新的方法以降低查找表占用空間的問題。

發明內容

本發明所要解決的技術問題是提供一種基于多級查表的壓縮伽羅華域的執行方法及系統，有效地降低查找表的占用空間，提高了系統的效率。

為了解決上述問題，本發明提供了一種基于多級查表的壓縮伽羅華域的執行系統，用于通訊系統，

包括多項式乘法器模塊、多級查表模塊、域加模塊，其中，

多項式乘法器模塊：用于在伽羅華域上將帶有系數的第一和第二多項式相乘來獲得它們的乘積值，輸入多級查表模塊；

多級查表模塊：用于將多項式乘法器模塊輸入的多項式的乘積值進行分級，通過分級查表的方式將獲得的數值輸入域加模塊；

域加模塊：用于根據多級查表模塊中分級比特位和分級層次的不同，將多級查表模塊輸入的數值進行位異或操作獲得最終值。

進一步地，上述執行系統還可包括，所述多項式乘法器模塊是通過與門、異或門來實現硬件的構建。

進一步地，上述執行系統還可包括，所述多級查表模塊的多級查表中的表是指同一個表，每一級查表只是對應地址的變化。

進一步地，上述執行系統還可包括，所述多級查表模塊中所述分級的方式包括以4比特、8比特、3比特、或5比特作為分級的分級方式。

進一步地，上述執行系統還可包括，所述多級查表模塊中，所述分級查表的方式包括兩級查表的方式。

本發明還提供了一種基于多級查表的壓縮伽羅華域的執行方法，用于通訊系統，包括，

在伽羅華域上將帶有系數的第一和第二多項式相乘來獲得它們的乘積值；

將多項式乘法器模塊輸入的多項式的乘積值進行分級，通過分級查表的方式獲得數值，并根據分級比特位和分級層次的不同，將該獲得的數值進行位異或操作獲得最終值。

進一步地，上述執行方法還可包括，所述多級查表中的表是指同一個表，每一級查表只是對應地址的變化。

進一步地，上述執行方法還可包括，所述將多項式乘法器模塊輸入的多項式的乘積值進行分級中所述分級的方式，包括以4比特、8比特、3比特、或5比特作為分級的分級方式。

進一步地，上述執行方法還可包括，所述分級查表的方式包括兩級查表的方式。

與現有技術相比，應用本發明，有效地降低查找表的占用空間，提高了系統的效率。

附圖說明

圖1是本發明的基于多級查表的壓縮伽羅華域的執行系統的結構示意圖；

圖2是本發明的基于多級查表的壓縮伽羅華域的執行方法的流程圖。

具體實施方式

下面結合附圖和具體實施方式對本發明作進一步說明。

本發明的主要構思是：本發明是在專利CN200580045323.1基礎上作的進一步改進，因而兩者基本結構相同，不同之處主要在于，當域的空間增大時，其查找表的空間呈指數級增長，因此在查表中本發明通過分級查表的方式，大幅度的減少了查表的空間，節省了資源，提高了效率，通常分級以4比特或8比特為基本單位。

本發明的壓縮伽羅華域的執行系統可以分為以下幾個部分，包括多項式乘法器模塊、多級查表模塊、域加模塊，用于通訊系統中編碼和加密，其裝置結構見圖1。

多項式乘法器模塊：用于在伽羅華域上將帶有系數的第一和第二多項式相乘來獲得它們的乘積值，輸入多級查表模塊；

本模塊的目的是計算兩個輸入域內數的乘積，以GF(2⁸)計算為例，其輸入為8個比特數據，假設分別為：

m1＝{a7a6a5a4a3a2a1a0}

m2＝{b7b6b5b4b3b2b1b0}