Electronic – 3-to-2 line encoder (or generally 2^(n-1)-to-n) — not priority, but telling how many inputs are on

adderdigital-comparatorencodersumming

This is not homework (not taking any classes) although it could be homework. I am wondering what is the easiest implementation using a single TTL chip or gates (fewest chip count) to encode the number of input lines that are high. So, not a priority encoder that says which line is on, but how many of them. Truth table:

+-----++---+
|INPUT||OUT|
|3|2|0||1|0|
+-+-+-++-+-+
|L|L|L||L|L|
+-+-+-++-+-+
|L|L|H||L|H|
|L|H|L||L|H|
|H|L|L||L|H|
+-+-+-++-+-+
|L|H|H||H|L|
|H|H|L||H|L|
|H|L|H||H|L|
+-+-+-++-+-+
|H|H|H||H|H|
+-+-+-++-+-+

Sometimes I feel like really solving this myself, as I did in the most intelligent design of an encoder that determines the maximum number of consecutive lines but sometimes I have higher goals and don't want to waste the time. Especially nice if there was one single chip that can do that.

The final purpose is to add this number of the 3 inputs on or off to an existing 3-bit number without overflow, but rather a bounded sum, i.e., …, 3+3=6, 4+3=7, 5+3=7, 6+3=7, 7+3=7. So, if there was one or two chips that can do that that would be cool. I'm designing Conway's Game of Life in hardware that can produce a new field in a single iteration at the speed of the display frame-rate, computed at the same time that the display scans the memory, and this particular bounded sum of up to 3 lines with an existing 3-bit value, is what my neighbor-count algorithm needs.

UPDATE: actually, this "bounded sum" adder is even more restricted, it is bounded at 4, i.e., no addition needs to produce a value higher than 4. Only 0, 1, 2, 3, and 4 are needed. Anything greater than 4 just yields 4. This definitely will make a difference in how many gates are needed. I feel it.

Best Answer

The is a fairly standard building block when implementing a multiplier matrix (you are effectively "counting" the number of ones in a column). It's generally referred to as a "compressor" and there are various forms 3:2, 4:2, 7:3, etc. that wind up giving you what is called "carry-save form", ie. 2 numbers which must be added together.

Most compressors can be built out of cascaded full-adder blocks. The 74LS183 is a dual full-adder chip.

This definitely will make a difference in how many gates are needed. I feel it.

Unfortunately, your "feel" is not correct for the compressor. The problem is that a "1" can come from anywhere in the full number of bits. So, at some point, you may have to add bit 2^(n-1) to Bit 0 to get the count. That means that somehow you have to cascade all bits together so the number of gates is fixed.

Once you have the carry-save format, you have to add the two pieces together. Your "bounded sum" is called a "saturating add". Yes, you can probably save some gates at this step as you don't automatically have to add all the positions (if there is a 1 in any position above the saturation point you can just return MAX). However, that doesn't save you as many gates as you think (you still have to OR all those bits together).

However, if you are implementing in TTL you'll be better off using something like a 74LS382 (or 74LS381) and just add things up to minimize the number of chips. And possibly a 74LS85 binary magnitude comparator to get the saturate.

Good luck.

Related Topic