Browse Prior Art Database

Pattern Matching

IP.com Disclosure Number: IPCOM000033038D
Original Publication Date: 2004-Nov-22
Included in the Prior Art Database: 2004-Nov-22
Document File: 1 page(s) / 48K

Publishing Venue

IBM

Abstract

Bit mapping pattern matching

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 94% of the total text.

Page 1 of 1

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 pattern search.
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.

This...