TWI325560B - - Google Patents

Description

j32556〇 九、發明說明：【發明所屬之技術領域】

正替換頁

本發明係提供一種具即時偵錯能力之位元 ^亚列輸出型 心臟收縮陣列式雙重基底乘法器，尤指一種庫 碼用於有限場 GF(2。’具即時性錯誤偵測能力之乘法器之創新技術。 【先前技術】 按，目前我國揭露於中華民國專利公報中的『乘 相關發明專利技術’較相關者概可列舉如下： ’ 1、公告編號第382088號『有限場GF(2m)的細胞陣列 次方和電路』發明專利案。 2、 公告編號第440789號『乘法器』發明專利案。 3、 公告編號第255957號『t位元半平行處理式林羅 瓦場乘法器之設計方法』發明專利案。 4、 公告編號第360845號『陣列式乘法器架構及其方 法』發明專利案。

5、公告編號第405086號『快速正規乘法器架構 明專利案。 替 在有限場GF(2m)中，有效的代數運算（含加法' 乘法、 除法'及指數等運算）已廣泛地被應用於錯誤更正碼和密 瑪技術’舉凡_一進位BCH碼（BinaryBCHCode)之解碼、 RS碼（Reed_s〇l〇mon Code)之編碼與解碼及在安全通信 (Secure Communication)上數位信息的加密（Encryption) 與解密（Decryption)等。 儘管如此’有現場GF (2m)的乘法及乘法反元素的運算 5 1325560 %9.月1 · 5?簦正替換頁 仍然相當複雜；針對有V 法運算陸續有學 者提出快速演算法及快速電路’例如it〇h Tsujii、 Sunar-Koc、Hasan等，這些乘法器架構均基於特殊的多項 式’匕包括全一多項式（All-One Polynomial’AOP)、等距 多項式（Equally-Spaced Polynomial, ESP)和三項多項式 (Trinomial)。 另外’有學者Guo和Wang發展二段式乘法器，這是 使用一般乘法單元和降次方的處理單元所構成的；儘管上 面所述低複雜度乘法器是很適合於密碼技術，但其電路結 構並非心臟收縮陣列式電路，因此，假若m很大，即會產 生很長的傳播延遲。 有關低複雜度乘法器可以參考下列文獻： [1] D. E. R. Denning, Cryptography and Data Security,

Reading, MA: Addison-Wesley, 1983.

[2] Μ. Y. Rhee, Cryptography and Secure Communications, McGraw-Hill, Singapore, 1994.

[3] T. Itoh and S. Tsujii, "Structure of Parallel Multipliers for a Class of Finite Fields GF(2m),'' Information and

Computation, Vol. 83, pp. 21-40, 1989.

[4] C. K. Koc and B. Sunar, "Low Complexity Bit-Parallel

Canonical and Normal Basis Multipliers for a Class of Finite Fields," IEEE Trans. Computers, Vol. 47, No. 3, PP. 353-356, Mar. 1998. 1325560 [5] B. Sunar • Trinomials 普正替換貞· and C.K. Koc, "Mastrovito Multiplier for All IEEE Trans. Computers, Vol. 48, No. 5, PP. 522-527, May 1999.

[6] J. H. Guo and C.L. Wang, "Low-Complexity Power-Sum Circuit for GF(2m) and Its Applications", IEEE Trans. Circuits and Systems-II, Vol. 47, No. 10, PP. 1091-1097, Oct. 2000.

[7] M· A. Hasan, M. Wang, V. K. Bhargava, ^Modular

construction of low complexity parallel multipliers for a class of finite fields GF(2m)，” IEEE Trans. Computers, Vol_41, No.8, pp.962-971，August 1992. 在超大型積體電路技術（VLSI )中，陣列式處理器具 有簡單和規則的電路系統，包括三個類型電路架構：心臟 收縮（Systolic )、細胞（Cellular )和管道（Pipeline );陣 列式處理器的優點是可定義成一個基本細胞（Basic ceu ) 或者一些細胞。對於有限場GF(2m)的現存心臟收縮陣列乘 法器大多數基於兩種演算法：最低位元處理優先（Least significant bit first)陣列及最高位元處理優先（M〇st significant bit first)陣列來計算有限場的兩個元素之乘 積。這些乘法器適合在錯誤更正碼方面的應用，但是，這 些心臟收縮陣列乘法器就密碼應用而言，則具有很複雜的 電路和較長的計算延遲。例如Wei的乘法器的等待時間需 要3xm脈波延遲；（511〇_〜&11§的乘法器之等待時間則需要 7 1325560 备9Λ· Ff 正替換頁 2.5 xm 脈波延遲。 --—---一。一- 對於有限場GF(2m)，元素的表示式主要包含有多項式 基底（Polynomial bas is )(或稱為標準基底（Standard basis))、雙重基底（Dual basis )和正規基底（Normal basis)。在雙重基底中，根據線牲回饋，串聯式Beriekamp 乘法器能夠很有效地被實現^ Wang發展了另外一類型的雙 重基底乘法器，其係使用自身雙重的正規基底（Self-dual normal basis )。前不久，Wu-Hasan-Blake使用雙重基底來 設計低複雜度位元並列輸出型乘法器。Fenn則提出了雙重 和標準基底之間的轉換關係，他也提出位元並列輸出和串 列型的雙重基底乘法器。 相關的心臟收縮乘法器可以參考下列文獻： [1] S. W. Wei, "A Systolic Power-Sum Circuit for GF(2m)," IEEE Trans. Computers, Vol. 43, No. 2，PP. 226〜229,

