Build a bit-counting comparator using NAND logic gates

11

A bit-counting comparator (BCC) is a logic circuit that takes some number of counting inputs A1, A2, A3, ..., An as well as inputs B1, B2, B4, B8, ... representing a number. It then returns 1 if the total number of A inputs that are on is greater than the number represented in binary by the B inputs (e.g. B1, B2, and B8 would make the number 11), and 0 otherwise.

For example, for a bit-counting comparator that takes 5 inputs, of which A2, A4, A5, and B2 are set to 1, will return 1 because there are 3 A inputs that are on, which is greater than 2 (the number represented by only B2 being on).

Your task is to create a bit-counting comparator that takes a total of 16 A inputs and 4 B inputs (representing bits from 1 to 8), using only two-input NAND gates, and using as few NAND gates as possible. To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

  • NOT: 1
  • AND: 2
  • OR: 3
  • XOR: 4

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

The logic circuit that uses the fewest NAND gates to produce a correct construction wins.

Joe Z.

Posted 2014-04-08T14:56:04.590

Reputation: 30 589

So any answer that uses no NAND gates at all will win? That should be easy. Am I allowed to use AND gates with 16 inputs? – r3mainer – 2014-04-08T15:08:38.657

@squeamishossifrage Did you read the question? AND gates add 2 to your score. – Rainbolt – 2014-04-08T15:11:34.777

@squeamishossifrage One AND == two NAND – Timtech – 2014-04-08T15:38:19.093

@Timtech Then why the requirement to use "as few NAND gates as possible"? – r3mainer – 2014-04-08T15:45:23.943

1@squeamishossifrage, "using only NAND gates". The scores for other gates are the minimum number of NAND gates required to build them; essentially it's defining some convenience macros. – Peter Taylor – 2014-04-08T15:49:11.497

@PeterTaylor Aaaah, I see. So gates with 16 inputs are fine, then? – r3mainer – 2014-04-08T15:51:35.300

@squeamishossifrage None of the gates listed take 16 inputs. – Rainbolt – 2014-04-08T15:57:44.723

@Rusher Here's a 13-Input NAND gate: http://www.classiccmp.org/rtellason/chipdata/dm74als133.pdf

– r3mainer – 2014-04-08T16:03:42.833

"...16 A inputs and 4 B inputs (representing bits from 1 to 8)..." How come there are 8 bits from only 4 B inputs? – user80551 – 2014-04-08T16:16:56.720

@user80551 How many base ten digits do you need to represent the numbers zero through nine? Only one I hope. – Rainbolt – 2014-04-08T16:18:45.513

"because there are 3 lights on" -- where do lights come into the problem ? – Paul R – 2014-04-08T16:28:05.317

@Rusher I'm assuming each input is one bit. Oh wait, is it sum(total number of A-bits on)>int_representation(B) ? Then the question is a bit unclear – user80551 – 2014-04-08T16:54:22.677

@PaulR Lights are commonly used analogies for things that can be OFF or ON. – Rainbolt – 2014-04-08T16:59:05.597

1@user80551 You need 16 bits to tell if 16 bits are ON or OFF. You need 4 bits to represent a 4 bit number. The number of ON bits must be greater than the 4 bit number. I don't really understand why that is so difficult. See the part of the question that says "total number of A inputs that are on is greater than the number represented by the B inputs."? – Rainbolt – 2014-04-08T17:01:33.977

@user80551 It is indeed. – Joe Z. – 2014-04-08T17:52:12.640

@PaulR I tend to think of light switches when designing these logic gate problems. Sorry if I made a mental typo that made it incomprehensible. – Joe Z. – 2014-04-08T17:54:16.820

Answers

7

169 nands

Adds up the A's to get A{1,2,4,8,16}. Then does a binary comparison with the Bs.

I use a few more building blocks:

  • FA = full adder, 9 nands (from here)
  • HA = half adder, 7 nands (same ref)
  • EQ = equality, 5 gates (a.k.a. xnor)

