[Interview] FSM vs Shift Register [string matching]

Hi All,

String matching might be implemented in two ways - by a Shift Register (just shifting in the string while matching it with the pre-config value) and by FSM.

What's the difference in these two approaches? Why Shift Register could not behave as FSM?

Thank you!

If you think about it the shift register compare is just an unraveled FSM. So the FSM loop has been converted to the equivalent parallel operation.

That right there explains the difference between the two implementations. shift register (parallel), FSM (sequential).

For size the FSM will be smaller but you'll be required to repeat compares starting from the character following the beginning of the string that was last miscompared, so the end result is the compare operation can take much longer if there are multiple locations in the string that are near matches.

The shift register implementation scales based on the size of the match string, which could become an issue if the string is say 1000 characters.

No, I think that the difference is the functional operation as well...
Let's say you want to build a string detection, which is '1010'. Let's say, you have '000000010101' string in input... So, how many matches will be found be Shift Register? Two! But it was actually only one matched string. So...

- - - Updated - - -

shift register (parallel), FSM (sequential)

Click to expand...

Shift Register is also serial ...

FSM will be smaller

Click to expand...

Why?

end result is the compare operation can take much longer if there are multiple locations in the string that are near matches.

Click to expand...

Could you provide examples?

which could become an issue if the string is say 1000 characters

Click to expand...

1000 chars therefore 1000 FSM states - as the number of Shift Register stages ...

ivlsi said:

No, I think that the difference is the functional operation as well...
Let's say you want to build a string detection, which is '1010'. Let's say, you have '000000010101' string in input... So, how many matches will be found be Shift Register? Two! But it was actually only one matched string. So...

Click to expand...

you didn't say there had to be a specific delineation of the "string" (looks like serial data in your example). Unless you have a specific delineation then there could be a multitude of valid matches. Even your example doesn't prove anything I said was wrong.

Shift Register is also serial ...

Click to expand...

yeah but the compare is done in parallel, I guess you didn't understand that is what I meant by unraveling the FSM.

Why?

Click to expand...

Because unlike your implementation of an FSM to do this. I would implement a memory and address the data in it and compare as a SW program would do it. Makes for a slow but area efficient design, that incidentally will grow only a little as the width of the address to the memory grows regardless of the length of the strings (assuming the strings still fit in the memories).

Could you provide examples?

Click to expand...

search for abcd in the following "string"
abcabcabcabcabcd
search_string_char compared_to string_char
a==a, b==b, c==c, d!=a, start over at position 2: b!=a, start over at pos 3: c!=a, start over at pos 4: a==a, etc.

As you see the algorithm has to restart at the next char position to completely compare the entire string as it has a miscompare after the third char each time.

1000 chars therefore 1000 FSM states - as the number of Shift Register stages ...

Click to expand...

Only if you want to produce a brute force implementation that uses an FSM instead of the more direct approach using shift registers for the strings and a parallel compare operation.

Regards,
-alan

I would implement a memory and address the data in it and compare as a SW program would do it

Click to expand...

Hm... Could you provide more details on how to implement the string matching using Memory? Are you talking about HW implementation, aren't you?