Feb. 1994. ^ [2] C. S. Yeh, S. Reed, and T. K. Truong, "Systolic

Multipliers for Finite Fields GF("2W；," IEEE Trans. Computers, Vol. C-33, PP. 3 57-360, Apr. 1984.

[3] C. Y. Lee, E. H. Lu, and J. Y. Lee, "Bit-Parallel Systolic Multipliers for GF(2m) Fields Defined by All-One and Equally- Spaced Polynomials," IEEE Trans. Computers, No. 5, PP. 3 85-393, May 2001.

[4] C.Y. Lee, E.H. Lu, and L.F. Sun, "Low-Complexity 8 1325560 9%Α\ιΨ

Bit-Parallel Systolic Architectures for Computing AB2 + C in a Class of Finite Field GF(2m) ", IEEE Trans. CS-II，No. 5, PP. 5 19-523, May 2001.

[5 ] C.Y. Lee and C. W. Chiou, "Design of low-complexity bit-parallel systolic Hankel multipliers to implement multiplication in normal and dual bases of GF(2m)," IEICE Tran. Fund., vol. E 8 8 - A, no.11, pp. 3 1 69-3 1 79, Nov. 2 0 0 5.

[6] C.Y. Lee, J.S. Horng and I. C. Jou, "Low-complexity bit-parallel systolic Montgomery multipliers for special classes of GF(2m)，" IEEE Trans. Computers, vol. 54，no. 9, pp. 1 06 1 - 1070, Sep. 2005. 在超大型積體電路技術（VLSI )設計中，分佈於有限 域GF(2m)之心臟收縮陣列式結構基本上適合於快速計 异’並且依靠規則性電路去執行算術運算，他們的共通性 質提供結構特性，例如一致性、輸入/輸出平衡和簡單且 有規則的設計。從超大型積體電路技術（VLSI)技術觀點， 半導體製造商努力保證他們的產品是可靠的，然而在系統 任何時間中幾乎不可能沒有錯誤；一個在估計可靠性基本 的問題是在已知時間的週期、環境及規定的方法中任—個 系統功能’因此’如何在運用於GF(2m)位元並列輸出型 9 1325560

# 9教乂 g修正替換與I 心臟收縮陣列式的乘法器上加賓^技術能 力，將是非常重要的。 為達到輪出無錯誤，許多錯誤偵測結構如對稱的密碼系 統和不對稱的密碼系統已經有許多的報告發表出來。Fenn 等提議一種即時.偵測方法，係使用奇偶同位元預測結構於 位元串列輸出型GF(2m)乘法器。藉由使用相同的奇偶同 位兀偵測結構，Reyhani_Masoleh和Hasan提供錯誤偵測 方法在GF(2m)位元並列輸出型和位元串列.輸出型多項式 基底乘法器，其主要的問題在使用奇偶同位元偵測會花費 長時間來產生同位元；因此，這種方法不被允許提供位元 並列輸出型心臟收縮陣列式乘法器即時偵測能力，為了解 決這個問題，Chiou使用位移重計算（rES⑺方法提供全一 的多項式基底乘法器即時錯誤偵測能力。 令人遺憾’不可簡約的全一多項式非常稀有。假如m 小於和等於1 Q 0，只有1 3個數值存在。 相關具有即時錯誤偵測能力之乘法器可以參考下 列文獻： [1] S. Fenn, M. Gossel, M. Benaissa, and D. Taylor, "On-line error detection for bit-serial multipliers in GF(2m)," Journal of Electronic Testing: Theory and Applications, Vol.13, pp.29-40, 1998. 10 1325560 [2] A. Reyhani-Masoleh and M.A. Hasan, "Error detection in polynomial basis multipliers over binary extension ·· fields," Proc. of Cryptographic Hardware and Embedded • ‘ Systems-CHES 2002, LNCS 2523, pp.5 15-528, 2003. . [3] C. W. Chiou, "Concurrent error detection in array multipliers for GF(2m) fields," IEE Electronics Letters,

