Detecting bit transistion in std_logic_vector

[Tobias Baumann]

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

 

[Mike Treseler]

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

-- Mike Treseler

 

[Gabor]

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

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

 

[Tobias baumann]

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.

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;

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

 

[Tobias baumann]

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

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

 

[KJ]

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

 

[Philip Herzog]

Do someone know a good technique to implement this?

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

 

[backhus]

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

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

 

[Tobias Baumann]

Am 16.02.2012 10:27, schrieb Philip Herzog:

How much time do you have? Where does the data come from?

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.

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...

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

 

[Tobias Baumann]

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

 

[Tobias Baumann]

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.

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.

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

 

[backhus]

Am 16.02.2012 10:39, schrieb backhus:


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


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).


What are MSI functions?

Tobias

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

 

[Tobias Baumann]

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

 

[backhus]

 > 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

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

 

[Tobias Baumann]

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.

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.

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