CN118051202A - 一种三进制乘法器设计和实现方法及装置 - Google Patents

Abstract

本发明涉及一种三进制乘法器设计和实现方法及装置，该方法及装置首先构建华莱士树乘法器结构，再运用华莱士树乘法器结构并结合三进制逻辑综合法生成三进制乘法器的最简晶体管组合电路，旨在解决现有三进制乘法器设计中高延时、低能效等问题。

Description

一种三进制乘法器设计和实现方法及装置

技术领域

本发明涉及乘法器领域，具体而言，涉及一种三进制乘法器设计和实现方法及装置。

背景技术

当前计算机和集成电路均采用二值逻辑电路，以高低电平表征1和0两个状态，但是随着器件微型化的大潮到来，二值逻辑的弊端也开始显现：信息密度较低、布线面积难以进一步减小、信号传输效率不高。因此，要实现大的性能突破，其中一个方向便是使用多值逻辑系统来增加每个给定器件的信息表达量。人们开始从这种以“2”为基数的计数方式延展到一种以“3”甚至更大数为基数的进制并逐渐完备其逻辑与数学运算法则，理论上来说三进制逻辑是效率最高的进制，且三进制的信息密度是二进制的1.58倍。

三进制有两种表达方式：一种是状态集合为[0，1，2]的非平衡三进制，这种集合实际就是以3为基底的表达方式；另一种是状态集合为[-1，0，1]的平衡三进制。这种集合可以极大的扩充计算机的逻辑能力，且不需要添加额外的符号位，正负号一致性减少了乘法过程中的进位。

然而，对于如何实现三进制逻辑电路是个棘手问题，现行的半导体器件天生适合实现二进制逻辑，用来做三进制逻辑会有很大的面积开销和较大的静态功耗和延时。因此，目前的研究集中于设计适合三进制的晶体管，比如硅基隧穿型、碳基多阈值型的晶体管等，这些器件还存在的问题在于器件速度较慢，或是器件复杂难以制造等。不过目前来看碳基多阈值晶体管(CNTFET)是设计三进制逻辑电路的主流器件，但很多三进制加法器和乘法器等三进制逻辑电路的设计对比二进制的延时、功耗还是大很多。目前，传统的三进制乘法器采用的阵列型结构乘法器在运算速度比较慢，一些研究中的三进制乘法器的计算准确性也不够，三进制乘法器的能效还有很大提升空间的。所以，目前亟需一种低延时、高效率的三进制乘法器解决方案。

发明内容

本发明实施例提供了一种三进制乘法器设计和实现方法及装置，以至少解决现有三进制乘法器延时高、能效低的技术问题。

根据本发明的一实施例，提供了一种三进制乘法器设计和实现方法，包括以下步骤：

构建华莱士树乘法器结构；

运用华莱士树乘法器结构并结合三进制逻辑综合法生成三进制乘法器的最简晶体管组合电路。

进一步地，华莱士树乘法器结构包括：

计算1位的平衡三进制部分积电路；

计算1位的非平衡三进制部分积电路；

华莱士树乘法器结构，包括计算平衡三进制和非平衡三进制的两种乘法器结构；

基于三进制加法器的进位传播加法器。

进一步地，构建华莱士树乘法器结构包括：

首先是使用逻辑综合法生成设计平衡/非平衡三进制一位乘部分积电路，其中平衡三进制一位乘电路不需要进位输出，而非平衡乘法需要；

得到部分积后利用循环门加法器进行累加，每三行为一组，不足三行的保持，逐层累加剩下最后两行结果，再使用进位传播加法器输出最终结果。

进一步地，华莱士树乘法器的乘法计算流程包括：

步骤一、首先利用三进制一位乘法器生成按位乘结果，平衡三进制只有部分积结果；

步骤二、将生成的部分积阵列进行分组，每个阶段中每三行分为一组，不足三行的则保留到下一阶段处理；每组按列分配，一列中有三个元素的则作为全加器的输入，有两个元素的则作为半加器的输入，只有一个元素则保留到下一阶段处理；

步骤三、分配好输入后同时对各组进行加法计算；

步骤四、计算的和与对应进位结果按步骤一的形式摆放；

步骤五、判断新生成的部分积阵列是否只剩下最后的两行数据，若是则进入下一阶段步骤六，否则回到步骤四的处理；

