Method and apparatus for recognizing a bit pattern in a string of bits, altering the string of bits, and removing the alteration from the string of bits

Claim 2

A computer implemented method for recognizing a search pattern in an input string of bits, said method comprising the steps of: A) selecting a portion of said string of bits as a currently selected portion; B) selecting a first set of masked occurrence patterns based on said search pattern and those bits of said string of bits immediately preceding said currently selected portion, said first set of masked occurrence patterns including one or more masked occurrence patterns, each representing a plurality of bit patterns that would be present in said currently selected portion if at least part of said search pattern is contained in said currently selected portion; C) determining if said currently selected portion contains any of said first set of masked occurrence patterns; and D) determining if said string of bits contains said search pattern based on whether said currently selected portion contains any of said first set of masked occurrence patterns.

Claim 3

The method of claim 1, wherein said selecting in step B further comprises the steps of: B1) determining how much of said search pattern is contained in those bits of said string of bits immediately preceding said currently selected portion; and B2) selecting said first set of masked occurrence patterns such that if any of said first set of masked occurrence patterns are contained in said currently selected portion, said string of bits contains said search pattern.

Claim 4

The method of claim 1, wherein said method further comprises the steps of: repeating steps A through D on an unprocessed remainder of said string of bits, wherein said currently selected portion is now a processed portion of said string of bits.

Claim 5

The method of claim 1, wherein said determining in step C further comprises the step of comparing at least a first masked occurrence pattern of said first set of masked occurrence patterns to said currently selected portion.

Claim 6

The method of claim 4, wherein said method further includes the step of: E) performing the following steps if it was determined in step C that said currently selected portion contains any of said first set of masked occurrence patterns: E1) selecting a second set of masked occurrence patterns based on one of said first set of masked occurrence patterns determined in step C to be contained in said currently selected portion; E2) determining if said currently selected portion contains any of said second set of masked occurrence patterns; and E3) determining if said string of bits contains said search pattern based on whether said currently selected portion contains any of said second set of masked occurrence patterns.

Claim 7

The method of claim 5, wherein said determining in step E3 further comprises the step of comparing at least a first masked occurrence pattern of said second set of masked occurrence patterns to said currently selected portion, wherein each masked occurrence pattern in said second set of masked occurrence patterns represents a plurality of occurrence patterns that would be present in said currently selected portion if said search pattern is contained within said currently selected portion.

Claim 8

The method of claim 1, wherein said selecting in step B further comprises the steps of: B1) determining if said currently selected portion contains an exclusion pattern; and B2) selecting said first set of masked occurrence patterns based on said search pattern, those bits of said string of bits immediately preceding said currently selected portion, and whether said currently selected portion contains said exclusion pattern.

Claim 9

The method of claim 7, wherein said exclusion pattern is such that at least one masked occurrence pattern cannot be contained in said currently selected portion if said exclusion pattern is contained in said currently selected portion.

Claim 12

The method of claim 9, wherein said selecting in step B further comprises the steps of: B1) determining how much of said search pattern is contained in those bits of said string of bits immediately preceding said currently selected portion; and B2) selecting said first set of bit patterns such that if any of said first set of bit patterns are contained in said currently selected portion, said string of bits contains said search pattern.

Claim 13

The method of claim 9, wherein said operating in step C further comprises the steps of comparing at least a first pattern of said first set of bit patterns to said currently selected portion.

Claim 14

The method of claim 9, wherein said operating in step C further comprises the step of comparing at least a first masked pattern of a first set of masked bit patterns to said currently selected portion, wherein each masked bit pattern in said first set of masked bit patterns represents a plurality of bit patterns in said first set of bit patterns.

Claim 15

The method of claim 12, wherein said step A further includes the steps of: A1) selecting a location in said string of bits as a currently selected location; and A2) selecting said first number of consecutive bits from said string of bits starting at said currently selected location as said currently selected portion; and wherein said method further comprises the step of: F) performing the following steps if said altering in step E was performed: F1) selecting said first number of consecutive bits from said string of bits starting at said currently selected location as said currently selected portion; F2) selecting a second set of bit patterns based on one of said first set of masked bit patterns determined in step C to be contained in said currently selected portion; F3) determining if said currently selected portion contains any of said second set of bit patterns; F4) determining if said string of bits contains said search pattern based on whether said currently selected portion contains any of said second set of bit patterns; and F5) altering said string of bits in said pre-defined manner if it was determined said string of bits contains said search pattern.

