基于演化算法的奇偶校驗器自動設計

摘 要：基于演化算法技術，提出一種新的設計思想，實現奇偶校驗器的電路自動設計。實驗證明，多目標演化算法具有較少的運算量和較高的效率，能自動設計出使用邏輯門數更少、延時更小的奇偶校驗器。

關鍵詞：演化算法；奇偶校驗器；電路自動設計；多目標演化

中圖分類號：TP302； TN702文獻標志碼：A文章編號：1001-3695(2007)06-0257-02

奇偶校驗器的功能定義如下：僅當多位輸入中包含偶數（或奇數）個“1”時輸出為“1”，被稱作偶校驗器（或奇校驗器）。在差錯控制方法中，最簡單的檢錯方法是奇偶校驗，奇偶校驗器在計算機系統中的內存數據的檢錯、串行數據在傳輸過程中的檢錯等方面有著重要的應用。為此，如何設計出一個更為優良的奇偶校驗器成為電子設計者的一個巨大挑戰。

作為演化硬件［1］(Evolvable Hardware，EHW)研究的重要分支，電路演化設計［2］利用演化算法，如遺傳算法(Genetic Algorithm，GA)、基因表達程序設計(Gene Expression Programming，GEP)等來優化電路的結構和參數，以實現復雜電路自動設計［3］，新穎的、優化的電路設計結構。本文基于多目標演化算法，提出了一種解決邏輯電路自動設計的抽象模型。通過實驗設計分析，證明文中提出的方法是有效的。

1 設計模型

根據組合邏輯電路的特點，每一個邏輯電路都具有一個多個輸入多個輸出。由此，本文設計了如圖1所示的K×L陣列結構模型［2］。在該模型中，筆者對每一個陣列單元當作具有某一邏輯功能的函數。輸入中具有如下特點：常數0和1始終在模型設計的初始方案中，并把輸入的n個變量和對應n個變量的反變量一起當作輸入參數，因此，有n個變量的電路的輸入參數長度為：2×n+2。輸入可以是多個也可以是一個。

在圖1中，陣列單元CCN的編號為：CN= i+j×K，其中，1≤i≤K， 0≤j≤L-1；并且規定，陣列單元中數據輸入輸出的方向只能為以編號小的單元指向編號大的單元，這樣就可以防止出現回路電路。為了方便起見，單元的第一個輸入為A，第二個輸入為B。用C語言的符號表示這些邏輯操作：表示與；|表示或；^表示異或；!表示非。在該模型中，規定陣列單元的邏輯功能可以為二路選擇器［2］和表1中的功能中的任何一種。

2 多目標演化算法設計

演化算法［1，4］的要素有：編碼、適應值函數、雜交、變異、選擇機制、終止條件等。根據圖1給出的計算模型，設計出如下演化算法。

3.1 編碼方案

采用實數編碼［4］技術，對于一個具有n個輸入、m個輸出的電路來說，輸入部分編碼為2×n+2；陣列單元每一個單元采用三元數組形式（輸入1，輸入2，輸出），故整個陣列部分編碼長度為3×K×L；輸出個數為m。故整個模型編碼長度為：Length=2×n+2+K×L-1。染色體基因只包括陣列單元和輸出部分，故染色體個體的的長度為：3×K×L+m。

3.2 適應值多目標評估方法

由于電路設計是典型的多目標優化問題，多目標演化算法已經被用于該類問題的求解。

多目標問題的定義為

這里采用求和的形式，把多目標優化問題轉換為可利用單目標演化算法求解的等效問題。

邏輯電路的演化設計主要設計電路功能符合程度、所用邏輯門個數、延時級數等設計子目標：

（1）電路功能符合程度—— 輸入和輸出對給定功能的真值表的符合程度。

（2）所有邏輯門個數——是在完全符合給定真值表功能的情況下，使得設計出的電路所利用的門個數最少。 

（3）延時級數——設計出的電路的互連關系可以計算出該電路的延時，延時級數即定義為從輸入到輸出最長的一個電路流向。

3.3 雜交、變異方法

該編碼的雜交、變異均是對三元組進行操作。雜交操作在第一個三元組結尾處進行雜交操作，變異操作也是對三元組中的代表陣列單元功能的部位進行操作。

3.4 算法流程

本文設計演化算法，這里主要是遺傳算法［4］步驟：

（1） 設置初始化參數：PopSize、MaxGeneration、Pc、Pm等，編碼，初始化群體；

（2） 對初始群體進行評估；

（3） 采用排序選擇算法進行選擇操作，并產生選擇概率；

（4） 如果選擇概率大于雜交概率，交配池中父代兩兩進行雙點雜交操作；

（5） 如果選擇概率大于變異概率，從交配池中選取父代進行變異操作；

（6） 種群更新；

（7） 如果不滿足停機條件，繼續執行 （3）－（6）步。

4 偶校驗器的設計

根據第2部分的設計模型和第3部分的算法設計，筆者將將其應用到奇偶校驗器的設計中，正如本文開始所介紹的奇偶校驗器的功能定義，筆者設計了3位和4位的偶校驗器。偶校驗器的功能定義如下：僅當多位輸入中包含偶數（不包括0）個“1”時輸出為“1”，稱作偶校驗器。據此，這里就3位和4位偶校驗器的真值表不在文中列出。

對演化算法的編碼和模型中參數的設計如下：

（1）3位偶校驗器。模型陣列為3×3，3位變量輸入1位輸出，則染色體的編碼長度為3×3×3+1=28，其中實數編碼的最大實數為2+2×3+3×3-1=16。

（2）4位偶校驗器。模型陣列為4×4，4位變量輸入1位輸出，則染色體的編碼長度為3×4×4+1=49，其中實數編碼的最大實數為2+2×4+4×4-1=25。

根據本文設計的算法，程序計算出的3位偶校驗器的最優個體為（6 4 -4 5 6 -8 2 8 -4 3 8 5 3 8 -9 1 1 9 13 13 11 10 12 -1 6 11 9 15），其中使用門數為4，延時級數為3，根據這個染色體，對照設計模型，可以構造出對應的邏輯電路為圖2所示。

根據本文算法設計出的結果，將該結果與已有文獻的數據進行比較分析，3位偶校驗器的分析結果可如表2所示，4位偶校驗器的分析結果如表3所示。

通過表2和表3，可以看出，本文設計的方法具有一定的新穎性和高效性，在設計4位偶校驗器例子中，本文方法使用的門數和延時級數均少于已有的文獻［5］數據。

5 結束語

本文提出了一種用于演化設計的陣列模型，并基于多目標演化算法設計的思想，對奇偶校驗器進行了實例測試，根據實驗結果顯示，通過演化算法結合其他優化策略（如多目標優化思想）來實現邏輯電路的自動設計是很有用的。根據本文中的思想，我們還進行了二位乘法器、三位乘法器、二位加法器的設計，與已有的文獻［2，5］相比，均得到較好的結果。因此，將此思想推廣到超大規模集成電路［7］(VLSI)設計中，意義十分重大。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。