Original Publication Date: 2004-Nov-22
Included in the Prior Art Database: 2004-Nov-22
Bit mapping pattern matching
It is sometimes necessary to find a particular succession of bit in a flow of data. This is usually called pattern matching.
This description relates to a subset of pattern matching.
Instead of having a full pattern matching this description relates to a simplified pattern matching that apply in some specific cases.
This can mainly used when the searched data is a kind of bit mapping.
For instance, the matching can be see if there is one or more consecutive bit set to 1 in a bus. 000111100000 data has to be declared as match. 001011100000 has to be declared as unmatched. 001000000000 data has to be declared as match.
To do so a common method is to search for all possible combination. This can lead to a large amount of complex logic, and a very high parallel structure has to be used.
Instead of doing so, this invention describe such search has a number of transition, instead of
I.e. the above search is a search for a data which contains at most 2 transitions: 000111100000 ==> 000100100000 ==> There is 2 transitions ==> Match 001011100000 ==> 001110010000 ==> There is 4 transitions ==> No match 001000000000 ==> 001100000000 ==> There is 2 transitions ==> Match.
To do this pattern matching, the data received are passed through a bank of xor gate. Each bit is compared to the previous one.
Now instead of having a raw data, we get a bit map of transition.We just have now to count the number of ones to have the number of transition.