基于排序網(wǎng)絡(luò)的奇數(shù)大數(shù)邏輯門電路設(shè)計

王艷, 張楠, 郭靖

(1. 中北大學(xué) 電子測試技術(shù)國防重點實驗室, 太原 030051；2.儀器科學(xué)與動態(tài)測試教育部重點實驗室, 太原 030051)

0 引 言

高能輻射粒子在入射到SRAM存儲器敏感單元的過程中會產(chǎn)生電子-空穴對[1]，在電場作用下，存儲器敏感單元可以將這些電子-空穴對收集起來，并發(fā)生電荷積累。若積累的電荷超過臨界電荷值[2]，該存儲節(jié)點的電勢將會發(fā)生改變，同時引發(fā)邏輯電平值的改變，最終發(fā)生單粒子翻轉(zhuǎn)(Single Event Upset，SEU)現(xiàn)象[3]。SEU不會產(chǎn)生永久的錯誤，在存儲器的下一個寫入階段，重新寫入的值可以恢復(fù)這些錯誤。因此，SEU又被稱為軟錯誤(Soft Error)。

在微處理芯片內(nèi)，存儲器占總面積的30% 左右，因而存儲器中發(fā)生的軟錯誤將會直接影響芯片的功能。因此，可以通過加強存儲器的抗SEU能力來提高微處理芯片的可靠性。存儲器的抗SEU加固設(shè)計有許多種，錯誤糾錯碼(Error Correction Code，ECC)是其中之一[4]，其主要是通過ECC編譯碼的方式對存儲器進行加固[5]。隨著集成電路技術(shù)的發(fā)展，一次單粒子事件會引起多個單元同時翻轉(zhuǎn)(Multiple-Cell Upset，MCU)，而為了糾正MCU，就需要使用糾正能力更強的ECC[6]，但是其編譯碼方式將會越來越復(fù)雜，硬件開銷也將隨之增加。

一步大數(shù)邏輯可譯碼(One-Step Majority Logic Decodable，OS-MLD)可以使用一步大數(shù)邏輯譯碼器來進行譯碼，因此其譯碼程序和電路都非常簡單，這些碼包括差異集(Difference Set Code，DS)，低密度奇偶校驗(Euclidean Geometry Low Density Parity Check Code，EG-LDPC)和正交拉丁方(Orthogonal Latin Squares，OLS)[7]；其中，由于DS碼的復(fù)雜度低、速度快，且擁有更長的信息位，因此被廣泛的應(yīng)用于對存儲器進行MCU的糾錯保護。以(73, 45)DS碼為例，來解釋一步大數(shù)邏輯譯碼器的工作原理(見圖1)。譯碼時，首先將碼長為73位的DS碼(包含45個信息位)存入移位寄存器中[8]；然后，根據(jù)相應(yīng)的9組奇偶校驗組合對寄存器中數(shù)據(jù)進行錯誤檢測和糾正：

(1)如寄存器中C72發(fā)生了翻轉(zhuǎn)，則9組奇偶校驗組合通過異或門輸出的 γ0～ γ8中將有多數(shù)個1；此時，大數(shù)邏輯門(Majority Logic Gate，MLG)將輸出大數(shù)值1；C72與MLG輸出值1異或，從而糾正C72并輸出該值；

(2)如寄存器中C72沒有發(fā)生翻轉(zhuǎn)，仍保持其正確的值，則9組奇偶校驗組合通過異或門輸出的 γ0～ γ8中將有多數(shù)個0；此時，MLG的輸出值為0；將C72與MLG輸出值相比較，異或結(jié)果為0，表示該碼位沒有發(fā)生翻轉(zhuǎn)。

由此可見，MLG是OS-MLD譯碼器的重要組成部分，其性能和硬件開銷直接決定了一步大數(shù)邏輯譯碼器電路的復(fù)雜程度和硬件開銷。

圖1 (73, 45)DS碼的工作原理

1 MLG電路設(shè)計

1.1 傳統(tǒng)MLG電路

在OS-MLD譯碼器中，MLG電路可以評估奇偶校驗和的大數(shù)值，然后根據(jù)該大數(shù)值來準確的判斷譯碼位是否發(fā)生了錯誤：若該譯碼位為錯誤碼位，則可實現(xiàn)對該碼位的糾正。MLG電路的具體功能如下：當(dāng)輸入向量的值多數(shù)為1時，則輸出大數(shù)值為1；當(dāng)輸入向量的值多數(shù)為0時，則輸出大數(shù)值為0；若輸入向量的個數(shù)為偶數(shù)，且輸入向量0的個數(shù)與向量1的個數(shù)相等，則輸出大數(shù)值為0。傳統(tǒng)MLG電路的構(gòu)造方法為：

(1)假設(shè)輸入向量為γ0 ～γθ-1，θ為MLG電路輸入向量的個數(shù)；

(2)從γ0 ～γθ-1中選取ω個輸入向量，則共有種組合方式(若θ為偶數(shù)，ω=2-1θ+1；若θ為奇數(shù)，ω=2-1(θ+1))；

