Decoding method and apparatus for cyclic codes

Claim 1

In an apparatus for decoding a cyclic code generated by a generator polynomial ##EQU21## (where P i (x) is a m i -order irreducible polynomial) including 0-th to l-th feedback shift registers corresponding to the terms (x c +1) and P i (x), an error detecting circuit for detecting coincidence of a predetermined number of low order bits of said 0-th to l-th feedback shift registers and for detecting an all-zero condition of the high order bits of said 0-th to l-th feedback shift registers, said predetermined number being a minimum one of the numbers of bits (c, m 1 , m 2 , . . . m l ) of said feedback shift registers, said 0-th feedback shift register having an output terminal thereof connected to an input terminal thereof, and said 1st to l-th feedback shift registers each having an output terminal thereof connected to an input terminal thereof and having exclusive OR gates inserted between stages determined by the associated irreducible polynomial, said exclusive OR gates each receiving the output of the associated feedback shift register as one input thereto and said 0-th to l-th feedback shift registers having data input terminals at the b-th stage, where b is the minimum numbers of bits (c, m 1 , m 2 , . . . m l ) of said feedback shift registers; a method for decoding said cyclic code for correcting a single burst error by shifting said 0-th to l-th feedback shift registers until said error detecting circuit detects the coincidence and all-zero condition, comprising the steps of: shifting at least one of said 0-th to l-th feedback shift registers a predetermined number of times; and after said predetermined number of shifting, shifting said 0-th to l-th feedback shift registers simultaneously until said error detecting circuit detects the coincidence and all zero condition.

Claim 3

An apparatus for decoding a cyclic code generated by a generator polynomial ##EQU22## (where P i (x) is a m i -order irreducible polynomial) comprising: -th to l-th feedback shift registers corresponding to the terms (x c +1) and P i (x), said 0-th feedback shift register having an output terminal thereof connected to an input terminal thereof, and said 1st to l-th feedback shift registers each having an output terminal thereof connected to an input terminal thereof and having exclusive OR gates inserted between stages determined by the associated irreducible polynomial, said exclusive OR gates each receiving the output of the associated feedback shift register as one input thereto and said 0-th to l-th feedback shift registers having data input terminals at the b-th stage, where b is the minimum numbers of bits (c, m 1 , m 2 , . . . m l ) of said feedback shift registers; an error detecting circuit for detecting coincidence of a predetermined number of low order bits of said 0-th to l-th feedback shift registers and for detecting an all-zero condition of the high order bits of said 0-th to l-th feedback shift registers, said predetermined number being a minimum one of the numbers of bits (c, m 1 , m 2 , . . . m l ) of said feedback registers; a first controller for shifting at least one of said 0-th to l-th feedback shift registers a predetermined number of times; and a second controller for shifting said 0-th to l-th feedback shift registers simultaneously after said predetermined number of times of shifting by said first controller until said error detecting circuit detects the coincidence and all-zero condition.

Claim 4

An apparatus for decoding a cyclic code generated by a generator polynomial ##EQU22## (where P i (x) is a m i -order irreducible polynomial) comprising: -th to l-th feedback shift registers corresponding to the terms (x c +1) and P i (x), said 0-th feedback shift register having an output terminal thereof connected to an input terminal thereof, and said 1st to l-th feedback shift registers each having an output terminal thereof connected to an input terminal thereof and having exclusive OR gates inserted between stages determined by the associated irreducible polynomial, said exclusive OR gates each receiving the output of the associated feedback shift register as one input thereto and said 0-th to l-th feedback shift registers having data input terminals at the b-th stage, where b is the minimum numbers of bits (c, m 1 , m 2 , . . . m l ) of said feedback shift registers; an error detecting circuit for detecting coincidence of a predetermined number of low order bits of said 0-th to l-th feedback shift registers and for detecting an all-zero condition of the high order bits of said 0-th to l-th feedback shift registers, said predetermined number being a minimum one of the numbers of bits (c, m 1 , m 2 , . . . m l ) of said feedback registers; a first controller for shifting at least one of said 0-th to l-th feedback shift registers a predetermined number of times; and a second controller for shifting said 0-th to l-th feedback shift registers simultaneously after said predetermined number of times of shifting by said first controller until said error detecting circuit detects the coincidence and all-zero condition.

Claim 5