Vol.38, No.14, pp.688-689, July 2002. 緣是於此，本發明係在於提出了 一種具有即時性錯誤 φ 偵測能力的GF(2m)乘法器。 【發明内容】 在超大型積體電路（VLSI )設計，分佈於有限場領域 的GF(2 )心臟收縮陣列式結構基本上適合於快速計算，並 且依罪規則性電路去執行算術運算，其共通性質是提供結 構特性，例如一致性、輸入/輸出平衡和簡單和有規則的設 計。從VLSI技術觀點，半導體製造商努力保證他們的產 品是可靠的，但在系統中任何時間裡幾乎不可能沒有錯誤 產生；所以在已知時間的週期、環境及規定的方法中任一 個系統功能中，可靠性基本問題的估計是非常重要的，因 此，如何對分佈於GF(2m)位元並列輸出型心臟收縮陣列式 雙重基底乘法器提供即時錯誤 了碎兩偵測技術能力’將是本案的 目的0 為達上述之目的，本發明坦 月k出一種具即時偵錯能力之 位元並列輸出型心臟收縮陣 ’平^式雙重基底乘法器，其電路 11 1325560 y%·孔修正替換頁 一檢測裝置，用以控制資料編碼、 哪碼及抢碼技術之 錯誤檢測，該乘法器的電路特性；#斜右阳 竹庇你對有限場GF(2m)中之— . 第一元素A與一第二元素B進行乘籍道曾 祀叮人槓運鼻，以得到第三元 素C，纟中元素A是以多項式基底（1，<Λ 〇表示式1 -素Β及C是以雙重基底之表示式，該有限場GF(2m)為不可 分解之多項式所產生的，及α為該不可分解的多項式之 根，該弟一元素 Α.被表 + % 衣不為一 m 位元 ^:〜+巧^: +〜^^+八+〜-#"1-1，該第二元素姑主_达 ^反衣不為 1X1位元 5 = 6。爲+0丨户1+62爲+人+\_】凡_1’該第三元争（*1一 L散衣不為一 m位元 C'^+^+c^+A+k^，其中所有元素的係數是等於〇或 1’該乘法器包括有兩單元：

一雙重基底乘法單元，其電路句紅A 电吩a括由（m+l)xm個細 胞組成，以形成（m+ 1) xm陣列，且每— _ ^ 細胞包含有二個以

上輸入信號線、三個以上輸出信號線· ^ . , A π*深，母一細胞包含—個 以上AND閘、一·個以上XOR閘和= 〇 一個以上早位兀暫存器 # (Latch);及 —雙重基底轉換單元，其電路包括m.2_inputXQR 閑所構成。 法單元包含： 函數：計算6ro+i，和 其中，該乘法器的雙重基底乘 U細胞，係在第i列執行下列 % 4碼+^^,.+州，其中 OSG/w-2; 7=1 時 W細胞，其中在u和之兩者在U 係使用4個信號，6,，U，巧、和户， 細胞是最後計算 去完成6m+,計算的 12 1325560 --：--------Ί 8¾. 修正替換頁 錯誤檢測，其中匕在U-細胞的第（i-Ι)列被計算，特別是假 • 若i = 〇，貝1J Λ =怂時；且W細胞使用和&，其中在， .. 則是為了計算已預測的奇偶同位檢測4 ; V細胞，在最後列，Vm-丨，j細胞在執行0^5和尸c 兩者計算；此Vnm細胞需負算責任和整體乘法器 錯誤檢測。 其中，該乘法器在上述U、V和W細胞之一發生不良 時會發生單一陷入錯誤，並藉由該乘法器偵測出該錯誤。 Φ 其中，可檢測的錯誤包括：在巧上的錯誤，細胞uu 的輸出信號P7.，使用來自輸入信號的一通過線。 其中，可檢測的錯誤更包括：在上的錯誤，細胞uu 的輸出信號A，亦是來自輸入信號α,的通過線。 其中，可檢測的錯誤更包括：在6,.+7上的錯誤，細胞 Ui，j的輸出信號&.，也使用來自輸入信號的一通過線。 其中，可檢測的錯誤更包括：在上錯誤，細胞 Ui，j I 的輸出信號ζ，也使用來自輸入信號g的一通過線，因此其 上錯誤容易檢測出。 其中，可檢測的錯誤更包括：在c7.上的錯誤，假如一 個錯誤在不良的細胞Ui . j.的輸入信號c;上出現，該錯誤將 影響輸出信號&的最後結果，因此，計算在V-細胞C的奇 偶同位檢測位元，使用方程式尽能被計算，在W-細胞 y=〇 c的已預測奇偶同位檢測位元，使用方程式44被執 13 行’最後在Vm·^-細胞，比— 一~1 较貫際的奇偶同位檢測尸c和已 預測奇偶同位檢測4，這個扭 ΊΕΙ錯誤則檢測出。 其中，可檢測的錯誤爭6 包括：在，或‘上的錯誤， 假如一個錯誤在不良的細胞 ΰ ui，j.的輸入信號u上出現，這 個錯誤將影響輸出信號 . λ Λ Λ 6m+i，因此，使用方程式 、=心+之％+^„+,+办,’ \^在此 W. ixa nh At 細胞旎變成邏輯1，那就是 說此錯誤能被檢測出，且在， _ ^ 田胞Ui,j上4、錯誤也能使用方 程式\«=之,〆之,4+1,.+6,檢測出。

其中’可檢測的.錯誤更句杯·产έ a 又巴括.在乓或pc上錯誤，假如

一個錯誤在細胞Wi，m.的輸入 .W 1。现尸c上出現，則在.細胞Vm· j , m ’匕藉由應用方程式+P膝：磁Λ、，ra ) #、C 4+Pc將變成邏輯1，而能被檢測出 此錯，3在"V m 1 ·-么田fli?，D上/· 》 杜vm-M、..田胞’乓的輸出信號不良時，使用方 程式+々’亦能發現在乂心^的錯誤。 有關本發明所採用之技術、手段及其功效，兹舉一較 佳實施例並配合圖式詳細說明於后，相信本發明上述之目

