how to approach string/pattern checking in VHDL?

Question

I have a problem - that I think I can solve with regular 'c' like operations but I was wondering if there is a better way, something like 'regexp' for VHDL

the problem is that I have a string/collection of bits, "101010101010101" and I want to look for the pattern (with no overlapping) "1010" inside

what are my best options for attacking this problem?

edit : I'd like to mention that the input is parralel, all the bits at once and not in serial it is still possible to implement this as an FSM - but it there a more efficient way?

Martin Thompson · Accepted Answer · 2013-12-04 14:47:04Z

2

If all you want to do is find a pattern within a vector, then you can just iterate over it. Assuming "downto" vectors:

process (vec, what_to_find)
begin
   found <= 0;
   for start in vec'high downto vec'low+what_to_find'length loop
       if vec(start downto start - what_to_find'length) = what_to_find then
           found <= start;
       end if;
   end for;    
end process;

Depending on the sizes of your input and search vectors compared to the target device, this will be a reasonable or unreasonable amount of logic!

edited Dec 4, 2013 at 14:47

answered Dec 3, 2013 at 11:03

Martin Thompson

16.9k1 gold badge40 silver badges58 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

YNWA Over a year ago

hi, thanks for the reply - I was wondering about this line "if vec(start downto start - what_to_find'length) - what_to_find then" what it does? is the '-' sign is substraction or some other vector operator I'm unfamiliar with?

Martin Thompson Over a year ago

Sorry, the second - sign should be an equals (=)! Does that make more sense now?

BennyBarns · Accepted Answer · 2013-12-03 07:40:11Z

1

VHDL does not have builtin regex support, however what you are planning to solve is a pattern matching problem. Basically what you do is build a statemachine (which is what happens when evaluating a regular expression) and use it to match the input. The most simple approach is to check whether the first n bit match your pattern, then shift and continue. Longer, or more interesting patterns, e.g., incorporating quantifiers, matching groups etc. require a bit more.

There are numerous approaches to do that (try google vhdl pattern matching, it is used,e.g., for network traffic analysis), I even found one that would automatically generate the vhdl. I would guess, however, that a specialized hand-made version for your problem would be rather more efficient.

answered Dec 3, 2013 at 7:40

BennyBarns

6305 silver badges12 bronze badges

2 Comments

YNWA Over a year ago

so a regular FSM, I though about that - but that needs a CLOCK right? anyway to do that without a CLOCK?

YNWA Over a year ago

only way I can think about it without a clock is back to WHILE statement - anyway around it?...I just want to make sure that I am not doing dirty work when there is a more elegent/industry acceptible method

Morten Zilmer · Accepted Answer · 2013-12-03 10:09:28Z

The there is no generally applicable VHDL solution for that kind of pattern matching, but the solution should be driven by the requirements, since size and speed can vary greatly for that kind of design.

So, if timing allows for ample time to do an all parallel compare and filtering of overlapping patterns, and there is plenty of hardware to implement that, then you can do a parallel compare.

For an all parallel implementation without FSM and clock, then you can make a function that takes the pattern and collection, and returns a match indication std_logic_vector with '1' for start of each match.

The function can then be used in concurrent assign with:

match <= pattern_search_collection(pattern, collection);

The function can be implemented with something along the lines of:

function pattern_search_collection(pat : std_logic_vector;
                                   col : std_logic_vector) return std_logic_vector is
  ...
begin
  -- Code for matching with overlap using loop over all possible positions
  -- Code for filtering out overlaps using loop over all result bits
  return result;
end function;

Collectives™ on Stack Overflow

how to approach string/pattern checking in VHDL?

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related