英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
布尔代数在开关电路设计和误差检测中的应用
总结-寻求简化具有多个输出的开关电路的一般问题的解决方案。这个问题的数学处理只适用于布尔代数中可能用*#39;多项式#39;表示的电路，表明这种电路的多输出问题的某些部分可能被减少为一个输出问题，其输入相等数量与原始问题中输入和输出数量的总和，在两个输出的情况下可以实现特别简单的减少为了简化称为“ 多项式”的布尔表达式，描述了各种技术，其中操作“独占“或”出现在术语之间“，所描述的方法特别适用于自动计算机，并且已经在Illiac上进行过测试。在被称为”网络“的某些” 多项式“类别的成员之间存在意外的度量关系。“这种关系可以用于构建错误检测代码，提供两个编解码器中的比特数。
根据Shannon的工作，开关电路的设计主要依赖于逻辑代数，Burkhart，Kalin，Aiken，Quine,等人已经开发了系统方法，用于减少逻辑代数中的多项式表达式。这些技术应用的大部分有效性取决于设计者的技能以及他愿意花费的时间来控制应用系统性复位过程后获得的代数表达式。 在经常遇到的情况下尤其如此，在这种情况下，特定电路需要多于一个的输出。这里，处理单输出电路的系统方法将扩展到多输出情况 提出修改建议。
多个输出电路
开关电路将被定义为一个电路，其中电路中任何点的电压（或电流）可以取两个可能的值中的任意一个。 这些值可以用符号0和1任意描述。假设这个电路具有施加输入电压的p点,,, ... ,和其他点，，，...，，从中可以得到输出。 将进一步假定电路中的所有电压将由个输入的组合效应唯一确定。 如果每个q输出都针对p个输入端的每个允许值组合指定，则电路的逻辑规范已经完全给出，并且每个输出可以表示为输入的逻辑函数
（1）
一般来说，输入中某些值的组合不会发生，因此输入不会完全独立。 这种关系将用附属条件
（2）来表示
从来不会发生的那些输入值的组合就是g = 1的那些组合。因此，条件（2）完全指定了这些组合。现在可以使用代数操作来简化函数表达式（1），同时利用辅助条件（2）。这些操作应该倾向于。根据规定的简单标准简化对应于（1）的开关电路，同时保持电路的逻辑规范。如果这些操作是凭经验进行的话，可能相当困难且乏味。 通常有必要扩展函数以使它们更复杂，然后才可以简化。因此，开发了系统方法来减轻设计者在减少功能中涉及的一些繁琐工作。
输入,, ..., 的函数可以用规范形式表示
（3）
其中表示的补码（或否定），而符号“”表示逻辑运算“或”。在一个特定的术语中，输入及其补码通过逻辑运算“和”连接。j 1项的系数是具有值0或1的常数，并且用于在输入值使得j 1项中的其他因子全部为1时定义的值。
扩展（3）是布尔代数中所谓的多项式的特例。 然而，在一般多项式中，术语不需要依赖于所有输入，但它可以由输入的少于p和输入的补数的乘积表示。因此和也可以看作是多项式。 如果在术语之间使用“异或”（由“ ”指定）的操作，则可以形成不同类型的多项式。 这样的多项式将被称为 多项式，而前一类型将被称为多项式。由于（3）中的所有项都是不相交的（从不超过一个项可能等于1），所以扩展（3）也可以写成 多项式，并且可以使用“ ”来代替“”出现，给出 （4）
在讨论多个输出函数时，结果对于 多项式和多项式都是有效的，而符号“ ”将用于表示这两种操作。此外，术语多项式意味着任何一种多项式。 布尔代数中的函数，如和g也将以多项式形式表示。
如果已经以多项式形式实现了函数的适当减少，则必须指定一组多项式，每个多项式在制造某些z函数时将被使用。这些多项式将写成，其中如果在的构造中使用，则的值将为0如果不是，则值为1。一般来说，这些多项式有个，因为对于全部而言，不可能是1。简化后的功能将被写为
（5）
其中总和被取代为所有其中= 0的。在该总和中，多项式之间的运算是“”或“ ”取决于是否正在使用多项式或 多项式而。 在形成具有输出的开关电路中，每个多项式将被首先制造，然后根据（5）进行组合。
现在可以将减少产生输出的开关电路的问题分为两部分：
- 同时使多项式组最小化的问题。
- 最小化（5）中这些多项式之间的连接词数量的问题。当多项式都不为零时，由于连接词的结构是不可改变的，因此可以忽略（b）部分。另一方面，如果输出数量大，输入数量小，则（b）部分倾向于承担与（a）部分相当的重要性。
定理1：同时最小化用于构造具有p个输入和q个输出的“电路”的多项式的问题可以由寻找最小多项式来代表具有p q个输入的某个单个输出电路的问题来代替。
证明：为了这个定理的目的，没有必要精确地定义最小化的含义，因为这两个过程仅仅被证明是等价的。
假设在上述定理中描述的虚构单输出电路除了在多输出电路中使用的输入,,, ... ,之外还假定使用q个输入,，...,。 假想电路的单输出F被定义为
（6）
正如假设输入,,, ... ,受条件所限制的那样，人工输入将受以下条件限制： （7）
为了将所有这些条件表达为单一条件，可以添加它们:
（8）
在这最后一个表达式中使用的总和被理解为使用“”操作，而该证明中的所有其他和表示“”或“ ”，具体取决于正在考虑哪种类型的多项式。
如果（6）所定义的F被最小化，则条件（8）将被表示为多项式P。从（7）可以看出
（9）
而出现在P中的每个可以相应地被替换。替换完成后，可以写出结果多项式
（10）
其中，是涉及,,, ... ,的多项式， 并且符号由下式定义：
表达式（10）中的总和被不是全部为1的值的个组合取代了。
- 中的现在仍然是用（10）中的方法来确定。 从（6）和（7）可以看出，如果假设值1，关系（6）将变为。 然后（10）变成（5），因为（10）中包含的项消失。如果（5）没有被这个过程最小化，那么存在满足（5）的一个更简化的集合。 这些方程可以在（6）中被替代，并且可以使用（7）被操纵成（10），从而得到（10）的更简化版本。 由于（10）被认为是最小的，所以与假设相矛盾并且证明了该定理。
公式（5）现在表示由最小多项式组成的多输出电路。
当q = 2时，定理1专门表示一种方便的方式，定理2表示这种特殊情况。公式（7）则变成
如果使用单个条件，那么这两个方程都将自动满足，因此可以通过该方程消除，并且不需要附属条件。
定理2：使具有以多项式形式表达的p个输入的两个输出电路最小化的问题可以由最小化具有p 1个输入的单个输出电路的问题来代替。
等式可以表示如下：
在（6#39;）中，用代替（6）中的，并且在（10）中用代替。这样（7）变得不再必要。
举例来说，可以使用没有附属条件方程组：
这些方程表示一个单级二进制加法器，其中是输出，是进位。公式（6）变为：
另外没有附属条件要使用。 使用 多项式缩减技术，将在下一节中进行描述，该多项式可以被缩减为
这给了
以完成构造。
多输出电路由下式表示：
这些表达式不一定是Z1和Z2的最简单形式。 通过将“ ”替换为“”并通过因式分解进一步减少超出了本讨论的范围，因为所得到的表达式将不再是多项式。
减少 多项式
Quine以及Burkhart，Kalin和Aiken对多项式的还原进行了全面分析.这些方法的扩展包括了IS Reed所执行的辅助条件的可能性。将这些方法应用于定理1允许多个输出电路。
通过使用包含 多项式的方法进行电路缩减提供了一个替代过程，该过程通常与涉及多项式的过程产生显着不同的结果。 通过回顾，操作“ ”的重要性质为：
（11）
如果将式（i）作为定义，则可以直接推导出其他式。由于规则（v），很明显，一个式子不需要在多项式中保留重复项。出于这个原因，将假设重复项总是以任何多项式表示进行组合。操作可以在多项式上执行，使它们等于相同的布尔函数，但改变它们的形式。两个多项式和只有当它们在等效时才被认为是等价的。这样的关系将被写成，而将被认为意味着两个多项式等于相同的布尔函数，但不一定是等价的。符号将表示包含两个项的多项式和，除了根据（v）组合重复项。将表示两个多项式的扩展乘积，并且将表示仅具有和共有的项的多项式。
可以用来改变 多项式的形式而不改变其功能的一般算子由下列关系式定义：
其中是取决于的 多项式并且可以是 或者可能不依赖于。如果与无关，则运算符是自己的逆，因为。这种类型的特殊操作可以以各种方式形成。类型的四个运算符可以通过下式来定义：
其中，，和是独立于的多项式。 它们是：
符号将被用来表示这四个运算符中的任何一个，并且可以被证明具有代数性质
定理3：运算符将多项式归约为其规范形式（4）。
证明：是一个多项式，其中每个项包含或。为了看到这个可以写成A，P 如果多项式中的所有项都包含或，那么也具有此属性，因为不会引入既不包含也不包含的项。因此的每一项都包含每个输入或其补数。因此具有（4）的形式，（4）是每个函数的唯一规范形式。 从此以后，表达式将被缩写为。
定理4：如果那么它有可能通过一般类型的p运算将转换为。
证明：如果代表和的典范形式，则关系和则满足。现在可以将表达式中的多项式视为不依赖于的因子，因为它们由关系和来定义。由于所涉及的是常数，所得到的运算符可能不再被认为是类型，这些运算符将被写成和 当用于该等式时，运算符具有相同的效果，但是当应用于不同的多项式时，它将不具有相同的效果，因为在的情况下多项式将被不是在的情况下改变。
因此，如果
和
然后
和
但
而
由于算子使用常数通常是它们自己的反转，所以很显然
及
然而，算子可能被认为是单个算子，因为可能加入了的参数，并证明了该定理。
从定理4可以看出，类型的运算足以将任意多项式减小到其最小形式。这种减少通常是不可能的，因为在不知道的情况下通常无法找到所需的操作。
如果组合型算子，将获得各种特征形式。 定理5证明了这些形式的存在。
定理5：如果，则其中可以代表每个j的四个运算符，，或中的不同者，但是必须等式两边意思相同。
证明：设则根据属性1和3，类似地，并因此。
根据这个性质，算子可以被认为产生了“特征”多项式。由于每个运算符（它可以是，，或）有四种可能的选择可用，所以这种扩展的数量是个。 这种类型的特别对称的扩展是由算子产生的。 诸如由产生的其他扩展具有将在后面描述的奇异量度属性。
在类型在类型的操作符的帮助下执行多项式的简化，但是原则上必须依赖于由数学上不太感兴趣的算符，其由下式定义：
其中，和不涉及或，并且由关系式定义。 由等代表的多项式与以前一样被定义为那些包含和等共有术语的项。没有的方便的代数性质，但它倾向于减少它应用的多项式。 如果“a”表示多项式中的一个项，则会影响以下类型的简化：
（12）
因此可以应用于多项式的最简单的简化类型之一是由表示的，其将由表示。尽管算子倾向于简化它所应用的多项式，但它通常会产生比通过更精细的方法所获得的结果复杂得多的结果。为了获得比仅仅通过使用运算符可能实现的更大的简化，每当随后应用运算符进行更大的简化时，可以通过反转前三个运算（12）中的一个来扩展每个项。 这种被称为方法I的过程可以逐步解释如下：
- 从一个多项式开始简化。 它首先被简化为规范形式：
- 通过使用最初简化了该结果
- 简化算子根据以下定义构造：
的连续应用产生
- 根据以下定义构造运算符
并且最终结果由下式给出：
在这个过程中，只要通过应用算子可以简化多项式，运算符和就具有扩展多项式的效果。
通过使用门多项式可以形成比运算符更有效的运算符。 如果表示具有在多项式和中的任一个或两个中的项的多项式，则多项式可以被定义为：
其中
为了符号的目的，让
并让
并让
然后
最后
。
现在可以将方法II描述为方法I，其中代替出现。 方法II具有形成多达两次扩展的优点，提供稍后的收缩使其具有优势，并因此产生更有效但更耗时的过程。
对于这些过程的选择而不是涉及扩展和扩展的其他过程的理由主要基于它们在减少随机选择的多项式方面的效率。 一组20个随机选择的5个输入函数被用于比较不同的过程。 取最终多项式中的项数作为方法有效性的方便度量，表I中比较了方法I、方法II和简单的算子得到的结果。
表I
五个输入的二十个随机函数用于测试三个简化过程。 简单扩展的术语数量在每个案例中都有列出
lt;
全文共7765字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11137]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
