Burst error correction code

Claim 2

An error correcting system for correcting bursts of errors in a bit stream having an arbitrary burst length up to B bits long, said error correcting system having an encoder for generating parity bits from information bits applied thereto and applying said information bits and said parity bits to utilization means, said encoder comprising: information bit sample and storage means having B + 1 stages for receiving and storing B + 1 successive information bits; parity bit generating means connected to the first and last of said B + 1 stages of said information bit sample and storage means, said parity bit generating means including modulo 2 adder means for taking the modulo 2 sum of the information bits stored in said first and last stages of said information bit sample and storage means to thereby generate a parity bit at an output thereof associated with the information bits stored in said first and last stages of said information bit sample and storage means; parity bit sample and storage means having 2B + 1 stages for receiving and storing 2B + 1 successive parity bits, and and input and an output, said input of said parity bit sample and storage means being coupled to said output of said modulo 2 adder means; switch means connected to said information bit sample and storage means and the output of said parity bit sample and storage means for alternately transferring information and parity bits respectively therefrom to said utilization means; and clock means connected to said information bit sample and storage means and said parity bit sample and storage means for successively shifting said information bits and said parity bits between successive stages of said information bit sample and storage means and said parity bit sample and storage means, respectively, said clock means being further connected to said switch means, said switch means being responsive to said clock means for applying one information bit and one parity bit to said utilization means between each shift of information in said information bit and said parity bit sample and storage means.

Claim 3

An error correcting system as recited in claim 1 wherein said switch means is connected to the first stage of said B + 1 stages of said information bit sample and storage means and to the output of said parity bit sample and stage means, said last mentioned output being connected to the last stage of said parity bit sample and storage means.

Claim 4

An error correcting system as recited in claim 1 further including a decoder comprising: means for receiving said information bits and said parity bits; second information bit sample and storage means having at least B + 1 stages for storing at least B + 1 received information bits having an input coupled to said receiving means, and an output; syndrome bit generating means having inputs and an output, said inputs being connected to the last stage of said B + 1 stages of said second information bit sample and storage means, to the one of said last mentioned B + 1 stages precedent said last mentioned last stage by B stages, and to said receiving means, said syndrome bit generating means including second modulo 2 adder means for taking the modulo 2 sum of the received information bits stored in the stages connected to said syndrome bit generating means and a received parity bit associated therewith to thereby generate a syndrome bit associated with said last mentioned stored information bits and the parity bit associated therewith at said output; syndrome bit sample and storage means having B + 1 stages for storing B + 1 syndrome bits, said syndrome bit sample and storage means having a first stage thereof coupled to the output of said second modulo 2 adder means and a last stage; correction signal generating means having inputs connected to the first and last stages of said B + 1 stages of said syndrome bit sample and storage means, and an output, said correction signal generating means being responsive to the syndrome bits stored in the stages connected thereto for providing a correction signal at the output thereof only when both of said stored syndrome bits have the same predetermined value; and correcting means connected to the output of said second information bit sample and storage means and the output of said correction signal generating means for correcting information bits present at the output of said second information bit sample and storage means in response to the correction signal from said correction signal generating means.

Claim 5

An error correcting system as recited in claim 3 further including delay means connected to said receiving means and said second information bit sample and storage means for delaying the received information bits applied to said second information bit sample and storage means.

Claim 6

An error correcting system as recited in claim 4 wherein said delay means includes delay sample and storage means having 2B - 1 stages.

Claim 7

An error correcting system as recited in claim 3 wherein said second information bit sample and storage means includes 3B stages for storing 3B received information bits.

Claim 8

An error correcting system as recited in claim 6 further including second clock means connected to said second information bit sample and storage means and said syndrome bit sample and storage means for successively shifting said received information bits and said syndrome bits between successive stages of said second information bit sample and storage means and said syndrome bit sample and storage means, respectively.

Claim 9

In an error correcting system for correcting bursts of errors in a bit stream having an arbitrary burst length up to B bits long, an encoder for generating parity bits from information bits applied thereto comprising: information bit sample and storage means having B + 1 stages for serially receiving and storing said information bits, said information bit sample and storage means having a first stage and a last stage; means connected to said first stage of said information bit sample and storage means for applying each information bit thereto for storage therein; clock means connected to said information bit sample and storage means for sequentially shifting each information bit through said B + 1 stages from said first stage to said last stage thereof; modulo 2 adder means connected to the first and last stages of said information bit sample and storage means for taking the modulo 2 sum of the information bits stored therein to thereby generate a parity bit in response to each pair of information bits stored in the first and last stages of said information bit sample and storage means; parity bit sample and storage means having 2B + 1 stages for serially receiving and storing said parity bits, said parity bit sample and storage means having a first stage connected to said modulo 2 adder means and a last stage, said parity bit sample and storage means being further coupled to said clock means and responsive thereto for sequentially shifting each parity bit through said 2B + 1 stages from said first stage to said last stage thereof; and switch means having first and second input terminals and an output terminal, said first input terminal being connected to the first stage of said information bit sample and storage means and said second terminal being connected to the last stage of said parity bit sample and storage means, said switch means being further coupled to said clock means and responsive thereto for alternately coupling said first stage of said information bit sample and storage means and said last stage of said parity bit sample and storage means to said output terminal.

Claim 10