步骤六、最后的两行数据作为进位传播加法器的输入，计算出最终的三进制乘法结果。

进一步地，三进制逻辑综合法包括以下步骤：

步骤一、制定三进制逻辑门的功能真值表；

步骤二、根据功能真值表判断是产生Vdd/Gnd路径的上拉/下拉网络还是半Vdd路径的上拉/下拉网络；

步骤三、判断如果是Vdd/Gnd路径的上拉/下拉网络则由奎因-麦克拉斯基算法处理；判断如果是半Vdd路径的上拉/下拉网络则进行无关项处理后再用奎因－麦克拉斯基算法处理，然后判断输出是否包含所有无关项，如果是则进入步骤四，否则，需要重新回到无关项处理；

步骤四、优化表达式，到达最简晶体管数量和最低延时；

步骤五、选择最佳的SOP；

步骤六、获取从SOP到晶体管网络的映射关系；

步骤七、得到三进制逻辑的SPICE电路模型。

进一步地，根据三进制逻辑门函数的真值表导出的上拉/下拉网络，得到四个上拉/下拉表:

对于Vdd/Gnd路径的上拉表，如果真值表的输出为1，则表的状态变为ON；否则，表的状态变为OFF；

对于Vdd/Gnd路径的下拉表，如果真值表的输出为-1，则表的状态变为ON；否则，表的状态变为OFF；

对于Vdd/2路径的上拉表，真值表的输出为0时，表的状态变为ON；当真值表的输出为1时，表的状态变为无关项，表示相应的输入组合不影响网络的切换操作；对于其余情况，表的状态变为OFF；

对于Vdd/2路径的下拉表，当真值表的输出为-1时状态变为无关项，真值表的输出为0时为ON，当真值表的输出为0时为OFF真值表为1。

进一步地，转换路径的上拉/下拉表中的无关项，每个无关项转换为ON或OFF，选择利用最少晶体管数量的最佳情况；

对于生成的上拉/下拉表，对三进制函数进行最小化处理。

进一步地，使用Q-M算法将给定的最小项规范表达式合并到具有最佳晶体管数量的SOP表达式中，具体包括：

第一步：算法通过反复合并蕴涵项来找到所有的主蕴涵项；该算法从生成的上拉/下拉表中提取最小项；提取的最小项是上拉/下拉表中相应输出为ON的输入组合；生成蕴涵项时，根据三进制逻辑中“0”的数量和“+”的数量进行分组；在对所有蕴涵项进行分组后，该算法检查是否与相邻组中的其他蕴涵项合并；如果一个蕴涵项的组合为[x，y]，则[x±1，y]、[x，y±1]、[x-1，y+1]和[x+1，y-1]组合与它相邻；合并两个具有相邻组且仅相差一个三进制组的蕴涵项，并以此迭代合并，直到不能再与其他蕴涵项合并为止；

第二步：通过对适当的主要蕴涵项求和来获得SOP；使用从第一步获得的本质素蕴涵项，构造一个质蕴涵图；在算法获得所有基本素蕴涵项之后，搜索所有可能的非本质素蕴涵项组合，这些组合需要覆盖所有小项；最后，某些SOP则需通过将本质蕴涵项和所需的非本质蕴涵项相加产生。

进一步地，用Q-M算法产生多个SOP时，选择其中最佳的SOP；决定最佳SOP的两个因素为：网络的最小晶体管数量以及网络中的最小传播延迟；

如果晶体管数量相同，则选择其中含有阈值电压绝对值为碳纳米晶体管数量最少的SOP；SOP中的每个乘积项是通过串联晶体管来构造的；

最后，通过在SPICE模型中连接网络中的合适节点来合成逻辑门。

根据本发明的另一实施例，提供了一种三进制乘法器设计和实现装置，包括：

乘法器结构构建单元，用于构建华莱士树乘法器结构；

组合电路生成单元，用于运用华莱士树乘法器结构并结合三进制逻辑综合法生成三进制乘法器的最简晶体管组合电路。

一种存储介质，存储介质存储有能够实现上述任意一项三进制乘法器设计和实现方法的程序文件。

一种处理器，处理器用于运行程序，其中，程序运行时执行上述任意一项的三进制乘法器设计和实现方法。

本发明实施例中的三进制乘法器设计和实现方法及装置，首先构建华莱士树乘法器结构，再运用华莱士树乘法器结构并结合三进制逻辑综合法生成三进制乘法器的最简晶体管组合电路，旨在解决现有三进制乘法器设计中高延时、低能效等问题。

附图说明

此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：

图1为本发明三进制乘法器设计和实现方法的流程图；

图2为本发明中逻辑综合法各步骤处理的流程图；

图3为本发明中上拉/下拉网络以及Vdd路径图和上拉/下拉网络以及Gnd路径图；

图4为本发明中上拉/下拉网络以及Vdd/2路径图；

图5为本发明中非平衡三进制部分积电路结构及其真值表图；

图6为本发明中平衡三进制部分积电路结构及其真值表图；

图7为本发明中平衡三进制的6-trit×6-trit华莱士树乘法图；

图8为本发明中平衡三进制华莱士树乘法在阶段4中用到的进位传播加法器的结构图；

图9为本发明中非平衡三进制的6-trit×6-trit部分积阵列示意图；

图10为本发明中华莱士树乘法器计算流程图；

图11为本发明中华莱士树乘法器和传统乘法器的性能对比图；

图12为本发明中三进制乘法器设计和实现装置的模块图。

具体实施方式

为了使本技术领域的人员更好地理解本发明方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分的实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都应当属于本发明保护的范围。

需要说明的是，本发明的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本发明的实施例能够以除了在这里图示或描述的那些以外的顺序实施。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法、系统、产品或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它步骤或单元。

根据本发明一实施例，提供了一种三进制乘法器设计和实现方法，参见图1，包括以下步骤：

S101:构建华莱士树乘法器结构；

S102:运用华莱士树乘法器结构并结合三进制逻辑综合法生成三进制乘法器的最简晶体管组合电路。

本发明实施例中的三进制乘法器设计和实现方法，首先构建华莱士树乘法器结构，再运用华莱士树乘法器结构并结合三进制逻辑综合法生成三进制乘法器的最简晶体管组合电路，旨在解决现有三进制乘法器设计中高延时、低能效等问题。

为解决目前计算三进制逻辑的乘法器电路中普遍存在的高延时、低能效等缺点，本发明提出一种低延时、高能效的三进制乘法器设计和实现方法，旨在解决现有三进制乘法器设计中高延时、低能效等问题。包括平衡三进制的部分积电路模块、非平衡三进制的部分积电路模块以及计算平衡三进制和非平衡三进制的两种华莱士树乘法器结构；树状的加法器累加结构和并行运算思想是本发明的核心，以及运用低功耗网络结构的逻辑综合法设计逻辑电路的提出。

本发明为解决其技术问题提出以下技术方案：

1、三进制逻辑综合法

三进制逻辑综合法是根据三进制功能逻辑的真值表要求，来生成最简晶体管组合电路(sum of products，下面简称为SOP)的综合法，如图2所示，该方法包括以下步骤：

步骤一、制定三进制逻辑门的功能真值表；

步骤二、根据真值表判断是产生Vdd/Gnd路径的上拉/下拉网络还是半Vdd路径的上拉/下拉网络；

步骤三、如果是Vdd/Gnd路径的上拉/下拉网络则由Quine-McCluskey(奎因-麦克拉斯基)算法处理。如果是半Vdd路径的上拉/下拉网络则进行无关项处理后再用奎因－麦克拉斯基算法处理，然后判断输出是否包含所有无关项，如果是则进入步骤四，否则，需要重新回到无关项处理步骤；

步骤四、优化表达式，到达最简晶体管数量和最低延时；

步骤五、选择最佳的SOP；

步骤六、晶体管映射：从SOP到晶体管网络的映射方法见表1，共使用6种阈值电压的CNTFET(单壁碳管纳米场效应晶体管)，其阈值电压与管中碳原子排列角度的手性矢量有关；

步骤七、得到三进制逻辑的SPICE电路模型。

2.华莱士树乘法器结构，类似于二进制的华莱士树乘法，三进制的乘法也适用。该结构可以极大地减少最长延迟路径，实现低延迟、高效率计算。首先是设计平衡/非平衡三进制一位乘(部分积)电路，这需要使用逻辑综合法生成，其中平衡三进制一位乘电路不需要进位输出，而非平衡乘法需要。得到部分积后利用循环门加法器进行累加，每三行为一组，不足三行的保持，逐层累加剩下最后两行结果，再使用进位传播加法器输出最终结果。

