Let be a polynomial root of the generator polynomial of a cyclic code over a finite field , viewed in an field extension. Every codeword satisfies , so a received polynomial has syndrome . A single-symbol error givesTo identify both value and position from this one syndrome, the maps must be injective over the allowed nonzero values and coordinate positions. Equivalently, the powers for distinct positions must not be proportional by a nonzero element of the base finite field. In the binary case , distinct powers suffice.
For nonbinary errors, distinct powers alone do not suffice. Over , take and two positions. Errors in position zero and in position one both evaluate to , although and are distinct. Additional syndromes or stronger conditions on the powers are then necessary.
Let a binary cyclic code of length have defining zeros of a cyclic code and , with of multiplicative order . A single error in position has error polynomial and syndromesThus and are necessary for a single-error pattern. Search the distinct powers of for ; if it is absent, this is not a single-error syndrome. Otherwise flip the unique coordinate and test membership in the full cyclic code, for example by divisibility by its entire generator polynomial of a cyclic code.
Checking only the two roots is sufficient only when they generate all defining checks, including their field conjugates. A cyclic code with additional defining roots requires those checks too. If the full membership test succeeds and the minimum Hamming distance is at least five, the corrected codeword is the unique codeword within two errors of the received word: two such codewords would be at Hamming distance at most four. The two-syndrome relation alone does not establish membership.
Articles by others on the same topic
There are currently no matching articles.