# US 2013/0159819 A1 · Method, apparatus and decoder for decoding cyclic code

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0159819 A1
- Document ID: US20130159819A1
- Status: Published application
- Kind: A1
- Application number: 13/705,528
- Filed: 2012-12-05
- Published: 2013-06-20
- Earliest claimed: 2011-12-19
- Assignees: International Business Machines Corporation
- Inventors: Guofan Jiang; Yufei Li; Zhi Gui Liu; Yang Liu; Fan Zhou
- Web page: https://patentgrep.com/patent/US20130159819A1

## CPC

- H03M 13/09: Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
- H03M 13/1595: {Parallel or block-wise remainder calculation}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

A method, apparatus and decoder for decoding cyclic code are proposed. The decoding method comprises: receiving a transmitted cyclic code; calculating the initial syndrome of the cyclic code; by using the initial syndrome and w prestored successive shift operators, calculating respectively w successive shift syndromes in a w-bit window of the cyclic code in parallel; and detecting/locating error in the cyclic code based on the obtained syndromes. The decoding apparatus corresponds to the above method. And the corresponding decoder is also proposed in this invention. The method, apparatus and decoder according to the invention could process the cyclic code within a window width and thus enhance decoding efficiency in parallel.

## Claims

### Claim 1

A method for decoding cyclic code, comprising:
receiving a transmitted cyclic code;
calculating the initial syndrome of the cyclic code;
by using the initial syndrome and w pre-stored successive shift operators, calculating respectively w successive shift syndromes in a w-bit window of the cyclic code in parallel; and
determining error in the cyclic code based on the obtained shift syndromes.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the window width w is a power of 2.

### Claim 3 (depends on 1)

The method according to claim 1, wherein said window width w successive shift operators are xi mod g(x), where i=1, 2, . . . , w, and g(x) is the generator polynomial of the cyclic code.

### Claim 4 (depends on 1)

The method according to claim 1, wherein said w successive shift operators are x−i mod g(x), where i=1, 2, . . . , w, and g(x) is the generator polynomial of the cyclic code.

### Claim 5 (depends on 1)

The method according to claim 1, further comprising: estimating in advance errors adjacent to the beginning and/or the end of the cyclic code.

### Claim 6 (depends on 1)

The method according to claim 1, wherein said determining error in the cyclic code based on the obtained shift syndromes comprises: obtaining all shift syndromes corresponding to the cyclic code by shifting the window, obtaining the shortest shift syndrome by comparing all the shift syndromes, and estimating error code in the cyclic code according to the shortest shift syndrome.

### Claim 7

An apparatus for decoding cyclic code, comprising:
a receiving unit, configured to receive a transmitted cyclic code;
an initial syndrome obtaining unit, configured to calculate the initial syndrome of the cyclic code;
a window processing unit, configured to, by using the initial syndrome and window width w pre-stored successive shift operators, obtain respectively in parallel window width w successive shift syndromes in a w-bit window of the cyclic code; and an error detecting and locating unit, configured to determine error in the cyclic code based on the obtained shift syndromes.

### Claim 8 (depends on 7)

The apparatus according to claim 7, wherein the window width w is a power of 2.

### Claim 9 (depends on 7)

The apparatus according to claim 7, wherein said window width w successive shift operators are xi mod g(x), where i=1, 2, . . . , w, and g(x) is the generator polynomial of the cyclic code.

### Claim 10 (depends on 7)

The apparatus according to claim 7, wherein said window width w successive shift operators are x−i mod g(x), where i=1, 2, . . . , w, and g(x) is the generator polynomial of the cyclic code.

### Claim 11 (depends on 7)

The apparatus according to claim 7, further comprising an error predicting unit, configured to estimate in advance errors adjacent to the beginning and/or the end of the cyclic code.

### Claim 12 (depends on 7)

The apparatus according to claim 7, further comprising an error estimating unit, configured to obtain all shift syndromes corresponding to the cyclic code by shifting the window, obtain the shortest shift syndrome by comparing all the shift syndromes, and estimate error code in the cyclic code according to the shortest shift syndrome.

### Claim 13

A decoder for decoding cyclic code, comprising:
a data buffer for storing received cyclic code and initial syndrome;
a parallel computing circuit, comprising w multipliers, for applying w prestored successive shift operators to the initial syndrome, and thus outputting in parallel w successive shift syndromes in a w-bit window of the cyclic code; and
an error detecting circuit, comprising a zero detecting module, for detecting the number of zeros in the syndromes and outputting error pattern based on the detecting result.

### Claim 14 (depends on 13)

The decoder according to claim 13, wherein window width w is a power of 2.

### Claim 15 (depends on 13)

The decoder according to claim 13, wherein said w successive shift operators are xi mod g(x), where i=1, 2, . . . , w, and g(x) is the generator polynomial of the cyclic code.

### Claim 16 (depends on 13)

The decoder according to claim 13, wherein said w successive shift operators are x−i mod g(x), where i=1, 2, . . . , w, and g(x) is the generator polynomial of the cyclic code.

### Claim 17 (depends on 13)

The decoder according to claim 13, further comprising an error predicting circuit, which comprises L−1 multipliers and an error detecting module, wherein the L−1 multipliers are used to apply L−1 prestored successive shift operators and thus obtain L−1 syndromes, and wherein the error detecting module estimates in advance errors adjacent to the beginning and/or the end of the cyclic code based on the L−1 syndromes, where L is the error length corresponding to the cyclic code.

### Claim 18 (depends on 17)

The decoder according to claim 17, wherein the L−1 multipliers apply the shift operators xi mod g(x) to the initial syndrome, respectively, thus obtaining L−1 syndromes, where i=1, 2, . . . , L−1, and g(x) is the generator polynomial of the cyclic code, and wherein the error detecting module determines errors adjacent to the end of the cyclic code based on the obtained L−1 syndromes.

### Claim 19 (depends on 17)

The decoder according to claim 17, wherein the L−1 multipliers apply the shift operators x−i mod g(x) to the initial syndrome, respectively, thus obtaining L−1 syndromes, where i=1, 2, . . . , L−1, and g(x) is the generator polynomial of the cyclic code, and wherein the error detecting module determines errors adjacent to the beginning of the cyclic code based on the obtained L−1 syndromes.

### Claim 20 (depends on 13)

The decoder according to claim 13, further comprising an error estimating circuit, which comprises w 1-counting modules, a plurality of comparators and a minimum counter, wherein the w 1-counting modules count the numbers of 1s in the w shift syndromes, and the plurality of comparators compare the counting of the w 1-counters, and store the shortest shift syndrome into the minimum counter.