本发明提供的低延时、高效率的三进制华莱士树型乘法器模型，包括：

计算1位的平衡三进制部分积电路；

计算1位的非平衡三进制部分积电路；

华莱士树乘法器结构，包括计算平衡三进制和非平衡三进制的两种乘法器结构；

基于三进制加法器的进位传播加法器。

根据本发明实施例，参见图2-11，提供了一种低延时、高效率的三进制部分积电路和华莱士树乘法器结构。

实施例一

输入信号中带有下标为N或P的，是输入信号经过NTI、PTI后的输出结果。其中，NTI与PTI是三进制的两种反相器，PTI是将中间态输入变为高态输出的正三进制反相器，NTI是将中间态输入变为低态输出的负三进制反相器。比如信号A经过NTI输出为AN，经过PTI输出为A_P；工作电压Vdd取0.9V；

两个部分积电路的基本的结构可分为上拉网络和下拉网络，其原理为：

1.Vout＝Vdd时：(图3左)

上拉网络A开启，上拉网络B开启；下拉网络A关闭，上拉网络B关闭；红色双通路开启，使输出迅速变为Vdd；

2.Vout＝Gnd时：(图3右)

上拉网络A关闭，上拉网络B关闭；下拉网络A开启，上拉网络B开启；蓝色双通路开启，使输出迅速变为Gnd；

3.Vout＝Vdd/2时：(图4)

从Vdd转换到Vdd/2:下拉网络B和P型传输晶体管打开以转换。但由于阈值下降，无法将输出端子拉至|Vtp|＝0.428V以下；

从Gnd转换到Vdd/2:所有上拉网络都被关闭。上拉网络B和N型通晶体管接通以转移过渡。但由于阈值下降，无法将Vdd-Vtn＝0.472V以上的输出端拉起。因此，最后电路将会稳定在1/2(0.428+0.472)＝0.45V处电位，即Vdd/2的中间态；

下面说明从三进制逻辑门函数的真值表生成上拉/下拉表的方法。三进制逻辑门由四个上拉/下拉网络组成，每个网络执行不同的开关操作。因此，每个对应的网络都需要一个上拉或下拉表。上拉/下拉表存在ON或OFF状态，代表着相应输入组合网络的ON/OFF状态。如果电流流过特定输入组合的网络，则表示该网络已开启，相应的输出变为ON。例如，当输入变量A为-1且输入变量B为1时，如果Vdd/Gnd路径的上拉表的输出为ON，则电流流过Vdd/Gnd的上拉网络输入组合的路径。

根据三进制逻辑门函数的真值表导出的上拉/下拉网络，可得到四个上拉/下拉表:

(1)对于Vdd/Gnd路径的上拉表，如果真值表的输出为1，则表的状态变为ON；否则，表的状态变为OFF；

(2)对于Vdd/Gnd路径的下拉表，如果真值表的输出为-1，则表的状态变为ON；否则，表的状态变为OFF；

(3)对于Vdd/2路径的上拉表，真值表的输出为0时，表的状态变为ON；当真值表的输出为1时，表的状态变为无关项(X)，表示相应的输入组合不影响网络的切换操作。对于其余情况，表的状态变为OFF。

(4)对于Vdd/2路径的下拉表，当真值表的输出为-1时状态变为无关项，真值表的输出为0时为ON，当真值表的输出为0时为OFF真值表为1。

对于生成的上拉/下拉表，需要对三进制函数进行最小化处理。在处理之前，本发明必须转换路径的上拉/下拉表中的无关项。每个无关项都可以转换为ON或OFF，本发明选择利用最少晶体管数量的最佳情况。奎因－麦克拉斯基算法的作用是为了最小化布尔函数。这里用Q-M算法处理是将给定的最小项规范表达式合并到具有最佳晶体管数量的SOP表达式中。