的、構造及特徵，當可由之得一深入而具體的瞭解。 【實施方式】 【有限場GF(2m)簡介】 一，設有限場GF(2m)是由不可分解的多項式 P⑺+Λ-ιχβΜ+Λ +y>+/。所產生的，其中所有係數乂均為〇或 1。假設α是F(x)的一個根，GF(2m)的元素能夠 被表示如下： d + α,α+Λ + ua1"-1。 其中所有係數均為〇·或1且基底0，α，Λ 稱之為標準 基底或夕項式基底（Standard basis，Polynomial basis)。此 外’標準基底對應之雙重基底（Dual basis)的形式队，爲， 1325560 99'r-1 /]! 20 % 正替換頁 有下列特性：

Tr(ya^j)= if i = J if i^j

其中 7V(·)是轨跡函數（Trace function)，且；Ke GF(2m)， "0。對於hGF(2m)，乂 = 2叫,=2<成，其中α,和α;分別為元素 A的多項式基底與雙重墓底之對應 函數。從< e GF(2)，我們得到

Triya'fij) = Tr ] = Υ^α/Γ^γα1 β^= a] \ _/=0 ) >=〇 從F(a) = 0，我們可獲得下列關係式. m-\ m-1 /=0 /=0

.a2m~2 = ^ a1 /=0 其中所有係數都等於 1 或 〇。假設元素 5 = 60爲+'於+八足一是以雙重基底表示式，應用軌跡函數於方 程式（3)之兩邊可得

Tr(ja'B) - bn i = 0，l，八，m — 1 (4a) 及 15 1325560 /] im Τ>〇α’5) = [ /广m)~, ί = 7«，w + 1，Λ，2w - 2 (4b) 假設6 = 7>〇^5)，ζ· = 0,1，八，2m-2。假如元素C是兩元素A及 B之積，則有下列關係式

b〇 K Λ 〜 - Κ-ι α0 b2 Λ κ αι C1 M M 0 Μ Μ Μ K Λ ^2πι-2_ .am-\. 其中 6=7>〇^5) ( / = 0，1，八，2/«-2) ’ ο,·=7>〇α’〇 ( z=0，l，A，w-l)，且

AsXa〆。 /=0 從上述方程式，mxm矩陣被叫為 Hankel矩陣-向 量。為了探究分佈於GF(2m)位元並列輸出型雙重基底乘法 器，乘積C使用方程式（3 ) - ( 4 )能被寫成. 777—1 匸：叫召 + …㈤+八= ( 6 ) (=0 其中

C,. = α!Β = οί0β0 + οίλβ +Λ + > ct J = f{ya'+JB) = bi+J 如上所述，下列演算法可實現雙重基底乘法。 雙重基底乘法的演算法：

Input: A= [a〇, a j, ... B = [b〇,b}, ..., bm.]J and P = [p〇,pl, 1]

Output: C = [c〇, c}, ..., cm.]J=AB 16 1325560

For :0 to m- 1 ο 滅iiUg修正替換頁

For :0 to m-1 b m + i o

For j = 0 to

Cj = Cj + aibi+j bm + i^bi+jPj + b 根據上述湞真法，參閱第—圓& _ _ ,. 弟 圖所示’顯示位元並列輸

七塑心臟收縮陣列式雙重基底乘沐TO 出“ 士处留-々队Γ 去态（1 〇)，其包含m i目同的功此單凡細胞（2 0 )。而氣乂m 相妓-闰士 U』而母個功能單元細胞（2 0 ) 則如第一圖中所不，係包括二個2輪 一個2輸入X0R閘（2 2 )及士加 ainu闸^ j丄； 一 a .兮雷政+ i ± 個1位元栓閘（2 3 ) 所組ΐ要ί 脈週期的傳輸延遲，且每個細 胞是需要由一個2輸入AND閘f 9 Ί、

