Browse Prior Art Database

Fast Double Error Correction

IP.com Disclosure Number: IPCOM000050319D
Original Publication Date: 1982-Oct-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 3 page(s) / 40K

Publishing Venue

IBM

Related People

Olderdissen, U: AUTHOR [+2]

Abstract

The arrangement shown in the figure is suitable for rapidly determining two erroneous bit positions i and j in a data word by reducing circuit delays to a minimum. The parity check matrix (H-matrix) comprises an uppermost row for an overall parity to permit triple error detection, an upper part for 4-bit column vectors c and a lower part for 4-bit column vectors c(i)/3/. This H-matrix is generated by the generator prime polynomial G(x)=x/4/ x + 1 (see R.W. Hamming's book Coding and Information Theory, Prentice Hall Inc., New York, 1980, Chapter 11).

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

Page 1 of 3

Fast Double Error Correction

The arrangement shown in the figure is suitable for rapidly determining two erroneous bit positions i and j in a data word by reducing circuit delays to a minimum. The parity check matrix (H-matrix) comprises an uppermost row for an overall parity to permit triple error detection, an upper part for 4-bit column vectors c and a lower part for 4-bit column vectors c(i)/3/. This H-matrix is generated by the generator prime polynomial G(x)=x/4/ x + 1 (see R.W. Hamming's book Coding and Information Theory, Prentice Hall Inc., New York, 1980, Chapter 11).

With L being a primitive root of G(x), G(L)=L/4/ + L + 1=0 and L/4/=L + 1. Powers of L of 4 and higher can therefore be reduced to powers of 3 and lower, and the successive powers L/1/ to L/15/ generate all the fifteen different non-zero 4-tuples possible. A column C of the H-matrix can thus be written as C(k)=1

c(k(3))

c(k) with c(k)=L/k/ , i.e., the kth power of L, and c(k)/3/=L/3k/, all in modulo 2 arithmetic. In the absence of an error in the received n-bit data word vector v, the syndrome vector S=H x v/T/ equals zero, with H being the parity matrix and v/T/ being the transpose of data vector v. For a single error in position i, the syndrome vector S equals the column vector C(i) of H, i.e., S=C(i)=(1, L/i/, L/3i/).

For a double error occurring in positions i and j, the syndrome vector is S=C(i)+C(j) (1)

Therefore, the result of the modulo 2 addition (XOR) of S to one of the column vectors of H, belonging to an erroneous bit position, is the column vector of the other erroneous bit position, i.e., S + C(i)=C(j).

A fast way of identifying the two erroneous bit positions from the syndrome vector S comprises three steps:
1. Generate S=H x v/T/.
2. Determine S + C(k) for every column vector C(k) of H.
3. Determine whether the resulting vector is a member of the set

of column vectors of H.

For the third step, S is split into S=S(0), S(1), S(2). S(0) is the overall parity and the first element of S. S(0)=0 (1) for an even (odd) number of erroneous bits. S(1) contains four bits subsequently labelled as s(0), s(1), s(2), s(3). S(2) also comprises four bits. From equation (1) it follows that

S(1)=a/i/ + a/j/, and a/i/=S(1) + a/j/

(2)

S(2)=a/3i/ + a/3j/=(S(1) + a/j/)/3/ + a/3j/

Thus, K is an erroneous bit position if and only if (S(1) + a/K/)/3/=S(2) + a/3K/ (3)

1

Page 2 of 3

Equation (3) can be simplified to

S(1)/3/ + S(1)/2/a/K/ + S(1) a/2K/ + S(2)=0 (4)

With the four bits of S labelled t(0), t(1), t(2), t(3) and using the rules of polynomial multiplication, we get t(0)=s(0)+s(0)s(2)+s(1)s(2)+s(3)s(1)

t(1)=s(3)+s(0)s(1)+s(0)s(2)+s(2)s(3)

t(2)=s(2)+s(0)s(1)+s(0)s(2)+s(0)s(3)+s(1)s(2)+s(1)s(3)+s(2)s(3)

t(3)=s(1)+s...