SEARCH MEMORY

• US 3,742,460 A
• Filed: 12/20/1971
• Issued: 06/26/1973
• Est. Priority Date: 12/20/1971
• Status: Expired due to Term

• Current Assignee: Robert M. Englund
• Original Assignee: Robert M. Englund
• Inventors: Englund, Robert M.
• Primary Examiner(s): Zache, Raulfe B.
• Assistant Examiner(s): Vandenburg, John P.
• Application Number:
  US05/209,963
• Time in Patent Office: 554 Days
• Field of Search: 340/172.5,173AM
• US Class Current: 1/1
• CPC Class Codes: G11C 15/04 using semiconductor elements
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A Search memory organization using as the designator words, which words are the words that are stored in the Search memory and that are compared to the one search word held in the search register, words that are generated from blocks of data words is disclosed. Each of the (block) designator words includes two portions: a first common portion that includes the binary data that are common to all the data words of the block; and, a second word portion that includes the binary data that are not common to all the data words of the block. Thus, all the data words in each block are represented by only a single block designator word whereby only one block designator word need be searched for comparison to the one search word rather than all the data words of the block.

Claims

1. The method of performing a block search upon a plurality of data words, comprising:

assembling a plurality of data words, each of said data words comprising two portions of ordered bits;

a first common portion of ordered N-bits in length; and

, a second word portion of ordered W-bits in length;

generating a lesser plurality of block designator words from a greater plurality of said data words, each of said block designator words comprising;

a first common portion of ordered N-bits in length that includes binary data that are common to all the data words represented by said block designator word;

a second coded portion coded into a 1-of-C code of ordered Cbits in length, only one C-bit coded for identifying a separate one of all the data words that are represented by said block designator word;

storing in a search register a single search word comprising;

a first common portion of ordered N-bits in length; and

, a second word portion of ordered W-bits in length;

storing in a Search memory said plurality of block designator words;

encoding the ordered W-bits of the second word portion of said search word into an ordered 1-of-C code of C-bits in length;

coupling each separate one of the ordered N-bits of the common portion of said search word in said search register to each separate like-ordered one of the like-ordered N-bits of the common portion of the block designator words in said Search memory;

coupling each separate one of the ordered C-bits of said ordered 1-of-C code of the encoded portion of said search word to each separate like-ordered one of the like-ordered C-bits of said ordered 1-of-C code of the second coded portion of the block designator words in said Search memory;

comparing bit-by-bit each separate one of the like-ordered Nbits of the first common portion of the search word to each separate like-ordered one of the like-ordered N-bits of the first common portion of the block designator words in said Search memory;

comparing bit-by-bit each separate one of the like-ordered Cbits of the ordered 1-of-C code of the encoded portion of said search word to each separate like-ordered one of the ikeordered C-bits of the ordered 1-of-C code of the second coded portion of the block designator words in said Search memory;

generating match/mismatch signals indicating the results of said bit-by-bit comparison.

2. The method of claim 1 further comprising:

locking out the bit-by-bit comparison of the like-ordered C-bits of the ordered 1-of-C code of the encoded portion of said search word with the like-ordered C-bits of the ordered 1-of-C code of the encoded portion of any one of said block designator words in said Search memory if the bit-by-bit comparison of the like-ordered N-bits of the first common portion of said search word determines a mismatch of any one of the like-ordered N-bits of the first common portion of said one block designator word in said Search memory.

3. A block search processor, comprising:

a search register for storing a single search word comprising two portions of ordered bits;

a first common portion of ordered N-bits in length; and

, a second word portion of ordered W-bits in length;

encoder means for encoding the W-bits of the word portion of said search word into a 1-of-C code of ordered C-bits in length;

a Search memory for storing a plurality of block designator words, each block designator word associated with a block of data words and comprising two portions of ordered bits;

a first common portion of ordered N-bits in length that includes the binary data that is common to all the data words of the block; and

, a second word portion coded into a 1-of-C code of ordered C-bits in length, only one ordered C-bit coded for identifying a separate one of the data words of the block;

each separate block designator word having a separately associated Search memory output line for providing as outputs thereof match/mismatch signals that indicate the results of a bit-by-bit comparison of the ordered bits of said search word to the like-ordered bits of each of said block designator words;

means for coupling each separate one of the ordered N-bits of the common portion of said search word in said search register to each separate like-ordered one of the like-ordered N-bits of the common portion of the block designator words in said Search memory; and

, means for coupling each separate one of the ordered C-bits from said encoder means to each separate like-ordered one of the like-ordered C-bits of the coded portions of the block designator words in said Search memory.

4. The block search processor of claim 3 wherein:

each of the true of each of the ordered N-bits of the common portion of said search word in said search register and each of the complement of the like-ordered bits of the ordered N-bits of the common portion of each of said block designator words in said Search memory are coupled to a separately associated NAND gate and thence to the one associated block designator word Search memory output line;

each of the complement of each of the ordered N-bits of the common portion of said search word in said search register and each of the true of the like-ordered bits of the ordered N-bits of the common portion of each of said block designator words in said Search memory are coupled to a separately associated NAND gate and thence to the one associated block designator word Search memory output line;

only the true of each of the ordered C-bits from said encoder means and only the complement of each of the like-ordered bits of the ordered C-bits of the coded portion of each of said block designator words in said Search memory are coupled to a separately associated NAND gate and thence to the one associated block designator word Search memory output line.