〇 9、月一你- J β /闸C 2 1 )、一個2輸入X0R 閘h)( 2 3 )的最大計算延遲。 此外’該又重基底乘法器由Fenn耸描q 甘* — Λ丨接舻雪路rvTST、从此从11等&議•’其·適於實現超大 变積體電：（VLSI)技術。然而，此乘 何錯誤。因此，為了解決這個問題， 悄刃任 位元偵測結構，使得乘法器呈i Li們可以使用奇偶同 r軍F:一 f: 益具有即時錯誤偵測能力。 【早一功此早兀細胞錯誤（singu_ce丨丨Fau…槿 在陣列電路中，使用的錯誤模型為單—功处 ，誤（Single_ce„ Fault)模型，亦即同時間允C 2細胞 :兀細胞失.效。卜個功能單元細胞失效的：，：個功能 從功能單元細胞的輸出埠的stuck-at fault:::為又 電路中〜成邏輯電路的功能失效，如信號線路的 17 1325560 斷路或短路、 1. stuck-at-l(s-a-l)錯誤型態 固定為邏輯1值。 2. stuck-at-l(s-a-O)錯誤型態 固定為邏輯0值。 根據上述陷入錯誤模型 C = A㊉B，若輸入信號a發生 值為C = J ;若輸入信號a發 出值為C = B。 坤.私响！正替換買 —~~—~---- 如邏輯電路的輸出信號值均 如邏輯電路的輸出信號值均 ’以2-input x〇R閘為例， s-a-l錯誤時，X0R閘的輪出 s-a-l錯誤時，x〇R閘的輪 本發明係使GFp"1)位元·^而丨& , 收縮陣列式 • 、 兀並列輸出型心 雙重基底乘法器具有即時錯誤偵測能力。 假叹早一功能早元細胞錯 也錯誤（Slngle-cell Fault)模 式。從先前的有限場說明在方程式（6)裡，此雙重基底 法包含兩種運算：狀況！由。—計算^的錯誤偵.. 和狀況2在原有的乘法上的铒 疋工们錯誤偵測。因此，以下將分 討論分析兩種狀況之錯誤偵制姓 海决價測結構’並利用本發明新的 時錯誤彳貞測技術結構來解·決。其討論如下. 狀況1 : 在中計算U的錯誤偵測讓我們考慮6m+, δ十算。從方程式（6)，U可由下式計算得到 +ι1+;/νι在以下假設中單一功能單元細胞錯 誤（Single-cell Fault)模式可再分解成細胞輸出訊號發生單 Ps入錯誤（single stuck-at fault)，對於此錯誤模型而言， 一個錯誤在邏輯閘（如x〇R及AND等）導致在其輸入或輸 出其中之一 s-a-〇錯誤或者s_a_l錯誤。從上述方程式中 18 1325560 热.扎1满爹正替換頁 計算U，在第一圖的細胞Qib—使贯 > 個~-2~^r^r~^ND閘（2 1 )及一個2輸入XOR閘（2 2 )去完成I計算，如第二 圖中所顯示。在細胞Qi，j錯誤行為能被分類如下的5種情 況0 (a).·假如輸入信號/；,.在AND-1閘有一陷入錯誤，則在第i 列細胞，計算\+ί如 〆”!+/

j-\ m-\hpk+TA+iPk k=Q k=j+\ j~\ /77—1YJbk+iPk+Kj+ Yj^k^Pk k=0 for s-a-0 for s~a-l k=j+\ (b):假如輸入信號6,+;在AND- 1閘有一陷入錯誤，貝ij在第i· 列細胞，計算U如. m-\

Tjh+iPk+Tjh+iPk f〇r s-a-0 k=j+\ m-\ k=0 y-i

Tj^iPk+Pi+Tj^丨Pk for s — a-\ k~0 k-y+i (c):假如輸入信號\+,_在XOR-3閘有一陷入錯誤，則在第i 列細胞，計算6„+,如 m-\

m+i

YjKiP, k=j+\ m-\ for bJ+lPj+ for k=j+\ s-a-0 s-a-l (d):假如AND-l閘的輸出信號有一陷入錯誤，則在第i列 細胞，計算U，.如 ym+i j-\ m-\ Tjh+iPk+hPk f〇r k=Q k=_/'+l j-\ m-1 Σ^+,^+ι+Σ6^λ f〇r 5-a-0 s-a-l A：=y+i (e)·.假如XOR-3閘的輸出信號有一陷入錯誤，則在第i列 細胞，計算6„+,_如 19 1325560 年月曰修 正 …—ι

hPi for s-a-Q k=y+i m-\ 1+ for s-a-\ k=j+l 令足是B元素的奇偶同位校驗位元且被定義成 PB=b0+bl+A + bm_x 其中” + ”符號指表示模數2加法（modulo-2 addition) (即互斥或計算）。 從方程式（6)能獲得那十匕足^。因此，預 測奇偶同位檢測位元被計算如下： 户〇3=厶1十厶2+人+〜 （7) 從方程式（4), \可計算如下 =Σ,Ρ,Κν^Β) = YJpibi (8)

/=0 /=0 v J 將方程式 （8)代入方程式 （7),此W預測的奇偶同位檢測 位元可被執行如下 Ρ〇β = Κρ〇 + Σ^/ (1 + Pf) = b〇P〇 + Y,bipi 因此，假設奇偶同位檢測位元Ps被預先計算好，因為 Ρ〇Β=Σ^ 5 且总=尸, 則我們有 会αΒ + 乒B =bm + bQ. 因此，讓我們定義參數 < 如下列函數；這樣的參數能被用 於計算的檢測。 ~P〇B+Pb +bm +^0 (9) 20 1325560 ^ l\ i%f 正替換頁 此參數纹=1指示錯誤L計算的存在。類似地，U的 • 錯誤偵測能被執行且使用下列函數 (10) (11) -各 d+hi+bi 其中 Λ /w — 1 _ K<B=bi-^+lLb^Pj y=i 狀況2 : 在整個乘法計算上的錯誤偵測根據G = ，已知 /=0 ' G = ，其中g,+ =吨，它可以直接地被獲得，當α = 0， G的輸 出是邏輯〇和當α = 1輸出是邏輯Β。令5 = 且尺Μ皮分 /'=0 /=0

