数字多路选择器树形网络设计理论和算法分析

史群峰

[摘 要]：本文提出以逻辑函数不相交的简化积之和形式的代数方法实现数字多路选择器的方法，通过实例证明，该种方法是科学有效的。

[关键词]：数字多路选择器 树形网络设计

多路选择器是多功能通用逻辑模块的一种，当使用多路选择器通用模块实现多变量组合的函数时，受模块的地址墙个数的限制，需要选取变量集合的一个划分，并将划分块中的变量分配给网络中每级网络中各个选择器的控制墙，作为控制墙的变量，以树形网络的形实实形。每级网络中各个选择器控制变量的配置最终决定多路选择器的繁简程度，如果构成多路选择器网络用的数目是最小的，就被称为最小树形网络，这个网络每级、每个控制变量的配置即为最佳配置。利用多路选择器网络实现任意布尔函数是近代数字学者认为非常重要的一个课题，本文尝试用逻辑函数不相交的简化积之和形式的代数方法实现数字多路选择器的方法实现多路选择网络设计的最小树型网络，并且提出实现的理论、方法，给出运算的实例，通过一系列实例可以证明这种理论和操作方法是可以实现的，它可以实现多路选择器的最终综合。

一、理论

多路选择器使用逻辑模块实现布尔函数的理论，是由于布尔函数的展开式。如果在一个变量集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.