Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Determining the burst-correcting limit of cyclic codes

: Matt, H.J.; Massey, J.L.

IEEE transactions on information theory 26 (1980), Nr.3, S.289-297
ISSN: 0018-9448
Fraunhofer HHI ()
error correction codes; cyclic codes; burst correcting link; error correction code; submatrix column rank; code parity check matrix; linear feedback shift register; parity check polynomial

Two new computationally efficient algorithms are developed for finding the exact burst-correcting limit of a cyclic code. The first algorithm is based on testing the column rank of certain submatrices of the parity-check matrix of the code. An auxiliary result is a proof that every cyclic (n,k) code, with a minimum distance of at least three, corrects at least all bursts of length ((n-2k+1)/2) or less. The second algorithm, which requires somewhat less computation, is based on finding the length of the shortest linear feedback shift-register that generates the subsequences of length n-k of the sequence formed by the coefficients of the parity-check polynomial h(x), augmented with ((n-k)/2)-1 leading zeros and trailing zeros. Tables of the burst-correcting limit for a large number of binary cyclic codes are included.