Chapter 9.4 - Single-Bit Error Correcting And Single-Byte Error Locating

9.4 SINGLE-BIT ERROR CORRECTING AND SINGLE-BYTE ERROR
LOCATING (SEC-Se=bEL) CODES

We study here another class of error locating codes, namely Single-bit Error Correcting
and Single e-bit (within a b-bit byte) Error Locating codes, or SEC-S_e/bEL codes.

9.4.1 Code Conditions and Bounds

Let E_s be the error set consisting of all single-bit errors, and let E_i(E_j) be the set of e
or fewer bits errors in the i( j)-th byte excluding single-bit errors, where e < b and b is
the byte length. Thus E_i Ç E_s = E_j Ç E_s = φ for all i ≠ j, where f is the empty set. The
following theorem describes the necessary and sufficient conditions that characterize
SEC-S_e/bEL codes.

Theorem 9.10 A linear code, described by the parity-check matrix H, corrects all
errors in E_s and locates all errors in E_i, or E_j , where i ≠ j, if and only if:

where H^T means the transpose of H.

Proof It is apparent that conditions 1 and 2 and conditions 1 and 3 are necessary conditions
for correcting all single-bit errors and for indicating the location of an erroneous byte
containing e or fewer errors, respectively. Conditions 1 and 4 are also necessary conditions
for distinguishing single-bit errors from single-byte errors that exclude single-bit errors. So
the SEC-S_e/bEL codes must satisfy conditions 1 to 4.

Inversely, a code that satisfies conditions 1 to 4 allows us to distinguish single-bit errors
from single-byte errors. Then we can correct all single-bit errors and locate all single-byte
errors. Therefore this code is an SEC-S_e/bEL code. Q.E.D.

Since the S_e/bEL codes, where e = b, are equivalent to the single b-bit byte error
correcting codes (or SbEC codes), the SEC-S_e/bEL codes, where e = b, are also equivalent
to the SbEC codes. This leads to the following theorem.

Theorem 9.11 Linear SEC-S_e/bEL codes satisfy

2 ≤ e ≤ b − 1.

The next two theorems give the lower bounds on check-bit length of the SEC-S_e/bEL codes.

Theorem 9.12 Linear (N, N − R) SEC-S_e/bEL codes satisfy

Proof The lower bounds on the check-bit length of the S_e/bEL codes are obtained by the
fact that syndromes produced by e/2 or fewer bits errors should be different from each
other [WOLF63].

For odd e. Syndromes produced by (e − 1)/2 or fewer bits errors in a given byte
should differ from each other because, otherwise, there might exist e − 1 or fewer bits
errors in that byte that result in a zero syndrome. This violates condition 3 of Theorem 9.10.
Conditions 3 and 4 say that syndromes produced by (e − 1)/2 + 1 = (e + 1)/2-bit errors
in a byte should be different from each other and also different from those produced by
(e − 1)/2 or fewer bits errors in that byte. In this case it is because, otherwise, there might
exist e or fewer bits errors in that byte that result in a zero syndrome. This case violates the
conditions of the code. Therefore syndromes produced by (e + 1)/2 or fewer bits errors in
a byte should differ from each other. It is apparent that syndromes produced by (e + 1)/2
or fewer bits errors in a byte should also be different from those in another byte. Hence the
following inequality holds:
For even e. By condition 3 of Theorem 9.10, the syndromes produced by e/2 or
fewer bits errors in a byte should differ from each other. However, syndromes produced
by (e + 2)/2-bit errors in a byte are capable of being equal to those produced by other
(e + 2)/2-bit errors in the same byte only when there exist no erroneous bits at the same
bit positions in these two (e + 2)/2-bit errors. There exist at most

of the (e + 2)/2-bit errors in a byte that have the same syndromes, where [x] means the
largest integer less than or equal to x. From conditions 3 and 4 of Theorem 9.10, any
syndromes produced by (e + 2)/2-bit errors should be different from those produced by
e/2-bit errors. Hence there exists at least the following number of distinct nonzero
syndromes:

Hence we have the following inequality: