Error control apparatus and method using cyclic code

• US 6,516,439 B2
• Filed: 07/06/2001
• Issued: 02/04/2003
• Est. Priority Date: 11/15/1999
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Kodama, Yukio, Kyomoto, Takeshi
• Primary Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US09/899,062
• Publication Number:
  US 20010056563A1
• Time in Patent Office: 578 Days
• Field of Search: 714/758, 714/746, 714/701, 714/716, 714/750, 714/752, 714/754, 714/759, 714/761, 714/774, 714/786, 714/794, 714/797, 714/796, 714/795, 375/262, 375/259, 375/341, 341/143
• US Class Current: 714/758
• CPC Class Codes: H03M 13/091 Parallel or block-wise CRC computation
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/2703 the interleaver involving at least two directions
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes

Abstract

An error control apparatus includes: a deinterleaver for deinterleaving data of a predetermined number of bits coded by predetermined cyclic codes, which is to be interleaved in accordance with a predetermined interleaving order; a first cyclic code checking circuit for receiving an output of the deinterleaver and making a cyclic code check on the data of the predetermined number of bits by a check system corresponding to a coding system of the cyclic code; and a second cyclic code checking circuit for receiving an output of the deinterleaver and making a cyclic code check on the data of the predetermined number of bits by a check system corresponding to the coding system of the cyclic code simultaneously with the cyclic code check by the first cyclic code checking circuit in substantially the same time while canceling an interleave effect by the deinterleaver.

Claims

1. An error control circuit including:

a deinterleaver for deinterleaving data of a predetermined number of bits coded by predetermined cyclic codes and to be interleaved in accordance with a predetermined interleave order;

a first cyclic code checking circuit for receiving an output of said deinterleaver and conducting a cyclic code check on said data of the predetermined number of bits by a check system corresponding to a coding system of said cyclic code; and

a second cyclic code checking circuit for receiving an output of said deinterleaver and conducting a cyclic code check on said data of the predetermined number of bits by a check system corresponding to the coding system of said cyclic code simultaneously with the cyclic code check by said first cyclic code checking circuit in substantially the same time while canceling an interleave effect by said deinterleaver.

2. The error control circuit according to claim 1, wherein said second cyclic code checking circuit includes:

an input data line connected to an output of said deinterleaver;

a data bus including data signal lines of the number corresponding to the maximum degree of a polynomial of generating said cyclic code;

a plurality of partial check bit calculating circuits each connected to said input data line and said data signal line, which are provided in correspondence with the maximum degree of a polynomial of generating said cyclic code, for calculating a check bit in a predetermined position of said cyclic code by executing a predetermined computation sequence determined by the coding system of said cyclic code and a system of said interleave on data supplied from said input data line and data on said data signal line; and

computation control means connected to each of said plurality of partial check bit calculating circuits, for controlling the computation sequence to be performed by said partial check bit calculating circuits.

3. The error control circuit according to claim 2, each of said plurality of partial check bit calculating circuits includes:

computating means connected to said computation control means, said input data line, and said data bus, for executing a computation determined by a computation instruction signal supplied from said computation control means on data on said input data line and data on a predetermined data line on said data bus;

data holding means having an input connected to an output of said computating means and an output connected to a predetermined data line on said data bus, for holding data outputted from said computating means and outputting the data onto said predetermined data line; and

computation result holding means connected to an output of said data holding means, for executing a computation using 2 as a modulus between data held by itself and an output of said data holding means each time computations of the number corresponding to a number obtained by dividing said predetermined number of bits by the number of stages of said interleave are finished.

4. The error control circuit according to claim 3, wherein said computating means can execute clock cycle computations determined by said generation polynomial, of only the number of kinds corresponding to the number of interleave stages of said interleave.

5. The error control circuit according to claim 4, wherein said computation designation signal designates any of said clock cycle computations.

6. The error control circuit according to claim 1, wherein said cyclic code is a 16-bit CRC code.

7. The error control circuit according to claim 1, wherein said interleave is 16-stage interleave.

8. An error control method including:

a step of deinterleaving data of a predetermined number of bits coded by predetermined cyclic codes and to be interleaved in accordance with a predetermined interleaving order;

a step of receiving data deinterleaved in said deinterleaving step, and conducting a first cyclic code check on said data of the predetermined number of bits by a check system corresponding to a coding system of said cyclic code; and

a step of receiving said deinterleaved data and conducting a second cyclic code check on said data of the predetermined number of bits by a check system corresponding to the coding system of said cyclic code simultaneously with the step of conducting said first cyclic code check in substantially the same time.

9. The error control method according to claim 8,

wherein said step for conducting said second cyclic code check includes:

a step of initializing a plurality of temporary cyclic check data holding means of the number corresponding to the maximum degree of a polynomial of generating said cyclic code; and

a step of calculating a check bit in each of positions of said cyclic codes by performing a computation sequence made by a plurality of clock cycle computations determined by a coding system of said cyclic code and said interleave system on data deinterleaved in said deinterleaving step while using said plurality of temporary cyclic check data holding means.

10. The error control method according to claim 9, wherein a number obtained by dividing said predetermined number of bits by the number of interleave stages of said interleave represents the number of data in an interleave stage,

data of said predetermined number of bits is divided into plural partial data every said number of data in said interleave stage, and

the step of calculating a check bit in said each position includes:

a step of performing a process of calculating temporary cyclic check data every said plural partial data; and

a step of obtaining cyclic check data of said predetermined number of bits by adding the temporary cyclic check data calculated every said partial data.

11. The error control method according to claim 10, wherein a plurality of kinds of clock cycle computations include computations from a 1clock-cycle computation to a maximum degree clock cycle computation corresponding to the number of stages of said interleave, and a number corresponding to each of the positions of said predetermined number of bits is designated to each of said plural partial data, and

a process of calculating said temporary cyclic check data includes:

a step of initializing plural data holding means of the number corresponding to the maximum degree of the polynomial of generating said cyclic code to a predetermined initial value;

a step of performing clock cycle computations of said maximum degree on input data and data held in said plural data holding means and repeating a process of holding a result in each of bits of said plural data holding means only by the number smaller than the number of said interleave stages by one; and

a process of performing said clock cycle computation determined by a number given to said partial data on input data and data held in said plural data holding means and holding the result in each of bits in said plural data holding means.

12. The error control method according to claim 11, wherein the step of calculating cyclic check data of said data of the predetermined number of bits includes a step of performing addition using 2 as a modulus between data held in each of said plural data holding means and data held in corresponding one of said plural temporary cycle check bit holding means and holding a result of the addition in said corresponding temporary cycle check bit holding means.

13. The error control method according to claim 8, wherein said cyclic code is a 16-bit CRC code.

14. The error control method according to claim 8, wherein said interleave is 16-stage interleave.