數(shù)字多路選擇器樹形網(wǎng)絡(luò)設(shè)計理論和算法分析

史群峰

[摘 要]：本文提出以邏輯函數(shù)不相交的簡化積之和形式的代數(shù)方法實現(xiàn)數(shù)字多路選擇器的方法，通過實例證明，該種方法是科學(xué)有效的。

[關(guān)鍵詞]：數(shù)字多路選擇器 樹形網(wǎng)絡(luò)設(shè)計

多路選擇器是多功能通用邏輯模塊的一種，當(dāng)使用多路選擇器通用模塊實現(xiàn)多變量組合的函數(shù)時，受模塊的地址墻個數(shù)的限制，需要選取變量集合的一個劃分，并將劃分塊中的變量分配給網(wǎng)絡(luò)中每級網(wǎng)絡(luò)中各個選擇器的控制墻，作為控制墻的變量，以樹形網(wǎng)絡(luò)的形實實形。每級網(wǎng)絡(luò)中各個選擇器控制變量的配置最終決定多路選擇器的繁簡程度，如果構(gòu)成多路選擇器網(wǎng)絡(luò)用的數(shù)目是最小的，就被稱為最小樹形網(wǎng)絡(luò)，這個網(wǎng)絡(luò)每級、每個控制變量的配置即為最佳配置。利用多路選擇器網(wǎng)絡(luò)實現(xiàn)任意布爾函數(shù)是近代數(shù)字學(xué)者認(rèn)為非常重要的一個課題，本文嘗試用邏輯函數(shù)不相交的簡化積之和形式的代數(shù)方法實現(xiàn)數(shù)字多路選擇器的方法實現(xiàn)多路選擇網(wǎng)絡(luò)設(shè)計的最小樹型網(wǎng)絡(luò)，并且提出實現(xiàn)的理論、方法，給出運算的實例，通過一系列實例可以證明這種理論和操作方法是可以實現(xiàn)的，它可以實現(xiàn)多路選擇器的最終綜合。

一、理論

多路選擇器使用邏輯模塊實現(xiàn)布爾函數(shù)的理論，是由于布爾函數(shù)的展開式。如果在一個變量集X=（x1，x2x3，……xn）中實現(xiàn)布爾函數(shù)f，那么變量X上的劃分方式為：

其中：

n≧s≧，

變量集中B1、B2為劃分快，它們滿足

（為空集）， ，

對于定義變量集X=（x1，x2x3，……xn）上的邏輯函數(shù)f關(guān)于xi的展開式為：

其中、 、 分別為函數(shù)f中 、 的限制，如果它們把 賦值為0和1，那么 被稱為限制變量，展開式如下：

由于變量集X選取劃分為：

那么可以得到：

在這個公式中，函數(shù)f關(guān)于積項 、 的函數(shù)限制為：

；

因此可以得到： ；

如果將一個定義在X上的函數(shù)及子積上的某個積項 ，那么關(guān)于P的函數(shù)限制 的運算被稱為限制運算。

它定義為：

其中：

變量 的極性為文字 、文字 、文字 ，即 ，其中1≦s≦r，可以通過：

看到對限制變量集合中的各限制變量賦值為：

，其中 ，當(dāng) =1時，其中1≦s≦r，則可以得到f的結(jié)果，它可以是常量為0，1或者單個文字的平凡子函數(shù)，或者為一個非平凡子函數(shù)。

二，.算法與實例

1，算法

算法一，要求得到函數(shù)f不相交的最簡SOP形式

A：將函數(shù)f的最簡SOP形式的各積項以尺寸大小排列，

設(shè)此序列： ；

其中

將0 f。

B：檢查積項 - ，或者 任何兩個積項的相交情況，

（二）如果其中任何兩個積項都不相交，則轉(zhuǎn)為E；

（三）如果 或 時，如果P1與Pl（2≦i≦k或k）時相交，根據(jù)如果函數(shù)f由兩個相交的積項P1與P2組成的SOP形式，則f=P1+P2為最簡的定律，可以推知 取代原積項Pi，如果不相交，則 ，保持原積項不變，進(jìn)入C。

（四）當(dāng) ，

或 ，或j=k，或j=k首先在p1-pi中選取某個Pk作為Pl與Pk，相交的積項Pl[1≦l≦k（或k，l i）]的數(shù)目較??；

在與Pi相交的其余各積項中，各pi1中得到的文字?jǐn)?shù)較小，根據(jù)以上（2）中的方法可以求到每個pl，但到新積項的最小值，該條件被滿足時，積個新積極項中所含文字?jǐn)?shù)的和最小，之后進(jìn)入C。

C：f+P1 f，通過B能得到各積項或其子SOP形式中的積項，可得到由大到小的重新排列序列：

D：如果k>1，則進(jìn)入B，如果等于1，進(jìn)入E

D檢查k（或者k）數(shù)值，如果大于1，則：

，結(jié)束算法。

如果等于1，則：

，結(jié)束算法。

算法二，求函數(shù)f用M（1）實現(xiàn)最小樹形網(wǎng)絡(luò)。

