Method and system for decoding of binary shortened cyclic code
AssigneeHellosoft, Inc.
InventorNanda Kishore Chavali
Life of this patent
Estimating the term…
Abstract
A computationally efficient method and system for decoding shortened cyclic codes is presented. The increase in computational efficiency is achieved by improvement of the syndrome calculation step. Two embodiments of the present invention are described; the first embodiment is optimized for a hardware implementation and the second embodiment is optimized for a Digital Signal Processor (DSP) implementation. The present invention is applicable to decoding of all the binary shortened cyclic codes, including Fire codes used for Coding Scheme-1 (CS-1) for GSM.
Claims20
A method of correcting errors in a corrupted code-word, the code-word encoded using a (n−l, k−l) shortened cyclic code for b bit burst error correction, the method comprising the steps of:
- a. multiplying the corrupted code-word with a syndrome-calculation polynomial, the syndrome-calculation polynomial being the remainder left on dividing a shift polynomial xl by the generator polynomial of the shortened cyclic code;
- b. calculating a syndrome corresponding to the corrupted code-word, the syndrome being calculated as the remainder left on dividing the product of the corrupted code-word with the syndrome-calculation polynomial by the generator polynomial of the shortened cyclic code;
- c. trapping a burst error pattern using the syndrome;
- and
- d. correcting the corrupted code-word using the burst error pattern.
A method of correcting errors in a corrupted code-word, the code-word encoded using a (n−l, k−l) shortened cyclic code for b bit burst error correction, the method comprising the steps of:
- a. calculating a shortened syndrome as the remainder left on dividing the corrupted code-word by the generator polynomial of the shortened cyclic code;
- b. multiplying the shortened syndrome with a syndrome-calculation polynomial, the syndrome-calculation polynomial being the remainder left on dividing a shift polynomial xl by the generator polynomial of the shortened cyclic code;
- c. calculating a syndrome corresponding to the corrupted code-word, the syndrome being the remainder left on dividing the product of the shortened syndrome and the syndrome-calculation polynomial by the generator polynomial of the shortened cyclic code;
- d. trapping a burst error pattern using the syndrome;
- and
- e. correcting the corrupted code-word using the burst error pattern.
A system for performing error-correction on a corrupted code-word, the code-word encoded using a (n−l, k−l) shortened cyclic code for b bit burst error correction, the system comprising:
- a. a division circuit calculating a shortened syndrome using the corrupted code-word and the generator polynomial of the shortened cyclic code;
- b. a multiplication and division circuit calculating the syndrome using the shortened syndrome, the coefficients of a syndrome-calculation polynomial and the coefficients of the generator polynomial of the shortened cyclic code;
- c. a Zero Condition Checker checking whether all the last n−k−b bits of the contents of the multiplication and division circuit are zero;
- d. a Buffer Stage storing the first k−l bits of the corrupted code-word;
- e. a error-correcting modulo-2 adder correcting the contents of the Buffer Stage using the contents of the multiplication and division circuit;
- and
- f. a Second Control Logic synchronizing the division circuit, the multiplication and division circuit, the Zero Condition Checker, the Buffer Stage and the error-correcting modulo-2 adder.
Dependencies are inferred from the claim text.