An apparatus for decoding a Fire code comprising: first and second feedback shift registers for receiving an input code, said first feedback shift register having an output terminal thereof connected to an input terminal thereof and having an exclusive OR gate inserted between stages thereof, said second feedback shift register having an output terminal thereof connected to an input terminal thereof and having an exclusive OR gate inserted between stages thereof, said exclusive OR gate receiving the output of said second feedback shift register as one input thereto; an error detecting circuit for detecting coincidence of the lower c bits of said first and second feedback shift registers and for detecting an all-zero condition of the high (c-m) bits of said second feedback shift register; a first controller for shifting one of said first and second feedback shift registers a predetermined number of times; and a second controller for shifting said first and second feedback shift registers simultaneously after the shifting by said first controller until said error detecting circuit detects the coincidence and all-zero condition, whereby a burst error is detected.

Claim 6

An apparatus for decoding a Fire code comprising: first and second feedback shift registers for receiving an input code, said first feedback shift register having an output terminal thereof connected to an input terminal thereof and having an exclusive OR gate inserted between stages thereof, said second feedback shift register having an output terminal thereof connected to an input terminal thereof and having an exclusive OR gate inserted between stages thereof, said exclusive OR gate receiving the output of said second feedback shift register as one input thereto; an error detecting circuit for detecting coincidence of the lower c bits of said first and second feedback shift registers and for detecting an all-zero condition of the high (c-m) bits of said second feedback shift register; a first controller for shifting one of said first and second feedback shift registers a predetermined number of times; and a second controller for shifting said first and second feedback shift registers simultaneously after the shifting by said first controller until said error detecting circuit detects the coincidence and all-zero condition, whereby a burst error is detected.

Claim 7

A method for decoding a Fire code generated by a generator polynomial G(x)=P(x)·(x c +1), where P(x) is an m-order irreducible polynomials, and received as a received code F*(x), and for correcting a single burst error, with an apparatus including a first feedback shift register, and a second feedback shift register, said first feedback shift register having an output terminal thereof connected to an input terminal thereof and having an exclusive OR gate inserted between the stages thereof, said exclusive OR gate receiving the output of said feedback shift register as one input thereto, said second feedback shift register having an output terminal thereof connected to an input terminal thereof, and an error detecting circuit for detecting coincidence of the lower c bits of said first and second feedback shift registers and for detecting all-zero condition of high (c-m) bits of said second feedback shift registers, said method comprising the steps of: inputting the received code F*(x) in said first feedback shift register, whereby a residue obtained by dividing F*(x) by P(x) is retained in said first feedback shift register when the code F*(x) has been inputted therein, and inputting the received code F*(x) in said second feedback shift register, whereby a residue obtained by dividing F*(x) by (x c +1) is remained in said second feedback shift register when the code F*(x) has been inputted therein; shifting said first feedback shift register by γ times and shifting said second feedback register by ω times, respectively, where γ and ω are integers ω-γ=e·t-c·k e·t≦e·c- g c·k≦e·c-g t=0, 1, . . . , c k=0, 1, . . . , e t and k are not simultaneously zero e is the period of P(x) g is the length of the input code F*(x); and shifting said first and second feedback shift registers simultaneously until said error detecting circuit detects the coincidence and all-zero conditions, wherein the number of times of shifting j shows an error location information.

Claim 8

A method for decoding a Fire code generated by a generator polynomial G(x)=P(x)·(x c +1), where P(x) is an m-order irreducible polynomials, and received as a received code F*(x), and for correcting a single burst error, with an apparatus including a first feedback shift register, and a second feedback shift register, said first feedback shift register having an output terminal thereof connected to an input terminal thereof and having an exclusive OR gate inserted between the stages thereof, said exclusive OR gate receiving the output of said feedback shift register as one input thereto, said second feedback shift register having an output terminal thereof connected to an input terminal thereof, and an error detecting circuit for detecting coincidence of the lower c bits of said first and second feedback shift registers and for detecting all-zero condition of high (c-m) bits of said second feedback shift registers, said method comprising the steps of: inputting the received code F*(x) in said first feedback shift register, whereby a residue obtained by dividing F*(x) by P(x) is retained in said first feedback shift register when the code F*(x) has been inputted therein, and inputting the received code F*(x) in said second feedback shift register, whereby a residue obtained by dividing F*(x) by (x c +1) is remained in said second feedback shift register when the code F*(x) has been inputted therein; shifting said first feedback shift register by γ times and shifting said second feedback register by ω times, respectively, where γ and ω are integers ω-γ=e·t-c·k e·t≦e·c- g c·k≦e·c-g t=0, 1, . . . , c k=0, 1, . . . , e t and k are not simultaneously zero e is the period of P(x) g is the length of the input code F*(x); and shifting said first and second feedback shift registers simultaneously until said error detecting circuit detects the coincidence and all-zero conditions, wherein the number of times of shifting j shows an error location information.