US5319762A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Associative memory capable of matching a variable indicator in one string of characters with a portion of another string
Assignee: F Poszat HU LLC
•
Filing: 1990-09-07
•
Granted: 1994-06-07
•
Expires: 2010-09-07
Abstract
Abstract An associative memory that finds the location of at least one string of characters in the associative memory that matches a string of characters presented sequentially as an input to the associative memory. The string of characters in the associative memory, the input string of characters, or both may include a specially marked characters, or set of characters, that acts as a "variable indicator." The specially marked character, or set of characters, will "match" a portion of the other string. A flag is set in the associative memory at either the starting locations or the ending locations of the matching strings. Flags are provided only at locations of stored matching strings of characters found within a selected addressable area or areas. Each flag can be moved from a first byte to a second byte in the associative memory that has a predetermined location relative to the first byte. A selection circuit selects one of the matching stored strings of characters by enabling a test signal which selects one of the flags to propagate through the associative memory circuit in a daisy-chain manner. The daisy-chain path is segmented in order to decrease the propagation time of the test signal. A summation circuit, useful in neural network applications, adds a number presented as at least one input byte to the associative memory to a number stored as at least one byte in the associative memory at the location of a stored string of characters that matches the input string.
Inventors
- 👤 Rollin P. Mayer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 23:33
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/02; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90339; G06N; G06N3/00; G06N3/02; G06N3/04; G06N3/044; G06N3/06; G06N3/063; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
183 words
An electrical circuit comprising: a memory comprising a plurality of storage bytes for storing characters, circuitry for receiving an input string of characters presented as an input to the electrical circuit, and for simultaneously comparing a plurality of the characters stored in the storage bytes with a first characters in the input string to find at least one character stored in the storage bytes that matches the first character in the input string, string-associative means for finding a location in the memory of at least one stored string of characters that matches the input string of characters by enabling at least one string signal to propagate through the storage bytes, the string signal continuing to propagate as long as consecutive stored characters match consecutive input characters, and variable control means for matching a variable indicator contained in one of said input and stored strings of characters with a portion of another of said input and stored strings by enabling the string signal to propagate through at least one storage byte that stores a character differing from a corresponding character in the input string.
Claim 2
Dependent Claim
183 words
An electrical circuit comprising: a memory comprising a plurality of storage bytes for storing characters, circuitry for receiving an input string of characters presented as an input to the electrical circuit, and for simultaneously comparing a plurality of the characters stored in the storage bytes with a first characters in the input string to find at least one character stored in the storage bytes that matches the first character in the input string, string-associative means for finding a location in the memory of at least one stored string of characters that matches the input string of characters by enabling at least one string signal to propagate through the storage bytes, the string signal continuing to propagate as long as consecutive stored characters match consecutive input characters, and variable control means for matching a variable indicator contained in one of said input and stored strings of characters with a portion of another of said input and stored strings by enabling the string signal to propagate through at least one storage byte that stores a character differing from a corresponding character in the input string.
Claim 3
Dependent Claim
43 words
The electrical circuit of claim 1, further comprising flag setting means for associating a flag with the stored string of characters that matches the input string of characters, the flag being set at the starting location of the stored string of matching characters.
Claim 4
Dependent Claim
52 words
The electrical circuit of claim 1, further comprising summation circuitry for adding a number presented as at least one input byte to the electrical circuit to a number stored as at least one byte at the location in the memory of the string of characters that matches the input string of characters.
Claim 5
Dependent Claim
201 words
The electrical circuit of claim 1, wherein said string-associative means is configured for finding the location in the memory of a plurality of stored strings of characters that match the input string of characters, said electrical circuit further comprises a plurality of flag circuits, each associated with a respective storage byte, for marking with flags the locations in the memory of the plurality of stored strings of characters that match the input string of characters, and said electrical circuit further comprises selection means for selecting one of the plurality of stored characters marked with flag by enabling a test signal for testing the flag circuits to propagate in a daisy-chain manner through a plurality of first-level chains of gates, each gate in each first-level chain receiving as inputs the propagating test signal and an output from a flag circuit, and by enabling other test signals to propagate in a daisy-chain manner through each of at least one higher-level chain of gates, each gate in each higher-level chain receiving as inputs the propagating test signal and a single output of a lower-level chain of gates that indicates whether a flag is present in any of the flag circuits in the lower-level chain.
Claim 6
Dependent Claim
128 words
The electrical circuit of claim 1, further comprising a plurality of flag circuits, each associated with a respective storage byte, for marking with flags the locations in the memory of the plurality of stored strings of characters that match the input string of characters, selection means for selecting one of a plurality of flags, the selection means producing a selected flag signal at a location in the memory of the selected flag, and flag clearing means for receiving a clear selected flag signal, and for gating the clear selected flag signal with the selected flag signal at the location in the memory of the selected flag, to produce a signal for clearing the selected flag, in order to permit another flag to be selected by the selection means.
Claim 7
Dependent Claim
116 words
The electrical circuit of claim 1, further comprising: flagging means for flagging the location in the memory of the stored matching string of characters, and address readout means for producing as an output an address of the flag marking the stored matching string of characters in the memory, the address readout means comprising a row address encoder for receiving a signal from each row of bytes indicating whether the flag is present in the row and for encoding the signals into a row address and a column address encoder for receiving a signal from each column of bytes indicating whether the flag is present in the column and for encoding the signals into a column address.
Claim 8
Dependent Claim
27 words
The electrical circuit of claim 6 wherein the flagging means flags the location in the memory of the stored string of matching characters by setting a flag.
Claim 9
Dependent Claim
45 words
The electrical circuit of claim 6 wherein the flagging means flags the location in the memory of the stored string of matching characters by selecting one of a plurality of existing flags marking the locations of a respective plurality of stored strings of matching characters.
Claim 10
Dependent Claim
41 words
The electrical circuit of claim 1, further comprising: flag setting means for associating a flag with the stored string of characters that matches the input string of characters, and indexing means for moving the flag a predetermined increment in the memory.
Claim 11
Dependent Claim
51 words
The electrical circuit of claim 9, wherein the flag setting means associates a plurality of flags with a corresponding plurality of stored strings of characters that match the input string of characters, and the indexing means moves a selected one of the plurality of flags a predetermined increment in the memory.
Claim 12
Dependent Claim
49 words
The electrical circuit of claim 9, wherein the flag setting means associates a plurality of flags with a corresponding plurality of stored strings of characters that match the input string of characters, and the indexing means moves all of the plurality of flags a predetermined increment in the memory.
Claim 13
Dependent Claim
20 words
The electrical circuit of claim 9 wherein the indexing means moves the flag to an adjacent byte in the memory.
Claim 14
Dependent Claim
50 words
The electrical circuit of claim 1, wherein said variable control means is a stored variable control means for matching a variable indicator contained in the stored string of characters that matches the input string of characters with a portion of the input string regardless of the contents of the portion.
Claim 15
Dependent Claim
28 words
The electrical circuit of claim 13, wherein the variable indicator comprises more than one character of the stored string of characters that matches the input string of characters.
Claim 16
Dependent Claim
48 words
The electrical circuit of claim 13, wherein the stored variable control means comprises means for matching more than one variable indicator in the stored string of characters that matches the input string of characters with corresponding portions of the input string regardless of the contents of the portions.
Claim 17
Dependent Claim
48 words
The electrical circuit of claim 13, wherein the stored variable control means comprises means for matching the variable indicator with a corresponding portion of the input string regardless of where the variable indicator is located within the stored string of characters that matches the input string of characters.
Claim 18
Dependent Claim
70 words
The electrical circuit of claim 13, wherein the string-associative means comprises a plurality of flag flip-flops, each associate with a respective storage byte, for marking locations in the memory at which a stored character matches a corresponding characters in the input string, and each flag flip-flop functions also as a variable flip-flop for marking locations in the memory at which a variable indicator matches a portion of the input string.
Claim 19
Dependent Claim
33 words
The electrical circuit of claim 13, wherein the stored variable control means matches the variable indicator with the portion of the input string only if the portion is at least one byte long.
Claim 20
Dependent Claim
49 words
The electrical circuit of claim 13, wherein the stored variable control means comprises means for ensuring that the stored string of characters is matched with the input string of characters even if the input string of characters has no bytes corresponding to the variable contained in the associative memory.
Claim 21
Dependent Claim
31 words
The electrical circuit of claim 13, wherein the stored variable control means matches the variable indicator with the portion of the input string only if the portion contains exactly one byte.
Claim 22
Dependent Claim
61 words
The electrical circuit of claim 13, wherein the variable indicator indicates to the stored variable control means a minimum length of the portion of the input string with which the variable indicator may match, and the stored variable control means matches the variable indicator with the portion of the input string only if the portion is at least the minimum length.
Claim 23
Dependent Claim
61 words
The electrical circuit of claim 13, wherein the variable indicator indicates to the stored variable control means a maximum length of the portion of the input string with which the variable indicator may match, and the stored variable control means matches the variable indicator with the portion of the input string only if the portion does not exceed the maximum length.
Claim 24
Dependent Claim
43 words
The electrical circuit of claim 1, wherein said variable control means is an input variable control means for matching a portion of the stored string of characters with a variable indicator contained in the input string regardless of the contents of the portion.
Claim 25
Dependent Claim
19 words
The electrical circuit of claim 23, wherein the variable indicator comprises more than one character of the input string.
Claim 26
Dependent Claim
45 words
The electrical circuit of claim 23, wherein the input variable control means is capable of matching more than one said portion of the stored string of characters with corresponding said variable indicators in the input string of characters regardless of the contents of the portions.
Claim 27
Dependent Claim
39 words
The electrical circuit of claim 23, wherein the input variable control means is capable of matching the portion of the stored string with the corresponding variable indicator regardless of where the variable indicator is located within the input string.
Claim 28
Dependent Claim
33 words
The electrical circuit of claim 23, wherein the input variable control means matches the portion of the stored string with the variable indicator only if the portion is at least one byte long.
Claim 29
Dependent Claim
32 words
The electrical circuit of claim 23, wherein the input variable control means matches the portion of the stored string with the variable indicator only if the portion contains zero or more bytes.
Claim 30
Dependent Claim
31 words
The electrical circuit of claim 23, wherein the input variable control means matches the portion of the stored string with the variable indicator only if the portion contains exactly one byte.
Claim 31
Dependent Claim
61 words
The electrical circuit of claim 23, wherein the variable indicator indicates to the input variable control means a minimum length of the portion of the stored string with which the variable indicator may match, and the input variable control means matches the portion of the stored string with the variable indicator only if the portion is at least the minimum length.
Claim 32
Dependent Claim
61 words
The electrical circuit of claim 23, wherein the variable indicator indicates to the input variable control means a maximum length of the portion of the stored string with which the variable indicator may match, and the input variable control means matches the portion of the stored string with the variable indicator only if the portion does not exceed the maximum length.
Claim 33
Dependent Claim
38 words
The electrical circuit of claim 23 further comprising stored variable control means for matching a portion of the input string of characters with a variable indicator contained in the stored string regardless of the contents of the portion.
Claim 34
Dependent Claim
73 words
The electrical circuit of claim 1, wherein said variable control means is a numerical variable control means for matching at least a portion of the stored string of characters with a number presented as a string of one or more input bytes if the portion of the stored string of characters represents a number that bears a predetermined mathematical relationship to the number presented as the string of one or more input bytes.
Claim 35
Dependent Claim
66 words
The electrical circuit of claim 33 wherein, if a stored character in the stored string is not within the portion of the stored string that the numerical variable control means matches with the number presented as a string of one or more input bytes, the string-associative means matches the stored character with an input character only if the stored character is identical to the input character.
Claim 36
Dependent Claim
77 words
The electrical circuit of claim 1, wherein said string-associative means is configured for finding the location in the memory of a plurality of stored strings of characters that match the input string of characters, said electrical circuit further comprises selection means for selecting an addressable area of the memory, and said electrical circuit further comprises flag means for providing flags in the memory only at locations of stored matching strings of characters found within the addressable area.
Claim 37
Dependent Claim
47 words
The electrical circuit of claim 35, wherein the selection means is capable of selecting a plurality of addressable areas of the memory, and the flag means provides flags only at locations of stored strings of characters found within any of the plurality of addressable areas of memory.
Claim 38
Dependent Claim
47 words
The electrical circuit of claim 35, wherein the flag means comprises: flag setting means for setting flags in the memory at locations of stored matching strings of characters, and flag clearing means for clearing flags outside of the addressable area of memory selected by the selection means.
Claim 39
Dependent Claim
95 words
The electrical circuit of claim 37, wherein the means for finding the location of a plurality of stored strings of characters that match the input string of characters finds the location of stored matching strings of characters even if the stored matching strings of characters are located outside of the addressable area of memory, and the flag setting means associates a flag with each stored matching strings of characters found within the memory even if the stored matching string of characters is located outside of the addressable area of memory selected by the selection means.
Claim 40
Dependent Claim
26 words
The electrical circuit of claim 37, wherein the flag clearing means clears all flags prior to the addressable area of memory selected by the selection means.
Claim 41
Dependent Claim
25 words
The electrical circuit of claim 37, wherein the flag clearing means clears all flags following the addressable area of memory selected by the selection means.
Claim 42
Dependent Claim
52 words
The electrical circuit of claim 37, wherein the memory is divided into subareas of memory organized into hierarchical levels, and at each hierarchical level, the flag clearing means clears flags within subareas of memory outside of any subarea within which the addressable area of memory selected by the selection means is located.
Claim 43
Dependent Claim
39 words
The electrical circuit of claim 41 wherein, at each hierarchical level, the flag clearing means clears flags only in subareas of memory preceding any subarea within which the addressable area of memory selected by the selection means is located.
Claim 44
Dependent Claim
39 words
The electrical circuit of claim 41 wherein, at each hierarchical level, the flag clearing means clears flags only in subareas of memory following any subarea within which the addressable area of memory selected by the selection means is located.
Claim 45
Dependent Claim
188 words
An electrical circuit comprising: a memory comprising a plurality of storage bytes for storing characters, circuitry arranged to receive an input string of characters presented as an input to the electrical circuit, and to simultaneously compare a plurality of the characters stored in the storage bytes with a first character in the input string to find at least one character stored in the storage bytes that matches the first character in the input string, a string-associative circuit arranged to find a location in the memory of at least one stored string of characters that matches the input string of characters by enabling at least one string signal to propagate through the storage bytes, the string signal continuing to propagate as long as consecutive stored characters match consecutive input characters, and a variable control circuit arranged to match a variable indicator contained in one of said input and stored strings of characters with a portion of another of said input and stored strings by enabling the string signal to propagate through at least one storage byte that stores a character differing from a corresponding character in the input string.
Claim 46
Dependent Claim
188 words
An electrical circuit comprising: a memory comprising a plurality of storage bytes for storing characters, circuitry arranged to receive an input string of characters presented as an input to the electrical circuit, and to simultaneously compare a plurality of the characters stored in the storage bytes with a first character in the input string to find at least one character stored in the storage bytes that matches the first character in the input string, a string-associative circuit arranged to find a location in the memory of at least one stored string of characters that matches the input string of characters by enabling at least one string signal to propagate through the storage bytes, the string signal continuing to propagate as long as consecutive stored characters match consecutive input characters, and a variable control circuit arranged to match a variable indicator contained in one of said input and stored strings of characters with a portion of another of said input and stored strings by enabling the string signal to propagate through at least one storage byte that stores a character differing from a corresponding character in the input string.
References Cited (Backward Citations)
US4118788A
Cited
US4296475A
Cited
US4598385A
Cited
US4575818A
Cited
US5122984A
Cited
US4958377A
Cited
US4852059A
Cited
US5175860A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-06-06 | 1997-12-06 | 1998-06-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-06-06 | 2001-12-06 | 2002-06-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-06-06 | 2005-12-06 | 2006-06-07 | $7700.00 | Window Closed / Lapsed |