Browse Prior Art Database

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

IP.com Disclosure Number: IPCOM000007090D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2002-Feb-25
Document File: 3 page(s) / 158K

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 64-bit input data word, a corresponding 8-bit checkword is generated. As a decoder, two modes are possible: detection and cor- rection. In detection mode, all single-, all double-, and some multiple-bit errors can be detected in the 72-bit input code word comprising a 64-bit data word and an 8-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 42% of the total text.

Page 1 of 3

0' M

MOIOlROLA Technical Developments Volume21 February 1994

OPTIMAL 64-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 64-bit input data word, a corresponding 8-bit checkword is generated. As a decoder, two modes are possible: detection and cor- rection. In detection mode, all single-, all double-, and some multiple-bit errors can be detected in the 72-bit input code word comprising a 64-bit data word and an 8-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 Hgenerated for 64-bit data with single-error correction and double-error detection capability:

H=[h "1

where

10000011

11000001

11100000

h = 01110000

00111000

00011100

00001110

00000111

10000101 10001001 10010001 10100001 10001010 10010010 11000010 11000100 11001000 11010000 01000101 01001001 01100001 01100010 01100100 01101000 10100010 10100100 10110000 00110001 00110010 00110100 01010001 01010010 01011000 10011000 00011001 00011010 10101000 00101001 00101100 01001100 10001100 00001101 01010100 10010100 00010110 00100110 01000110 10000110 00101010 01001010 00001011 00010011 00100011 01000011 00010101 00100101

10001111

11000111

11100011

11110001

11111000

01111100

00111110

00011111

and

10000000

01000000

00100000

00010000

f

U=

00001000

00000100

00000010

00000001

It has the theoretical minimum weight (total num- tion where each column contains five l's such that ber of l's = 27x8 = 216) and is also balanced (num- the matrix remains balanced.
ber of l's in each row = 27). Any number of rows
can be exchanged and any number of columns can The above matrix is what was actually imple- be exchanged without either eliminating its balanced mented in the checkword generator, which comprises minimal-weight characteristic or reducing its error 8 checkbit generators. Each row of h corresponds to detection and correction capability. Also note that a checkbit. Each checkbit is the modulo-2 sum of the last (right) 8 columns of h can be any combina- all the data bits corresponding to l's in the associated

0 Motorola. 1°C. 1994 31

[This page contains 14 pic...