# Coding a priority encoder

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?

• 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. Apr 13, 2014 at 15:42
• Dave, that is a answer, not a comment! Apr 13, 2014 at 16:11

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.