python 数据结构与算法分析 逻辑门半加器与全加器实现

这本书是北京大学的数据结构和算法python课程教材版本，视频哔哩哔哩第一章课后练习有逻辑门电路实现。

在数字电路中，所谓的门是一种只能实现基本逻辑关系的电路。最基本的逻辑关系是与、或、非，最基本的逻辑门是与门、或门和非门。逻辑门可由电阻、电容、二极管、三极管等分离原件组成分立元件门。门电路的所有设备和连接线也可以制成在同一个半导体基板上集成逻辑门电路。

半加器(半加只求本位和，暂时不管低位送来的进位数)

逻辑状态表

A	B	C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

其中，A与B相加的两个数，S是半加和数，C是进位数。

逻辑类型可以通过逻辑状态表写出:

半加器逻辑电路图

实现代码如下：

# 电路正向计算&半加器 # 超类LogicGate class LogicGate:      def __init__(self, n):         self.label = n         self.output = None      def getLabel(self):         return self.label      def getOutput(self):         self.output = self.performGateLogic()         return self.output   # 二引脚逻辑门 class BinaryGate(LogicGate):      def __init__(self, n, pinA=None, pinB=None):         super().__init__(n)          self.pinA = pinA         self.pinB = pinB         self.output = self.getOutput()      # def getPinA(self):     # if self.pinA == None:     # return int(input("Enter Pin A for gate"   self.getLabel()   "-->"))     # else:     # return self.pinA.getFrom().getOutput()      # def getPinB(self):     # if self.pinB == None:     # return int(input("Enter Pin B for gate"   self.getLabel()   "-->"))     # else:     # return self.pinB.getFrom().getOutput()      def __str__(self):         return "{} - pinA: {}; pinA: {}; output: {}".format(self.label, self.pinA, self.pinB, self.output)      def setNextPin(self, source):         if self.pinA == None:             self.pinA = source.output         else:             if self.pinB == None:                 self.pinB = source.output             else:                 raise RuntimeError("Error: NO EMPTY PINS")   # 单引脚逻辑门 class UnaryGate(LogicGate):      def __init__(self, n, pin=None):         super().__init__(n)          self.pin = None         self.output = self.getOutput()      # def getPin(self):     # if self.pin == None:     # return int(input("Enter Pin for gate"   self.getLabel()   "-->"))     # else:     # return self.pin.getFrom().getOutput()      def __str__(self):         return "{} - pin: {}; output: {}".format(self.label, self.pin, self.output)      def setNextPin(self, source):         if self.pin == None:             self.pin = source.output         else:             print("Cannot Connect: NO EMPTY PINS on this gate")   # 与门 class AndGate(BinaryGate):      def __init__(self, n, pinA=None, pinB=None):         super().__init__(n, pinA, pinB)      def performGateLogic(self):         # self.pinA = self.getPinA()         # self.pinB = self.getPinB()         if self.pinA == 1 and self.pinB == 1:             return 1         else:             return 0# 与非门 class NandGate(BinaryGate):      def __init__(self, n, pinA=None, pinB=None):         super().__init__(n, pinA, pinB)      def performGateLogic(self):         # self.pinA = self.getPinA()         # self.pinB = self.getPinB()         if self.pinA == 1 and self.pinB == 1:             return 0        else:
            return 1


# 或门
class OrGate(BinaryGate):

    def __init__(self, n, pinA=None, pinB=None):
        super().__init__(n, pinA, pinB)

    def performGateLogic(self):
        # self.pinA = self.getPinA()
        # self.pinB = self.getPinB()
        if self.pinA == 1 or self.pinB == 1:
            # pinA = self.getPinA()
            # pinB = self.getPinB()
            # if pinA == 1 or pinB == 1:
            return 1
        else:
            return 0


# 或非门
class NorGate(BinaryGate):

    def __init__(self, n, pinA=None, pinB=None):
        super().__init__(n, pinA, pinB)

    def performGateLogic(self):
        # self.pinA = self.getPinA()
        # self.pinB = self.getPinB()
        if self.pinA == 0 and self.pinB == 0:
            return 1
        else:
            return 0


# 异或门
class XorGate(BinaryGate):

    def __init__(self, n, pinA=None, pinB=None):
        super().__init__(n, pinA, pinB)

    def performGateLogic(self):
        # self.pinA = self.getPinA()
        # self.pinB = self.getPinB()
        if self.pinA == self.pinB:
            return 0
        else:
            return 1


# 非门
class NotGate(UnaryGate):
    def __init__(self, n, pin=None):
        super().__init__(n, pin)

    def performGateLogic(self):
        # self.pin = self.getPin()
        if self.pin == 1:
            return 0
        else:
            return 1