Claim 16

The method of claim 13, wherein said determining in step F3 further comprises the step of comparing at least a first masked occurrence pattern of a second set of masked bit patterns to said currently selected portion, wherein each masked bit pattern in said first set of masked bit patterns represents a plurality of bit patterns in said second set of bit patterns.

Claim 17

The method of claim 9, wherein said selecting in step B further comprises the steps of: B1) determining if said currently selected portion contains an exclusion pattern; and B2) selecting said first set of bit patterns based on said search pattern, those bits of said string of bits immediately preceding said currently selected portion, and whether said currently selected portion contains said exclusion pattern.

Claim 18

The method of claim 15, wherein said exclusion pattern is such that at least a first bit pattern which would indicate an occurrence of said search pattern in said string of bits if contained in said currently selected portion cannot be contained in said currently selected portion if said exclusion pattern is contained in said currently selected portion.

Claim 19

The method of claim 9, further comprising the steps of: E) altering said string of bits in a pre-defined manner if it was determined said string bits contains said search pattern.

Claim 20

The method of claim 17, wherein said altering said string of bits in a pre-defined manner in step E further comprises the steps of: E1) determining if each occurrence of said search pattern determined to be contained in said string of bits in step C is part of an occurrence of a frame delimiter; and E2) removing a bit from said string of bits after each occurrence of said search pattern determined to be contained in said string of bits in step C which was determined not to be an occurrence of said frame delimiter.

Claim 21

The method of claim 17, wherein said altering said string of bits in a pre-defined manner in step E further comprises the step of inserting a bit into said string of bits after each occurrence of said search pattern if said string of bits is to be transmitted.

Claim 22

The method of claim 19, wherein said step A further comprises the steps of: A1) selecting a location in said string of bits as a currently selected location; and A2) selecting said first number of consecutive bits from said string of bits starting at said currently selected location as said currently selected portion; and wherein said method further comprises the step of: F) repeating steps A through E on an unprocessed remainder of said string of bits, wherein at least said first number of consecutive bits starting at said currently selected location is now a processed portion of said string of bits.

Claim 23

The method of claim 20, wherein said method further includes the step of: transmitting in a frame said processed portions of said string of bits.

Claim 26

The apparatus of claim 22, wherein said plurality of instructions further embody logic for said selecting said first set of occurrence patterns by: B1) determining how much of said search pattern is contained in those bits of said string of bits immediately preceding said currently selected portion; and B2) selecting said first set of masked occurrence patterns such that if any of said first set of masked occurrence patterns are contained in said currently selected portion, said string of bits contains said search pattern.

Claim 27

The apparatus of claim 22, wherein said plurality of instructions further embody logic for: repeating steps A through D on an unprocessed remainder of said string of bits, wherein said currently selected portion is now a processed portion of said string of bits.

Claim 28

The apparatus of claim 22, wherein said plurality of instructions further embody logic for said determining if said currently selected portion contains any of said first set of occurrence patterns by comparing at least a first masked occurrence pattern of said first set of masked occurrence patterns to said currently selected portion.

Claim 29

The apparatus of claim 25, wherein said plurality of instructions further embody logic for: E) performing the following steps if it was determined in step C that said currently selected portion contains any of said first set of masked occurrence patterns: E1) selecting a second set of masked occurrence patterns based on one of said first set of masked occurrence patterns determined in step C to be contained in said currently selected portion; E2) determining if said currently selected portion contains any of said second set of masked occurrence patterns; and E3) determining if said string of bits contains said search pattern based on whether said currently selected portion contains any of said second set of masked occurrence patterns.

Claim 30

The apparatus of claim 26, wherein said plurality of instructions further embody logic for said determining if said currently selected portion contains any of said second set of occurrence patterns by: comparing at least a first masked occurrence pattern of said second set of masked occurrence patterns to said currently selected portion, wherein each masked occurrence pattern in said second set of masked occurrence patterns represents a plurality of occurrence patterns that would be present in said currently selected portion if said search pattern is contained within said currently selected portion.