第一步，算法通过反复合并蕴涵项来找到所有的主蕴涵项。该算法从生成的上拉/下拉表中提取最小项。提取的最小项是上拉/下拉表中相应输出为ON的输入组合。生成蕴涵项时，它们根据三进制逻辑中“0”的数量和“+”的数量进行分组。在对所有蕴涵项进行分组后，该算法检查它们是否可以与相邻组中的其他蕴涵项合并。如果一个蕴涵项的组合为[x，y]，则[x±1，y]、[x，y±1]、[x-1，y+1]和[x+1，y-1]等组合与它相邻。可以合并两个具有相邻组且仅相差一个三进制组的蕴涵项，并以此迭代合并，直到不能再与其他蕴涵项合并为止；

第二步，通过对适当的主要蕴涵项求和来获得SOP。使用从第一步获得的本质素蕴涵项，该算法构造一个质蕴涵图。在算法获得所有基本素蕴涵项之后，它会搜索所有可能的非本质素蕴涵项组合，这些组合需要覆盖所有小项；最后，某些SOP则需通过将本质蕴涵项和所需的非本质质蕴涵项相加产生的；

同时，如果用Q-M算法产生多个SOP时，必须选择其中最佳的SOP。决定最佳SOP的两个因素是：网络的最小晶体管数量以及网络中的最小传播延迟。如果晶体管数量相同，则选择其中含有阈值电压绝对值为0.687V的碳纳米晶体管数量最少的SOP，以减小网络的传播延迟；通过选择需要最少晶体管的SOP，可以最大限度地减少电路的功耗和面积，并最大限度地提高速度。SOP中的每个乘积项是通过串联晶体管来构造的，而不同乘积项间的或关系需要并联来实现。最后，通过在SPICE模型中连接网络中的合适节点来合成逻辑门。

另外，晶体管的体效应会影响电路系统的功耗。这里本发明将电路中的所有晶体管的体和源极(两个传输晶体管除外)都连接在一起，以消除晶体管的体效应。N型传输晶体管的体与Gnd相连，P型传输晶体管的体与Vdd相连。因此，当传输晶体管导通时，体效应被消除。而当传输晶体管关闭时，Vsb变为Vdd并且电流电平由于体效应而降低。因此，只有当输出电压保持在Vdd/2时才会出现体效应。通过体效应，减少了静态电流，降低了静态功耗。这种选择性开启体效应可以改善三进制逻辑门的静态功耗，同时尽量减小其性能下降。

实施例二

本实施例以6-trit×6-trit的平衡三进制乘法为例，对华莱士树乘法器的结构进行说明，这里的“trit”是三进制的基本单位，和二进制的转化关系为：1trit＝log₂3 bit≈1.58bit。平衡三进制华莱士树乘法的计算流程图在图7给出。

步骤一、首先需要利用三进制一位乘法器，即部分积电路生成按位乘结果，平衡三进制只有部分积结果。6-tirt乘法共产生36个部分积；

步骤二、需要将生成的部分积阵列进行分组，每个阶段中每三行分为一组，不足三行的则保留到下一阶段处理。每组按列分配，一列中有三个元素的则作为全加器的输入，有两个元素的则作为半加器的输入，只有一个元素则保留到下一阶段处理；

步骤三、分配好输入后即可同时对各组进行加法计算；

步骤四、计算的和(S)与对应进位(C)结果按步骤一的形式摆放；

步骤五、判断新生成的部分积阵列是否只剩下最后的两行数据，若是则进入下一阶段步骤六，否则回到步骤四的处理；

步骤六、最后的两行数据(图7的阶段4)作为进位传播加法器的输入，计算出最终的三进制乘法结果；

这里的进位传播加法器由对应的三进制加法器级联构成，共用到了一个三进制半加器(图中用THA表示)和六个三进制全加器(图中用TFA表示)，输出结果为7-trit。另外，m×n trit会生成(m+n)trit的结果，所以这里的6-trit×6-trit的输出为12-trit。

实施例三

非平衡三进制的华莱士树乘法器在生成部分积阶段与平衡三进制阵列相似，不同的在于除了乘积结果，还包括对应的36个进位结果。进位结果在排成部分积阵列时需要放在相应乘积结果的下一行，并向前进一位，与下一级部分积并列，见图9。其余的累加阶段与实施例二中的平衡三进制华莱士树乘法步骤相同。

根据本发明的另一实施例，提供了一种三进制乘法器设计和实现装置，参见图12，包括：

乘法器结构构建单元201，用于构建华莱士树乘法器结构；

