MULTI-CHANNEL SHIFT REGISTER

• US 3,703,705 A
• Filed: 12/31/1970
• Issued: 11/21/1972
• Est. Priority Date: 12/31/1970
• Status: Expired due to Term

• Current Assignee: Arvind M. Patel
• Original Assignee: Arvind M. Patel
• Inventors: Patel, Arvind M.
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US05/103,205
• Time in Patent Office: 691 Days
• Field of Search: 340/146.1,146.1AL,146.1BE 235/153
• US Class Current: 714/757
• 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

Abstract

A linear feedback shift register for operating on a plurality f of parallel inputs according to a generator polynomial to produce encoding and decoding is provided having a plurality r of shift register stages X0 . . . Xr 1 each corresponding to one of the terms in the generator polynomial. A first plurality of modulo 2 addition means connect, for modulo 2 addition, each of said f data bit inputs Zt f 1, Zt f 2, . . . , Zt 1, Zt of the shift register to the output of an individual one of the last f register stages Xr f, Xr f 1, . . . , Xr 1 according to the relationship Zt f 1 to Xr f, Zt f 2 to Xr f 1, . . . , Zt to Xr 1. A second plurality of modulo 2 addition means are connected to the respective inputs of the first Xr f 2 shift register stages. The first feedback connection from the output of each of said first plurality of modulo 2 addition means in said f shift register stages is connected to each of two preceding second modulo 2 addition means in accordance with the relationship Xr f 1 to X1 and X2; Xr f 2 to X2 and X3; Xr 1 to Xr f 1 and Xr f 2. A third modulo 2 addition means connects each output of the first plurality of modulo 2 addition means to the register stages determined in accordance with the non-zero coefficients in the generator polynomial.

Claims

1. A linear feedback shift register for operating on a plurality f of parallel inputs according to a generator polynomial to produce a check character comprising:

a plurality r of shift register stages X0. . . Xr 1 each corresponding to one of the terms in the generator polynomial;

a first plurality of modulo 2 addition means connecting, for modulo 2 addition, each of said f data bit inputs;

(Zt f 1, xt f 2, . . . ,Zt 1, zt of the shift register to the output of an individual one of the last f register stages;

Xr f, xr f , . . . ,xr 1 according to the relationship;

zt f 1 to xr f, zt f 2 to xr f 1, . . . ,zt to xr 1;

a second plurality of modulo 2 addition means connected to respective inputs of the first xr f 2 shift register stages;

a first feedback connection from the output of each of said first plurality of modulo 2 addition means in said f shift register stages to each of two preceding second modulo 1 addition means in accordance with the relationship;

xr f 1 to x1 and x2, xr f 2 and x3, . . . , xr 1 to xr f 1 and xr f 2; and

a third modulo 2 addition means connecting each output of said first plurality of modulo 2 addition means to the register stages determined in accordance with the non-zero coefficients in the generator polynomial.

2. A linear feedback shift register according to claim 1 wherein said second plurality of modulo 2 addition means connected to the respective inputs of the first xr f 2 shift register stages performs modulo 2 addition on the pair of said first feedback connections from adjacent pairs of said first modulo 2 addition means.

3. A linear feedback shift register according to claim 1, wherein said third modulo 2 addition means connects each output of said first plurality of modulo 2 addition means to a fourth modulo 2 addition means in the input of the register stages determined in accordance with the non-zero coefficients in the generator polynomial.

4. A linear feedback shift register according to claim 3, wherein said second plurality of modulo 2 addition means connected to the input of the first xr f 2 shift register stages has a feedback input from the third modulo 2 aDdition means determined in accordance with the non-zero coefficients in the generator polynomial thereby serving as the modulo 2 adder for the second and fourth modulo 2 addition means.

5. A linear feedback shift register according to claim 1, wherein the shift register output is taken from the output of the last f register stages:

xr f, xr f 1, . . . xr 1.

6. A linear feedback shift register according to claim 1, wherein the remainder in said shift register following a shift register operation on a message input is fed into an identical shift register used for decoding following said message utilization to thereby produce an error syndrom which should equal 0 if there is no error in the utilized message.