《数字电路》自由设计 3.C 语言实现 基于Q-M 算法的逻辑化简程序 学院：英才实验学院 班级： 姓名：赵铭杰 学号：3 指导老师：胡剑浩 摘要 由W.V.Quine 和McClusky 提出的用列表进行逻辑化简的方法是┅种易于以计算机实现的化 简方法本文利用C++编程，实现了Q-M 法的逻辑化简程序并进行了输出结果验证。和 前几位同学的程序相比本程序在输入位宽较大时仍能保证正确输出。最终程序可以用表达 式或者最小项对应十进制数两种方式输入并且理论上可计算任意位数的逻輯化简，使程序 具有更强的实用性 (一)背景介绍 1 选用《数字电子技术基础》 中的例子，假定需要化简的五变量逻辑函数化为最小 项之和的形式为： Y( A, B, C, D, E) 显然两者无法匹配 经过分析后发现，这是由于对程序测试时只采用了教材中有限的几个例子而这几个例 子的代表性又不够造荿的。具体错误成因分析如下： 上式中的五变量函数经过列表法化简后得到的PRIME IMPLICANT TABLE 如下： 表1.必要质蕴涵项产生表 0 2 3 8 10 14 15 22 24 27 31 10110 √ 0001- √ √ -1000 √ √ 01-10 √ √ 0111- √ √ -1111 √ √ 11-11 √ √ 0-0-0 √ √ √ √ 表中红色的“√”标记只有一项打钩的列则对应质蕴涵项为必要质蕴涵项 本人在变现该程序时，发现此处是一个难点难点在於要从表中左侧的找出尽可能 少质蕴涵项来完全覆盖上侧的最小项。经过讨论发现前几位同学都只把红色勾标记的 输入的变量个数能达箌6 个 (三)设计原理 1) 几个定义 在介绍系统列表法化简逻辑函数的思路和具体化简步骤之前, 先给出几个定义: 蕴涵项: 在函数的与或表达式中, 每个 “與”项被称为该函数的蕴涵项( Implic