Browse Prior Art Database

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

IP.com Disclosure Number: IPCOM000007220D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2002-Mar-06
Document File: 3 page(s) / 153K

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-, a11 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 43% of the total text.

Page 1 of 3

0 M MO-LA

Technical Developments Voluine 22 June 1994

OPTIMAL 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-, a11 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 num- ber 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 l'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 JO10 0111000 1011000 0011001 0011010 !OlOl 0011100 0101100 1001100 0001101 1010 0001110 0010110 0100110 1000110 io101 0000111 0001011 0010011 0100011 ~,OOlO

h=

and

u=

1000000

0100000

0010000

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:

84 0 MOtorOla, 1°C. 1994

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

Page 2 of 3

0 M

MO7VROLA Technical Developments Volume 22 June 1994

-o- -1--o-

1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1

  The above matrix h is what was actually implemented in the checkword generator, which com- prises 7 checkbit generators. Each row corresponds to a checkbit. Each checkbit is the modulo-2 sum of all the data bits corresponding to l's in the associated row of h. For example, the third bit of the checkword is the modulo-2 sum of data bits 0, 1,2, 8,9, 13, 15, 16, 19, 22, 23, 25, 28, 29. There are 13 or 14 l's in each row of h, therefore each of the...