Browse Prior Art Database

OPTIMAL 32-BIT SINGLE-ERROR CORRECTION/ DOUBLE-ERROR DETECTION CIRCUIT

IP.com Disclosure Number: IPCOM000007295D
Original Publication Date: 1994-Oct-01
Included in the Prior Art Database: 2002-Mar-12
Document File: 2 page(s) / 123K

Publishing Venue

Motorola

Related People

Scott E. Lloyd: AUTHOR

Abstract

This publication describes a circuit for correcting single-bit errors, detecting both single- and double- bit errors, and generating corresponding checkbits. The circuit can operate as encoder or decoder. As an encoder, based on a 32-bit input data word, a corresponding 7-bit checkword is generated. As a decoder, two modes are possible: detection and cor- rection. In detection mode, all single-, all double-, and some triple-bit errors can be detected in the 39-bit input code word comprising a 32-bit data word and an 7-bit checkword. In correction mode, single- bit errors in the input code word can be corrected. A block diagram is shown in Figure 1.

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

Page 1 of 2

MO7VROLA Technical Developments Volume 23 October 1994

Of'TlMAL 32-BIT SINGLE-ERROR CORRECTION/ DOUBLE-ERROR DETECTION CIRCUIT

by Scott E. Lloyd

  This publication describes a circuit for correcting single-bit errors, detecting both single- and double- bit errors, and generating corresponding checkbits. The circuit can operate as encoder or decoder. As

an encoder, based on a 32-bit input data word, a corresponding 7-bit checkword is generated. As a decoder, two modes are possible: detection and cor- rection. In detection mode, all single-, all double-, and some triple-bit errors can be detected in the 39-bit input code word comprising a 32-bit data word and an 7-bit checkword. In correction mode, single- bit errors in the input code word can be corrected. A block diagram is shown in Figure 1.

The invention is "optimal" because it is based

on a balanced minimal-weight Parity Check Matrix. The weight of a Parity Check Matrix is the total number of l's contained therein. Therefore, minimal- weight refers to a Parity Check Matrix containing a minimal (that is, the theoretical minimum) num- ber of 1's. Balanced refers to the relative number of l's in each row of the Parity Check Matrix. The closer each row has to the same number of l's, the more balanced the matrix. A perfectly balanced Parity Check Matrix has the same number of l's in each row.

  Below is a balanced minimal-weight Parity Check Matrix H generated for 32-bit data with single-error correction and double-error detection capability:

H=[h u]

1000011 1000101 1001001 1010001 1001 1100001 1100010 1100100 1101000 0100 1110000 0110001 0110010 0110100 1010 0111000 1011000 0011001 0011010 0101 0011100 0101100 1001100 0001'101 1010 0001110 0010110 0100110 1000110 0101 0000111 0001011 0010011 0100011 0010

- 1000000

0100000

0010000

u = 0001000

0000100

0000010

0000001

  It has the theoretical minimum weight (total nating its balanced minimal-weight characteristic number of l's = 15 x 5 + 14 x 2 = 103) and is also or reducing its error detection and correction capa- balanced (number of l's in each row = 13, 14). Any bility. There are three other columns that could be number of rows can be exchanged and any number substituted for any ofthe 32 existing columns while of columns can be exchanged without either elimi- maintaining functional correctness:

h=

and

0 Motorola, 1°C. 1994 79

[This page contains 14 pictures or other non-text objects]

Page 2 of 2

MOTOROLA Technical Developments Volumb 23 October 1994

1 0 1 0 1 0

This requires much less time and area than to com- pute the OR of all the 63 double-bit error patterns, each ofwhich must first be decoded.

'0 'l--o-

0 0 1

1 0 0

0 1 0 1 0 1

  This design was implemented in Motorola's H4C gate array technology and also in a standard cell technol...