Detecting bit transistion in std_logic_vector

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

  1. 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
    #1
    1. Advertising

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

    -- Mike Treseler
    Mike Treseler, Feb 15, 2012
    #2
    1. Advertising

  3. Tobias Baumann

    Gabor Guest

    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
    #3
  4. 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
    #4
  5. 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
    #5
  6. Tobias Baumann

    KJ Guest

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

    Kevin Jennings
    KJ, Feb 16, 2012
    #6
  7. 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
    #7
  8. Tobias Baumann

    backhus Guest

    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
    > 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
    backhus, Feb 16, 2012
    #8
  9. 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
    #9
  10. 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
    #10
  11. 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
    > 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
    Tobias Baumann, Feb 16, 2012
    #11
  12. Tobias Baumann

    backhus Guest

    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
    #12
  13. 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
    #13
  14. Tobias Baumann

    backhus Guest

    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
    #14
  15. 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
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Thomas Reinemann

    Detecting of 'U' in a std_logic_vector

    Thomas Reinemann, Oct 28, 2004, in forum: VHDL
    Replies:
    4
    Views:
    633
    Allan Herriman
    Nov 3, 2004
  2. Replies:
    3
    Views:
    1,750
    Timothy Bendfelt
    Jan 19, 2007
  3. Replies:
    9
    Views:
    970
    Juha Nieminen
    Aug 22, 2007
  4. Thomas Rouam
    Replies:
    6
    Views:
    1,128
  5. Jeff.M
    Replies:
    6
    Views:
    172
    Lasse Reichstein Nielsen
    May 4, 2009
Loading...

Share This Page