class Connector():
    def __init__(self, fgate, tgate):
        self.fromgate = fgate
        self.togate = tgate

        tgate.setNextPin(fgate)

    def getFrom(self):
        return self.fromgate

    def getTo(self):
        return self.togate
#半加器
class HalfAdder():

    def __init__(self, n, A, B):
        self.label = n
        self.A = A
        self.B = B
        self.S = XorGate("n1", A, B).output
        self.C = AndGate("n2", A, B).output

    def __str__(self):
        return "{} - A: {}; B: {}; S: {}; C: {}".format(self.label, self.A, self.B, self.S, self.C)

 运行测试

if __name__ == "__main__":
    g1 = AndGate("G1",0,1)
    g2 = AndGate("G2",1,1)
    g3 = OrGate("G3")
    g4 = NotGate("G4")

    c1 = Connector(g1,g3)
    c2 = Connector(g2,g3)
    c3 = Connector(g3,g4)
    print(g1)
    print(g2)
    print(g3)
    print(g4)
    print(g4.output)
    h1 = HalfAdder("h1", 0, 0)
    h2 = HalfAdder("h2", 0, 1)
    h3 = HalfAdder("h3", 1, 0)
    h4 = HalfAdder("h4", 1, 1)
    print(h1)
    print(h2)
    print(h3)
    print(h4)

与逻辑状态表对比，核验逻辑是否正确。

全加器

当多位数相加时，半加器可用于最低位求和，并给出进位数。第二位的相加有两个待加数Ai

和Bi，还有一个来自前面低位送来的进位数Ci-1.这三个数相加，得出本位和数（全加和数）Si和进位数Ci.这种就是“全加“，下表为全加器的逻辑状态表。

Ai	Bi	Ci-1	Ci	Si
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

全加器可用两个半加器和一个“或“门组成。

 全加器一位逻辑电路图

 四位全加器行波进位法逻辑电路图

 实现代码如下：

#全加器
class Adder():

    def __init__(self,n,A,B,cin=0):
        self.label=n
        self.A=A
        self.B=B
        self.cin=cin
        self.rs=None
        self.cun=None

    def performLogic(self):
        ha1=HalfAdder('h1',self.A,self.B)
        ha2=HalfAdder('h2',ha1.S,self.cin)
        self.rs=ha2.S
        self.cun=OrGate('n1',ha1.C,ha2.C).output
        return self.rs,self.cun

    def __str__(self):
        self.performLogic()
        return "{} - A: {}; B: {};cin: {}; S: {}; C: {}".format(self.label, self.A, self.B, self.cin,self.rs, self.cun)

#行波进位加法器（四位）
class FourAdder():
    def __init__(self,n,A1,A2,A3,A4,B1,B2,B3,B4):
        self.label=n
        self.A1=A1
        self.A2=A2
        self.A3=A3
        self.A4=A4
        self.B1=B1
        self.B2=B2
        self.B3=B3
        self.B4=B4
        self.a=None
        self.b=None
        self.c=None
        self.d=None
        self.c1=None
        self.c2=None
        self.c3=None
        self.c4=None

    def performLogic(self):
        a1=Adder('a1',self.A1,self.B1)
        a1.performLogic()
        a2=Adder('a2',self.A2,self.B2,a1.cun)
        a2.performLogic()
        a3=Adder('a3',self.A3,self.B3,a2.cun)
        a3.performLogic()
        a4=Adder('a4',self.A4,self.B4,a3.cun)
        a4.performLogic()
        self.a=a1.rs
        self.b=a2.rs
        self.c=a3.rs
        self.d=a4.rs

    def __str__(self):
        self.performLogic()
        return "{} - A1: {};A2: {};A3: {};A4: {}; B1: {};B2: {};B3: {};B4: {}; a: {};b: {}; c: {};d: {}"\
            .format(self.label, self.A1, self.A2,self.A3,self.A4,self.B1,self.B2,self.B3,self.B4, self.a,self.b, self.c,self.d)

运用了类的继承机制，由基本的与门、或门、与或门组成半加器，全加器可以看成是两个半加器组合运算，继承实现十分方便，同理，四位全加器是由四个全加器串联起来组成，测试如下：

if __name__ == "__main__":
    a1=Adder('a1',0,1,0)
    a2=Adder('a2',0,1,1)
    a3=Adder('a3',1,1,0)
    a4=Adder('a4',1,0,1)
    a5=Adder('a5',1,1,1)
    print(a1)
    print(a2)
    print(a3)
    print(a4)
    print(a5)

    f1=FourAdder('f1',0,1,1,0,1,1,0,0)
    print(f1)