The half and full adders have 2 outputs - they are distinguished with an r for result and c for carry.

The A{1,2,4,8,16} are the outputs from the half adders.

enter image description here

Keith Randall

Posted 2014-04-08T14:56:04.590

Reputation: 19 865

1

Wow. Just wow. Note that a half adder can be made in just 5 gates:http://codegolf.stackexchange.com/a/10848/9498 , 4 for xor, and 1 to invert the first nand in the xor. So we get an xor and an and. Picture: http://i.stack.imgur.com/qCFxa.png

– Justin – 2014-04-09T05:29:58.630

@Quincunx: thanks, the better half adder lowers the count to 161. I don't think we need a quartus diagram, but if you'd like to I can update the answer with it. – Keith Randall – 2014-04-09T23:17:31.007

5

751 nand gates

module BitCountingComparator(A, B, O);
    input [15:0] A;
    input [3:0] B;
    output O;

    wire [15:1] is;
    assign is[1] = A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] | A[8] | A[9] | A[10] | A[11] | A[12] | A[13] | A[14] | A[15];

    wire [14:0] and2;
    assign and2[0] = A[0] & A[1];
    assign and2[1] = A[1] & A[2];
    assign and2[2] = A[2] & A[3];
    assign and2[3] = A[3] & A[4];
    assign and2[4] = A[4] & A[5];
    assign and2[5] = A[5] & A[6];
    assign and2[6] = A[6] & A[7];
    assign and2[7] = A[7] & A[8];
    assign and2[8] = A[8] & A[9];
    assign and2[9] = A[9] & A[10];
    assign and2[10] = A[10] & A[11];
    assign and2[11] = A[11] & A[12];
    assign and2[12] = A[12] & A[13];
    assign and2[13] = A[13] & A[14];
    assign and2[14] = A[14] & A[15];

    wire [13:0] and3;
    assign and3[0] = and2[0] & A[2];
    assign and3[1] = and2[1] & A[3];
    assign and3[2] = and2[2] & A[4];
    assign and3[3] = and2[3] & A[5];
    assign and3[4] = and2[4] & A[6];
    assign and3[5] = and2[5] & A[7];
    assign and3[6] = and2[6] & A[8];
    assign and3[7] = and2[7] & A[9];
    assign and3[8] = and2[8] & A[10];
    assign and3[9] = and2[9] & A[11];
    assign and3[10] = and2[10] & A[12];
    assign and3[11] = and2[11] & A[13];
    assign and3[12] = and2[12] & A[14];
    assign and3[13] = and2[13] & A[15];

    wire [12:0] and4;
    assign and4[0] = and3[0] & A[3];
    assign and4[1] = and3[1] & A[4];
    assign and4[2] = and3[2] & A[5];
    assign and4[3] = and3[3] & A[6];
    assign and4[4] = and3[4] & A[7];
    assign and4[5] = and3[5] & A[8];
    assign and4[6] = and3[6] & A[9];
    assign and4[7] = and3[7] & A[10];
    assign and4[8] = and3[8] & A[11];
    assign and4[9] = and3[9] & A[12];
    assign and4[10] = and3[10] & A[13];
    assign and4[11] = and3[11] & A[14];
    assign and4[12] = and3[12] & A[15];

    wire [11:0] and5;
    assign and5[0] = and4[0] & A[4];
    assign and5[1] = and4[1] & A[5];
    assign and5[2] = and4[2] & A[6];
    assign and5[3] = and4[3] & A[7];
    assign and5[4] = and4[4] & A[8];
    assign and5[5] = and4[5] & A[9];
    assign and5[6] = and4[6] & A[10];
    assign and5[7] = and4[7] & A[11];
    assign and5[8] = and4[8] & A[12];
    assign and5[9] = and4[9] & A[13];
    assign and5[10] = and4[10] & A[14];
    assign and5[11] = and4[11] & A[15];

    wire [10:0] and6;
    assign and6[0] = and5[0] & A[5];
    assign and6[1] = and5[1] & A[6];
    assign and6[2] = and5[2] & A[7];
    assign and6[3] = and5[3] & A[8];
    assign and6[4] = and5[4] & A[9];
    assign and6[5] = and5[5] & A[10];
    assign and6[6] = and5[6] & A[11];
    assign and6[7] = and5[7] & A[12];
    assign and6[8] = and5[8] & A[13];
    assign and6[9] = and5[9] & A[14];
    assign and6[10] = and5[10] & A[15];

    wire [9:0] and7;
    assign and7[0] = and6[0] & A[6];
    assign and7[1] = and6[1] & A[7];
    assign and7[2] = and6[2] & A[8];
    assign and7[3] = and6[3] & A[9];
    assign and7[4] = and6[4] & A[10];
    assign and7[5] = and6[5] & A[11];
    assign and7[6] = and6[6] & A[12];
    assign and7[7] = and6[7] & A[13];
    assign and7[8] = and6[8] & A[14];
    assign and7[9] = and6[9] & A[15];

    wire [8:0] and8;
    assign and8[0] = and7[0] & A[7];
    assign and8[1] = and7[1] & A[8];
    assign and8[2] = and7[2] & A[9];
    assign and8[3] = and7[3] & A[10];
    assign and8[4] = and7[4] & A[11];
    assign and8[5] = and7[5] & A[12];
    assign and8[6] = and7[6] & A[13];
    assign and8[7] = and7[7] & A[14];
    assign and8[8] = and7[8] & A[15];

    wire [7:0] and9;
    assign and9[0] = and8[0] & A[8];
    assign and9[1] = and8[1] & A[9];
    assign and9[2] = and8[2] & A[10];
    assign and9[3] = and8[3] & A[11];
    assign and9[4] = and8[4] & A[12];
    assign and9[5] = and8[5] & A[13];
    assign and9[6] = and8[6] & A[14];
    assign and9[7] = and8[7] & A[15];

    wire [6:0] and10;
    assign and10[0] = and9[0] & A[9];
    assign and10[1] = and9[1] & A[10];
    assign and10[2] = and9[2] & A[11];
    assign and10[3] = and9[3] & A[12];
    assign and10[4] = and9[4] & A[13];
    assign and10[5] = and9[5] & A[14];
    assign and10[6] = and9[6] & A[15];

    wire [5:0] and11;
    assign and11[0] = and10[0] & A[10];
    assign and11[1] = and10[1] & A[11];
    assign and11[2] = and10[2] & A[12];
    assign and11[3] = and10[3] & A[13];
    assign and11[4] = and10[4] & A[14];
    assign and11[5] = and10[5] & A[15];

    wire [4:0] and12;
    assign and12[0] = and11[0] & A[11];
    assign and12[1] = and11[1] & A[12];
    assign and12[2] = and11[2] & A[13];
    assign and12[3] = and11[3] & A[14];
    assign and12[4] = and11[4] & A[15];

    wire [3:0] and13;
    assign and13[0] = and12[0] & A[12];
    assign and13[1] = and12[1] & A[13];
    assign and13[2] = and12[2] & A[14];
    assign and13[3] = and12[3] & A[15];

    wire [2:0] and14;
    assign and14[0] = and13[0] & A[13];
    assign and14[1] = and13[1] & A[14];
    assign and14[2] = and13[2] & A[15];

    wire [1:0] and15;
    assign and15[0] = and14[0] & A[14];
    assign and15[1] = and14[1] & A[15];

    wire and16;
    assign and16 = and15[0] & A[15];

    assign is[2] = and2[0] | and2[1] | and2[2] | and2[3] | and2[4] | and2[5] | and2[6] | and2[7] | and2[8] | and2[9] | and2[10] | and2[11] | and2[12] | and2[13] | and2[15];

    assign is[3] = and3[0] | and3[1] | and3[2] | and3[3] | and3[4] | and3[5] | and3[6] | and3[7] | and3[8] | and3[9] | and3[10] | and3[11] | and3[12] | and3[14];

    assign is[4] = and4[0] | and4[1] | and4[2] | and4[3] | and4[4] | and4[5] | and4[6] | and4[7] | and4[8] | and4[9] | and4[10] | and4[11] | and4[13];

    assign is[5] = and5[0] | and5[1] | and5[2] | and5[3] | and5[4] | and5[5] | and5[6] | and5[7] | and5[8] | and5[9] | and5[10] | and5[12];

    assign is[6] = and6[0] | and6[1] | and6[2] | and6[3] | and6[4] | and6[5] | and6[6] | and6[7] | and6[8] | and6[9] | and6[11];

    assign is[7] = and7[0] | and7[1] | and7[2] | and7[3] | and7[4] | and7[5] | and7[6] | and7[7] | and7[8] | and7[10];

    assign is[8] = and8[0] | and8[1] | and8[2] | and8[3] | and8[4] | and8[5] | and8[6] | and8[7] | and8[9];

    assign is[9] = and9[0] | and9[1] | and9[2] | and9[3] | and9[4] | and9[5] | and9[6] | and9[8];

    assign is[10] = and10[0] | and10[1] | and10[2] | and10[3] | and10[4] | and10[5] | and10[7];

    assign is[11] = and11[0] | and11[1] | and11[2] | and11[3] | and11[4] | and11[6];

    assign is[12] = and12[0] | and12[1] | and12[2] | and12[3] | and12[5];

    assign is[13] = and13[0] | and13[1] | and13[2] | and13[4];

    assign is[14] = and14[0] | and14[1] | and14[3];

    assign is[15] = and15[0] | and15[2];

    assign is[16] = and16;


    wire [15:1] eB;
    eB[1] = B[0];
    eB[2] = B[1];
    eB[3] = B[1] & B[0];
    eB[4] = B[2];
    eB[5] = B[2] & B[0];
    eB[6] = B[2] & B[1];
    eB[7] = eB[6] & B[0];
    eB[8] = B[3];
    eB[9] = B[3] & B[0];
    eB[10] = B[3] & B[1];
    eB[11] = eB[10] & B[0];
    eB[12] = B[3] & B[2];
    eB[13] = eB[12] & B[0];
    eB[14] = eB[12] & B[1];
    eB[15] = eB[14] & B[0];

    assign O = is[1] & ~is[2] & ~eB[1] |
        is[2] & ~is[3] & ~eB[2] |
        is[3] & ~is[4] & ~eB[3] |
        is[4] & ~is[5] & ~eB[4] |
        is[5] & ~is[6] & ~eB[5] |
        is[6] & ~is[7] & ~eB[6] |
        is[7] & ~is[8] & ~eB[7] |
        is[8] & ~is[9] & ~eB[8] |
        is[9] & ~is[10] & ~eB[9] |
        is[10] & ~is[11] & ~eB[10] |
        is[11] & ~is[12] & ~eB[11] |
        is[12] & ~is[13] & ~eB[12] |
        is[13] & ~is[14] & ~eB[13] |
        is[14] & ~is[15] & ~eB[14] |
        is[15] & ~eB[15];
endmodule

This is not fully golfed yet. I gave the answer in Verilog because this way, I was able to write a program to output each section. If it is mandatory to answer with a diagram, please let me know. They are equivalent. & is and, ~ is not, and | is or.

My strategy:

  • take A and put move all the 1s to the low numbers, store in is. (this is the majority of the program)
  • take B and unpack it into 16 bits (I called it eB for expanded B)
  • do a simple check.

Justin

Posted 2014-04-08T14:56:04.590

Reputation: 19 757