(3)根據(jù)組合方式列出相應(yīng)邏輯表達式，從而輸出大數(shù)邏輯值。

傳統(tǒng)的5輸入MLG電路如圖2所示：如輸入向量為 γ0 ～γ4，然后選取其中3個向量，則共有10種組合方式(“+”表示或門)：

Oout=γ0γ1γ2+γ0γ1γ3+γ0γ1γ4+γ0γ2γ3+γ0γ2γ4+γ0γ3γ4+γ1γ2γ3+γ1γ2γ4+γ1γ3γ4+γ2γ3γ4

(1)

由式(1)可知，5輸入傳統(tǒng)MLG電路需要29個兩輸入邏輯門。同理，6輸入傳統(tǒng)MLG電路需要59個兩輸入邏輯門；8輸入傳統(tǒng)MLG電路需要279個兩輸入邏輯門；9輸入傳統(tǒng)MLG電路需要629個兩輸入邏輯門。對比5、6、8、9輸入的傳統(tǒng)MLG電路可知，隨著輸入向量個數(shù)的增加，MLG的硬件開銷呈現(xiàn)指數(shù)增長的態(tài)勢。

圖2 傳統(tǒng)5輸入MLG電路

1.2 基于排序網(wǎng)絡(luò)的MLG電路

為了解決傳統(tǒng)MLG電路硬件開銷大的問題，文獻[9]提出了一種基于排序網(wǎng)絡(luò)的MLG電路的構(gòu)造方法。在計算機系統(tǒng)中，排序網(wǎng)絡(luò)用于將輸入數(shù)據(jù)重新排序，且排序過程與數(shù)據(jù)序列是相互獨立的。數(shù)據(jù)序列的排序由“黑盒”實現(xiàn)，在左側(cè)輸入原始序列，在右側(cè)輸出生成的新序列，從而實現(xiàn)對輸入序列從大到小的排序，即若輸入序列為10101011，則輸出序列為11111000。然而，隨著排序網(wǎng)絡(luò)輸入向量個數(shù)的增加，其電路的復(fù)雜程度也將會極大地增加，進而導(dǎo)致硬件開銷也增加很多。

針對這一問題，文獻[9]提出了一種基于排序網(wǎng)絡(luò)的MLG電路構(gòu)造方法。假設(shè)輸入向量的個數(shù)為θ(θ為偶數(shù))，構(gòu)造MLG電路則需要2個2-1θ輸入的排序網(wǎng)絡(luò)、2-1θ個兩輸入與門、1個2-1θ輸入或門?；谂判蚓W(wǎng)絡(luò)的8輸入MLG電路如圖3所示，該電路將一個8輸入MLG電路拆分為兩個4輸入的排序網(wǎng)絡(luò)[9]，對排序后的兩組向量進行比較(第一組第1個值與第二組第4個值比較，第一組第2個值與第二組第3個值比較，以此類推)，最后將比較后的值進行或運算，進而輸出正確的大數(shù)邏輯值。

圖3 文獻[9]構(gòu)造的8輸入MLG電路

表1給出了文獻[9]構(gòu)造的MLG電路邏輯門的使用數(shù)量，相比于傳統(tǒng)MLG電路，基于排序網(wǎng)絡(luò)的6輸入MLG電路使用的兩輸入與門減少了80.0%，兩輸入或門減少了42.8%；基于排序網(wǎng)絡(luò)的8輸入MLG電路使用的兩輸入與門減少了93.7%，兩輸入或門減少了76.3%。

文獻[9]僅構(gòu)造了偶數(shù)輸入的MLG電路，而DS碼需要奇數(shù)輸入的MLG電路來進行譯碼，表2所示為(21, 11)和(73, 45)的DS碼表。為此，文獻[10]提出了奇數(shù)輸入的MLG電路的構(gòu)造方法，如圖4所示。該電路將9輸入的排序網(wǎng)絡(luò)拆分為兩個4輸入的排序網(wǎng)絡(luò)，排序后通過組合邏輯電路輸出大數(shù)邏輯值。但是，這種構(gòu)造方法存在錯誤，并不能正確的輸出大數(shù)邏輯值：若輸入向量γ0～ γ8為000011111時，MLG電路的大數(shù)輸出值應(yīng)為1，但文獻[10]中構(gòu)造的9輸入MLG電路的大數(shù)邏輯輸出值實際為0。因此，該電路不能對所有輸入情況執(zhí)行正確的大數(shù)邏輯輸出。

圖4 文獻[10]中構(gòu)造的9輸入MLG電路

1.3 本文構(gòu)造的MLG電路

本文針對文獻[10]中存在的問題，提出了一種新型奇數(shù)輸入的MLG電路構(gòu)造方法。該MLG電路以排序網(wǎng)絡(luò)為基礎(chǔ)，其具體構(gòu)造步驟如下：

(1)假設(shè)輸入向量為γ0～ γθ-1，θ為MLG的輸入向量的個數(shù)；

(2)根據(jù)其大數(shù)閾值2-1(θ+1)，將輸入拆分為兩部分，分別使用2-1(θ+1)輸入的排序網(wǎng)絡(luò)和2-1(θ-1)輸入的排序網(wǎng)絡(luò)；

