**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 __S__ingle-bit __E__rror __C__orrecting

and __S__ingle __e__-bit (within a __b__-bit byte) __E__rror __L__ocating codes, or SEC-S_{e/b}EL 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/b}EL 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/b}EL 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/b}EL code. Q.E.D.

Since the S_{e/b}EL codes, where *e* = *b*, are equivalent to the single *b*-bit byte error

correcting codes (or S*b*EC codes), the SEC-S_{e/b}EL codes, where *e* = *b*, are also equivalent

to the S*b*EC codes. This leads to the following theorem.

**Theorem 9.11 *** Linear SEC-S*_{e/b}EL codes satisfy

The next two theorems give the lower bounds on check-bit length of the SEC-S_{e/b}EL codes.

**Theorem 9.12** * Linear (N, N − R) SEC-S*_{e/b}EL codes satisfy

*Proof * The lower bounds on the check-bit length of the S_{e/b}EL 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:

Theorem 9.13 * Linear (N, N − R) SEC-S*_{e/b}EL codes satisfy

This theorem can be easily proved, and the proof is therefore omitted.

**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 __S__ingle-bit __E__rror __C__orrecting

and __S__ingle __e__-bit (within a __b__-bit byte) __E__rror __L__ocating codes, or SEC-S_{e/b}EL 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/b}EL 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...

More >>
Show More...