Browse Prior Art Database

Subset Codes

IP.com Disclosure Number: IPCOM000081831D
Original Publication Date: 1974-Aug-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 3 page(s) / 64K

Publishing Venue

IBM

Related People

Bossen, DC: AUTHOR [+2]

Abstract

Use of compatible codes at different levels of a hierarchy permits minimization of circuitry used in the generation of check bits. For instance, when the L2 level is protected by an 8 byte SEC-DED code, two words from the L2 line can be assembled into a 16 byte word for an L3 level protected by a 16 byte SEC-MED code, so that the two sets of 8 check bits for the 8 byte SEC-DED code represent partial computations of the 16 check bits for the 16 byte SEC-MED code. This minimizes the circuitry needed to complete the generation of the 16 SEC-MED code check bits.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Subset Codes

Use of compatible codes at different levels of a hierarchy permits minimization of circuitry used in the generation of check bits. For instance, when the L2 level is protected by an 8 byte SEC-DED code, two words from the L2 line can be assembled into a 16 byte word for an L3 level protected by a 16 byte SEC-MED code, so that the two sets of 8 check bits for the 8 byte SEC-DED code represent partial computations of the 16 check bits for the 16 byte SEC- MED code. This minimizes the circuitry needed to complete the generation of the 16 SEC-MED code check bits.

The first codes that can be used for this purpose are Dual Hamming Codes. The important property of these codes is that one is the subset of the other. That is, the SEC-DFD 8 byte code for L2 is a subset, in the implementation sense, of the 16 byte L3 code. The L3 code has sufficient distance to detect almost all (> 99%) multiple errors.

Fig. 1 shows the various code matrices. H64 is an odd-weight SEC-DED, code and A64 is defined in terms of a degree 8 primitive polynomial g(x). Each column of A64 is equal to a distinct 3/i/ modulo g(x). In order to preserve the overall odd weight of the composite matrix, only the even weight approx./i/ vectors are chosen.

Let A and B denote the two 8 byte L2 words which are to be assembled into a single 16 byte L3 word, denoted by W. Further, define A, B, and W to be exclusive of check bits. Let C(A) and C(B) denote the check bits associated with A and B. For mechanization and operation, we can consider two cases: (1) Transfer from L2 to L3 (Fig. 2).

In this case, words A and B from L2 are to be assembled into 16 byte word
W. To produce the check bits C(W) for word W, do the following: Gate A through A(64) and bit by bit EX-OR the resulting 8 bits with C(B). Similarly, gate B through A(64) and EX-OR the resulting 8 bits with C(A). Gating is performed using appropriate controls to and from the error correction code (ECC) register. Note that it is also possible to check A and B for errors by gating through H(64) prior to C(W) generation. (2) Transfer from L3 to L2 (Fig. 3).

In this case, correction is necessary, together with generation of C(A) and C(B) from word W. Word W with check bits C(W) is loaded into the ECC register. A and B portions are gated through H(64) and A(64), as indicated in Fig. 3. The resultant bits are EX-ORed to C(W) to produce the syndrome. Single error is indicated by an odd-even or even-odd pattern on the syndrome halves. H(64), A(64...