0
\$\begingroup\$

Let's say I have a 25bit priority encoder. So each input pin from \$i_{24}\$ to \$i_0\$ has its distinct priority in our encoder. That means that if more than one inputs are active, the encoder will act as if only the input with the highest priority is active, and return a 5-bit vector, \$out_{4..0}\$ (according of course to ceil(log2(25))=5)

Ok, I guess that intro was not needed, everyone knows how a priority encoder works. My question is:----> If we want to change the priority of the inputs, and code a completely arbitrary priority for each input, how many bits is needed to contain the entire coding information?

So my line of thought was this: First input has 25 possible priorities, so we need 5 bits for it's value. Up until we have 16 inputs left, we need 5 bits for each input, so that's 9 inputs coded with 5 bits. Then we need 4 bits for next 8 inputs, 3 bits for next 4 inputs, 2 bits for next 2 inputs, 1bit for next 1 input, and zero bits for the last remaining input. That totals: \$9\cdot 5 + 8\cdot 4 + 4\cdot 3 + 2\cdot 2 + 1\cdot 1 + 1\cdot 0 = 94\$ bits. Is this correct? Do we need 94 bits to completely code priorities for a 25-input priory encoder?

\$\endgroup\$
2
  • 3
    \$\begingroup\$ There are 25! permutations of 25 items, or 1.55*10^25. This number could be represented with 84 bits, but the decoding could be somewhat cumbersome. 94 is probably a good compromise, but the decoding would be very straightforward if you simply used 25*5 = 125 bits. Those bits would be decoded to drive a 25x25 crossbar switch that maps the 25 inputs to the (fixed) priority encoder in an arbitrary order. \$\endgroup\$
    – Dave Tweed
    Apr 13, 2014 at 15:42
  • \$\begingroup\$ Dave, that is a answer, not a comment! \$\endgroup\$ Apr 13, 2014 at 16:11

2 Answers 2

1
\$\begingroup\$

One approach would be for each of the 25 inputs to either show 0 if deselected, or it's own 5-bit priority value P(i) if selected. Throw all the intermediate values into a sorting network that returns the maximum priority shown in a particular cycle. If you then have a comparator for each input to see if it's show priority equals the maximum as a single bit per input, then use a classic priority encoder technique (e.g. bitscan) on those bits.

Total storage for all priority bits is 25*5 as @Dave_Tweed mentions.

\$\endgroup\$
1
\$\begingroup\$

As other posters have indicated, storing 25x5 bits is probably the most practical way to represent the priority sequence. Rather than using a sorting network to identify the maximum priority and then using comparators to identify the node with that priority, I would suggest instead having a box which takes two pairs of five-bit inputs (each pair containing "value" and "index") and uses a 2x10 mux to output the pair with the highest value. Every node should have a 5-bit latch with an "output-enable" so it either outputs zero or the selected priority. The latch value of each node should be fed, along with the node number, into a tree whose nodes are as described above. A 25-input implementation would thus require a five-deep tree with 24 nodes.

\$\endgroup\$
2
  • \$\begingroup\$ Passing the index and priority through the network together is neat. Should be smaller and the worst case ripple sounds better also. \$\endgroup\$
    – shuckc
    May 27, 2014 at 9:24
  • \$\begingroup\$ @shuckc: It should work pretty well. If one pairs up IDs sensibly, many of the multiplexers won't need the full ten bits (e.g. compare the winner from #1-#3 to the winner from #4-#7, and only the bottom two bits will need multiplexing (the third bit will indicate whether the upper or lower set won). One thing I neglected to mention, though, is that for proper operation the inputs must be synchronized with whatever is going to be looking at the output. Otherwise a change to one of the inputs could cause the output to be momentarily bogus (a problem common to nearly any priority encoder). \$\endgroup\$
    – supercat
    May 27, 2014 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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