Detecting bit transistion in std_logic_vector

Discussion in 'VHDL' started by Tobias Baumann, Feb 15, 2012.

1. Tobias BaumannGuest

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, Feb 15, 2012

2. Mike TreselerGuest

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

-- Mike Treseler
Mike Treseler, Feb 15, 2012

3. GaborGuest

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

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
Gabor, Feb 15, 2012
4. Tobias baumannGuest

Re: Detecting bit transition in std_logic_vector

> 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, Feb 16, 2012
5. Tobias baumannGuest

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
Tobias baumann, Feb 16, 2012
6. KJGuest

Re: Detecting bit transition in std_logic_vector

On Feb 15, 7:01 pm, Tobias baumann <> 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

Kevin Jennings
KJ, Feb 16, 2012
7. Philip HerzogGuest

On 2/15/2012 16:56, Tobias Baumann wrote:
> 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
--
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)
Philip Herzog, Feb 16, 2012
8. backhusGuest

Re: Detecting bit transition in std_logic_vector

On 16 Feb., 01:56, KJ <> wrote:
> On Feb 15, 7:01 pm, Tobias baumann <> 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
>
> Kevin Jennings

Hi Kevin,
"Gatter" is german for gate.

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.

Have a nice synthesis
Eilert
backhus, Feb 16, 2012
9. Tobias BaumannGuest

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, Feb 16, 2012
10. Tobias BaumannGuest

Re: Detecting bit transition in std_logic_vector

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, Feb 16, 2012
11. Tobias BaumannGuest

Re: Detecting bit transition in std_logic_vector

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

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
Tobias Baumann, Feb 16, 2012
12. backhusGuest

Re: Detecting bit transition in std_logic_vector

On 16 Feb., 12:20, Tobias Baumann <> 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

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
backhus, Feb 17, 2012
13. Tobias BaumannGuest

Re: Detecting bit transition in std_logic_vector

> 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
Tobias Baumann, Feb 17, 2012
14. backhusGuest

Re: Detecting bit transition in std_logic_vector

On 17 Feb., 13:01, Tobias Baumann <> 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

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
backhus, Feb 20, 2012
15. Tobias BaumannGuest

Re: Detecting bit transition in std_logic_vector

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
Tobias Baumann, Feb 21, 2012