A note on optimum burst-error-correcting codes

Author

Elspas, B. ; Short, R.A.

Volume

8

Issue

1

fYear

1962

fDate

1/1/1962 12:00:00 AM

Firstpage

39

Lastpage

42

Abstract

A detailed study has been made of a certain class of systematic binary error-correcting codes that will correct the error bursts typical of some digital channels. These codes--generalizations of codes discovered by Abramson and Melas--are cyclic codes designed to correct any single burst of errors per $n$ -digit word provided that the width of the burst (regarded cyclically) does not exceed a certain number of digits, $b$ . Moreover, these codes are optimum in the sense that they employ the minimum number of redundant digits theoretically possible for a cyclic code with given values of $n$ and $b$ . A cyclic code is completely characterized by its generator polynomial $g(x)$ , hence, the properties of the code can be determined by analysis of the corresponding $g(x)$ . Necessary and sufficient conditions on $g(x)$ have been formulated for the corresponding cyclic code to be an optimum burst- $b$ correcting code. These conditions have been formulated into a series of tests that can be carried out (in principle) on any $g(x)$ . All optimum burst- $b$ cyclic codes with $n < 2^{12}$ and $b < 6$ have been found in this way and their generators are tabulated in the paper. In all, 98 codes are listed (not counting reciprocals) for $b = 3$ and $b = 4$ ; it was shown that no optimum codes exist for $b = 5$ within the limits stated. Practical codes for $b \\geq 6$ will probably be nonoptimum codes because of the extreme word lengths required for optimum ones.

Keywords

Burst-correcting codes; Cyclic codes; Character generation; Error correction; Error correction codes; Fires; Information theory; Integrated circuit testing; Reconnaissance; Redundancy; Sufficient conditions; Testing;

fLanguage

English

Journal_Title

Information Theory, IRE Transactions on

Publisher

ieee

ISSN

0096-1000

Type

jour

DOI

10.1109/TIT.1962.1057667

Filename

1057667