Browse Prior Art Database

Double Error Correction Circuit

IP.com Disclosure Number: IPCOM000073544D
Original Publication Date: 1971-Jan-01
Included in the Prior Art Database: 2005-Feb-22
Document File: 2 page(s) / 22K

Publishing Venue

IBM

Related People

Hsiao, MY: AUTHOR [+2]

Abstract

The drawing shows apparatus for correcting random double errors in a word of 64 data bits and 15 check bits. The data bits and check bits from a register 3 are encoded in an Exclusive OR tree 4 to form 15 syndrome bits. Conventional circuits, not shown, correct any single errors and signal whenever a double error is to be corrected. The syndrome, S = GT/i/ + GT/j/, is stored in a register 5 and in a register 6. The term T is the companion matrix for the code and G is a row vector, G = [10...0]. The term GT/i/ is associated with an error in a random position i of register 3, and the term GT/j/ is associated with an error in position j. Since there are a large number of combinations of positions where two errors may occur, decoding the syndrome directly requires extensive circuits and time consuming operations.

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

Page 1 of 2

Double Error Correction Circuit

The drawing shows apparatus for correcting random double errors in a word of 64 data bits and 15 check bits. The data bits and check bits from a register 3 are encoded in an Exclusive OR tree 4 to form 15 syndrome bits. Conventional circuits, not shown, correct any single errors and signal whenever a double error is to be corrected. The syndrome, S = GT/i/ + GT/j/, is stored in a register 5 and in a register 6. The term T is the companion matrix for the code and G is a row vector, G = [10...0]. The term GT/i/ is associated with an error in a random position i of register 3, and the term GT/j/ is associated with an error in position j. Since there are a large number of combinations of positions where two errors may occur, decoding the syndrome directly requires extensive circuits and time consuming operations. The apparatus of the drawing isolates the terms so that the errors can be corrected as single errors.

Register 6 is a linear feedback shift register arranged according to the generator polynomial of the error correction code. Shifting register 6 i times has the effect of multiplying the contents of the register by T/-i/ to produce (GT/i/ + GT/j/) T/-i/ = G + GT/j-i/. Thus, the output of register 6 after i shifts identifies error position j in one of 78 possible positions with respect to error position i. A linear feedback shift register 8 is similarly constructed according to the generator polynomial except that it is shifted...