 |
Claims  |
|
|
We claim:
1. A method for mapping operable homologous address locations in a
semiconductor memory device having faulty locations so as to enable such
semiconductor memory devices to be used, said method comprising:
organizing the semiconductor memory device as at least one memory block
having a plurality of memory banks to form an elementary information word;
identifying all operable homologous address locations of the memory banks
of the semiconductor memory device;
utilizing areas of the memory block having a limited number of faulty
locations by applying an error correction procedure implementing a
modified Reed-Solomon algorithm having a generator polynomial
g(x)=x.sup.4 +a.sup.201.x.sup.3 +a.sup.246.x.sup.2 +a.sup.201.x+1
by translating a data string in such a manner as to move an error always to
the first location of the data string;
detecting and correcting errors by logic test circuits;
establishing a map of the operable homologous address locations of the
memory banks;
storing the map of operable homologous address locations of the memory
banks in a non-volatile memory as data content respectively associated
with the memory bank, thereby forming a transcoding table of material
addresses in the non-volatile memory;
requesting access to a memory block identified by a sequential logical
address;
associating the sequential logical address of the memory block to a
material address of the non-volatile memory;
retrieving the data content of a selected material address from the
non-volatile memory; and
directly accessing the corresponding memory block enabled by the data
content retrieved from the non-volatile memory at the selected material
address.
2. A method as set forth in claim 1, wherein the data string includes data
coefficients and control byte coefficients;
said method further including coding the data string to maintain the data
coefficients separate from the control byte coefficients.
3. A method as set forth in claim 2, wherein coding of the data string is
accomplished in accordance with the relationship
c(x)=d(x)+t(x)
c.sub.1 =d.sub.1 i=n, n-k+1
c.sub.1 =t.sub.1 i=n-k, 1
t(x)=mod [x.sup.4.d(x), g(x)]
t.sup.r (x)=t.sup.r-1 (x)-t.sup.r-1 +x.sup.n-.eta. g(x) r=1, . . . 32,
wherein
c(x) is the coded data,
d(x) is the data included in the data string, and
t(x) is an error control.
4. A method as set forth in claim 3, further including decoding the data
string of a plurality of bytes to compute a syndrome S(x) in accordance
with the following relationships
S(x)=mod [a(x).V(x), g(x)]
S.sup.r (x)=g.sup.(r-1) (x)-S.sup.(r-1) 4g(x)-a(x).x.sup.r
r=1 . . . 36,
wherein V(x) is received data including coded data plus error correction.
5. A method as set forth in claim 1, wherein a supply voltage is provided
for the memory banks of the semiconductor memory device; further including
controlling voltage conditions relating to the supply voltage for the
memory banks and the voltage levels for input signals to the semiconductor
memory device during the mapping of the operable homologous address
locations of the memory banks.
6. A method as set forth in claim 1, wherein mapping of the operable
homologous address locations in the memory banks is carried out under
ambient room temperature conditions of the order of 25.degree. C. and
further under high temperature conditions of the order of 70.degree. C.
7. A semiconductor memory mapping system for use with a semiconductor
memory device having operable and faulty locations therein, wherein the
semiconductor memory device is organized as a plurality of memory blocks,
each memory block having a plurality of memory banks in order to form an
elementary information word, said memory mapping system comprising
means for organizing the operable and faulty locations in a memory block
into a plurality of byte sub-strings from an individual byte string of the
memory block, wherein each byte sub-string including a plurality of bytes
is accompanied by a plurality of control bytes, there being a total of 36
characters in a composite unit character string including 32 characters of
regular information and 4 characters for error control;
translation means operable upon a byte sub-string of regular characters and
error control characters for transposing a detected error in the character
string to the first location of the character string;
test control logic circuits for detecting an error located in the first
location of the translated 36 character string and for correcting the
error existing in the first location; and
said test control logic circuits being responsive to the identification of
a polynomial expression indicative of the presence of an error in a byte
string, the polynomial structure being in the form of a modified
Reed-Solomon algorithm with a generator polynomial in the form
g(x)=x.sup.4 +a.sup.201.x.sup.3 +a.sup.246.x.sup.2 +a.sup.201.x+1.
8.
8. A memory mapping system as set forth in claim 7, further including a
coder circuit for operating upon a respective 36-character string having
data coefficient locations and control byte coefficients to maintain the
data coefficient locations separate from the control byte coefficients in
the 36-character string in accordance with the following mathematical
relationships
c(x)=d(x)+t(x)
c.sub.i =d.sub.i i=n, n-k+1
c.sub.i =t.sub.i i=n-k, 1
t(x)=mod [x.sup.4.d(x),g(x)]
t.sup.r (x)=t.sup.r-1 (x)-t.sup.r-1 +x.sup.n-.eta. g(x) r=1, . . . 32,
wherein
c(x) is the coded data,
d(x) is the data included in the data string, and
t(x) is an error control.
9. A memory mapping system as set forth in claim 8, wherein said coder
circuit comprises a ladder network having four transversal arms and two
longitudinal legs forming opposite sides of the ladder network between
which the four transversal arms extend, said coder circuit including
a first 8-bit exclusive-OR logic circuit in one transversal arm of the
ladder network for receiving an input signal;
an output multiplexer circuit having first and second inputs, the first
input of said output multiplexer circuit receiving the input signal;
an AND logic gate circuit included in a first longitudinal leg forming one
side of the ladder network and having first and second inputs for
respectively receiving a first selection signal and the output of said
first exclusive-OR logic circuit;
respective 8-bit multiplier circuits provided in each of the remaining
three transversal arms of said ladder network;
a second longitudinal leg forming the other side of the ladder network
including four master-slave flip-flop circuits;
respective exclusive-OR logic circuits being disposed at nodes formed by
the remaining three transversal arms and the second longitudinal leg
forming the other side of said ladder network and alternating with said
master-slave flip-flop circuits in the second longitudinal leg of said
ladder network; and
the fourth flip-flop circuit disposed in the second longitudinal leg of
said ladder network being connected to the second input of said output
multiplexer circuit.
10. A memory mapping system as set forth in claim 7, further including a
decoder circuit for correcting errors within a syndrome of four bytes,
said decoder circuit including a first decoder block, a second decoder
block and a third decoder block connected in cascade;
a first memory block of a first in-first out data memory connected in
parallel with respect to said first decoder block;
a first exclusive-OR logic circuit connected to the output of said first
memory block and the output of said second decoder block;
a first correction block interposed in the connection between the output of
said second decoder block and said first exclusive-OR logic circuit;
a second memory block of a first in-first out memory;
the output of said first exclusive-OR logic circuit being connected to an
input of said third decoder block and to said second memory block;
a second exclusive-OR logic circuit having an input connected to the output
of said third decoder block and an input connected to the output of said
second memory block; and
a second correction block interposed in the connection between the output
of said third decoder block and an input of said second exclusive-OR logic
circuit.
11. A memory mapping system as set forth in claim 10, wherein said first
decoder block comprises:
a first set of four 8-bit multiplier circuits connected in parallel with
respect to each other for receiving an input signal;
four exclusive-OR logic circuits having inputs for respectively receiving
the output of a corresponding one of said four 8-bit multiplier circuits;
four master-slave flip-flop circuits respectively connected to the outputs
of a corresponding one of said four exclusive-OR logic circuits;
a second set of three 8-bit multiplier circuits connected in parallel with
respect to each other;
the output of the last one of said master-slave flip-flop circuits being
connected directly to the first one of said four exclusive-OR logic
circuits and to the remaining three exclusive-OR logic circuits via
corresponding ones of said second set of three 8-bit multipliers; and
a multiplexer circuit having respective inputs for receiving the outputs of
all of said master-slave flip-flop circuits.
12. A memory mapping system as set forth in claim 10, wherein said second
decoder block comprises:
a first decoder block;
a set of identical decoder blocks and a further decoder block connected in
parallel with respect to each other and to the output of said second
decoder block;
a selection and correction block for receiving the outputs from said set of
identical decoder blocks and said further decoder block; and
an exclusive-OR logic circuit having inputs for respectively receiving the
output of said selection and correction block and a signal V(x) and
providing an output signal V'(x).
13. A memory mapping system as set forth in claim 12, wherein said first
decoder block of said second decoder block comprises:
a set of four double-state master-slave flip-flop circuits;
three exclusive-OR logic circuits, a corresponding one of said three
exclusive-OR logic circuits being interconnected between successive
double-state master-slave flip-flop circuits so as to provide alternating
double-state master-slave flip-flop circuits and an exclusive-OR logic
circuit;
the output of the last flip-flop circuit being connected directly to the
first flip-flop circuit;
three 8-bit multiplier circuits connected in parallel with respect to each
other and respectively connected to an input of a corresponding one of
said three exclusive-OR logic circuits;
the output of the last flip-flop circuit being respectively connected to
each of said three exclusive-OR logic circuits through the respective
8-bit multiplier circuit; and
each of said four flip-flop circuits being connected in parallel to receive
the input signal.
14. A memory mapping system as set forth in claim 12, wherein said set of
identical decoder blocks comprises
first and second sets of four input connections;
four exclusive-OR logic circuits coupled to said first set of four input
connections;
four 8-bit multiplier circuits connected to said second set of four input
connections and having respective outputs connected to a corresponding one
of said four exclusive-OR logic circuits;
four NOR gate circuits respectively connected to the outputs of said four
exclusive-OR logic circuits;
four AND logic gate circuits, a respective one of said four AND logic gate
circuits having an input connected to the output of a corresponding one of
said four NOR logic gate circuits; and
an OR logic gate circuit having inputs connected to the outputs of said
four AND logic gate circuits.
15. A memory mapping system as set forth in claim 12, wherein said further
decoder block comprises:
first, second, and third NOR logic gate circuits;
first, second, and third NAND logic gate circuits;
said first NOR logic gate circuit having an output connected to said first
and third NAND logic gate circuits;
said second NOR logic gate circuit having an output connected to said first
and second NAND logic gate circuits;
said third NOR logic gate circuit having an output connected to said second
and third NAND logic gate circuits;
a fourth NAND logic gate circuit having three inputs respectively connected
to the outputs of said first, second and third NAND logic gate circuits
and providing a signal TANA as an output; and
an AND logic gate output circuit having first and second inputs
respectively receiving the output signal TANA from said fourth NAND logic
gate circuit and a signal S.sub.4.sup.(r).
16. A memory mapping system as set forth in claim 10, wherein said third
decoder block comprises:
four exclusive-OR logic gate circuits;
four master-slave flip-flop circuits interconnected with said four
exclusive-OR logic circuits in an alternating sequence such that each of
said four exclusive-OR logic circuits is followed by a master-slave
flip-flop circuit;
four 8-bit multiplier circuits connected in parallel for receiving an input
signal V'(x) and having outputs connected to an input of a corresponding
one of said four exclusive-OR logic circuits;
a signal block for providing an output signal VERR having respective inputs
for receiving the outputs of said four master-slave flip-flop circuits;
a further exclusive-OR logic circuit having an output connected to the
first exclusive-OR logic circuit included in said four exclusive-OR logic
circuits and to inputs of the remaining three exclusive-OR logic circuits;
three 8-bit multiplier circuits interposed in the connection between the
output of said further exclusive-OR logic circuit and the inputs of said
remaining three exclusive-OR logic circuits; and
a final exclusive-OR logic circuit having an input connected to said signal
block for receiving the output signal VERR and a second input for
receiving a signal S'(x) and providing as an output a signal
c(x)=d(x)+t(x), wherein
S'(x) is a syndrome signal,
c(x) is the coded data,
d(x) is the data included in the data string, and
t(x) is an error control. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
This invention broadly relates to a method and to circuitry to enable use
of partially operative memories, that is memories having faulty locations,
as well as to an equipment for mass production of suitable mapped memory
blocks and for large scale exploitation of such circuit approach.
More particularly, a first aspect of this invention is related to focusing
a method to utilize semiconductor dynamic memories having manufacturing
defects, namely memories having faulty locations and as such not
utilizable in conventional applications.
In a second aspect, this invention relates to a circuit approach adapted to
exploitation of such a method and, therefore, adapted to detect and to
correct errors not detectable or not correctable by means of approaches
according to the prior art.
In a third aspect, this invention relates to an equipment for mapping or
practically testing single memory modules and for permanently storing the
final map in an OTP (One Time Programmable) memory, in order to enable use
of said memory modules in the circuitry and according to the method of
this invention
BACKGROUND OF THE INVENTION
Based upon statistical considerations involving the inherent defectiveness
of the silicon crystal lattice, the defectiveness induced by foreign
particles into the internal geometrical structures of the integrated
circuits and the defectiveness induced by swings of the production process
parameters into the internal structures of the integrated circuits, it can
be argued that the production efficiency of the memory circuits is a
monotonically decreasing function of the utilized silicon surface and in
effect of the number of memory calls utilized on a single chip.
A close analysis of the damages materially caused, however, shows that the
concerned memory devices have only a few rows or a few columns or a few
tens of not operative locations. Furthermore, such defects can be detected
only in very severe operation conditions, hardly simulatable without
particular test equipment. Anyway, notwithstanding this "scarce" defect
occurrence rate, said faulty memories cannot be employed in such
applications as memory banks for traditional computers.
Taking as a base the observation that, since the memories as presently used
can be considered as byte-oriented, the immediate solution to map all
faulty bytes cannot be adopted, because as a matter of fact, such a step
would require more information than one could subsequently store, this
invention is based upon the concept of developing a memory array adapted
to operate by blocks and then of retrieving memory blocks, rather than
memory bytes, thereby renouncing to develop a byte-oriented memory array,
fully compatible with the memory arrays conventionally utilized in present
computers.
Based upon this concept, therefore, a first step aimed at making such
memory devices utilizable provides for organizing them as memory banks in
order to form an elementary information "word", as it occurs in
conventional applications, and, thereafter, it provides for identifying
all not-faulty homologous address locations: this is carried out at
predetermined supply voltage and temperature conditions, as it will be
illustrated, and, since the obtained results generally are not coincident,
only those locations which have been positively tested are selected.
The result of this step, which is defined as "mapping", is stored in a
not-volatile OTP memory associated to the memory bank.
The external user, who desires to retrieve the data stored in the various
memory blocks, will have access to them by utilizing successive (logical)
memory addresses and will exploit to this aim the operation of this
not-volatile memory which will provide for transcoding the map stored
therein into the (material) addresses associated to the memory banks. In
other words, the access to the memory blocks is developed in two
successive stages. In a first stage, the intelligent portion of the
system, for instance a central processing unit (CPU), requests an access
to a block identified by a sequential (logical) address. At this point,
the system provides for associating the material address of a block of the
memory array to said logical address. This association or transcoding
operation is carried out by said not-volatile memory. As a matter of fact,
the user receives a logical address from outside, gets access to said
address of the OTP memory, retrieves the content thereof and utilizes it
for a direct and immediate access to the correspondent material block of
the memory array.
All above set forth steps, however, represent only a portion of the whole
method, because:
it can be reasonably believed that the originally faulty memory chips can
be degraded in the long run more easily than perfectly operating chips,
and therefore, they can subsequently have faulty locations even if such
locations may have originally proved as error-free,
troublesome variations of the number of error-free locations could be
encountered, which could cause manufacturing problems, because it is
necessary that each memory bank has a certain minimum number of error-free
locations.
According to the rule, as it has already observed, all faulty locations
should be identified, but this wold pose an excessively severe constraint.
Aiming at solving this problem and at providing a system adapted to be
operative also when some defectiveness exists and also aiming at enlarging
the number of locations wherein it is possible to store information, by
utilizing also regions featuring a limited defectiveness, a second stage
of the method according to this invention provides for applying techniques
designed for error correction (ECC).
More particularly, the developed technique is based upon the theory of the
cyclic polynomial codes and specially upon the REED-SOLOMON code with
generator polynomial
g(x)=x.sup.4 +a.sup.201 .multidot.x.sup.3 +a.sup.246 .multidot.x.sup.2
+a.sup.201 .multidot.x+1
The R-S code has been adopted, among other, because it is not
byte-oriented, but it is oriented on the base of a character string and it
can be realized by acting upon the code parameters with desired
redundancy. In the case of this invention, a redundancy of 12.5% has been
adopted.
Since the block as not considered is a 512 byte block (such number has been
adopted since it corresponds to that of a conventional peripheral
equipment) and since some difficulties would be encountered in embodying
such a function into a silicon wafer, it is proposed to divide the 512
byte string into various sub-strings and to determine the correction bytes
for each sub-string.
Clearly, this approach does not utilize the R-S code in optimal manner. In
fact, in a R-S type code, if a 512 byte string and 64 control bytes are
considered, up to 32 bytes can be corrected, regardless of the positions
they occupy in the string. On the contrary, thanks to the proposed
division, according to which 32 byte sub-strings plus 4 control bytes are
provided, only 2 bytes can be replaced in a 32 byte string and this can be
made only in the considered string and cannot be made in other strings.
The capability of the code is rather reduced, but the arrangement is found
to be satisfactory, with respect to the number of the logic gates that
should be implemented and to the whole necessary equipment.
Further details and advantages of this invention will be evident from the
following specification by referring to the enclosed drawing wherein the
preferred embodiment is shown by way of illustration and not by way of
limitation.
BRIEF DESCRIPTION OF THE DRAWINGS
In the drawings:
FIG. 1 shows a block diagram of a circuit to implement the use method for
partially faulty memories according to this invention;
FIGS. 2A and 2B respectively show as a separate block, including the
mathematics implemented therein, the circuit arrangement of a coder than
can be utilized for practical implementation of this invention;
FIG. 3 shows a block diagram, also including the mathematics implemented in
the various sections, of a decoder (1) that can be utilized for practical
implementation of this invention;
FIGS. 4A and 4B respectively show as a separate block, including the
mathematics implemented therein, the circuit arrangement of decoder (2)
included as a part of decoder (1) of FIG. 3;
FIG. 5 shows a block diagram, also including the mathematics implemented
therein, of decoder (3) included as a part of decoder (1) of FIG. 3;
FIGS. 6A and 6B respectively show as a separate block, including the
mathematics implemented therein, the circuit arrangement of decoder (4)
included as a part of decoder (3) of FIG. 5;
FIGS. 7A and 7B respectively show as a separate block, including the
mathematics implemented therein, the circuit arrangement of one of
decoders (5) included as a part of decoder 3 of FIG. 5;
FIGS. 8A and 8B respectively show as a separate block, including the
mathematics implemented therein, the circuit arrangement of decoder (6)
included as a part of decoder (3) of FIG. 5;
FIGS. 9A and 9B respectively show as a separate block, including the
mathematics implemented therein, the circuit arrangement of decoder (7)
included as a part of decoder (1) of FIG. 3;
FIG. 10 shows a diagram of an equipment adapted for mapping partially
faulty memories, for use according to this invention.
DESCRIPTION OF PREFERRED EMBODIMENT
By referring now at first to FIG. 1, it can be observed that the basic
concept of this invention is implemented by means of an arrangement of a
memory array that, in the embodiment shown therein, comprises a matrix of
3.times.4 16 Mb ARAM memories, which can include memories with faulty
locations that can be used according to this invention. A not volatile OTP
memory wherein the "map" of the locations of the memory bank is stored is
associated to said memory matrix. Furthermore, a user circuit (ASIC) is
shown which can have access to the memory bank by using successive
(logical) memory addresses supplied thereto by an intelligent portion of
the circuit, for instance a central processing unit (CPU). Such access can
be obtained by using said not volatile memory OTP that converts the
logical address requested by the user into a material address of the
memory array. As a matter of fact, the user circuit receives from outside
a logic address and utilizes it to gain access to said OTP memory which,
in turn, supplies to it a material address that enables it to obtain
direct access to the memory bank.
As it has above mentioned, aiming at utilizing regions characterized by a
limited number of faulty locations by means of techniques designed for
error correcting applications, a technique has now been developed based
upon the cyclic polynomial code theory, in particular the Reed-Solomon
code with generator polynomial
g(x)=x.sup.4 +a.sup.201.x.sup.3 +a.sup.246.x.sup.2 +a.sup.201.x+1
For the sake of convenience, it has been chosen to divide the information
elementary or unit strings into groups of 32 characters (8 bits per
character). The R-S code adds 4 characters to each of said groups for
error control. In this manner, it is possible to correct two
error-affected characters in a string comprising 36 characters in total.
During the decoding procedure the syndrome block consisting of four
characters is computed and a test is carried out in order to search one or
two errors.
When a procedure based upon the conventional decoding technique is
followed, it is possible to correct one error and two errors can be
corrected only if they are included in four successive characters. This
allows also character strings containing one error to be considered as
good, otherwise such strings would be eliminated during the mapping stage.
This approach, however, is not completely satisfactory, in that the dynamic
memories are subject to the well known phenomenon of the "soft error"
caused by incidence of the alpha particles by which the information
content of the memory cells can be modified. When such a phenomenon
affects a character contained in a block wherein an erroneous character is
already present, due to a faulty cell, in total two errors should be
corrected, placed at a distance greater than three locations.
This problem has been solved by developing a change to be made in the
conventional decoding technique by addition of test circuits (test
patterns) which enable two errors placed at any locations to be detected
and corrected. This technique provides for translating the 36 character
string in such a manner as to move an error always to the first location
of the string and for adding specialized circuits designed to detect an
error located in the first location plus a further error located in anyone
to the locations pertaining thereto and to correct the error existing in
the first position:
______________________________________
circuit number positions
______________________________________
0 1-2-3-4
1 1-5-6-7-8
2 1-9-10-11-12
3 1-13-14-15-16
4 1-17-18-19-20
5 1-21-22-23-24
6 1-25-26-27-28
7 1-29-30-31-32
8 1-33-34-35-36
______________________________________
The operation is based upon the fact that the test circuit identifies a
particular polynomial structure, which indicates the presence of an error
in a byte assembly. Each test circuit evidences the presence of errors in
5 particular positions, so that 9 test circuits are needed to analyse all
36 positions.
As it can be seen in FIG. 3, at the decode stage, the concerned 36 bytes
are applied to a decoder circuit 1 which computes the syndrome S(x) and
transmits it in parallel to those test circuit having a level higher than
zero (Decoder 3; FIGS. 3 and 5).
Assuming that only two errors are present in whichever position, one only
of such test circuits will succeed in locating the errors and in
correcting the one being in the first positi | | |
