Browse Prior Art Database

Error Detecting And Correcting Circuit

IP.com Disclosure Number: IPCOM000098473D
Original Publication Date: 1960-Nov-01
Included in the Prior Art Database: 2005-Mar-07
Document File: 4 page(s) / 62K

Publishing Venue

IBM

Related People

Brandt, WE: AUTHOR

Abstract

The circuitry corrects single errors and detects double errors in a multi-bit binary word.

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

Page 1 of 4

Error Detecting And Correcting Circuit

The circuitry corrects single errors and detects double errors in a multi-bit binary word.

Data bits are identified by letters A through G; redundancy bits as R1, R2, R4 and R8; the parity bit as P. The redundancy and parity bits are encoded in the word as the parity of a unique combination of data bits as follows: R1 = A, B, D, E, G

R2 = A, C, D, F, G

R4 = B, C, D

R8 = E, F, G

P = R1, R2, R4, R8, A, B, C, D, E, F, G.

Data bits A through G may be in any permutation arrangement, and if the other five bits are encoded by the above relationship, a complete twelve-bit computer word has properties of single error correction and double error detection. A check of the accuracy of the entire word is made by checking the parity of each of the unique combinations of bits and their respective redundancy bits. A separate set of parity check bits, K0, K1, K2, K4 and K8, is generated in an error detector and an examination of these bits indicates the status of errors in the twelve-bit computer word. These parity check bits are generated by the following combinations of data and redundancy bits. K0 = P, R1, R2, R4, R8, A, B, C, D, E, F, G

K1 = R1, A, B, D, E, G

K2 = R2, A, C, D, F, G

K4 = R4, B, C, D

K8 = R8, E, F, G.

The generation of the parity check bits is the same as the redundancy bits in that, if the combination of bits represents an even number of 1's, as it should if the bits are properly encoded, the K bit associated with the group should be 0.

If one bit is in error, K0 is 1. If two bits are in error, K0 is 0 but not all of the other K bits are 0. If there is no error, all K bits are 0.

To determine the location of the bit in error when K0 = 1, the computer word bits are given the following number equivalents: Bit: P R1 R2 A R4 B C D R8 E F G No. equivalent: 0 1 2 3 4 5 6 7 8 9 10 11

When K1, K2, K4 and K8 are given weights of 1, 2, 4 and 8, respectively, the sum of these K bits, that are equal to 1, gives the number equivalent of the bit in error.

For example K0 = 1: Remaining K bits equal to 1 No. equivalent Bit in error None 0 P

1

Page 2 of 4

K1,K2,K4 1+2+4=7 D

K1,K8 1+8=9 E

The twelve-bit computer word is entered into a Data Storage Device 10. A Decoder 11 causes the computer word to be read out sequentially from 10 to an Error Detector 12. Here the parity check bits are generated to indicate the presence or absence of an error. The parity check bits are transmitted to an Error Analyzer 13 which gives an indication of the check sequence steps which should be followed.

When a single error is detected for the first time, the address of the bit in error is indicated by the parity check bits. The parity check bits in 12 are placed in 11 to energize a single one of twelve lines 14 corresponding to the bit in error. The address signal, a bit status signal from 12 and a pulse from 13 combine to reverse the stable state of the bit in error.

A correction is attempted only once for one computer word. T...