Claim 31

The apparatus of claim 22, wherein said plurality of instructions further embody logic for said selecting said first set of occurrence patterns by: B1) determining if said currently selected portion contains an exclusion pattern; and B2) selecting said first set of masked occurrence patterns based on said search pattern, those bits of said string of bits immediately preceding said currently selected portion, and whether said currently selected portion contains said exclusion pattern.

Claim 32

The apparatus of claim 28, wherein said exclusion pattern is such that at least one masked occurrence pattern cannot be contained in said currently selected portion if said exclusion pattern is contained in said currently selected portion.

Claim 35

The apparatus of claim 30, wherein said plurality of instructions further embody logic for said selecting said first set of bit patterns by: B1) determining how much of said search pattern is contained in those bits of said string of bits immediately preceding said currently selected portion; and B2) selecting said first set of bit patterns such that if any of said first set of bit patterns are contained in said currently selected portion, said string of bits contains said search pattern.

Claim 36

The apparatus of claim 30, wherein said plurality of instructions further embody logic for said operating on the bits of said currently selected portion in parallel to determine if said currently selected portion contains any of said first set of bit patterns by: comparing at least a first pattern of said first set of bit patterns to said currently selected portion.

Claim 37

The apparatus of claim 30, wherein said plurality of instructions further embody logic for said operating on the bits of said currently selected portion in parallel to determine if said currently selected portion contains any of said first set of bit patterns by: comparing at least a first masked pattern of a first set of masked bit patterns to said currently selected portion, wherein each masked bit pattern in said first set of masked bit patterns represents a plurality of bit patterns in said first set of bit patterns.

Claim 38

The apparatus of claim 33, wherein said plurality of instructions further embody logic for said selecting a portion of said string of bits as a currently selected portion by: A1) selecting a location in said string of bits as a currently selected location; and A2) selecting said first number of consecutive bits from said string of bits starting at said currently selected location as said currently selected portion; and wherein said plurality of instructions further embody logic for: F) performing the following steps if said altering in step E was performed: F1) selecting said first number of consecutive bits from said string of bits starting at said currently selected location as a currently selected portion; F2) selecting a second set of bit patterns based on one of said first set of masked bit patterns determined in step C to be contained in said currently selected portion; F3) determining if said currently selected portion contains any of said second set of bit patterns; F4) determining if said string of bits contains said search pattern based on whether said currently selected portion contains any of said second set of bit patterns; and F5) altering said string of bits in a pre-defined manner if it was determined said string of bits contains said search pattern.

Claim 39

The apparatus of claim 34, wherein said plurality of instructions further embody logic for said altering said string of bits in a pre-defined manner by: comparing at least a first masked occurrence pattern of a second set of masked bit patterns to said currently selected portion, wherein each masked bit pattern in said first set of masked bit patterns represents a plurality of bit patterns in said second set of bit patterns.

Claim 40

The apparatus of claim 30, wherein said plurality of instructions further embody logic for said selecting said first set of bit patterns by: B1) determining if said currently selected portion contains an exclusion pattern; and B2) selecting said first set of bit patterns based on said search pattern, those bits of said string of bits immediately preceding said currently selected portion, and whether said currently selected portion contains said exclusion pattern.

Claim 41

The apparatus of claim 36, wherein said exclusion pattern is such that at least a first bit pattern which would indicate an occurrence of said search pattern in said string of bits if contained in said currently selected portion cannot be contained in said currently selected portion if said exclusion pattern is contained in said currently selected portion.

Claim 42

The apparatus of claim 30, wherein said plurality of instructions further embody logic for: E) altering said string of bits in a pre-defined manner if it was determined said string of bits contains said search pattern.

Claim 43

The apparatus of claim 38, wherein said altering said string of bits in a pre-defined manner in step E further comprises the steps of: E1) determining if each occurence of said search pattern determined to be contained in said string of bits in step C is part of an occurence of said frame delimiter, and E2) removing a bit from said string of bits after each occurence of said search pattern determined to be contained in said string of bits in step C which was determined not to be an occurence of said frame delimiter.

Claim 44

