Three module memory system constructed with symbol-wide memory chips and having an error protection feature, each symbol consisting of 2I+1 bits

A three module memory system is disclosed wherein a data word of 2.sup.i+1 bits is stored. Half of the data word is stored in each of two memory modules. A third memory module is provided, wherein each of the modules allows for storing symbols of 2.sup.i +1 bits. An error protection code is disclosed which for symbols of five bits has a minimum distance profile of (4, 2, 0) and for symbols of nine or seventeen bits has a minimum distance profile of (6, 2, 0). Thus a single bit error is correctable, a single symbol error is detectable, and up to four arbitrary bit errors are detectable. Also a simple and systematic decoder is disclosed.

BACKGROUND OF THE INVENTION 
The invention relates to a system memory constructed with symbol-wide 
memory chips and having an error protection feature. Developments in 
memory technology have resulted in storage chips accommodating multiple 
data bits per memory location in each chip with corresponding multiple 
outputs. Errors in the storage of data in these memories are generally 
classified as occurring due to two distinct causes. One is a 
non-destructive environmental phenomenon caused by impingement of atomic 
alpha particles. Those particles, present in ordinary background atomic 
radiation, have energy values vis-a-vis the data signal stored in the 
cell. When such cells are struck by atomic alpha particles, the binary 
values stored in the cell may flip to an opposite value. Hence a data 
error occurs. These errors are therefore transient and usually influence a 
single bit at a time. These failures at small values of the minimum 
circuit detail occur relatively often. 
The second major cause of error is the actual physical failure of one of 
the memory components. This failure produces a permanent or "hard" error. 
In general, the latter category of errors occurs relatively infrequently. 
On the other hand, such errors can influence any number of bits in a 
symbol, and therefore have more dramatic impact. Now, usually symbols are 
2.sup.i bits wide, wherein i may have values of 1 . . . 4. Furthermore 
memory chips with symbols of (2.sup.i +1) bits (i.e. 2.sup.i data bits 
plus one parity bit) have been manufactured, so that on the level of a 
memory chip a single bit error in a symbol may be detected. The present 
invention makes use of the latter type of memory chips, while extending 
the amount of error protection. 
SUMMARY OF THE INVENTION 
Thus, there is a requirement in such memory systems to detect and correct 
all single bit errors in a memory word consisting of three symbols, to 
detect all errors wherein a single symbol in a word has any number of bit 
errors (up to a fully inverted byte), and furthermore to detect as many 
coexistent single bit errors occurring in different symbols of the same 
word. 
The object of the invention is attained by a three module memory system, 
each module having an equal number of memory symbol locations, each memory 
symbol location having an equal number of 2.sup.i +1 memory bit locations, 
a memory word thus containing 3(2.sup.i +1) bits with 3.ltoreq.i, said 
memory system comprising input means for receiving user words of 
2.sup.(i+1) bits, encoding means fed by said input means for multiplying a 
user word received by a generator matrix (GO) to produce a memory word for 
storing in three corresponding memory symbol locations, wherein 
(GO)=(P).times.(G).times.(Q), wherein (P) is an arbitrary regular matrix 
of dimensions (2.sup.i+1).times.(2.sup.i+1), (Q) is an arbitrary 
permutation matrix of dimensions {3.times.(2.sup.i 
+1)}.times.{3.times.(2.sup.i +1)} for effecting bit-wise permutation 
within a code symbol and/or symbol-wise permutation within a code word, 
the choice for (P) and (Q) including identity matrices, and wherein G is a 
matrix for implementing a bitwise systematic error protection code having 
a minimum distance profile of (p, 2, 0) wherein p is at least equal to 
five. The invention provides a large class of [51, 32] and [27, 16] codes 
capable of correcting single bit errors, to detect up to four bit errors 
or to detect single memory chip failures, and also a class of [15, 8] 
codes capable of correcting single-bit errors, to detect up to two bit 
errors or to detect single memory chip failures. Furthermore, the present 
invention presents a convenient method for generating codes that have two, 
three, or four single bit error detecting capabilities. The constructed 
codes are optimal in the sense that there are no [27, 16] or [15, 8] codes 
having better correction/detection properties than the best codes 
presented hereinafter. Also, the [51, 32] code is close to optimum. 
RELEVANT STATE OF THE ART 
As a particular state of the art we cite EP patent application No. 100 825, 
corresponding to U.S. patent application Ser. No. 391,062 now abandoned 
which discloses a single bit error correction, double bit error detection, 
single byte error detection system in a memory word of three symbols of 
nine bits each. Thus, the present invention provides an improved error 
protection: up to four bit errors, instead of only two. Moreover, our 
coding scheme allows for simpler decoders using less hardware than 
necessary for the prior art realization. Further advantageous aspects of 
the invention are recited in the dependent claims.

