Build a full adder using 2 4:2:1 MUXes and the constants 0 and 1

A question in computer structures,

Bu开发者_如何学JAVAild a full adder using 2 4:2:1 MUXes and the constants 0 and 1. Use minimum amount of constants.

Obviously this question is solvable using not gates too, but I am interested in the question without them.

If you mean a four-input mux, you can do (to add a, b, and c):

carry = mux(/* controls */ a, b, /* inputs */ 0, c, c, 1);

I'm not sure how to get sum without some other gate. One option is (with AND and OR):

sum = mux(/* controls */ carry, a, /* inputs */ b|c, 0, 1, b&c);

With XOR (probably obvious):

sum = mux(/* controls */ a, b^c, /* inputs */ 0, 1, 1, 0);

Here's a sketch of why you can't do it with two muxes:

Since you have two muxes and two outputs, each mux must produce one output; thus, you need to compute sum from carry or compute carry from sum. You can't compute sum with just the three inputs without a NOT gate, and so you need to compute carry first. You can do that; then you need to get sum from the inputs and carry. Since the inputs are symmetric, the mux for sum can have its controls be either two inputs or one input and carry. The first case fails for the same reason that you can't compute sum first. Looking at the truth table and all possible combinations of carry and one input (call it a), there is no way to compute sum uniquely for the case where carry and a are the same using only one variable or constant as the input to each data input of the sum mux.

I just wrote a simple little C# program to check every possible input combination, and it fails to find a solution. So, unless I made some kind of program error, there is no solution to this problem.

using System;

class Program
{
    static void Main(string[] args)
    {
        bool[] aValues = new bool[] { false, false, false, false, true, true, true, true };
        bool[] bValues = new bool[] { false, false, true, true, false, false, true, true };
        bool[] cValues = new bool[] { false, true, false, true, false, true, false, true };
        bool[] carryValues = new bool[] { false, false, false, true, false, true, true, true };
        bool[] constantFalse = new bool[] { false, false, false, false, false, false, false, false };
        bool[] constantTrue = new bool[] { true, true, true, true, true, true, true, true };

        bool[] sumValues = new bool[] { false, true, true, false, true, false, false, true };

        bool[][] allInputs = new bool[][] { aValues, bValues, cValues, carryValues, constantFalse, constantTrue };

        for (int controlOneIndex = 0; controlOneIndex < allInputs.Length; controlOneIndex++)
            for (int controlTwoIndex = 0; controlTwoIndex < allInputs.Length; controlTwoIndex++)
                for (int inputOneIndex = 0; inputOneIndex < allInputs.Length; inputOneIndex++)
                    for (int inputTwoIndex = 0; inputTwoIndex < allInputs.Length; inputTwoIndex++)
                        for (int inputThreeIndex = 0; inputThreeIndex < allInputs.Length; inputThreeIndex++)
                            for (int inputFourIndex = 0; inputFourIndex < allInputs.Length; inputFourIndex++)
                            {
                                for (int calculationIndex = 0; calculationIndex < sumValues.Length; calculationIndex++)
                                {
                                    if (MuxResult(allInputs[controlOneIndex][calculationIndex],
                                                allInputs[controlTwoIndex][calculationIndex],
                                                allInputs[inputOneIndex][calculationIndex],
                                                allInputs[inputTwoIndex][calculationIndex],
                                                allInputs[inputThreeIndex][calculationIndex],
                                                allInputs[inputFourIndex][calculationIndex]) != sumValues[calculationIndex])
                                    {
                                        goto tryNextValue;
                                    }
                                }
                                Console.WriteLine("Success: controls: {0} {1}   inputs: {2} {3} {4} {5}",
                                    controlOneIndex, controlTwoIndex, inputOneIndex, inputTwoIndex, inputThreeIndex, inputFourIndex);
                            tryNextValue: ;
                            }
        Console.WriteLine("done");
        Console.ReadLine();
    }

    private static bool MuxResult(bool controlOne, bool controlTwo, bool inputOne, bool inputTwo, bool inputThree, bool inputFour)
    {
        if (controlOne)
        {
            if (controlTwo)
                return inputFour;
            else
                return inputTwo;
        }
        else
        {
            if (controlTwo)
                return inputThree;
            else
                return inputOne;
        }
    }
}

A B Cin S cout
0 0 0   0 0
0 0 1   1 0
0 1 0   1 0
0 1 1   0 1
1 0 0   1 0
1 0 1   0 1
1 1 0   0 1
1 1 1   1 1

By taking A, as the selection line to two 2*1 muxs we have in the first mux in input number 0 B XOR Cin in input number 1 B XNOR Cin -> this mux for S in the second mux in input number 0 we have B AND Cin in input number 1 we have B OR Cin -> this for Cout .

A Full adder in VB

Class fullAdder

    Private _A As Boolean
    Private _B As Boolean
    Private _Cin As Boolean
    Private _Sum As Boolean
    Private _Cout As Boolean

    Public Sub New()
        Me.A = False
        Me.B = False
        Me.Cin = False
    End Sub

    Public Sub SetInputs(a As Boolean, b As Boolean, cIn As Boolean)
        Me.A = a
        Me.B = b
        Me.Cin = cIn
    End Sub

    'Inputs           Outputs
    'A  B  Cin        Cout  S
    '0  0   0         0     0
    '1  0   0         0     1
    '0  1   0         0     1
    '1  1   0         1     0
    '0  0   1         0     1
    '1  0   1         1     0
    '0  1   1         1     0
    '1  1   1         1     1 

    Public Sub DoAdd()
        'debugIn()
        Dim ABxor As Boolean = Me.A Xor Me.B
        Me.Sum = ABxor Xor Me.Cin
        Dim ABxorAndCin As Boolean = ABxor And Me.Cin
        Dim ABand As Boolean = Me.A And Me.B
        Me.Cout = ABxorAndCin Or ABand
        'debugOut()
    End Sub

    Private Sub debugIn()
        Debug.WriteLine("'I {0} {1} {2}", Me.A, Me.B, Me.Cin)
    End Sub

    Private Sub debugOut()
        Debug.WriteLine("'O {0} {1}", Me.Cout, Me.Sum)
        Debug.WriteLine("")
    End Sub

    Public Property Sum() As Boolean
        Get
            Return Me._Sum
        End Get
        Set(ByVal value As Boolean)
            Me._Sum = value
        End Set
    End Property

    Public Property Cout() As Boolean
        Get
            Return Me._Cout
        End Get
        Set(ByVal value As Boolean)
            Me._Cout = value
        End Set
    End Property

    Public Property A() As Boolean
        Get
            Return Me._A
        End Get
        Set(ByVal value As Boolean)
            Me._A = value
        End Set
    End Property

    Public Property B() As Boolean
        Get
            Return Me._B
        End Get
        Set(ByVal value As Boolean)
            Me._B = value
        End Set
    End Property

    Public Property Cin() As Boolean
        Get
            Return Me._Cin
        End Get
        Set(ByVal value As Boolean)
            Me._Cin = value
        End Set
    End Property

End Class