Browse Prior Art Database

Systematic (12,8) Code for Correcting Single Errors And Detecting Adjacent Errors

IP.com Disclosure Number: IPCOM000121694D
Original Publication Date: 1991-Sep-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 1 page(s) / 35K

Publishing Venue

IBM

Related People

Blaum, M: AUTHOR [+2]

Abstract

The following problem was studied (1): given a byte stored as three 4-bit nibbles such that 8 of the bits carry information and 4 are redundant, encode the information bits in such a way that any single error will be corrected and any two adjacent bits in error in a nibble will be detected. A solution was derived at that, in fact, corrects any single error and detects 8 out of 9 cases of double adjacent errors in a nibble. Disclosed is an optimal solution to the problem; namely, a systematic (12,8) code that can correct any single error and detect any of the 9 patterns of double adjacent errors within a nibble.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 75% of the total text.

Systematic (12,8) Code for Correcting Single Errors And Detecting
Adjacent Errors

      The following problem was studied (1):  given a byte
stored as three 4-bit nibbles such that 8 of the bits carry
information and 4 are redundant, encode the information bits in such
a way that any single error will be corrected and any two adjacent
bits in error in a nibble will be detected. A solution was derived at
that, in fact, corrects any single error and detects 8 out of 9 cases
of double adjacent errors in a nibble.  Disclosed is an optimal
solution to the problem; namely, a systematic (12,8) code that can
correct any single error and detect any of the 9 patterns of double
adjacent errors within a nibble.

      Consider a (12,8) code with the following parity check matrix:
                1  1  0  0     1  0  0  1     1  0  1  0
                1  0  1  0     1  0  1  0     1  0  0  1
      H =
                1  0  0  1     1  1  0  0     0  0  1  1
                1  0  0  1     0  0  1  1     1  1  0  0
      As can be seen, the 4 x 4 submatrix of H at locations 2, 3,
6 and 10 is the identity matrix.  Hence, the code carries information
in bits 1, 4, 5, 7, 8, 9, 11, and 12.

      Notice that the syndromes corresponding to the 9 double
adjacent errors within nibbles are 0111, 1100, or 1011. They do not
correspond to any of th...