Linear priority encoder in Xilinx Virtex4

Hello,

I need a linear priority encoder that has N input and N outputs.
Searching the group, I saw a thread where Peter Alfke stated :

--- cut ---

> Let me tell you what can be done in Virtex-4 (probably also in
> Spartan3):
> A priority "linear encoder" with 4 x N inputs and 4 x N outputs, each
> output corresponding to a prioritized input.
> Only one output is ever active, the one corresponding to the
> highest-priority active input.
> Total cost: 5N+1 (LUTs+flip-flops).
> Such a 32-input linear priority encoder uses 41 LUTs = 21 slices (<6
> CLBs), and runs at >250 MHz.
> The design is fully modular (per 4 bits).
>Peter Alfke

--- cut ---

But no details where given.

Can someone provide more details on how that implemented in a slice ?

Thanks.

    Sylvain

Sylvain Munaut <SomeOne@SomeDomain.com> schrieb:

> Hello,
>
> I need a linear priority encoder that has N input and N outputs.
> Searching the group, I saw a thread where Peter Alfke stated :
>
> --- cut ---
>
> > Let me tell you what can be done in Virtex-4 (probably also in
> > Spartan3):
> > A priority "linear encoder" with 4 x N inputs and 4 x N outputs, each
> > output corresponding to a prioritized input.
> > Only one output is ever active, the one corresponding to the
> > highest-priority active input.
> > Total cost: 5N+1 (LUTs+flip-flops).
> > Such a 32-input linear priority encoder uses 41 LUTs = 21 slices (<6
> > CLBs), and runs at >250 MHz.
> > The design is fully modular (per 4 bits).
> >Peter Alfke
>
> --- cut ---
>
> But no details where given.
>
> Can someone provide more details on how that implemented in a slice ?
>
> Thanks.
> 
>     Sylvain

was possible meant as brain teaser!

Antti

On 25 Aug 2006 01:26:55 -0700, "Sylvain Munaut
<SomeOne@SomeDomain.com>" <246tnt@gmail.com> wrote:

>Hello,
>
>I need a linear priority encoder that has N input and N outputs.
>Searching the group, I saw a thread where Peter Alfke stated :
>
>--- cut ---
>
>> Let me tell you what can be done in Virtex-4 (probably also in
>> Spartan3):
>> A priority "linear encoder" with 4 x N inputs and 4 x N outputs, each
>> output corresponding to a prioritized input.
>> Only one output is ever active, the one corresponding to the
>> highest-priority active input.
>> Total cost: 5N+1 (LUTs+flip-flops).
>> Such a 32-input linear priority encoder uses 41 LUTs = 21 slices (<6
>> CLBs), and runs at >250 MHz.
>> The design is fully modular (per 4 bits).
>>Peter Alfke
>
>--- cut ---
>
>But no details where given.
>
>Can someone provide more details on how that implemented in a slice ?
>
>Thanks.
>
>    Sylvain

Let me try to verbally sketch this out for you for 4 bits:
Imagine two colums of luts. There is one lut on the left for 4 inputs
and 4 on the right one for each output. The left LUT is a 4 input OR
and all the LUTs on the right are AND gates but with bubbles on some
inputs. The top right LUT is just an AND of top first input bit and
the output of left LUT. The second LUT on the right has first input
inverted, second bit and output of left LUT. The third LUT has first
two inputs inverted, third input, and output of left LUT. The last LUT
has the first 3 inputs inverted and output of left LUT. This gives you
4 input, 4 output priority encoder with 5 LUTs. Now you have to be
able to cascade this ie you have to disable the output of left (OR)
LUT by a higher up left LUT. For this purpose you can use the carry
chain.
HTH.

> Let me try to verbally sketch this out for you for 4 bits:
> Imagine two colums of luts. There is one lut on the left for 4 inputs
> and 4 on the right one for each output. The left LUT is a 4 input OR
> and all the LUTs on the right are AND gates but with bubbles on some
> inputs. The top right LUT is just an AND of top first input bit and
> the output of left LUT. The second LUT on the right has first input
> inverted, second bit and output of left LUT. The third LUT has first
> two inputs inverted, third input, and output of left LUT. The last LUT
> has the first 3 inputs inverted and output of left LUT. This gives you
> 4 input, 4 output priority encoder with 5 LUTs. Now you have to be
> able to cascade this ie you have to disable the output of left (OR)
> LUT by a higher up left LUT. For this purpose you can use the carry
> chain.

Thanks ! Exactly what I was looking for ;)

     Sylvain

Sylvain Munaut <SomeOne@SomeDomain.com> wrote:
> > Let me try to verbally sketch this out for you for 4 bits:
> > Imagine two colums of luts. There is one lut on the left for 4 inputs
> > and 4 on the right one for each output. The left LUT is a 4 input OR
> > and all the LUTs on the right are AND gates but with bubbles on some
> > inputs. The top right LUT is just an AND of top first input bit and
> > the output of left LUT. The second LUT on the right has first input
> > inverted, second bit and output of left LUT. The third LUT has first
> > two inputs inverted, third input, and output of left LUT. The last LUT
> > has the first 3 inputs inverted and output of left LUT. This gives you
> > 4 input, 4 output priority encoder with 5 LUTs. Now you have to be
> > able to cascade this ie you have to disable the output of left (OR)
> > LUT by a higher up left LUT. For this purpose you can use the carry
> > chain.
>
> Thanks ! Exactly what I was looking for ;)
>

Well, actually I'm having trouble with the chaining ... how do you
implement
what you describe (masking the lower priority OR luts) when a higher
one is active.

I have the slice schema before me and I can't figure that out ...
(damn, am I slow today ...)

I see that :
 - I could chain two stages, but no more than two.
 - I could use a big or of all the upper priority groups with the carry
chain and then use it to mask the left OR. But then for 3 groups, I
would need :
   - Upper priority group : - Just 1 LUT4 for the OR + 4 LUT4 for
encoding
   - Middle priority group : - 1 LUT4 for the OR + 1 LUT4 for the
'masking' + 4 LUT4 for encoding
   - Low priority group - 1 LUT4 for the OR + 2 LUT4 for the masking +
4 LUT4 for encoding

So that would be 18 LUT4.

And 5*3 + 1 = 16; So there is better ;)



   Sylvain