(3)對2-1(θ+1)輸入的排序網(wǎng)絡(luò)排序后的輸出與2-1(θ-1)輸入的排序網(wǎng)絡(luò)排序后的輸出使用組合邏輯電路來輸出大數(shù)邏輯值。

本文以5輸入MLG電路的構(gòu)造方法為例，解釋其構(gòu)造過程：

(1)假設(shè)輸入向量為γ0～ γ4，θ=5，則其大數(shù)閾值為2-1(θ+1)=3；

(2)使用一個2-1(θ+1)=3輸入的排序網(wǎng)絡(luò)和一個2-1(θ-1)=2輸入的排序網(wǎng)絡(luò)來進行排序；

(3)對兩個排序網(wǎng)絡(luò)的輸出使用組合邏輯電路來輸出大數(shù)邏輯值。

本文以5輸入MLG電路的構(gòu)造方法為例，解釋其構(gòu)造過程：

(1)假設(shè)輸入向量為γ0～ γ4，θ=5，則其大數(shù)閾值為2-1(θ+1)=3；

(2)使用一個2-1(θ+1)=3輸入的排序網(wǎng)絡(luò)和一個2-1(θ-1)=2輸入的排序網(wǎng)絡(luò)來對輸入向量進行排序；

(3)對兩個排序網(wǎng)絡(luò)的輸出使用組合邏輯電路來輸出大數(shù)邏輯值。

圖5中，當(dāng)輸入γ0～ γ4為01111時，對γ0～ γ1排序，輸出α0～ α1(10)，對γ2～ γ4排序，輸出ε0～ ε2(111)；之后，α0、ε1通過與門，輸出1；α1、ε0通過與門，輸出0；最后，1、0、ε3(1)通過或門，輸出大數(shù)邏輯值1。對其他輸入進行類似分析，證明本文提出的5輸入MLG電路可對所有輸入情況正確實現(xiàn)大數(shù)邏輯的功能。

圖5 本文構(gòu)造的5輸入MLG電路

本文構(gòu)造的9輸入MLG電路如圖6所示：當(dāng)輸入γ0～ γ8為000011111時，構(gòu)造的MLG電路可以正確的輸出大數(shù)邏輯值0。因此，文章提出的基于排序網(wǎng)絡(luò)構(gòu)造的奇數(shù)輸入的MLG電路可以正確的實現(xiàn)大數(shù)邏輯的功能。

圖6 本文構(gòu)造的9輸入MLG電路

表3給出了本文構(gòu)造的MLG電路邏輯門的使用數(shù)量。由表3可得，相比于傳統(tǒng)MLG電路，本文構(gòu)造的5輸入MLG電路使用的兩輸入與門減少了70.0%，兩輸入或門減少了33.3%；本文構(gòu)造的9輸入MLG電路使用的兩輸入與門減少了96.4%，兩輸入或門減少了86.4%。

2 功能驗證及硬件開銷比較

采用Xilinx的FPGA-XC6SLX16進行功能驗證，利用Verilog硬件描述語言對本文構(gòu)造的5輸入和9輸入MLG電路進行功能驗證。圖7為本文構(gòu)造的5輸入MLG電路的功能仿真圖：若輸入向量γ0 ～γ4為10100，輸出大數(shù)邏輯值為0；若輸入向量為10101，輸出大數(shù)邏輯值為1。圖8為本文構(gòu)造的9輸入MLG電路的功能仿真圖：若輸入向量γ0 ～γ8為000011111，輸出大數(shù)邏輯值為1；若輸入向量為000011110，輸出大數(shù)邏輯值為0。這些仿真結(jié)果表明，本文構(gòu)造的新型MLG電路能夠?qū)崿F(xiàn)正確的大數(shù)邏輯功能。

圖7 本文構(gòu)造的5輸入MLG電路仿真結(jié)果

圖8 本文構(gòu)造的9輸入MLG電路仿真結(jié)果

表4給出了在FPGA上使用傳統(tǒng)MLG電路和本文構(gòu)造的MLG電路實現(xiàn)DS碼譯碼器的硬件開銷。相比于使用傳統(tǒng)MLG電路，(21，11)DS碼譯碼器在使用本文構(gòu)造的5輸入MLG電路時，Slices減少了28.5%，邏輯延時減少了17.3%，6-LUT減少了21.7%，F(xiàn)lip-Flops減少了19.4%；(73，45)DS碼譯碼器在使用本文構(gòu)造的9輸入MLG電路時，Slices減少了80.7%，邏輯延時減少了63.6%，6輸入LUT減少了78.0%，F(xiàn)lip-Flops減少了74.3%。

3 結(jié)束語

文章使用排序網(wǎng)絡(luò)構(gòu)造了一種新型奇數(shù)輸入的大數(shù)邏輯門電路，可有效減少邏輯門的使用數(shù)量，并降低電路的邏輯延時、Slices、Flip-Flops、LUT等。因此，DS碼譯碼器可使用本文構(gòu)造的MLG電路來進行譯碼操作，進而可降低加固存儲器時所帶來的硬件開銷。