Browse Prior Art Database

Single Burst Detection Analysis for Polynomial Error Correction Codes

IP.com Disclosure Number: IPCOM000081371D
Original Publication Date: 1974-May-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 4 page(s) / 18K

Publishing Venue

IBM

Related People

Petersen, JE: AUTHOR

Abstract

Let d be the maximum value for which all single-burst errors of d symbols or less are detectable by a linear error correction code, assuming that the code corrects all single-burst errors of length b or less. It is well known that d is at least (D-b-1), where D is the Hamming distance of the code, but a larger value than this may actually hold, particularly when only a portion of the code cycle length is used. This description presents an algorithm which finds the true value of d for polynomial codes given the defining polynomial [p(x)], the correctable burst length [b], and the maximum record length [n].

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 33% of the total text.

Page 1 of 4

Single Burst Detection Analysis for Polynomial Error Correction Codes

Let d be the maximum value for which all single-burst errors of d symbols or less are detectable by a linear error correction code, assuming that the code corrects all single-burst errors of length b or less. It is well known that d is at least (D-b-1), where D is the Hamming distance of the code, but a larger value than this may actually hold, particularly when only a portion of the code cycle length is used. This description presents an algorithm which finds the true value of d for polynomial codes given the defining polynomial [p(x)], the correctable burst length [b], and the maximum record length [n].

Let C be the class of polynomials over a finite field with nonzero constant terms, let A be the subclass of C whose members are of degree less than b, and assume that p(x) belongs to C. The true value of d is given by the minimum degree of those c(x) in C, for which c(x)-x/k/a(x) is divisible by p(x) for some a(x) in A and some nonzero k in the range -n to n. This immediately gives an upper bound for d or r-b, where r is the degree of p(x). Since multiplication by nonzero field elements does not affect divisibility or degrees of polynomials, the constant terms of a(x) and p(x) may be assumed to be 1.

Assuming for the moment that c(x) and k are known, the divisibility condition transforms into a system of simultaneous linear equations by replacing the powers of x in x/k/a(x) with their equivalent reduced polynomials modulo p(x), and equating the coefficients of the resulting polynomial to those of c(x). This system consists of (r-1) equations in the (b-1) unknown coefficients of a(x).

If v(m) is the vector consisting of the coefficients of the reduced polynomial equivalent to x/m/ modulo p(x), then the system is soluble if and only if there is a linear combination of v(k+1), ..., v(k+b-1) which equals c*-v(k), where c* is the coefficient vector of c(x). This means that a c(x) of minimum degree can be found for each value of k, by starting with c*=v(k) and reducing it towards zero as far as possible by adding multiples of v(k+1), ..., v(k+b-1), or linear combinations thereof in a systematic manner.

For j = (k+1),- (k+2), ..., (k+b-1), let w(j)=v(j)+u(j), where each u(j) is a linear combination of v(k+1), v(k+2), ..., v(j-1) and with the u(j) chosen so that no two of the w(j) represent polynomials of the same degree. Then, starting with c*=v(k), successive reduction by w(j)'s of matching degree until no matching w(j) is found, yields the coefficient vector of a minimum c(x) for this value of k. The c(x) thus found may not belong to C as required, but this has no effect on the search for an overall minimum since c(x)/x, which is of lower degree, is a minimum for the exponent (k-1).

The speed achieved by the algorithm is predominantly due to using the w(j) rather than the v(j) to find c(x). Since the process of adjusting the w(j) so that no two "degrees" match invol...