Detecting bit transistion in std_logic_vector

T

Tobias Baumann

Guest
Hi everybody

I have a 32 bit std_logic_vector, for example something like this:

00010101111111111101010000000000

Now I want to find the place where the 1's start to be constant for at
least five times and where it ends to be constant. In the example above
I try to indicate

00010101111111111101010000000000
^ ^
| |

Do someone know a good technique to implement this? A working solution
is to loop over all bits and compare like:

-- find first transistion
for i in 0 to 27 loop

if (match_mask(i+5-1 downto i) = "11111") then
first_trans := i;
exit;
end if;

end loop;

-- find last transistion
for i in 0 to 27 loop

if (match_mask(31-i downto 31-i-5+1) = "11111") then
last_trans := 31-i;
exit;
end if;

end loop;

But is this effective (I want to synthesize the code with XST)? Does
someone know how to make it better?

Thanks a lot,
Tobias
 
Tobias Baumann wrote:
Hi everybody

I have a 32 bit std_logic_vector, for example something like this:

00010101111111111101010000000000

Now I want to find the place where the 1's start to be constant for at
least five times and where it ends to be constant. In the example above
I try to indicate

00010101111111111101010000000000
^ ^
| |

Do someone know a good technique to implement this? A working solution
is to loop over all bits and compare like:

-- find first transistion
for i in 0 to 27 loop

if (match_mask(i+5-1 downto i) = "11111") then
first_trans := i;
exit;
end if;

end loop;

-- find last transistion
for i in 0 to 27 loop

if (match_mask(31-i downto 31-i-5+1) = "11111") then
last_trans := 31-i;
exit;
end if;

end loop;

But is this effective (I want to synthesize the code with XST)? Does
someone know how to make it better?

Thanks a lot,
Tobias
Click to expand...
I imagine you could have tried synthesis by now, but generally
loops with "exit" don't synthesize in XST. The loop needs to
have a constant number of iterations. You can use variables
within the loop to keep track of conditions that are met, and
use these to prevent any action from happening after you would
have exit. Something like:

found := '0';
for i in 0 to 27 loop

if (match_mask(31-i downto 31-i-5+1) = "11111") and (found = '0') then
last_trans := 31-i;
found := '1';
end if;

-- Gabor
 
If you want to find transitions, the mask should be "011111".
I would write a function.

-- Mike Treseler
 
I imagine you could have tried synthesis by now, but generally
loops with "exit" don't synthesize in XST.
Click to expand...
XST works without any errors. But when I observe my design with
technology viewer, I see a lot of gatters, so I think the design can be
optimized.


found := '0';
for i in 0 to 27 loop

