Back to results
US 8,028,125 B2Granted
Content-addressable memories and state machines for performing three-byte matches and for providing error protection
AssigneeComtech EF Data Corp.
InventorsPatrick A. Owsley, Brian Banister, Tom Hansen, Jason Franklin, Nathan Hungerford, Seth Sjoholm, Ed Coulter
Life of this patent
Estimating the term…
Abstract
A method and system for detecting matching strings in a string of characters utilizing content addressable memory is disclosed.
Claims33
A method comprising:
- detecting a match of sequential input characters with sequential characters stored in memory locations of a content addressable memory (CAM);
- detecting a primary match of N or more sequential characters;
- tracking a length of the primary match;
- tracking a potential string match in progress, wherein the potential string match comprises two to N−1 sequential input characters matching two to N−1 sequential characters stored in the CAM;
- tracking a plurality of potential string matches that transition to a primary match simultaneously until the longest match is determined;
- terminating a primary match when a next sequential character stored in the CAM does not match the current input character;
- resetting the plurality of potential string matches while tracking the primary match;
- and
- outputting an address of a longest determined match when all primary matches have terminated.
6 more elements
A method of detecting matching strings in a string of characters, wherein a character can be an predetermined number of bits, the method comprising:
- storing the string of characters in a content addressable memory, wherein an individual memory cell in the content addressable memory stores a character of the string of characters,
- comparing input data to the characters stored in the individual memory cells to determine if the input data matches the character stored in the individual memory cell,
- defining a plurality of discrete states in a plurality of state machines, the plurality of discrete states comprising a write state, a one-byte match state, a two-byte match state, and a three-byte match state,
- transitioning between states in a plurality of concurrently operating state machines based on the present state of the state machine and the presence of a running match,
- wherein the transitioning comprises:
- entering the write state in each individual state machine in response to a character being stored in an individual memory cell,
- entering the one-byte match state in each individual state machine when starting in the write state and when there is a one-byte match between the input data and a character stored in a first memory cell,
- entering the two-byte match state in each individual state machine when starting in the one-byte match state and when there is a second match between the input data and a second character stored in a second memory cell, and
- entering the three-byte match state in each individual state machine when starting in the two-byte match state and when there is a third match between the input data and a third character stored in the third memory cell;
- outputting a primary match signal that indicates a three-byte match when the state machine is in the three-byte match state;
- receiving signals representing sequences of matched characters;
- and
- outputting the matched characters.
10 more elements
A system for detecting matching strings of characters in a larger string of characters, wherein a character can be a predetermined number of bits, the system comprising:
- a string match module, wherein the string match module comprises:
- a content addressable memory, wherein the content addressable memory comprises a plurality of individual memory cells, a plurality of compare circuits, and a plurality of individual state machines, each individual state machine operating concurrently,
- wherein each individual memory cell is logically connected to an individual compare circuit,
- wherein the plurality of individual memory cells stores a string of characters,
- wherein each individual memory cell stores a character of the string of characters,
- wherein each individual compare circuit is logically connected to an individual state machine,
- wherein each individual state machine is associated with an individual memory cell and with an individual compare circuit,
- wherein each individual compare circuit outputs to the associated state machines an intermediate match signal that indicates whether the input data matches the character stored in the associated memory cell,
- wherein each of the plurality of individual state machines comprises a plurality of discrete states, the plurality of discrete states comprising a write state, a one-byte match state, a two-byte match state, and a three-byte match state;
- wherein each individual state machine enters the write state in response to a character being stored in the memory cell associated with the individual state machine,
- wherein each individual state machine enters the one-byte match state when starting in the write state and when there is a one-byte match between the input data and a first character stored in a first memory cell,
- wherein each individual state machine enters the two-byte match state when starting in the one-byte match state and when there is a second match between the input data and a second character stored in a second memory cell,
- wherein each individual state machine enters the three-byte match state when starting in the two-byte match state and when there is a third match between the input data and a third character stored in the third memory cell,
- wherein each individual state machine outputs a primary match signal that indicates a three-byte match when the state machine is in the three-byte match state;
- and
- an output module, wherein sequences of matched data are output.
13 more elements
Dependencies are inferred from the claim text.