Browse Prior Art Database

Bidirectional Error Correcting codes

IP.com Disclosure Number: IPCOM000089304D
Original Publication Date: 1977-Oct-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 4 page(s) / 102K

Publishing Venue

IBM

Related People

Bossen, DC: AUTHOR [+2]

Abstract

This class of bidirectional codes will correct errors in storage devices which can reasonably be expected to have failure modes of major magnitudes in two orthogonal directions.

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 55% of the total text.

Page 1 of 4

Bidirectional Error Correcting codes

This class of bidirectional codes will correct errors in storage devices which can reasonably be expected to have failure modes of major magnitudes in two orthogonal directions.

An example of such a failure would be along the hatched bit lines (B/L) and word lines (W/L) of the memory array chip shown in Fig. 1. A (81,55) code of the class of codes mentioned can correct up to a 9-bit error in either direction of Fig. 1. The code-word is a 9 by 9 rectangular array. The implication here is that the code-word resides in some physical portion of, say, a 1 k by 9 array chip. In order to access the code-word, multiple accesses to different W/L's are made.

A code word is arranged in a format shown in Fig. 2. Let B(i) = (B(i1)

B(i2)...B(i9)) be the 9-bit byte along the i-th vertical (B/L) direction and B = ((B(1) B(2)...B(9)) be a code-word. The (81,55) code is defined by the equation: H . B/t/ = 0, (1) where H is of the form

(Image Omitted)

and I(9) is the identity matrix of dimension 9, T is the companion matrix of a degree 9 irreducible polynomial, Q(1) is an 8 by 9 matrix with 1's in the i-th row and 0's elsewhere.

A set of bit positions can be designated as check bit positions if the column vectors of H, corresponding to the bit positions, are linearly independent. It is easy to show that the check bit positions shown in Fig. 2 for the code defined in
(1) are legitimate.

If T is selected to be the companion matrix of the polynomial 1 + X/4/ + X/9/, H of (2) becomes the matrix shown in Fig. 3. The matrix shown in Fig. 4 can be used to compute the check bits. Note that B/L 9 and W/L 1 are byte parity checks. The rest of the check bits are computed from the equations corresponding to the middle section of the matrix. Le...