The apparatus of claim 38, wherein said plurality of instructions further embody logic for said altering said string of bits in a pre-defined manner by inserting a bit into said string of bits after said search pattern if said string of bits is to be transmitted.

Claim 45

The apparatus of claim 40, wherein said plurality of instructions further embody logic for: A1) selecting a location in said string of bits as a currently selected location; and A2) selecting said first number of consecutive bits from said string of bits starting at said currently selected location as said currently selected portion; and wherein said plurality of instructions further embody logic for: F) repeating steps A through E on an unprocessed remainder of said string of bits, wherein at least said first number of consecutive bits starting at said currently selected location is now a processed portion of said string of bits.

Claim 46

The apparatus of claim 41 wherein said plurality of instructions further embody logic for: transmitting in a frame said processed portions of said string of bits.

Claim 47

A computer system for recognizing a search pattern in an input string of bits, said computer system comprising: a first processor; a bus coupled to said first processor; a modern coupled to said bus for communication, said modem including: a second processor for executing instructions during operation, and a storage device coupled to said second processor storing a plurality of instructions, said plurality of instructions embodying logic for: A) selecting a first number of consecutive bits from said string of bits as a currently selected portion; B) selecting a first set of occurrence patterns based on said search pattern and those bits of said string of bits immediately preceding said currently selected portion; C) operating on the bits of said currently selected portion in parallel to determine if said currently selected portion contains any of said first set of occurrence patterns; and D) determining if said string of bits contains said search pattern based on whether said currently selected portion contains any of said first set of occurence patterns.

Claim 48

A computer system for recognizing a search pattern in an input string of bits, said computer system comprising: a first processor; a bus coupled to said first processor; a modern coupled to said bus for communication, said modem including: a second processor for executing instructions during operation, and a storage device coupled to said second processor storing a plurality of instructions, said plurality of instructions embodying logic for: A) selecting a first number of consecutive bits from said string of bits as a currently selected portion; B) selecting a first set of occurrence patterns based on said search pattern and those bits of said string of bits immediately preceding said currently selected portion; C) operating on the bits of said currently selected portion in parallel to determine if said currently selected portion contains any of said first set of occurrence patterns; and D) determining if said string of bits contains said search pattern based on whether said currently selected portion contains any of said first set of occurence patterns.

Claim 49

The computer system of claim 43, wherein said plurality of instructions further embody logic for said selecting said first set of occurrence patterns by: B1) determining how much of said search pattern is contained in those bits of said string of bits immediately preceding said currently selected portion; and B2) selecting said first set of occurrence patterns such that if any of said first set of occurrence patterns are contained in said currently selected portion, said string of bits contains said search pattern.

Claim 50

The computer system of claim 43, wherein said plurality of instructions further embody logic for said operating on the bits of said currently selected portion in parallel to determine if said currently selected portion contains any of said first set of occurence patterns by: comparing at least a first occurence pattern of said first set of occurence patterns to said currently selected portion.

Claim 51

The computer system of claim 43, wherein said plurality of instructions further embody logic for said operating on the bits of said currently selected portion in parallel to determine if said currently selected portion contains any of said first set of occurrence patterns by: comparing at least a first masked occurrence pattern of a first set of masked occurrence patterns to said currently selected portion, wherein each masked occurrence pattern in said first set of masked occurrence patterns represents a plurality of occurrence patterns in said first set of occurrence patterns.

Claim 52

The computer system of claim 43, wherein said plurality of instructions further embody logic for said selecting said first set of occurrence patterns by: B1) determining if said currently selected portion contains an exclusion pattern; and B2) selecting said first set of occurrence patterns based on said search pattern, those bits of said string of bits immediately preceding said currently selected portion, and whether said currently selected portion contains said exclusion pattern.

Claim 53

The computer system of claim 43, wherein said exclusion pattern is such that at least a first occurrence pattern which would indicate an occurrence of said search pattern in said string of bits if contained in said currently selected portion cannot be contained in said currently selected portion if said exclusion pattern is contained in said currently selected portion.

Claim 54

The computer system of claim 43, wherein said plurality of instructions further embody logic for: E) altering said string of bits in a pre-defined manner if it was determined said string of bits contains said search pattern.