if (match_mask(31-i downto 31-i-5+1) = "11111") and (found = '0') then
last_trans := 31-i;
found := '1';
end if;
Click to expand...
When I'm back at work, I try this approach and take a look into
technology viewer to see if there are any changes. Maybe the exit
statement will be synthesized like this (the XST documentation describes
that exit statement is supported in ISE 13.3 on Virtex 6, maybe other
configurations aren't).

Thanks,
Tobias
 
Am 15.02.2012 22:00, schrieb Mike Treseler:
If you want to find transitions, the mask should be "011111".
I would write a function.

-- Mike Treseler
Click to expand...
Thanks a lot, this makes my transistion unique and I don't need the exit
statement in my loop.

How would you write the function? Using a loop or if/elsif like:

if (match_mask(5 downto 0) = "111110") then
first_trans := 0;
elsif (match_mask(6 downto 1) = "111110") then
first_trans := 1;
elsif ...

Maybe I try both implementations and see what works more effective, but
if you have a good idea I would be glad to know.

Thanks,
Tobias
 
On Feb 15, 7:01 pm, Tobias baumann <ttob...@hotmail.com> wrote:
I imagine you could have tried synthesis by now, but generally
loops with "exit" don't synthesize in XST.

XST works without any errors. But when I observe my design with
technology viewer, I see a lot of gatters, so I think the design can be
optimized.
Click to expand...
I don't know what a 'gatter' is, but I'm guessing it's not good...or
at least not good to see a lot of them.

Another approach is to trade off time for logic. Have a five bit
counter that counts through the bits to give you the index (and to let
you know when you're done); shift the data through a shift register
and have another three bit counter to detect consecutive ones,
incrementing when you see a 1 coming out of the shift register, reset
the count to 0 when you see a 0. At most 32 clocks later you can have
your result.

Kevin Jennings
 
On 2/15/2012 16:56, Tobias Baumann wrote:
Do someone know a good technique to implement this?
Click to expand...
How much time do you have? Where does the data come from?

If the data comes in in a serial manner, one bit per clock cycle, the
transistion is pretty easy to detect on-the-fly. Otherwise, if you have
the time just shift it down and always run the detection on the lowest bits.

Otherwise, I think a process with a loop will do best and yes, this will
generate a lot of logic...

- Philip
--
Life's journey is not to arrive at the grave safely
in a well-preserved body, but rather to skid in
sideways, totally worn out shouting "holy shit, what
a ride!" (Mavis Leyrer)
 
On 16 Feb., 01:56, KJ <kkjenni...@sbcglobal.net> wrote:
On Feb 15, 7:01 pm, Tobias baumann <ttob...@hotmail.com> wrote:

I imagine you could have tried synthesis by now, but generally
loops with "exit" don't synthesize in XST.

XST works without any errors. But when I observe my design with
technology viewer, I see a lot of gatters, so I think the design can be
optimized.

I don't know what a 'gatter' is, but I'm guessing it's not good...or
at least not good to see a lot of them.

Another approach is to trade off time for logic.  Have a five bit
counter that counts through the bits to give you the index (and to let
you know when you're done); shift the data through a shift register
and have another three bit counter to detect consecutive ones,
incrementing when you see a 1 coming out of the shift register, reset
the count to 0 when you see a 0.  At most 32 clocks later you can have
your result.

Kevin Jennings
Click to expand...
Hi Kevin,
"Gatter" is german for gate.
So your guess was correct. :)

Your proposal for using a sequential approach seems the better way for
me too, unless there's something in the system requirements that holds
against it.
But with such sparse information it can't be known yet.

I only like to add that instead of pluggging MSI functions together
Tobias should design a nice little FSM.
FSMs are ideal for pattern recognition and can be fitted to the rest
of his system as needed.
He surely had learned about this in some digital basics class.

Have a nice synthesis
Eilert
 
Am 16.02.2012 10:27, schrieb Philip Herzog:
How much time do you have? Where does the data come from?
Click to expand...
I don't really know how much time I have. We design a completly new
product which isn't completly specified.

But one thing can I say: When the logic is too big, we can't buy a new
FPGA, so it's better to save space then time.

If the data comes in in a serial manner, one bit per clock cycle, the
transistion is pretty easy to detect on-the-fly. Otherwise, if you have
the time just shift it down and always run the detection on the lowest bits.
Click to expand...
The on the fly approach sounds good and I think it is possible to
implement. I try this and post if I had success (or no success).

Otherwise, I think a process with a loop will do best and yes, this will
generate a lot of logic...
Click to expand...
Yes this is a problem. First I thought it's ok to have a lot of logic,
but I need this for maybe 200 data lines and then it could be a problem.

Tobias
 
Am 16.02.2012 10:39, schrieb backhus:
Hi Kevin,
"Gatter" is german for gate.
So your guess was correct. :)
Click to expand...
Oh I'm sorry. I thought gatter is also english when speak it like
"getter" ;)

Your proposal for using a sequential approach seems the better way for
me too, unless there's something in the system requirements that holds
against it.
But with such sparse information it can't be known yet.
Click to expand...
Yes I will try it sequential, maybe I can to it on the fly (like Philip
mentioned it). My match_mask is also generated sequentially, so maybe I
can find the transition (so I wouldn't need the match mask).

I only like to add that instead of pluggging MSI functions together
Tobias should design a nice little FSM.
Click to expand...
What are MSI functions?

Tobias
 
Am 16.02.2012 01:56, schrieb KJ:
I don't know what a 'gatter' is, but I'm guessing it's not good...or
at least not good to see a lot of them.
Click to expand...
I'm sorry, I thought gatter can also be an english word. It means gate
like Eilert said.

Another approach is to trade off time for logic. Have a five bit
counter that counts through the bits to give you the index (and to let
you know when you're done); shift the data through a shift register
and have another three bit counter to detect consecutive ones,
incrementing when you see a 1 coming out of the shift register, reset
the count to 0 when you see a 0. At most 32 clocks later you can have
your result.
Click to expand...
I think thats the way I will do. I don't know exactly how I'm contrained
with my design, but when the FPGA is full we can't buy a new one, so
it's better to trade time for logic.

Thanks a lot.

Tobias
 
On 16 Feb., 12:20, Tobias Baumann <ttob...@hotmail.com> wrote:
Am 16.02.2012 10:39, schrieb backhus:

Hi Kevin,
"Gatter" is german for gate.
So your guess was correct. :)

Oh I'm sorry. I thought gatter is also english when speak it like
"getter" ;)

