0
\$\begingroup\$

I'm trying to make a 7 to 3 priority encoder for a circuit diagram for a class. The problem is that we have to take in a 7 bit number and output a 3 bit answer representing the maximum number of consecutive ones in the input.

Example:

0011100 = 011 (3)
1111111 = 111 (7)
0000000 = 000 (0)

The issue at the moment is that regardless of the input, it is always outputting 111 (7).

I have circuits for handling every possible combination of consecutive ones in the input, and am then piping that into a 7 to 3 priority encoder, but for some reason the encoder is not working the way it should. What am I doing wrong? Or is there a better way that I should be doing this?

Original Circuit diagram:

circuit

Attempt 2:

another try

\$\endgroup\$
  • \$\begingroup\$ Please explain the logic behind the Priority Encoder, as it isn't clear if the logic is faulty or the implementation of it is. \$\endgroup\$ – Scott Hunter Oct 20 '12 at 17:49
  • \$\begingroup\$ I'm basing it on an example I found for an 8 to 3 priority encoder online: tams-www.informatik.uni-hamburg.de/applets/hades/webdemos/… \$\endgroup\$ – PseudoPsyche Oct 20 '12 at 18:06
  • 1
    \$\begingroup\$ I think this question should be re-named. I don't see how this is a "priority encoder". A priority encoder encodes lines resolving multiple triggered lines by giving them a strict order of priority. But this isn't the case here and actually misleads the solution. There is nothing "priority" about it. It is a "consecutive high-bit counter". \$\endgroup\$ – Gunther Schadow Nov 14 '19 at 22:23
2
\$\begingroup\$
  • on your diagram, did you confuse PE2 and PE3 outputs?
  • for 1111111, PE1..PE7 are all going to be 1, so the last diagram would be wrong.
  • NAND is a much easier function to play with for consecutive 1s.

here's how I would do it:

LEN1 = AND(OR(a,b,c,d,e,f,g),NOR(NAND(a,b),NAND(b,c),NAND(c,d),NAND(d,e),NAND(e,f),NAND(f,g)))
LEN2 = AND(OR(NAND(a,b),NAND(b,c),NAND(c,d),NAND(d,e),NAND(e,f),NAND(f,g)),
           NOR(NAND(a,b,c),NAND(b,c,d),NAND(c,d,e),NAND(d,e,f),NAND(e,f,g)))
LEN3 = AND(OR(NAND(a,b,c),NAND(b,c,d),NAND(c,d,e),NAND(d,e,f),NAND(e,f,g)),
           NOR(NAND(a,b,c,d),NAND(b,c,d,e),NAND(c,d,e,f),NAND(d,e,f,g)))
LEN4 = AND(OR(NAND(a,b,c,d),NAND(b,c,d,e),NAND(c,d,e,f),NAND(d,e,f,g)),
           NOR(NAND(a,b,c,d,e),NAND(b,c,d,e,f),NAND(c,d,e,f,g)))
