[發明專利]一種基于二叉樹結構的有限域乘法器

在審

• 申請號: 201710095996.2
• 申請日: 2017-02-22
• 公開（公告）號: CN106909339A
• 公開（公告）日: 2017-06-30
• 發明（設計）人: 易海博;聶哲
• 申請（專利權）人: 深圳職業技術學院
• 主分類號: G06F7/52
• 分類號: G06F7/52
• 代理公司: 深圳市科吉華烽知識產權事務所(普通合伙)44248
• 代理人: 溫玉珍

1.一種基于二叉樹結構的有限域乘法器，其特征在于，包括：

輸入端口，用于輸入有限域GF(2ⁿ)的運算數a(x)和運算數b(x)；

輸出端口，用于輸出運算數a(x)和運算數b(x)的乘法結果c(x)；

以及，二叉樹結構，用于執行運算數a(x)和運算數b(x)的GF(2ⁿ)乘法運算；

其中，二叉樹結構包括n+1層，從上至下，第一層至第n層包括左二叉樹和右二叉樹，最下面一層為第n+1層；第n+1層的每個節點與第n層的三個節點相連。

2.根據權利要求1所述的基于二叉樹結構的有限域乘法器，其特征在于，所述左二叉樹和右二叉樹中，左根節點和左孩子節點代表數值0，右根節點和右孩子節點代表數值1；所述左二叉樹和右二叉樹中，除葉子節點外的每一個節點均與下一層的兩個孩子節點相連，所述下一層的兩個孩子節點中，左邊的節點為左孩子節點，右邊的節點為右孩子節點。

3.根據權利要求1所述的基于二叉樹結構的有限域乘法器，其特征在于，二叉樹結構的第一層至第n層中，從第一層的節點到第n層的節點的每條路徑代表有限域GF(2ⁿ)的一個元素。

4.根據權利要求1所述的基于二叉樹結構的有限域乘法器，其特征在于，在二叉樹結構中，第n+1層的每個節點代表兩個有限域元素的乘法結果。

5.根據權利要求1所述的基于二叉樹結構的有限域乘法器，其特征在于，在二叉樹結構中，第n層的每兩個節點與第n+1層的一個節點相連；若從第一層的節點到第n層的節點n_i的一條路徑代表有限域GF(2ⁿ)的元素i，從第一層的節點到第n層的節點n_j的一條路徑代表有限域GF(2ⁿ)的元素j，第n+1層的節點n_k代表GF(2ⁿ)的乘法運算i×j的結果，那么第n層的節點n_i和節點n_j分別與第n+1層的節點n_k相連。

6.根據權利要求5所述的基于二叉樹結構的有限域乘法器，其特征在于，在二叉樹結構中，若從第一層的節點到第n層的節點n_t的一條路徑代表有限域GF(2ⁿ)的元素t，當第n+1層的節點n_k代表的兩個有限域元素的乘法結果是t時，第n+1層的節點n_k與第n層的節點n_t相連。

7.根據權利要求1至6任意一項所述的基于二叉樹結構的有限域乘法器，其特征在于，所述二叉樹結構包括樹節點和樹節點之間的連線。

8.根據權利要求1至6任意一項所述的基于二叉樹結構的有限域乘法器，其特征在于，運算數a(x)的表現形式為a(x)＝a_n-1x^n-1+a_n-2x^n-2+...+a₀；運算數b(x)的表現形式為b(x)＝b_n-1x^n-1+b_n-2x^n-2+...+b₀；其中，a_n-1,a_n-2,...,a₀,b_n-1,b_n-2,...,b₀均是GF(2)的元素；乘法結果c(x)的表現形式為c(x)＝c_n-1x^n-1+c_n-2x^n-2+...+c₀，其中，c_n-1,c_n-2,...,c₀均是均是GF(2)的元素。