In an error correcting system for correcting bursts of errors in a bit stream having an arbitrary burst length up to B bits long, an encoder for generating parity bits from information bits applied thereto comprising: information bit sample and storage means having B + 1 stages for serially receiving and storing said information bits, said information bit sample and storage means having a first stage and a last stage; means connected to said first stage of said information bit sample and storage means for applying each information bit thereto for storage therein; clock means connected to said information bit sample and storage means for sequentially shifting each information bit through said B + 1 stages from said first stage to said last stage thereof; modulo 2 adder means connected to the first and last stages of said information bit sample and storage means for taking the modulo 2 sum of the information bits stored therein to thereby generate a parity bit in response to each pair of information bits stored in the first and last stages of said information bit sample and storage means; parity bit sample and storage means having 2B + 1 stages for serially receiving and storing said parity bits, said parity bit sample and storage means having a first stage connected to said modulo 2 adder means and a last stage, said parity bit sample and storage means being further coupled to said clock means and responsive thereto for sequentially shifting each parity bit through said 2B + 1 stages from said first stage to said last stage thereof; and switch means having first and second input terminals and an output terminal, said first input terminal being connected to the first stage of said information bit sample and storage means and said second terminal being connected to the last stage of said parity bit sample and storage means, said switch means being further coupled to said clock means and responsive thereto for alternately coupling said first stage of said information bit sample and storage means and said last stage of said parity bit sample and storage means to said output terminal.

Claim 11

In an error correcting system as recited in claim 8, said information bit sample and storage means and said parity bit sample and storage means each include a shift register having B + 1 stages and 2B + 1 stages, respectively.

Claim 12

In an error correcting system for correcting bursts of errors having an arbitrary burst length up to B bits long, a decoder for extracting and correcting information bits from a bit stream having information and parity bits, said decoder comprising: means for receiving said information bits and said parity bits; information bit sample and storage means having at least B + 1 stages, said information bit sample and storage means having a first stage coupled to said receiving means for receiving said information bits and a last stage; syndrome bit generating means having inputs and an output, said inputs being connected to the last stage of said information bit sample and storage means, to one of said B + 1 stages precedent said last stage by B stages and to said receiving means, said syndrome bit generating means including modulo 2 adder means for taking the modulo 2 sum of the received information bits stored in the stages connected to said syndrome bit generating means and a received parity bit associated therewith to thereby generate a syndrome bit in response to each received parity bit and the stored information bits associated therewith at said output; syndrome bit sample and storage means having B + 1 stages, said syndrome bit sample and storage means having a first stage connected to the output of said syndrome bit generating means for receiving said syndrome bits and a last stage; correction signal generating means having inputs connected to said last stage of syndrome bit sample and storage means and to the one of said last mentioned B + 1 stages precedent said last mentioned last stage by B stages, said correction signal generating means being responsive to the syndrome bits stored in the stages connected thereto for providing a correction signal at the output thereof only when both of said stored syndrome bits have the same predetermined value; correcting means connected to the last stage of said information bit sample and storage means and the output of said correction signal generating means for correcting information bits received from said information bit sample and storage means in response to the correction signal from said correction signal generating means; and clock means connected to said information bit sample and storage means and said syndrome bit sample and storage means for sequentially shifting each of said information bits and said syndrome bits, respectively, through each of said respective sample and storage means from said respective first stage to said respective last stage thereof.

Claim 13

In an error correcting system for correcting bursts of errors having an arbitrary burst length up to B bits long, a decoder for extracting and correcting information bits from a bit stream having information and parity bits, said decoder comprising: means for receiving said information bits and said parity bits; information bit sample and storage means having at least B + 1 stages, said information bit sample and storage means having a first stage coupled to said receiving means for receiving said information bits and a last stage; syndrome bit generating means having inputs and an output, said inputs being connected to the last stage of said information bit sample and storage means, to one of said B + 1 stages precedent said last stage by B stages and to said receiving means, said syndrome bit generating means including modulo 2 adder means for taking the modulo 2 sum of the received information bits stored in the stages connected to said syndrome bit generating means and a received parity bit associated therewith to thereby generate a syndrome bit in response to each received parity bit and the stored information bits associated therewith at said output; syndrome bit sample and storage means having B + 1 stages, said syndrome bit sample and storage means having a first stage connected to the output of said syndrome bit generating means for receiving said syndrome bits and a last stage; correction signal generating means having inputs connected to said last stage of syndrome bit sample and storage means and to the one of said last mentioned B + 1 stages precedent said last mentioned last stage by B stages, said correction signal generating means being responsive to the syndrome bits stored in the stages connected thereto for providing a correction signal at the output thereof only when both of said stored syndrome bits have the same predetermined value; correcting means connected to the last stage of said information bit sample and storage means and the output of said correction signal generating means for correcting information bits received from said information bit sample and storage means in response to the correction signal from said correction signal generating means; and clock means connected to said information bit sample and storage means and said syndrome bit sample and storage means for sequentially shifting each of said information bits and said syndrome bits, respectively, through each of said respective sample and storage means from said respective first stage to said respective last stage thereof.

Claim 14

In an error correcting system as recited in claim 10 wherein said information bit sample and storage means has 3B stages.

Claim 15

In an error correcting system as recited in claim 11 wherein each of said information bit sample and storage means and said syndrome bit sample and storage means includes a shift rEgister.

Claim 16

In an error correcting system as recited in claim 12 wherein said correction signal generating means includes an AND gate.

Claim 17

In an error correcting system as recited in claim 13 wherein said correcting means includes a modulo 2 adder.

Claim 18

In an error correcting system as recited in claim 10 wherein the output of said correction signal generating means is further coupled to the first stage of said syndrome bit sample and storage means, said syndrome bit sample and storage means being responsive to said correction signal to change the value of the syndrome bit stored in said last mentioned stage.