can we implement LIFO using SRL16 ???

[Oleg]

Hi,
My question is : can we implement LIFO bloc (Last In First Out) using
registers included in Xilinx LUT's( for exemple the SRL16) to improve
the design. I know that for FIFO , we can do so, but what can we do to
implement efficiently LIFO ???.
Thanks in advence.

 

[Ian Poole]

Impementing a LIFO using an SRL16 sounds hard (I'll need more coffee to
think about it), but using a RAM16x1S sounds a lot easier - you just need a
4-bit up/down counter and enough RAM16x1Ss to for your word width. The
RAM16x1S is a 16-bit RAM implemented in the LUT. If you write your code
using the "correct template" you won't have to mention the specific Xilinx
components - your synthesis tool will spot you want RAM and give you either
RAM16x1Ss or block ram (probably an option in your tool to control which
type of RAM is inferred - your tool should document the code and options).

HTH

Ian

--
Ian Poole, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * Perl * Tcl/Tk * Verification * Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, Hampshire, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail: (e-mail address removed)
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Ray Andraka]

Presumably, it would work in a batch mode, where you get the data in, and
then send it out in the reverse order (otherwise, how do you handle data
that comes in after the 'last' data was sent out). If so, then the answer
is yes, this is pretty easy to do. Basically the write side is handled by
the shifting. Read is done using a binary count. An up count will output
the most recent input first. You'll need a small state machine to
synchronize the input and output block timing.

SRL16's can also be used for reordering data into an arbitrary sequence.
In that case, you use four LUTs as ROMs to generate the address to the
SRL16, and a counter addresses the LUT ROM. If the counter is
synchronized to your incoming data, the LUT ROM selects which samples to
pick out at each clock tick. Don't forget to account for the movement of
the data through the SRL16 as you pick off the data. This makes a nifty
data reorder for many applications, including an FFT.

Hi,
My question is : can we implement LIFO bloc (Last In First Out) using
registers included in Xilinx LUT's( for exemple the SRL16) to improve
the design. I know that for FIFO , we can do so, but what can we do to
implement efficiently LIFO ???.
Thanks in advence.

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email (e-mail address removed)
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759

 

[Oleg]

Presumably, it would work in a batch mode, where you get the data in, and
then send it out in the reverse order (otherwise, how do you handle data
that comes in after the 'last' data was sent out). If so, then the answer
is yes, this is pretty easy to do. Basically the write side is handled by
the shifting. Read is done using a binary count. An up count will output
the most recent input first. You'll need a small state machine to
synchronize the input and output block timing.

SRL16's can also be used for reordering data into an arbitrary sequence.
In that case, you use four LUTs as ROMs to generate the address to the
SRL16, and a counter addresses the LUT ROM. If the counter is
synchronized to your incoming data, the LUT ROM selects which samples to
pick out at each clock tick. Don't forget to account for the movement of
the data through the SRL16 as you pick off the data. This makes a nifty
data reorder for many applications, including an FFT.


--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email (e-mail address removed)
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759

Hi and thanks a lot guys,

I tryed what u say, its more interesting to design a LIFO using Bloc
RAM or SRL16, that way we save on LUT's. I like the idea but the
probleme is that we have a countinious stream of blocks tobe inverted
like in the viterbi decoder. This imply a use of a double quantity of
memory. So while one is being saving incaming stream , the other one
is outputing the ordered block and then they alternativly switch
operations. When I used the D flip-flops to realise the LIFO, i could
use the same amount of registres (note double). Once the row of
registers is full, the direction of the shifting is inverted so at one
end you can start outputing the ordered block while from the other end
you start shifting in the incomming bits of the next block. each time
a full shift is completed, we inverte a direction on shifting....
The question now is how to do so with RAM bloc or SLR16.

 

[Ray Andraka]

For an SRL16, it is jsut a matter of modulating the address. You data shifts in on each
clock in forward order, so you want to change the address to read the data out in the
reverse order. In order to get a reversed sequence, you have to advance the read address
by 2 on each clock the while the input is shifting by 1. In order to accommodate a
continuous input stream, the length of the SRL16 register has to be twice the length of
your sequence, so you may have to cascade more than one SRL16.

Take the case of an 8 sample sequence