Your proposal for using a sequential approach seems the better way for
me too, unless there's something in the system requirements that holds
against it.
But with such sparse information it can't be known yet.

Yes I will try it sequential, maybe I can to it on the fly (like Philip
mentioned it). My match_mask is also generated sequentially, so maybe I
can find the transition (so I wouldn't need the match mask).

I only like to add that instead of pluggging MSI functions together
Tobias should design a nice little FSM.

What are MSI functions?

Tobias
Click to expand...
Hi Tobias.
MSI = Medium Scale Integrated
Stuff like counters, comparators and other "building blocks" like
known from ye olde 74xxx devices.

So you don't have a complete specification for some very new design of
yet unknown complexity, but the FPGA is already selected and
unchangable?
Who's managing that project? PHB?

Have a nice synthesis
Eilert
 
Hi Tobias.
MSI = Medium Scale Integrated
Stuff like counters, comparators and other "building blocks" like
known from ye olde 74xxx devices.
Click to expand...
Thanks a lot for this information.

So you don't have a complete specification for some very new design of
yet unknown complexity, but the FPGA is already selected and
unchangable?
Click to expand...
We build a board for calculating trigger signals in particale physics.
The FPGA is already selected because the next bigger ones are too expensive.

We also don't know how much logic we need for doing this calculation,
because other ones have first to do theoretical stuff. But we can't wait
for them, so we have to start buildung up the design. And because I
don't know how much logic we need, I try to use as little as possible.

Who's managing that project? PHB?
Click to expand...
I'm glad that it isn't so ;)

Have a nice synthesis
Click to expand...
Thanks a lot. My timing constraints don't met (but not because of this
problem). It's not a good day.

Tobias
 
On 17 Feb., 13:01, Tobias Baumann <ttob...@hotmail.com> wrote:
 > Hi Tobias.
 > MSI = Medium Scale Integrated
 > Stuff like counters, comparators and other "building blocks" like
 > known from ye olde 74xxx devices.

Thanks a lot for this information.

 > So you don't have a complete specification for some very new design of
 > yet unknown complexity, but the FPGA is already selected and
 > unchangable?

We build a board for calculating trigger signals in particale physics.
The FPGA is already selected because the next bigger ones are too expensive.

We also don't know how much logic we need for doing this calculation,
because other ones have first to do theoretical stuff. But we can't wait
for them, so we have to start buildung up the design. And because I
don't know how much logic we need, I try to use as little as possible.

 > Who's managing that project? PHB?

I'm glad that it isn't so ;)

 > Have a nice synthesis

Thanks a lot. My timing constraints don't met (but not because of this
problem). It's not a good day.

Tobias
Click to expand...
Hi Tobias,
I see, public funded projects often go strange ways due to budget and
time limits.
I know that situation very well.

Do you know the Xilinx forums?
http://forums.xilinx.com
For design problems with Xilinx devices beyond VHDL these forums are
better suited.
Especially when you have problems with timing clusure and need hints
on reducing area consumption.
See you there.

Have a nice synthesis
Eilert
 
Am 20.02.2012 07:57, schrieb backhus:
Hi Tobias,
I see, public funded projects often go strange ways due to budget and
time limits.
I know that situation very well.
Click to expand...
Yes, that's a little bit sad, but maybe it teachs the own creativity. ;)

Do you know the Xilinx forums?
http://forums.xilinx.com
For design problems with Xilinx devices beyond VHDL these forums are
better suited.
Especially when you have problems with timing clusure and need hints
on reducing area consumption.
See you there.
Click to expand...
Yes I know it and I'm already registered. I use it most time for more
Xilinx specific questions. But for this topic I thought I reach more
people who could help me.

Tobias
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top