组合电路生成单元202，用于运用华莱士树乘法器结构并结合三进制逻辑综合法生成三进制乘法器的最简晶体管组合电路。

本发明实施例中的三进制乘法器设计和实现装置，首先构建华莱士树乘法器结构，再运用华莱士树乘法器结构并结合三进制逻辑综合法生成三进制乘法器的最简晶体管组合电路，旨在解决现有三进制乘法器设计中高延时、低能效等问题。

一种存储介质，存储介质存储有能够实现上述任意一项三进制乘法器设计和实现方法的程序文件。

一种处理器，处理器用于运行程序，其中，程序运行时执行上述任意一项的三进制乘法器设计和实现方法。

上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。

与现有技术相比，本发明的优点至少在于：

在二进制中的华莱士树乘法运算的结构可以极大地减少最长延迟路径，将华莱士树乘法的思想迁移到三进制乘法器结构中也有此功效。相较于传统的阵列乘法器结构，由于采用了并行计算方法，华莱士树乘法结构的最长延迟路径(部分积电路与加法器)的长度可以减少为阵列型结构的一半以上，使用同样加法器构成华莱士树乘法器和传统阵列乘法器的性能对比如图11所示。并且，乘法计算的位数越高，华莱士树结构的优势越明显。因此，该结构可以显著地降低计算系统的延时、功耗和延时功耗积(PDP)，实现低延时、高效率的三进制乘法器。

本发明采用斯坦福大学提供的碳纳米管模型，基于Hspice软件对两种三进制部分积电路以及6位乘6位的三进制华莱士树乘法器进行搭建和仿真测试，仿真结果符合三进制乘法计算结果，并且通过测试得到数据与传统阵列型乘法器方案的仿真数据进行对比，实现更低的计算延时和PDP数据。

在本发明的上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。

在本申请所提供的几个实施例中，应该理解到，所揭露的技术内容，可通过其它的方式实现。其中，以上所描述的系统实施例仅仅是示意性的，例如单元的划分，可以为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，单元或模块的间接耦合或通信连接，可以是电性或其它的形式。

作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可为个人计算机、服务器或者网络设备等)执行本发明各个实施例方法的全部或部分步骤。而前述的存储介质包括：U盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、移动硬盘、磁碟或者光盘等各种可以存储程序代码的介质。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。

Claims (10)

1.一种三进制乘法器设计和实现方法，其特征在于，包括以下步骤：

构建华莱士树乘法器结构；

运用华莱士树乘法器结构并结合三进制逻辑综合法生成三进制乘法器的最简晶体管组合电路。

2.根据权利要求1所述的三进制乘法器设计和实现方法，其特征在于，所述华莱士树乘法器结构包括：

计算1位的平衡三进制部分积电路；

计算1位的非平衡三进制部分积电路；

华莱士树乘法器结构，包括计算平衡三进制和非平衡三进制的两种乘法器结构；

基于三进制加法器的进位传播加法器。

3.根据权利要求1所述的三进制乘法器设计和实现方法，其特征在于，所述构建华莱士树乘法器结构包括：

首先是使用逻辑综合法生成设计平衡/非平衡三进制一位乘部分积电路，其中平衡三进制一位乘电路不需要进位输出，而非平衡乘法需要；

得到部分积后利用循环门加法器进行累加，每三行为一组，不足三行的保持，逐层累加剩下最后两行结果，再使用进位传播加法器输出最终结果。

4.根据权利要求1所述的三进制乘法器设计和实现方法，其特征在于，所述华莱士树乘法器的乘法计算流程包括：

步骤一、首先利用三进制一位乘法器生成按位乘结果，平衡三进制只有部分积结果；

步骤二、将生成的部分积阵列进行分组，每个阶段中每三行分为一组，不足三行的则保留到下一阶段处理；每组按列分配，一列中有三个元素的则作为全加器的输入，有两个元素的则作为半加器的输入，只有一个元素则保留到下一阶段处理；

步骤三、分配好输入后同时对各组进行加法计算；

步骤四、计算的和与对应进位结果按步骤一的形式摆放；

步骤五、判断新生成的部分积阵列是否只剩下最后的两行数据，若是则进入下一阶段步骤六，否则回到步骤四的处理；

