基于排序網絡的奇數大數邏輯門電路設計

王艷, 張楠, 郭靖

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

0 引 言

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

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

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

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

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

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

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

1 MLG電路設計

1.1 傳統MLG電路

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

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

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

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

傳統的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輸入傳統MLG電路需要29個兩輸入邏輯門。同理，6輸入傳統MLG電路需要59個兩輸入邏輯門；8輸入傳統MLG電路需要279個兩輸入邏輯門；9輸入傳統MLG電路需要629個兩輸入邏輯門。對比5、6、8、9輸入的傳統MLG電路可知，隨著輸入向量個數的增加，MLG的硬件開銷呈現指數增長的態勢。

圖2 傳統5輸入MLG電路

1.2 基于排序網絡的MLG電路

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

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

圖3 文獻[9]構造的8輸入MLG電路

表1給出了文獻[9]構造的MLG電路邏輯門的使用數量，相比于傳統MLG電路，基于排序網絡的6輸入MLG電路使用的兩輸入與門減少了80.0%，兩輸入或門減少了42.8%；基于排序網絡的8輸入MLG電路使用的兩輸入與門減少了93.7%，兩輸入或門減少了76.3%。

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

圖4 文獻[10]中構造的9輸入MLG電路

1.3 本文構造的MLG電路

本文針對文獻[10]中存在的問題，提出了一種新型奇數輸入的MLG電路構造方法。該MLG電路以排序網絡為基礎，其具體構造步驟如下：

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

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

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

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

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

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

(3)對兩個排序網絡的輸出使用組合邏輯電路來輸出大數邏輯值。

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

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

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

(3)對兩個排序網絡的輸出使用組合邏輯電路來輸出大數邏輯值。

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

圖5 本文構造的5輸入MLG電路

本文構造的9輸入MLG電路如圖6所示：當輸入γ0～ γ8為000011111時，構造的MLG電路可以正確的輸出大數邏輯值0。因此，文章提出的基于排序網絡構造的奇數輸入的MLG電路可以正確的實現大數邏輯的功能。

圖6 本文構造的9輸入MLG電路

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

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

采用Xilinx的FPGA-XC6SLX16進行功能驗證，利用Verilog硬件描述語言對本文構造的5輸入和9輸入MLG電路進行功能驗證。圖7為本文構造的5輸入MLG電路的功能仿真圖：若輸入向量γ0 ～γ4為10100，輸出大數邏輯值為0；若輸入向量為10101，輸出大數邏輯值為1。圖8為本文構造的9輸入MLG電路的功能仿真圖：若輸入向量γ0 ～γ8為000011111，輸出大數邏輯值為1；若輸入向量為000011110，輸出大數邏輯值為0。這些仿真結果表明，本文構造的新型MLG電路能夠實現正確的大數邏輯功能。

圖7 本文構造的5輸入MLG電路仿真結果

圖8 本文構造的9輸入MLG電路仿真結果

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

3 結束語

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