DEFINITIONS AND PRELIMINARIES 
By w(x) we denote the Hamming weight of a binary vector x, i.e. the number 
of components (bits) in x having the value 1. The length of a code is the 
number of bits in a code word, the dimension is the number of 
(non-redundant) data bits derivable from a code word. For a binary linear 
[3 m, k] code C of length 3 m and dimension k, such that all codewords c 
in C are partioned into three symbols c.sub.1, c.sub.2, c.sub.3 of length 
m, c=(c.sub.1, c.sub.2, c.sub.3), the minimum distance profile 
d(C)=(d(C.vertline.0), d(C.vertline.1), d(C.vertline.2)) is defined in 
FIG. 1. The first component of the minimum distance profile is the minimum 
weight in bits of the code. The second component of the minimum distance 
profile is the minimum weight of the partial code, where in each code word 
the "heaviest" code symbol had been deleted, and so on. The profile thus 
has as many relevant elements as there are symbols in a code word. Each 
following element of the profile cannot be higher than any preceeding 
element of the profile. Any number of elements of the profile may be equal 
to zero. 
Now, in the reference given supra a [27, 16] binary linear code is 
constructed having code words consisting of three symbols of 9 bits, and 
having minimum distance profile (4, 2, 0). This minimum distance profile 
quarantees the following properties for the code: 
*single bit error correction, 
*double bit error detection, 
*single symbol error detection. 
The minimum distance for the whole code is four: this is enough for single 
bit error correction, double bit error detection. The next element of the 
minimum distance profile is 2: this means that an arbitrary error in any 
one symbol is detectable. On the other hand, if one symbol would be left 
out of consideration (erasure symbol), this would mean single bit-error 
detection capability left. The latter feature is not used herein, however. 
In the following paragraph we shall construct [27, 16] binary linear codes 
having codewords consisting of three symbols of 9 bits each, and having 
minimum distance profile (6, 2, 0). This minimum distance profile 
quarantees the following properties for the code: 
*single bit error correction, 
*double bit error detection, 
*triple bit error detection, 
*quadruple bit error detection, 
*single symbol error detection. 
Taken in isolation, the first element "6" of the minimum distance profile 
would also allow for correction of two single bit errors and detection of 
three single bit errors. This latter stratagem could, however, endanger 
the feature of single symbol error detection. Thus, it was felt, that the 
error protection measured out hereabove would be more useful in memory 
management. 
The codes generated are optimal in the sense that any [27, 16] binary 
linear code having code words consisting of three symbols of 9 bits has a 
minimum distance profile (a, b, c) such that a.ltoreq.6, b.ltoreq.2, c=0. 
Moreover, from the specific example codes given, numerous other codes may 
be constructed having either the same, or lesser error protection 
capabilities, but therein still surpassing the capabilities of the prior 
art cited herebefore. In as far as the capability is smaller, such codes 
may be generated by superposing one or two noise bits on the generator 
matrix and then checking for the correct remaining protection level. It is 
believed that the code given hereinafter is also optimum for easy 
decoding. 
CONSTRUCTION OF [27, 16] CODES HAVING MINIMUM DISTANCE PROFILE (6, 2, 0) 
The generator matrix of the code may be written as 
##EQU1## 
wherein each matrix Mi (i=0 . . . 5) consists of 2.sup.i rows and 2.sup.i 
+1 columns. General code theory such as given in F. J. Mac Williams et 
al., "The theory of error correcting codes", Amsterdam 1977 is considered 
as representing the general state of the art. 
The codes are constructed as follows: Let a be a zero of the primitive 
polynomial p(x)=x.sup.8 +x.sup.4 +x.sup.3 +x.sup.2 +1 over GF(2). Define c 
to be c=a.sup.85. a is a primitive element of GF(2.sup.8). This finite 
field has 16 normal bases 
N.sub.b :={a.sup.b2.spsp.i : i=0, 1, 2, 3, 4, 5, 6, 7} 
for b=5, 9, 11, 15, 21, 29, 39, 43, 47, 53, 55, 61, 63, 87, 91, 95. These 
values are taken from the litterature on coding theory. GF(2.sup.4) has 
two normal bases, GF(2.sup.16) has a multitude thereof; see Peterson & 
Weldon, Theory of Error Correcting Codes, MIT 1975 (2.sup.nd ed.). Instead 
of the above choice for c=c.sup.2 =a.sup.170 would do as well; note that 
85=255:3. Now, for each of these normal bases we define an 8 by 8 binary 
matrix M.sub.b as shown in FIG. 2. 
In this matrix, m.sub.ij, i,j in {0, 1, . . . 7} are defined by the 
relations 
##EQU2## 
i=0, 1, . . . , 7. 
This means that (m.sub.i0, m.sub.i1, . . . , m.sub.i7) is the binary 
representation of ca.sup.b2.spsp.i with respect to the normal basis 
N.sub.b. 
These matices M.sub.b satisfy the relations M.sub.b.sup.3 =I and I+M.sub.b 
+M.sub.b.sup.2 =0. In FIG. 3 the matrices M.sub.b are given for b in a set 
A.sub.5 :={5, 11, 15, 29, 47, 53, 63, 87}. FIG. 4 gives the matrices 
M.sub.b for b in a set A.sub.4 :={9, 21, 39, 43, 55, 61, 91, 95}. 
We need the following properties: 
*Property 1: 
The [16, 8] binary linear codes with generator matrix [I M.sub.b ] for b in 
A.sub.5 have minimum bit distance 5. This can be shown by straightforward 
checking. 
*Property 2: 
The [16, 8] binary linear codes with generator matrix [I M.sub.b ] for b in 
A.sub.4 have minimum bit distance 4. The code words of weight 4 have one 
component equal to 1 in the first eight positions and three components 
equal to 1 in the last eight positions or vice versa. 
*Proof: 
This is easy to check by using the matrices given in FIG. 4. For a binary 
matrix A, let p.sup.T (A) denote the column vector of the row-parities of 
A, i.e. 
p(A).sub.i =.SIGMA..sub.j A.sub.ij. 
Now we state the following theorem. 
*Theorem 3: 
For b in A.sub.4 or A.sub.5, M:=M.sub.b, the [27, 16] binary linear code C 
with generator matrix shown in FIG. 5, has minimum distance profile (6, 2, 
0) if each code word of C is considered as being three symbols of 9 bits 
(I denotes the 8 by 8 identity matrix, 0 denotes the 8 by 8 all zero 
matrix). 
*Proof: 
From the properties 1 and 2 it follows that the [16, 8] code with generator 
matrix [Ip.sup.T (I).vertline.Mp.sup.T (M)] has minimum bit distance 6. 
Since [M.sup.2 I]=M.sup.2 [IM], also the code with generator matrix 
[Ip.sup.T (I).vertline.M.sup.2 p.sup.T (M.sup.2)] has minimum bit distance 
6. Now let c=(c.sub.1, c.sub.2, c.sub.3)=(m.sub.1, m.sub.2) G be a code 
word of the code C, where c.sub.1, c.sub.2, and c.sub.3 are binary vectors 
of length 9 and m.sub.1 and m.sub.2 are vectors of length 8. We 
distinguish three cases: 
A. m.sub.1 .noteq.0, m.sub.2 =0. Then c=m.sub.1 [Ip.sup.T 
(I).vertline.0p.sup.T (0).vertline.Mp.sup.T (M)]. 
Hence w(c).ltoreq.6. 
B. m.sub.1 =0, m.sub.2 .noteq.0. Then c=m.sub.2 [Ip.sup.T 
(I).vertline.0p.sup.T (0).vertline.M.sup.2 p.sup.T (M.sup.2)]. 
Hence w(c).ltoreq.6. 
C. m.sub.1 .noteq.0, m.sub.2 .noteq.0 
C1. If c.sub.3 .noteq.0 then w(c.sub.i).ltoreq.2 for i=1, 2, 3. So 
w(c).ltoreq.6. 
C2. If c.sub.3 =0 then m.sub.1 =m.sub.2 M, and hence c=(m.sub.2 M p(m.sub.2 
M).vertline.m.sub.2 p(m.sub.2).vertline.00). w(c)=w(m.sub.2 [M, p.sup.T 
(M).vertline.I, p.sup.T (I)]).ltoreq.6. 
From these observations it follows that the code C has minimum distance 
profile (6, 2, 0). FIGS. 6a, 6b, 6c give the actual generator matrix, G 
and parity check matrix H, of a code so derived. Herein we have chosen for 
b the value 9 (FIG. 4, first case). Furthermore, for clarity instead of 
binary zeroes, dots were used in a parity check matrix of the code 
construction in Theorem 3. 
In general, the code generator matrix can be written as a product of three 
matrices [P].times.[G].times.[Q]. Herein, [P] is any 16.times.16 regular 
matrix, [G] a 16.times.27 generator matrix as constructed hereinabove, or 
along a similar reasoning for any of the other normal bases, or modified 
in such a way as to lose only a limited part of the error protection 
capability. Q is a 27.times.27 permutation matrix. This latter matrix 
consists of 3 rows and 3 columns of submatrices the latter each being a 
9.times.9 submatrix. The 9.times.9 submatrices are positioned in such a 
way that each row or column of three submatrices has exactly one 
subpermutation matrix that is non-zero, all other submatrices consisting 
exclusively of zeroes. Each subpermutation matrix operates on exactly one 
associated symbol. Each row and each column of any subpermutation matrix 
consists of eight zeroes and exactly a single one. 
The parity check matrix so derived can be used for syndrome decoding of the 
code. The all-zero syndrome indicates a correct code word. The 27 
syndromes of single bit errors are used for correcting the associated 
errors. There are 2048-1-27=2020 remaining syndromes. These are used for 
detecting all single symbol errors, all double, triple and quadruple bit 
errors, and also the larger part of any other error configurations (but 
not all of these). In fact, it is quite improbable for any error 
configuration outside the above list to produce any of the 28 syndrome 
configurations that would ultimately give a correct user word (even if all 
error patterns have equal probability the probability thereof would not be 
more than about 28/2048, that is about 11/2%). The decoder may be 
implemented as in FIG. 2 of the reference, using 27 11-way AND-gates. But 
an implementation using less hardware is described in the next section. 
Furthermore it should be remarked that the codes constructed in Theorem 3 
are optimal, in the sense that for any [27, 16] binary linear code having 
code words consisting of three symbols of 9 bits the minimum distance 
profile (a, b, c) would satisfy a.ltoreq.6, b.ltoreq.2, c=0. This applies 
because any [27, 16] binary linear code has a minimum bit distance less 
than or equal to 6, and an [18, 16] binary linear code has a minimum bit 
distance of less than or equal to 2. 
ENCODER AND DECODER IMPLEMENTATION 
In this section we describe the encoder and decoder implementation of a 
[27, 16] code (in which each code word is considered to be composed of 
three symbols of 9 bits) constructed hereinbefore by taking b=9. A 
generator matrix G of this code is given in FIG. 6a. From this follows a 
straightforward construction of the encoder, which only needs to implement 
matrix multiplication operations. A parity check matrix H of this code is 
given in FIG. 6c. From FIG. 6c we see that the parity check matrix H has a 
nice structured form. In fact only two blocks of 8.times.8 elements of 
irregular layout occur. This structured form is used in the decoder 
design. Define s=s(r) to be the syndrome of a received vector r: 
s=(s.sub.1, s.sub.2 . . . , s.sub.11).sup.T =Hr.sup.T. 
The syndromes {s=He.sup.T .vertline.w(e)=1} are used for single bit error 
correction. The remaining nonzero syndromes are used for error detection, 
without thereby specifying the nature of the error. 
Define the signals A.sub.0, A.sub.1, A.sub.2, A.sub.3 as follows: 
A.sub.0 =s.sub.1 s.sub.2 s.sub.3, 
A.sub.1 =s.sub.1 s.sub.2 s.sub.3, 
A.sub.2 =s.sub.1 s.sub.2 s.sub.3, 
A.sub.3 =s.sub.1 s.sub.2 s.sub.3. 
Herein, syndrome bits s.sub.1, s.sub.2, s.sub.3 in fact are parity bits 
over the associated code symbol and s.sub.i is the inverse value of 
s.sub.i. Their implementation using NOR-gates is given in FIGS. 7a-7d. If 
no error occurs then A.sub.0 =1. If a single bit error occurs then 
A.sub.1, A.sub.2, A.sub.3 point to the symbol in which it occurs: A.sub.i 
=1 if this single bit error is in symbol i. Now consider the vectors 
u.sub.j, v.sub.j, w.sub.j of length 8 being the last 8 bits of the 
respective syndromes resulting from the single bit errors in positions j, 
j+9, and j+18 respectively (j=1, 2, . . . , 8). Because M.sup.2 =I+M it 
holds that u.sub.j and v.sub.j only differ in one position and their 
difference is exactly w.sub.j. We use this fact in the construction of the 
decoder. For example, for j=1, the vectors u.sub.1, v.sub.1, w.sub.1 have 
the forms shown in FIGS. 8a, 8b, 8c, i.e. they correspond to the 
respective first columns of the 8.times.9 lower matrices in FIG. 6c. 
FIG. 9 defines the further intermediate signals X.sub.1, Y.sub.1, Z.sub.1, 
B.sub.1, C.sub.1, D.sub.1, SE.sub.1, SE.sub.10, SE.sub.19. The first six 
of these serve for detecting the above vectors u.sub.1, v.sub.1, w.sub.1, 
while aiming for a low number of gates to be used. Thus, X.sub.1 signals 
the four zeroes in v.sub.1. Further, Y.sub.1 signsls the three ones in 
u.sub.1. Finally, Z.sub.1 signals that none of these latter three ones 
occurs. The complete detection of u.sub.1, v.sub.1, w.sub.1 is done by the 
signals B.sub.1, C.sub.1, D.sub.1. Checking for occurrence in the correct 
symbol is done by signals SE.sub.1 (Single error), SE.sub.10, SE.sub.19. 
Thus, if one bit error occurs at postion 1 then SE.sub.1 =1, if one bit 
error occurs at position 10 then SE.sub.10 =1, if one bit error occurs at 
position 19 then SE.sub.19 =1. 
An implementation of the above formulas X.sub.1, Y.sub.1, Z.sub.1, B.sub.1, 
C.sub.1, D.sub.1 is given in FIG. 10. The inputs of the box are the 8 bits 
s.sub.4, s.sub.5, . . . , s.sub.11 of the syndrome vector. The outputs of 
the box are the three bits B.sub.1, C.sub.1, D.sub.1. The internal of the 
box consists of three NAND-gates and three NOR-gates and is two gates 
deep. This box is called BOX 1. Other implementations with other gates are 
possible, we only provide one possibility. From the lay out of the matrix 
(H) in FIG. 6c the generation of signals B.sub.2 . . . 8, C.sub.2 . . . 8, 
D.sub.2 . . . 8 is now straightforward; the number of NAND-gates required 
for each set could vary. 
DESCRIPTION OF A COMPLETE DECODER 
FIG. 11 gives a complete (de)coder of the [27, 16] code given herebefore. 
On input 100 the sixteen bit wide user data arrive. Element 102 is the 
check bit generator, wherein the eleven check bits, inclusive of the three 
symbol-wise parity bits are produced. Note that the code is systematic on 
two levels, in that the user bits are not changed, and also in that the 
eight non-parity bits are themselves part of a [9, 8] systematic code 
symbol. If a non-systematic code were used, element 102 would have more 
outputs (anywhere from 12 through 27). Element 104 is the three module 
memory system. Note that the memory may consist of a plurality of memory 
banks, each bank consisting of three memory modules. 
At the output of memory 104, syndrome generator 106 by means of matrix 
multiplication generates the eleven syndrome bits S.sub.1 . . . 11 as 
indicated. Boxes 108 . . . 114 correspond to FIGS. 7a through 7d, 
respectively, for generating signals A.sub.0 . . . A.sub.3. Box 116 
corresponds exactly to FIG. 10. In similar way as FIG. 10, boxes 118 
through 130 derive X2 . . . X8, Y2 . . . Y8, Z2 . . . Z8, B2 . . . B8, C2 
. . . C8, D2 . . . D8. 
These boxes may all contain three NAND gates and three NOR gates and have a 
depth of two gates. Element 132 is an eight input NOR gate and signals 
whether none of the snydrome bits S.sub.4 . . . S.sub.11 is logic one. 
There are 24 AND gates 134. The first three have as inputs B1, C1, D1 and 
A1, A2, A3, respectively and produce signals SE1, SE10, SE19, 
respectively. The next three are fed by box 118, and by boxes 110, 112, 
114, and so further. Three final AND gates 136 are fed in parallel by the 
output of NOR gate 132 and by signals A1, A2, A3, respectively, to produce 
signals SE9, S18, SE27. Single bit errors are corrected, because a single 
bit error in position j forces SEj=1 and SEi=0 for i.noteq.j. The code 
word of 27 bits wide forwarded from storage box 104 to error corrector 
138, which consists of 27 two input EX-OR gates, each of which receives a 
code bit and a corresponding single bit error detection signal SE to 
invert the code bit. Output 140 is connectable to a user device. In this 
way also the redundancy bits are updated for single-bit-errors. If this is 
not required, the associated eleven EX-OR-gates and inputs from elements 
104, 134, 136 are omitted. The remainder of the arrangement is not 
modified. 
Element 142 is a 27 bit wide NOR gate, which may be constructed by 
connecting less wide gates in a free structure. Output 144 signals "No 
single-bit error" (either zero errors or an error pattern that is 
detectably different from a single bit error pattern). NOR gate detects 
132 that not one of syndrome bits S4 . . . S11 is "one". The same is done 
by NOR gate 108 for syndrome bits S1 . . . S3. NAND gate 146 therefore 
generates an OR function of all syndrome bits. A "one" signal on output of 
AND gate 148 therefore signals a non-zero syndrome, which nevertheless has 
not been recognized as any particular single bit error. Therefore a 
non-correctable error is detected in this manner. It would be recognized 
that the logic depth of the error recognizing device is low: two gates in 
boxes 116-130, one gate each in AND gates 134, 138, and one or only a few 
in NOR gate 142, one more by way of AND gate 148. 
CONSTRUCTION OF [15, 8] CODES HAVING MINIMUM DISTANCE PROFILE (4, 2, 0) 
*Theorem 4: 
If M is a 4 by 4 binary matrix such that M.sup.3 =I and the code generated 
by [I M] has minimum bit distance 3, then the [15, 8] binary linear code C 
with generator matrix given in FIG. 5, has minimum distance profile (4, 2, 
0) if each codeword of C is considered as being three symbols of 5 bits. 
*Proof: 
Analogous to the proof of Theorem 3. 
Matrices M satisfying the conditions of Theorem 4 are constructed in 
corresponding manner as shown hereinbefore for a different code format. 
The codes constructed in Theorem 4 are optimal. 
CONSTRUCTION OF [51, 32] CODES HAVING MINIMUM DISTANCE PROFILE (6, 2, 0) 
*Theorem 5: 
If M is a 16 by 16 binary matrix such that M.sup.3 =I and the code 
generated by [I M] has minimum bit distance at least 5, then the [51, 32] 
binary linear code C with generator matrix given in FIG. 5 has minimum 
distance profile (6, 2, 0) if each codeword of C is considered as being 
three symbols of 17 bits. 
*Proof: 
Analogous to the proof of Theorem 3. 
Matrices M satisfying the conditions of Theorem 5 are constructed in 
corresponding way was explained hereabove. 
In similar way, codes can be calculated for wider memory words, such as a 
(99, 64) code. Generally, error detecting capabilities increase with 
increasing word length.