步骤六、最后的两行数据作为进位传播加法器的输入，计算出最终的三进制乘法结果。

5.根据权利要求1所述的三进制乘法器设计和实现方法，其特征在于，所述三进制逻辑综合法包括以下步骤：

步骤一、制定三进制逻辑门的功能真值表；

步骤二、根据功能真值表判断是产生Vdd/Gnd路径的上拉/下拉网络还是半Vdd路径的上拉/下拉网络；

步骤三、判断如果是Vdd/Gnd路径的上拉/下拉网络则由奎因-麦克拉斯基算法处理；判断如果是半Vdd路径的上拉/下拉网络则进行无关项处理后再用奎因－麦克拉斯基算法处理，然后判断输出是否包含所有无关项，如果是则进入步骤四，否则，需要重新回到无关项处理；

步骤四、优化表达式，到达最简晶体管数量和最低延时；

步骤五、选择最佳的SOP；

步骤六、获取从SOP到晶体管网络的映射关系；

步骤七、得到三进制逻辑的SPICE电路模型。

6.根据权利要求5所述的三进制乘法器设计和实现方法，其特征在于，根据三进制逻辑门函数的真值表导出的上拉/下拉网络，得到四个上拉/下拉表:

对于Vdd/Gnd路径的上拉表，如果真值表的输出为1，则表的状态变为ON；否则，表的状态变为OFF；

对于Vdd/Gnd路径的下拉表，如果真值表的输出为-1，则表的状态变为ON；否则，表的状态变为OFF；

对于Vdd/2路径的上拉表，真值表的输出为0时，表的状态变为ON；当真值表的输出为1时，表的状态变为无关项，表示相应的输入组合不影响网络的切换操作；对于其余情况，表的状态变为OFF；

对于Vdd/2路径的下拉表，当真值表的输出为-1时状态变为无关项，真值表的输出为0时为ON，当真值表的输出为0时为OFF真值表为1。

7.根据权利要求6所述的三进制乘法器设计和实现方法，其特征在于，转换路径的上拉/下拉表中的无关项，每个无关项转换为ON或OFF，选择利用最少晶体管数量的最佳情况；

对于生成的上拉/下拉表，对三进制函数进行最小化处理。

8.根据权利要求7所述的三进制乘法器设计和实现方法，其特征在于，使用Q-M算法将给定的最小项规范表达式合并到具有最佳晶体管数量的SOP表达式中，具体包括：

第一步：算法通过反复合并蕴涵项来找到所有的主蕴涵项；该算法从生成的上拉/下拉表中提取最小项；提取的最小项是上拉/下拉表中相应输出为ON的输入组合；生成蕴涵项时，根据三进制逻辑中“0”的数量和“+”的数量进行分组；在对所有蕴涵项进行分组后，该算法检查是否与相邻组中的其他蕴涵项合并；如果一个蕴涵项的组合为[x，y]，则[x±1，y]、[x，y±1]、[x-1，y+1]和[x+1，y-1]组合与它相邻；合并两个具有相邻组且仅相差一个三进制组的蕴涵项，并以此迭代合并，直到不能再与其他蕴涵项合并为止；

第二步：通过对适当的主要蕴涵项求和来获得SOP；使用从第一步获得的本质素蕴涵项，构造一个质蕴涵图；在算法获得所有基本素蕴涵项之后，搜索所有可能的非本质素蕴涵项组合，这些组合需要覆盖所有小项；最后，某些SOP则需通过将本质蕴涵项和所需的非本质蕴涵项相加产生。

9.根据权利要求8所述的三进制乘法器设计和实现方法，其特征在于，用Q-M算法产生多个SOP时，选择其中最佳的SOP；决定最佳SOP的两个因素为：网络的最小晶体管数量以及网络中的最小传播延迟；

如果晶体管数量相同，则选择其中含有阈值电压绝对值为碳纳米晶体管数量最少的SOP；SOP中的每个乘积项是通过串联晶体管来构造的；

最后，通过在SPICE模型中连接网络中的合适节点来合成逻辑门。

10.一种三进制乘法器设计和实现装置，其特征在于，包括：

乘法器结构构建单元，用于构建华莱士树乘法器结构；

组合电路生成单元，用于运用华莱士树乘法器结构并结合三进制逻辑综合法生成三进制乘法器的最简晶体管组合电路。