in 0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
S0 0 1 2 3 4 5 6
7 8 9 10 11 12 13 14 15
S1 0 1 2 3 4 5
6 7 8 9 10 11 12 13 14
S2 0 1 2 3 4
5 6 7 8 9 10 11 12 13 14
S3 0 1 2 3
4 5 6 7 8 9 10 11 12 13 14
S4 0 1 2
3 4 5 6 7 8 9 10 11 12
13
S5 0 1
2 3 4 5 6 7 8 9 10 11
12
S6 0
1 2 3 4 5 6 7 8 9 10
11 12
S7
0 1 2 3 4 5 6 7 8 9
10 11
S8
0 1 2 3 4 5 6 7 8 9
10 11
S9
0 1 2 3 4 5 6 7 8 9
10
S10
0 1 2 3 4 5 6 7 8 9
10
S11
0 1 2 3 4 5 6 7 8 9
S12
0 1 2 3 4 5 6 7 8 9
S13
0 1 2 3 4 5 6 7 8
S14
0 1 2 3 4 5 6 7 8
addr
0 2 4 6 8 10 12 14 0 2
4 6 8 10 12 14 0
out
7 6 5 4 3 2 1 0 15 14
13 12 11 10 9 8

All you need is an SRL16 and a small counter, plus muxes if you are cascading SRL16's to
get a long enough sequence buffer.

You can also do other address sequences, for example you could use the sequence: 3 0 3 0 6
3 6 3 to get a 3 bit bit-reversed address ordering (output is ordered 0,4,2,6,1,5,3,7 ).
Putting a LUT ROM between a binary counter and the SRL16 address makes it easy to generate
an arbitrary address sequence, and for speed, register the LUT ROM outputs too.

I have also used SRL16's in sorting applications to do the position swaps. In that case,
the address is modulated based on a compare that happens between samples before the SRL16.

Hi and thanks a lot guys,

I tryed what u say, its more interesting to design a LIFO using Bloc
RAM or SRL16, that way we save on LUT's. I like the idea but the
probleme is that we have a countinious stream of blocks tobe inverted
like in the viterbi decoder. This imply a use of a double quantity of
memory. So while one is being saving incaming stream , the other one
is outputing the ordered block and then they alternativly switch
operations. When I used the D flip-flops to realise the LIFO, i could
use the same amount of registres (note double). Once the row of
registers is full, the direction of the shifting is inverted so at one
end you can start outputing the ordered block while from the other end
you start shifting in the incomming bits of the next block. each time
a full shift is completed, we inverte a direction on shifting....
The question now is how to do so with RAM bloc or SLR16.

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email (e-mail address removed)
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759

 

[Ray Andraka]

Oops, sorry about that. Looks like my fonts get messed and it wrapped.

For an SRL16, it is jsut a matter of modulating the address. You data shifts in on each
clock in forward order, so you want to change the address to read the data out in the
reverse order. In order to get a reversed sequence, you have to advance the read address
by 2 on each clock the while the input is shifting by 1. In order to accommodate a
continuous input stream, the length of the SRL16 register has to be twice the length of
your sequence, so you may have to cascade more than one SRL16.

Take the case of an 8 sample sequence

in 0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
S0 0 1 2 3 4 5 6
7 8 9 10 11 12 13 14 15
S1 0 1 2 3 4 5
6 7 8 9 10 11 12 13 14
S2 0 1 2 3 4
5 6 7 8 9 10 11 12 13 14
S3 0 1 2 3
4 5 6 7 8 9 10 11 12 13 14
S4 0 1 2
3 4 5 6 7 8 9 10 11 12
13
S5 0 1
2 3 4 5 6 7 8 9 10 11
12
S6 0
1 2 3 4 5 6 7 8 9 10
11 12
S7
0 1 2 3 4 5 6 7 8 9
10 11
S8
0 1 2 3 4 5 6 7 8 9
10 11
S9
0 1 2 3 4 5 6 7 8 9
10
S10
0 1 2 3 4 5 6 7 8 9
10
S11
0 1 2 3 4 5 6 7 8 9
S12
0 1 2 3 4 5 6 7 8 9
S13
0 1 2 3 4 5 6 7 8
S14
0 1 2 3 4 5 6 7 8
addr
0 2 4 6 8 10 12 14 0 2
4 6 8 10 12 14 0
out
7 6 5 4 3 2 1 0 15 14
13 12 11 10 9 8

All you need is an SRL16 and a small counter, plus muxes if you are cascading SRL16's to
get a long enough sequence buffer.

You can also do other address sequences, for example you could use the sequence: 3 0 3 0 6
3 6 3 to get a 3 bit bit-reversed address ordering (output is ordered 0,4,2,6,1,5,3,7 ).
Putting a LUT ROM between a binary counter and the SRL16 address makes it easy to generate
an arbitrary address sequence, and for speed, register the LUT ROM outputs too.

I have also used SRL16's in sorting applications to do the position swaps. In that case,
the address is modulated based on a compare that happens between samples before the SRL16.


--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email (e-mail address removed)
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email (e-mail address removed)
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759