LEN5 = AND(OR(NAND(a,b,c,d,e),NAND(b,c,d,e,f),NAND(c,d,e,f,g)),
           NOR(NAND(a,b,c,d,e,f),NAND(b,c,d,e,f,g))
LEN6 = AND(OR(NAND(a,b,c,d,e,f),NAND(b,c,d,e,f,g)),
           NOT(NAND(a,b,c,d,e,f,g)))
LEN7 = NOT(NAND(a,b,c,d,e,f,g))

ANS1 = OR(LEN1,LEN3,LEN5,LEN7)
ANS2 = OR(LEN2,LEN3,LEN6,LEN7)
ANS3 = OR(LEN4,LEN5,LEN6,LEN7)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ah yes, thank you. I switched those, but it did not have an effect on the output. \$\endgroup\$ – PseudoPsyche Oct 20 '12 at 18:05
  • \$\begingroup\$ I tried re-implementing it with your suggestions, but I still getting 0 and 7 regardless of input. I've added an image of the new diagram to the OP. \$\endgroup\$ – PseudoPsyche Oct 21 '12 at 0:45
1
\$\begingroup\$

Okay, so I finally got it working. I used my original circuits that determine the number of consecutive bits, but then used part of dnozay's solution to construct the final 3-bit answer.

hooray

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The priority encoder part of your circuit is still not quite right. For example, if both PE4 and PE2 are asserted, it will output "110" instead of "100". On the right-hand side of this diagram, you need to inibit each output if any of the inputs above it are asserted, not just the next one up. \$\endgroup\$ – Dave Tweed Oct 22 '12 at 15:59
  • \$\begingroup\$ BTW, what does the "0" in a box connected to a signal denote? \$\endgroup\$ – Dave Tweed Oct 22 '12 at 16:01
  • \$\begingroup\$ Actually, in the context of your string-length logic, my previous comment doesn't matter. If PE4 is asserted, then all of PE3 through PE1 are asserted, too, so your simplified inhibition logic will work. But it doesn't work as a general-purpose priority encoder. \$\endgroup\$ – Dave Tweed Oct 22 '12 at 20:19
1
\$\begingroup\$

All the answers so far bug me as so very heavy on gates and so very special to these exact 7 bits in the task. I wonder if I could reduce the number of gates? OK, your gates are all primitive, and so anything we might build with higher order components might end up having a higher transistor count, but definitely we should be able to do a lower chip count?

I follow two ideas:

  1. using a shift register and a finite state automaton
  2. using a type of neural network where each cell is aware of its neighbors

Shift Register and FSA

Using a shift register and a finite state automaton would be like coding software as it would run in cycles. We load the shift register with all 7 bits. And then we clock them out with 7 cycles. We could begin in state 0, now if a 1 comes out we go into state 1 and advance a counter. Every time we are in state 1 and a 1 comes out, we advance that counter. If we fall back to 0, we have to consider if the current number in the counter can still be outdone by the bits that are yet to follow. So, I have a second counter that gets every clock pulse and the current sequence-of-ones counter. If the sequence-of-ones-counter is greater than the number of bits yet to come, we have our result. If there are still more to come, we continue until the next 1 occurs. That is, at that point we can check (again or for the first time) whether there are still sufficient bits left to outdo the current sequence-of-ones-counter. If so, we now count this down as subsequent 1s are seen, while we count a third counter up. If the last bit was seen, we output the counter that is higher.

This is just the brainstorming blurb. Next comes the optimizing. Given the small number of only 7 bits, there are very few situations which we can enumerate, and then produce a complex cluster like the one in your own answer. The benefit of my approach, however, is that it easily scales for a much higher word size.

So, I can clearly save extra comparison steps, I can be nifty about the use of comparators, subtraction, with inverters, etc. But essentially we can code the solution. I started it and then threw it away because I don't have time to perfect it.

Network Of Neighbor-Aware Cells

In this approach I put all the seven lines of input with gates to compare with their neighboring lines. If the line is 1 and the neighboring line is 0 that line doesn't count for much. If the neighboring line is also 1, then we like to know what the next line after the neighboring line is. So each line can have a certain maximum number of bits to either side:

LINE LEFT RIGHT
---- ---- ----
  1    0    6
  2    1    5
  3    2    4
  4    3    3
  5    4    2
  6    5    1
  7    6    0
---- ---- ----

Let's build it up recursively.

  1. 1 line, is it's own output
  2. 2 lines: OR them together for 1, AND them together for 2
  3. 3 lines: OR them together for 1, AND each 2 neighboring lines, OR those outputs together for 2, then AND the 2 outputs of the previous ANDs for 3
  4. 4 lines: OR them together for 1, AND each 2 neighboring lines, OR those outputs together for 2, then AND each two of the neighboring outputs of the previous ANDs, OR them together for 3, then AND the 2 outputs of the previous ANDs together for 4.
  5. 5 lines: OR them together for 1, AND each 2 neighboring lines, OR those outputs together for 2, then AND each 2 neighboring outputs of the previous ANDs, OR them together for 3, then AND each 2 neighboring outputs of the previous ANDs, OR those outputs together for 4, then AND the outputs of the previous ANDs together for 5.
  6. ...

You see how this goes. You build a pyramid of 2-input AND gates each between the neighboring lines, no matter how many lines you will need n/2 * n AND gates, and n-1 OR gates.

pyramid of and gates

The output from these OR gates and the apex AND gate -- I call them E1, E2, ..., En, n lines, now still need to be encoded, but "priority encoding" isn't really necessary here.

We simply take E1, E3, E5, and E7 and OR them together to make the LSB of the output, A0. Then we take E2 and E6, (and also E3 and E7), and OR them together to make the middle bit, A1. Finally our E4 (and OR-ed together with E5, E6, and E7) is the MSB of the output, A2. If we had the more general case with n lines, this schema would easily be continued.

This is the most beautiful solution I can come up with.

(EDIT: I had some speculative naive implementation with transistors here, but that didn't work out and I deleted it because it was too half-baked and rather embarrassing.)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Once you accept a sequential rather than combinatorial solution, there's essentially no reason to build it from discrete parts rather than use an MCU or at least a CPLD. The CPLD could probably also implement a combinatorial solution should it need to be blindingly fast (which is typically the legitimate reason for ruling out a sequential one). In terms of the actual question on this page, keep it mind it was coursework imposing limitations on the nature of solution. \$\endgroup\$ – Chris Stratton Nov 14 '19 at 23:20
  • \$\begingroup\$ @ChrisStratton, are you referring to my first brain-storm option, with that shift register? Yeah, sure, this was really just part of brainstorming. I just didn't like all this combinatorics built so inelegantly from gates. My second approach, the network of neighbor-aware lines is what I really want and should be unbeatably blazingly fast as it requires the minimum number of P-N / N-P transitions. Just something is wrong with my transistor implementation sketch. Trying to figure that out just now. \$\endgroup\$ – Gunther Schadow Nov 14 '19 at 23:32
  • \$\begingroup\$ Another implementation would be to use a non-volatile memory (for example EPROM). It only needs to be 128x3 but these days it would not be possible to get one that small.Just program it with the patters. If speed is not an issue you can put it into a small microcontroller - one chip with at least 10 I/O, $1 or less. \$\endgroup\$ – Kevin White Nov 15 '19 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.