基于演化算法的奇偶校驗(yàn)器自動(dòng)設(shè)計(jì)

摘 要：基于演化算法技術(shù)，提出一種新的設(shè)計(jì)思想，實(shí)現(xiàn)奇偶校驗(yàn)器的電路自動(dòng)設(shè)計(jì)。實(shí)驗(yàn)證明，多目標(biāo)演化算法具有較少的運(yùn)算量和較高的效率，能自動(dòng)設(shè)計(jì)出使用邏輯門數(shù)更少、延時(shí)更小的奇偶校驗(yàn)器。

關(guān)鍵詞：演化算法；奇偶校驗(yàn)器；電路自動(dòng)設(shè)計(jì)；多目標(biāo)演化

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

奇偶校驗(yàn)器的功能定義如下：僅當(dāng)多位輸入中包含偶數(shù)（或奇數(shù)）個(gè)“1”時(shí)輸出為“1”，被稱作偶校驗(yàn)器（或奇校驗(yàn)器）。在差錯(cuò)控制方法中，最簡單的檢錯(cuò)方法是奇偶校驗(yàn)，奇偶校驗(yàn)器在計(jì)算機(jī)系統(tǒng)中的內(nèi)存數(shù)據(jù)的檢錯(cuò)、串行數(shù)據(jù)在傳輸過程中的檢錯(cuò)等方面有著重要的應(yīng)用。為此，如何設(shè)計(jì)出一個(gè)更為優(yōu)良的奇偶校驗(yàn)器成為電子設(shè)計(jì)者的一個(gè)巨大挑戰(zhàn)。

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

1 設(shè)計(jì)模型

根據(jù)組合邏輯電路的特點(diǎn)，每一個(gè)邏輯電路都具有一個(gè)多個(gè)輸入多個(gè)輸出。由此，本文設(shè)計(jì)了如圖1所示的K×L陣列結(jié)構(gòu)模型［2］。在該模型中，筆者對每一個(gè)陣列單元當(dāng)作具有某一邏輯功能的函數(shù)。輸入中具有如下特點(diǎn)：常數(shù)0和1始終在模型設(shè)計(jì)的初始方案中，并把輸入的n個(gè)變量和對應(yīng)n個(gè)變量的反變量一起當(dāng)作輸入?yún)?shù)，因此，有n個(gè)變量的電路的輸入?yún)?shù)長度為：2×n+2。輸入可以是多個(gè)也可以是一個(gè)。

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

2 多目標(biāo)演化算法設(shè)計(jì)

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

3.1 編碼方案

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

3.2 適應(yīng)值多目標(biāo)評估方法

由于電路設(shè)計(jì)是典型的多目標(biāo)優(yōu)化問題，多目標(biāo)演化算法已經(jīng)被用于該類問題的求解。

多目標(biāo)問題的定義為

這里采用求和的形式，把多目標(biāo)優(yōu)化問題轉(zhuǎn)換為可利用單目標(biāo)演化算法求解的等效問題。

邏輯電路的演化設(shè)計(jì)主要設(shè)計(jì)電路功能符合程度、所用邏輯門個(gè)數(shù)、延時(shí)級數(shù)等設(shè)計(jì)子目標(biāo)：

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

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

（3）延時(shí)級數(shù)——設(shè)計(jì)出的電路的互連關(guān)系可以計(jì)算出該電路的延時(shí)，延時(shí)級數(shù)即定義為從輸入到輸出最長的一個(gè)電路流向。

3.3 雜交、變異方法

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

3.4 算法流程

本文設(shè)計(jì)演化算法，這里主要是遺傳算法［4］步驟：

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

（2） 對初始群體進(jìn)行評估；

（3） 采用排序選擇算法進(jìn)行選擇操作，并產(chǎn)生選擇概率；

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

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

（6） 種群更新；

（7） 如果不滿足停機(jī)條件，繼續(xù)執(zhí)行 （3）－（6）步。

4 偶校驗(yàn)器的設(shè)計(jì)

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

對演化算法的編碼和模型中參數(shù)的設(shè)計(jì)如下：

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

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

根據(jù)本文設(shè)計(jì)的算法，程序計(jì)算出的3位偶校驗(yàn)器的最優(yōu)個(gè)體為（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），其中使用門數(shù)為4，延時(shí)級數(shù)為3，根據(jù)這個(gè)染色體，對照設(shè)計(jì)模型，可以構(gòu)造出對應(yīng)的邏輯電路為圖2所示。

根據(jù)本文算法設(shè)計(jì)出的結(jié)果，將該結(jié)果與已有文獻(xiàn)的數(shù)據(jù)進(jìn)行比較分析，3位偶校驗(yàn)器的分析結(jié)果可如表2所示，4位偶校驗(yàn)器的分析結(jié)果如表3所示。

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

5 結(jié)束語

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

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