Circuitry for detecting and correcting errors in data words occurring in Reed-Solomon coded blocks and determining when errors are uncorrectable by syndrome analysis, Euclid's algorithm and a Chien search

摘要

Circuitry for detecting and correcting errors in data words occurring in Reed-Solomon coded blocks contains a plurality of stages. One stage constructs syndromes in the data flowing through the blocks. Another stage detects erasures in the syndromes. Another stage applies a Euclid's algorithm withPPT.sub.s (x)={Q.sub.s-1 (x) ·T.sub. s-1 (x)}+T.sub.s-2 (x),PPR.sub.s (x)={Q. sub.s-1 (x). multidot.R.sub.s-1 (x)}+R.sub.s-2 (x),PP andP PI Q.sub.s-1 (x)=R.sub.s-2 (x)/R.sub.s-1 (x)P Pwherein T.sub.s (x), R.sub.s (x), and Q.sub.s-1 (x) are polynomials representing the position of the error, its value, and a provisional value respectively, and R.sub.s (x) and T.sub.s (x) can be normalized with a minimal coefficient T.sub.s (0)=&dgr; such that R(x)=R. sub.s (xi/&dgr; and T(x)=T.sub.s (x)/&dgr;. Another stage detects error positions X. sub.k and values Y.sub.k by conducting a Chien zero-root search in conjunction with ##EQU1## wherein T'(X.sub.k) is the first derivative of T at a place x.sub.k. Another stage uses the accordingly calculated error positions X.sub.k and values Y.sub.k to correct signal- duration matched data words in a currently occurring Reed-Solomon coded block. when the two counts are equal. An exclusive-OR stage has one input terminal which receives the error value at the top of the fourth stack in accordance with the control signal, another input terminal which receives the signal- duration matched data words, and an output terminal that emits corrected data words.]