Semiconductor associative memory

Details Semiconductor associative memory Semiconductor associative memory

2002-01-18

2004-02-17

Elms, Richard (Department: 2824)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S189070, C365S154000, C365S156000

Reexamination Certificate

active

06693815

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATIONS
This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 2001-011760, filed Jan. 19, 2001, the entire contents of which are incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an associative memory and more particularly to a small-area, associative memory with fast parallel minimum-distance-search capability, used for artificial intelligence systems, data-bank systems, mobile network terminals and the like.
2. Description of the Related Art
Conventionally, an associative memory is activated by searching for the “best match data” between an input data composed of W units, each k bits long, and R reference data, each also composed of W units, each k bits long. The associative memory has a function of generating comparative bits to clarify the best match data by comparing stored reference data with input data, also called search data or match data, input from outside.
The “best match data” is defined as data with the smallest measure, which is of distance here. As the measure of distance, conventionally, the Hamming distance and Manhattan distance are best known. The Hamming distance is used for data strings, voice patterns, black-and-white pictures and the like, and the Manhattan distance is used for color pictures, gray-scale pictures and the like.
If the bit length of a unit of input data or reference data is 1 bit (k=1), the Hamming distance is applied. That is, the Hamming distance is defined as the number of bits that are different from each other in two items of data to be compared.
On the other hand, if the input data is composed of units of coded numbers such as X
in
={x
1
, x
2
, x
3
, . . . x
W
}, Y
ref
={y
1
, y
2
, y
3
, . . . y
W
}, the Manhattan distance is applied. At this time, the Manhattan distance between two items of data is defined as follows.
D
M
⁢
 
⁢
a
⁢
 
⁢
n
⁢
 
⁢
h
≡
∑
i
=
1
W
|
x
i
-
y
i
|
(
1
)
Basically, the following methods have been used to search for the best matching of most similar data (hereinafter referred to as the winner) according to conventional art. That is,
(a) Use of an analog neural network (H. P. Graf and L. D. Jackel, “Analog Electronic Neural Network Circuits”, IEEE Circuits and Device Mag., vol. 5, p. 44, 1989),
(b) Use of plural SRAMs and separate digital search circuits (A. Nakada et al., “A Fully Parallel Vector-Quantization Processor for Real-Time Motion Picture Compression”, IEEE Journ. Solid-State Circuits, vol. 34, pp. 822-830, 1999; T. Nozawa et al., “A Parallel Vector Quantization Processor Eliminating Redundant Calculations for Real-time Motion Picture Compression”, ISSCC Digest of Tech. Papers, pp. 234-235, 2000),
(C) Use of an analog winner-take-all circuit (Analog Winner-Take-All circuit; WTA circuit) employing MOS transistors used as source-followers (S. M. S. Jalalenddine and L. G. Johnson, “Associative IC Memories with Relational Search and Nearest-Match Capabilities”, IEEE Journ. Solid-State Circuits, vol. 27, pp. 892-900, 1992).
However, these methods have the following problems. That is, because the circuit complexity of the search circuit increases in order of R
2
(O(R
2
)) or in order of R*W (O(R*W)), the occupied area in a chip increases (see the documents in (a) and (b), above) and furthermore the time necessary for searching is increased (about 1 &mgr;s). Another problem is that the searchable range only extends to a small W (see the document in (c), above).
Conventionally, in an artificial intelligence system using associative memory, hardware having a high area efficiency is almost impossible to achieve; therefore, generally, artificial intelligence systems are constructed on high-performance computers using complicated software.
There have not yet been any mobile terminals capable of video communication. The reason is that if video data-compression technologies such as MPEG are employed, a tremendous amount of hardware is needed in the sender/receiver terminal. With an associative memory, a data compression method based on a code book can be used (A. Nakada et al., “A Fully Parallel Vector-Quantization Processor for Real-Time Motion Picture Compression”, IEEE Journ. Solid-State Circuits, vol. 34, pp. 822-830, 1999).
According to this method, first, a data stream is divided into blocks of a specified number of bits and next, best match blocks, which are those most similar to the ones in the code book, are determined using the associative memory. In the final stage, only the identifier of a block is transmitted to the receiver. The data transmitted in this way is reconstructed according to the code book. Therefore, the receiver can be constructed with a very simple structure.
This technology is suitable for transmission of video signals and is called vector quantization. The associative memory of the present invention is advantageously used in fields of bandwidth compression of video signal in mobile communication terminals, artificial intelligence systems, data bank systems and the like with plural compact chips or a single compact chip.
As described above, the problem with the conventional winner search method is that if the unit number W of input data or the number R of reference data increases, the circuit complexity of the search circuit strongly increases proportionally to R
2
so that the required chip area strongly increase and searching takes longer.
The present invention has been developed to solve the above problems and, therefore, an object of the present invention is to provide an associative memory capable of fast parallel searching with a search circuit implemented on a small chip area by avoiding an increase in the number of circuits proportionally to R
2
and reducing this increase to be proportional to R. Such an associative memory is intended to be applied to the fields of bandwidth compression of video signals in mobile communication, including mobile network terminals, artificial intelligence and the like.
BRIEF SUMMARY OF THE INVENTION
To achieve the above-described objective according to the present invention, there is an associative memory with a fast parallel minimum-distance-search capability, which is formed of a CMOS circuit, realizing fast search with a small chip area by avoiding a strong increase in the number of circuits even if the unit number W of the input data or the number R of the reference data is large.
Specifically, the present invention provides a semiconductor associative memory including a memory array comprising: unit storage circuits each having k bits arranged in R rows of W columns (R, W, k are natural numbers); unit comparison circuits arranged in R rows of W columns for comparing input data of W×k bits with reference data of W k-bit units stored in the unit storage circuits at every k bit; weighted word comparators for weighting each bit of output data output from each row of the unit comparison circuit; row decoders of R rows; and column decoders of W×k columns.
Preferably, the unit in the memory array is composed of binary-coded data and the bit number k of the unit is k=1 in the case where the Hamming distance is used to search for reference data matching with the input data and k>1 in the case where the Manhattan distance is used.
Further, preferably, in the case where the retrieval of the reference data based on the input data is carried out using the Hamming distance, the unit storage circuit is composed of an SRAM memory cell, the unit comparison circuit comprises a 2-input EXOR circuit or a 2-input EXNOR circuit each connected to the complementary output portion of a latch circuit constituting the SRAM memory cell, the weighted word comparator including a transistor, or two transistors connected to each other in series connected to the 2-input EXOR circuit or EXNOR circuit.
Further, preferably, in the case where retrieval of the reference data based on the input data is carri

Affiliated with

Also associated with

Rating

Semiconductor associative memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Semiconductor associative memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Semiconductor associative memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3298149