I別地表示成雙重基底和Β的奇偶同位檢測位元。則輸出G ' 的奇偶同位檢測，根據A 對應a和Β的輸入信號是已 /=0 知，其中& =吨，0 s m -1，是G的係數。因此輸出G的此 預測的奇偶同位檢測位元能被表示如下：

Pg=^b (12) 首先，從方程式（6 )計算，由《4 = 6;怂+\+,/?1+八+6,+;„_,足 被執行。如同/^巧_,凡+ §&._,巧它是.容易計算的奇偶同位 戶1 21 丄扣：)6〇 id. ί. 1¾ 正替換貢] 檢測位元。因此，此乘積測奇偶 同位檢測位元能.被計算如下： 二 W-1 (13)

Pc^A 接 原先的乘積C的奇偶同位檢測位元是由方程式（6 ) 獲得，即， m~\ 〇,.=Σ^

'=〇 ,=〇 J 最後’乘積c的錯誤檢測能被比較與實際奇偶同位檢 測Pc和預測奇偶同位檢測矣，那就是， A ^ ec=Pc + Pc (14) 此參數e'c=1表明存在單一陷入錯誤。 如上所述，兩方程式（10)和（14)被用來偵測乘法器輸 =。假若U計算是無錯誤，則1=〇,且、,=1旗標存在單」 :入，誤。特別地，當此單一陷入錯誤發生在U計算，這 θ %疋不弓丨入進~+'計算的轔出，其中&户基於方程式（1〇) ，谓測所有單一陷入錯誤發生於‘計算。當陷入錯誤 生於S計算，此錯誤是不引入c，計算的輸出，其中因 為债測在整個乘法器全部陷入錯誤，陷入錯誤的旗標 /現gj方程4 (1〇)和（14)是分佈於GF⑺其 、別不入錯帛’並且價測任何奇數的陷 :誤。由於相似的料、很清楚的偶數的陷入錯誤發生 二:W將不被L檢測出。與此類似&值不能 任何偶數的陷入錯誤發生在細胞第i行。 22 1325560 itl 替妗頁 因此，為達上述之目的，本發明提出 種有限場GF(2m) 之低複雜度的心臟收縮陣列式雙重基底乘 。 _ 在益，其電路特 性係包含有： 一檢測裝置，用以控制資料編碼、解 $碼及密碼技術之 錯誤檢測，該乘法器係對有限場GF(2m) Φ & 、]丫兩種類型的奇偶 位元檢測預測功能由（m+m個細朐 %組成，其包括 個u細胞，（m+lMi v細胞和（功…個w细胞。 u細胞在第i列執行下列函數：呷曾 ^ m—1 ρα^=^ρ〇+Σ^-Ηρ., ^ 。當U和P、兩者在u細胞是 最後计异’ W細胞使用4個信號，Ά 士、；J叫·笞的扭 m+’ ^,+1s和户心’去元

·曰誤偵測。其中匕在U_細胞 算。特別是’假若i =。，則“…之：(")列被D ® 3知"，力Λ 于此之外，W細胞使 算。在最後列，v 最後.’.此Vn A i Si2，為了計算已預測的奇Μ η π ^ Γ堝同位檢測pc計 W細胞在0心·^—1執行am义和pc兩者計算。 d。摘Μ上、+ ，m細胞需要計算和整體乘法器錯誤檢 須1 述結構，此電路需要3m+l時鐘 每-細胞需要1 μ 吁鐘週期的延遲。 個2輸入and閘，一個2輸入x〇R閘和 -位元栓閘的最大計算延遲。 在本發明& 乘法器中，單一陷入錯誤模式被假設。令 陣列的第1列和第 J仃在圖三被指示為xpj細胞，直中，，X” 表示U，V和W辇。 ’、 ’ 3種細胞類型之一。假設X 細胞是不 完美的。不良的料* π馮能被分類為以下的7種情況可被檢 測0 23

1325560 (1)在Pj線路上的錯誤 細胞Ui,j的輸出信號Pj，使用來自輸入信號Pj的一通 過線，因此在圖三中陣列比較原始輸入信號Pj和原始 輸出信號Pj容易檢測出在它上一個錯誤。因此，在 信號Pj線路上的錯誤能被忽視。 (2) 在ai線路上的錯誤 細胞Ui;j的輸出信號a;，亦是來自輸入信號a;的通過 線，因此其上錯誤容.易檢測出。因此，在信號a i線 路上的錯誤能被忽視。 (3) 在6,:+;上的錯誤 細胞Uij的輸出信號心，也使用來自輸入信號的一 通過線，因此其上錯誤容易檢測出。因此，在信號&,.+; 上的錯誤能被忽視。 (4) 在；ζ.上錯誤 細胞U i j的輸出信號，也使用來自輸入信號&的一通 過線，因此其上錯誤容易檢測出。因此，在信號6上 的錯誤能被忽視。 (5) 在〜上的錯誤 假如一個錯誤在不良的細胞Ui .的輸入信號&上出 現。這個錯誤將影響輸出信號&。 那就是，此錯誤影 響在輸出信號&最後結果。因此，計算在V-細胞C 的奇偶同位檢測位元，使用方程式.能被計算。 在W-細胞C的已預測奇偶同位檢測位元，使用方程式 24 1325560 Θΰ： 0 111 正替換頁 4=心匕被執行。最後在m-細胞，比較實際的奇 y=〇 in | 偶同位檢測Pc和已預測奇偶同位檢測各，這個錯誤則檢 測出。 (6)在U或匕,5上的錯誤 假如一個錯誤在不良的細胞U i , j .的輸入信號k+ί上出 現。這個錯誤將影響輸出信號L β因此，使用方程 式（1 0 ) ’ 在此w i，m -細胞能變成邏辑1 ’那就是說 此錯誤能被檢測出。與此類似地，在細胞Uu上之，々錯 誤也能使用方程式（1 〇 )被檢測出。 (7)在4或尺上錯誤

