數字多路選擇器樹形網絡設計理論和算法分析

史群峰

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

[關鍵詞]：數字多路選擇器 樹形網絡設計

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

一、理論

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

其中：

n≧s≧，

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

（為空集）， ，

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

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

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

那么可以得到：

在這個公式中，函數f關于積項 、 的函數限制為：

；

因此可以得到： ；

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

它定義為：

其中：

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

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

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

二，.算法與實例

1，算法

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

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

設此序列： ；

其中

將0 f。

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

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

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

（四）當 ，

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

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

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

D：如果k>1，則進入B，如果等于1，進入E

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

，結束算法。

如果等于1，則：

，結束算法。

算法二，求函數f用M（1）實現最小樹形網絡。

本文提出的算法，是先求出承數f用二選一選擇器來實現最小數形網絡，再將網絡轉化為M（C）（C>1）來實現，由于最小化目標使現函數f在數形網絡中每個選擇器數目能連接的最大數目的平凡子函數。

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

B由于算法理論得到的函數f的SOP形轉轉化為不相交的最簡SOP式，這可以根據算法一實現。

C：要得到樹形網絡小最化目標，需要得到函數f變量級的劃分，根據定律可知：

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

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

其中：

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

在定理中的a為平凡子函數，則：

，或者使a為單個M（1）實現的積項；

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

根據定理：

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

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

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

D：用限制運算求得函數限制 ；

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

2，應用實例

用M（2）實現以下函數

的最小樹型網絡結構為例，

1）得到化簡形式

使用最小化方法將準備實現的函數f化簡為DRSOP形式為：

2）得到樹形網絡最小化目標

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

上式的積項為： ；

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

；

對于積項 與 ，可以得到：

；

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

于是可以劃分為： ；

3）限制運算

求得函數f關于 、 、 、 的函數限制為：

，

，

4）求單個M（1）實現

如果 與 不能用單個M（1）實現，則繼續進行2）與3）的過程，得到結果為：

， ；

， ， ，

與 的函數限制都可以用單個M（1）實現，其余函數限制為平凡子函數，算法結束。

根據以上函數限制可以得到函數f的用M（1）用最小樹形網絡實現形實為：

M（1）實現的最小樹形網絡

轉化為M（2）實現的最小樹形網絡形式為：

M（2）實現的最小樹形網絡

三、結論

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

參考文獻：

[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.