本文提出的算法，是先求出承數(shù)f用二選一選擇器來實現(xiàn)最小數(shù)形網(wǎng)絡(luò)，再將網(wǎng)絡(luò)轉(zhuǎn)化為M（C）（C>1）來實現(xiàn)，由于最小化目標(biāo)使現(xiàn)函數(shù)f在數(shù)形網(wǎng)絡(luò)中每個選擇器數(shù)目能連接的最大數(shù)目的平凡子函數(shù)。

A：將函數(shù)f化為SOP形之，可以使用前面算法理論得到。

B由于算法理論得到的函數(shù)f的SOP形轉(zhuǎn)轉(zhuǎn)化為不相交的最簡SOP式，這可以根據(jù)算法一實現(xiàn)。

C：要得到樹形網(wǎng)絡(luò)小最化目標(biāo)，需要得到函數(shù)f變量級的劃分，根據(jù)定律可知：

一個定義在變量集X上的函數(shù)f，與定量集X上的一個化分為：

在函數(shù)的簡化積之和的形式中，如果有一個積項：

其中：

Pk為含 部份或全體的積項，單個文字為積項的特例，f的SOP形式除積項Pa外的每個積項Pl中，都含有一個文字 ，函數(shù)f關(guān)于積項P的函數(shù)限制為 。

在定理中的a為平凡子函數(shù)，則：

，或者使a為單個M（1）實現(xiàn)的積項；

或（和）能生成一個或多個函數(shù)限制為0的積項；

根據(jù)定理：

對于一個定義在變量集X上的函數(shù)f，與變量集X上的劃分式，在函數(shù)f的RSOP形式中，如果兩個積項 與 含有公因子 ，在SOP形式中提出公因子后可得到：

，其中 ， 得 為部份或全體 的兩個積項，在此SOP形式中除了 與 之外的每個積項Pl中，都至少含有一個文字 ，函數(shù)關(guān)于積項P的函數(shù)限制為 ；

可以得到t為一個平凡子函數(shù)，即： 或（和）能生成分支共享的子函數(shù)；

D：用限制運算求得函數(shù)限制 ；

E：如果 是為不能用單個M（1）實現(xiàn)的非平凡子函數(shù)，則繼續(xù)C與D直到函數(shù)限制為平凡子函數(shù)，或者為可用單個M（1）實現(xiàn)為止，結(jié)束算法。

2，應(yīng)用實例

用M（2）實現(xiàn)以下函數(shù)

的最小樹型網(wǎng)絡(luò)結(jié)構(gòu)為例，

1）得到化簡形式

使用最小化方法將準(zhǔn)備實現(xiàn)的函數(shù)f化簡為DRSOP形式為：

2）得到樹形網(wǎng)絡(luò)最小化目標(biāo)

根據(jù)以上算法理論與定理可以得到函數(shù)f的變量集上的劃分。

上式的積項為： ；

除上式積項外，每個積項都應(yīng)該含有 集合中的文字，并且：

；

對于積項 與 ，可以得到：

；

積項 以及f中除積項 和積項 以外其余各項都都至少含有一個屬于 集合中的文字，并且 ，

于是可以劃分為： ；

3）限制運算

求得函數(shù)f關(guān)于 、 、 、 的函數(shù)限制為：

，

，

4）求單個M（1）實現(xiàn)

如果 與 不能用單個M（1）實現(xiàn)，則繼續(xù)進(jìn)行2）與3）的過程，得到結(jié)果為：

， ；

， ， ，

與 的函數(shù)限制都可以用單個M（1）實現(xiàn)，其余函數(shù)限制為平凡子函數(shù)，算法結(jié)束。

根據(jù)以上函數(shù)限制可以得到函數(shù)f的用M（1）用最小樹形網(wǎng)絡(luò)實現(xiàn)形實為：

M（1）實現(xiàn)的最小樹形網(wǎng)絡(luò)

轉(zhuǎn)化為M（2）實現(xiàn)的最小樹形網(wǎng)絡(luò)形式為：

M（2）實現(xiàn)的最小樹形網(wǎng)絡(luò)

三、結(jié)論

為了合理的選擇數(shù)字多路選擇器樹形網(wǎng)絡(luò)配置，有提出了卡諾圖分割法，然后用該種方法，函數(shù)變量超過6個時，圖形分割會變得復(fù)雜，也有提出使用Walsh譜法，使用該種方法當(dāng)函數(shù)變量增加時，譜系數(shù)會大幅度增加，也有提出利用計算機(jī)綜合自動法，然而算法非常復(fù)雜，而現(xiàn)在使用基于邏輯函數(shù)不相交的積之和形式的代數(shù)方法，既可以使現(xiàn)數(shù)字多路選擇器數(shù)形網(wǎng)絡(luò)達(dá)到最小樹形的實現(xiàn)，也則可以避免以上方法的弊端，經(jīng)過實例證明，這種方法是科學(xué)合理的。

參考文獻(xiàn)：

[1].VOLTH R P.ULM implicants for minimization of universal logic module circuits[J].IEEE Trans Comput 1977，C-26（5）；417-424.

[2].TOSSER A J，AOUAD-SYAD D.Casade networks of logic functions built in multiplexer units[J].IEE Proc Pt E，1980，127（2）：64-68.