假如一個錯誤在細胞Wi , m•的輸入信號4上出現’則 在細胞Vm·】’ m ，^;藉由應用方程式（14)將變成邏輯 1。那就是說，此錯誤能被檢測出。與此類似地’在 Vh j-細胞，pc的輸出信號是不良的。使用方程式. (14)，在Vm_hm錯誤能被發現。 上所述，被提議的即時錯誤檢測結構使用兩個奇 同位檢測預測，4和4，在整個乘法器裡執行檢測錯誤。 被提議的乘法器優點被描述如下： ⑴全部單-原有的錯誤（singlestuck· 方程式（⑷及（14)能被檢剩。 精由使 (2)被提議有即時錯誤檢測㈣ 雙重基底乘法器比較，僅需 ^ 值而要一個額外 為讓本發明之卜；g Μ 的時 乙上述目的、特徵、和優點 7 雙重盖底垂沐怒1 “ ^ ~在無即時 鐘 25 易 1325560 正替換頁 下文特舉-較佳實施例’並配合所附圖式，作詳細說明如 下，以期能使熟悉本發明相關技術之人士，得依本說明書 之陳述據以實施。 習用的在不具即時錯誤檢制 、檢測位兀並列輸出心臟收縮陣 列式雙重基底乘法器表示如第一 弟圖’而本發明具即時錯誤 檢測位元並列輪出心臟收縮陣列式雙重基底乘法器被顯示 在第三圖，其乘法器由(叫)個細胞組成，其包括_ (m - 1)個 U .細胎 f q η、( 聣 c 3 Ο )’（111+1)個 V 細胞（3 i )和（111_1} 個 w田胞（3 2 )。u，v 和 w 細胞（3 〇 )、（ 3 1 )、（ 3 2 )的詳、’’田的书路被分別描述在第四圖、第五圖及第六圖。 ’’·不上所述，雖然本發明已以較佳實施例揭露如上，然 .其並非用以限定夫 疋本發明，任何熟習此技藝者，在不脫離本 月之精神與範圍，當可作各種之更動與潤飾，因此本發 明之保護範圍以巾請專利範圍所界定者為準。 【圖式簡單說明】 第—圖孫- μ 圖。’、70並列心臟收縮陣列式雙重基底乘法器之架構 ^。圖係位元並列心臟收縮陣列式雙重基底乘法器之細胞 第三圖# 士 . 雙重其☆、發明具即時錯誤檢測位元並列心臟收縮陣列式 =里暴底乘法器。 第四圖伯；士 ％ 第五圖從本發明詳細的Ui . j細胞電路示意圖。 第六圖I’本發明詳細的Wi，m細胞電路示意圖。 糸本發明詳細的Vm ,」細胞電路示意圖。 主要元件符號說明】 (1〇)雙重基底乘法器 26 1325560 修 正替換頁 (2 Ο )單元細胞 (2 1 ) 2輸入AND閘 (2 2 ) 2輸入XOR閘 (2 3 ) 1位元栓閘 (3 0 ) u細胞 (3 1 ) V細胞 (3 2 ) w細胞

27

Claims (1)

1. I32WW 十、申請專利範圍： 位元並列輪出型心臟收縮 1 · 一種具即時偵錯能力之 路特性係包含有 陣·列式雙重基底乘法器，其電 一檢測裝置’用以控制眘 枓編碼、解褐及密瑪技術之 錯誤檢測’該乘法器的電路特性 係對.有限場GF(2T)中之一 第一元素A與一第二元辛b推 凡京β進仃乘積運算，以得到第三元 素C’其中元素Α是以多項式其 / 土底(1，α，α，八，α/»-ι)之表示式，元 素Β及C是以雙重基底之表示式 八，該有限場GF(2m)為不可 分解之多項式所產.生的，及 α為該不可分解的多項式之 根；該第一元素Α被表示為一⑺位元 >叫+¥ + «/+八+“^，該第二元素B被表示為一瓜位元 +IA-,，該第三元素c被表示為一 m位元 c=c(A+clA+i^2+A，其中所有元素的係數是等於0或 1，該乘法器包括有兩單元： • 一雙重基底乘法單元，其電.路包括由（m+1)xm個細 胞組成’以形成（m+Dxm陣列，且每—細胞包含有三個以 上輸入信號線、三個以上輸出信號線；每一細胞包含一個 以上AND閘、一個以上XOR閘和三個以上單位元暫存器 (Latch);及 . . 一雙重基底轉換單元，其電路包括樹狀式2_inputx〇R 閘所構成；其中， 該乘法器的雙重基底乘法單元包含有三種小細胞 細胞、W細胞與V細胞）；其中， 該U細胞’係在第i列執行下列函數：計算U，心和 28 1325560 Λ /π-1 之-丨 S=6,>1 尸。+Σ6,>7+ιΑ，其中 〇SKw_2; ' 7=1 -. 該W細胞，其中在6#，和之,+,β兩者在U細胞是最後計 •. 時，係使用4個信號，4，\+,，之％和之*，去完成U計算 錯誤檢測，其中匕在U-細胞的第（i-Ι)列被計算，特別是 若i = 0，則忍時；且W細胞使用之和a,·，其中在OSKm-• 則是為了計算已預測的奇偶同位檢測4 ; 該V.細胞，在最.後列，Vm_ ] ,j細胞在Osysm-l執行β 籲和/^兩者計算；此Vm-w細胞需負〜乂，計算責任和整體 法器錯誤檢測。 2 ·如申請專利範圍第1項所述之具即時偵錯能力 位元並列輸出型心臟收縮陣列式雙重基底乘法器，其中 該乘法器在上述U、’V和W細胞之一發生不良時會發生 一陷入錯誤，並藉由該乘法器偵測出該錯誤。 3 ·如申請專利範圍第2項所述之具即時偵錯能力 Φ 位元並列輸出型心臟收縮陣列式雙重基底乘法器，其中 可檢測的錯誤包括：在户;上的錯誤，細胞Ui，j的輸出信 A，使用來自輸入信號A的一通過線。 4 ·如申請專利範圍第2項所述之具即時偵錯能力 位元並列輸出型心臟收縮陣列式雙重基底乘法器，其中 可檢測的錯誤更包括：在α,上的錯誤，細胞Uij的輸出信 α,，亦是來自輸入信號α,的通過線。 5 ·如申請專利範圍第2項所述之具即時偵錯能力 位元並列輸出型心臟收縮陣列式雙重基底乘法器，其中 算 的 假 -2， 乘 之 早 之 5 號 之 5 號 之 29 1325560 可檢測的錯誤更包括：在δί+;上的錯誤’細胞Ui，j的輸出 號b，也使用來自輸入信號心的一通過線。 6 ·如申請專利範圍第2項所述之具即時偵錯能力 位元並列輸出型心臟收縮陣列式雙重基底乘法器，其中 可檢測的錯誤更包括：在·上錯誤，細胞Uij的輪出信 巧，也使用來自輸入信號ζ的一通過線’因此其上錯誤容 檢測出。 7 .如申請專利範圍第2項所述之具即時偵錯能力 位元並列輸出型心臟收縮陣列式雙重基底乘法.器.，其中 可檢測_的錯誤更包括.在cy上的錯誤’假如.一個錯誤在 良的細胞U i ’ j.的輸入信號Cy上出現，該錯誤將影響輪出 號勺的最後結果’因此，計算在V-細胞c的奇偶同位檢 位元，使用方程式乓=^勺能被計算，在W-細胞C的已預 奇偶同位檢測位元，使用方程式4之,s被執行，.最德 j^O % I 又 細胞，比較實際的奇偶同位檢測Pc和已預測奇偶 位檢測4，這個錯誤則檢測出。 8 .如申請專利範圍第2項所述之具即時偵錯能力 位元並列輸出塑心臟收縮陣列式雙重基底乘法器，其中 可檢測的錯誤更包括：在iu或之^上的錯誤，假如一個錯 在不良的細胞Ui’j.的輸入信號上出現，這個錯誤將影 輸出信號U因此’使用方程式K,s+t,s+6m+iH，k在 Wi，m -細胞能變成邏輯1，那就是說此錯誤能被檢測出， 信 之 號 易 之 不 信 測 測 在 同 之 ) 誤 響 此 且 30 1325560 在細胞Ui，j上錯誤也能使用方程式夂+; =Ρ,β+Ρ, . 測出。 % 9 ·如申請專利範圍第2項所述之具即時偵 -. 位元並列輸出型心臟收縮陣列式雙重基底乘法器 . 可檢測的錯誤更包括：在4或尽上錯誤，假如一個 胞Wi，m.的輸入信號4上出現，則在細胞Vm-l，m ^ 應用方程式& =各+尽將變成邏輯1，而能被檢測出 且在 Vnj -細胞，尸c的輸出信號不良時，使 ® t =各+ Pc，亦能發現在V m _ i，m的錯誤。 4 +\+,. +匀檢 錯能力之 ，其中， 錯誤在細 ,t藉由 此錯誤； 用方程式 31 1325560 f，/月（以修正贅換頁 B、、 · <<.»1.·»,. 1^.. %— _如· njnuxl· _頃 U»_· I _»-1 . 式· 如次頁 32 .1325560 七、指定代表圖： (一） 本案指定代表圖 (二） 本代表圖之元件 (3 0 ) U細胞 夢11¾正替換頁 --------J 爲··第（三）圖。 符號簡單說明： (3 1 ) V細胞 (3 2 ) W細胞 八、本案若有化學式時，請揭示最能顯示發明特 徵的化學式：