PSEUDONOISE SEQUENCE GENERATORS WITH THREE-TAP LINEAR FEEDBACK SHIFT REGISTERS

• US 3,700,869 A
• Filed: 12/04/1970
• Issued: 10/24/1972
• Est. Priority Date: 12/04/1970
• Status: Expired due to Term

• Current Assignee: Marvin Perlman
• Original Assignee: Marvin Perlman
• Inventors: Perlman, Marvin
• Primary Examiner(s): Ruggiero, Joseph F.
• Assistant Examiner(s): Gottman, James F.
• Application Number:
  US05/095,183
• Time in Patent Office: 690 Days
• Field of Search: 235/152 340/146.1AL 331/78 444/1
• US Class Current: 708/252
• CPC Class Codes: G06F 2207/581 Generating an LFSR sequence, e.g. an m-sequence; sequence may be generated without LFSR, e.g. using Galois Field arithmetic
• CPC Class Codes: G06F 2207/583 Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register

Abstract

A PN linear recurring binary sequence generator is described. It comprises a linear feedback shift register of r stages with three-tap feedback logic. The three stages which are fed back are i, j and r, wherein i<j<r. The stages i, j and r are selected to correspond to the exponents of a tetranomial which includes either an (r-1)th degree or an (r-2)th degree primitive polynominal over GF(2) as a factor. The PN sequence length is 2r 1-1 or 2r 2-1 when the shift register is properly initialized.

Claims

1. A linear feedback shift register for providing a pseudonoise linear recurring binary sequence of length 2x-1, comprising:

a shift register of r successively interconnected binary stages, each stage being in either a first binary state or a second binary state, r and x being integers with r being greater than 4, and x being equal to not less than r- 2 and not more than r1 at least all of the first (r-

     3) stages and the (r-

     1)th stage being settable initially to a binary state opposite the binary state in whiCh the rth stage is set initially; and

feedback means coupled to the ith, jth and rth stages of said shift register for providing an input to the first stage of said shift register which is a function of the modulo 2 summation of the outputs of said ith, jth and rth stages, the rth stage representing the last stage, the jth stage representing any stage except the first and the last and the ith stage representing any stage ahead of said jth stage, i, j and r being equal to the exponents of a tetranomial of degree r which includes as a factor a primitive polynomial of degree x.

2. The arrangement as recited in claim 1 wherein r is a degree selected from the group consisting of 9, 14, 15, 17, 20, 25, 27, 28, 31 and 33.

3. The arrangement as recited in claim 1 wherein x r- 1 and is equal to a degree selected from the group consisting of 8, 13, 14, 16, 19, 24, 26, 27, 30 and 32.

4. The arrangement as recited in claim 1 wherein r has a value selected of the group of values consisting of 5 through 12 and 14 through 34.

5. A feedback shift register for providing a pseudonoise linear recurring binary sequence of length 2r 1-1, comprising:

a shift register including a succession of r interconnected binary stages, where r is an integer greater than 4, each stage being in either a first binary state or a second binary state, each stage being responsive to a clock pulse to shift the binary state thereof to a succeeding stage, all of said stages except the last stage in the sequence being initially settable to said first binary state and the last stage being initially settable to said second binary state; and

means coupled to the outputs of the ith, jth and rth stages in said sequence for performing a modulo 2 summation of said outputs and for supplying the summation as an input to the first stage in said sequence, the rth stage representing the last stage, the jth stage representing any stage preceding the last stage and the ith stage representing a stage preceding the jth stage, i, j and r representing the exponents of terms of a tetranomial of degree r which is factorable to include a primitive polynomial of degree r- 1, the tetranomial being expressable as f(x) 1+ xi+xj+xr (1+ x) phi (x), wherein phi (x) is a primitive polynomial of degree r- 1.

6. The arrangement as recited in claim 5 wherein r- 1 is equal to any value in a group of values consisting of 8, 13, 14, 16, 19, 24, 26, 27, 30 and 32.

7. The arrangement as recited in claim 5 wherein r has a value selected of the group of values consisting of 5 through 12 and 14 through 34.

8. A linear feedback shift register for providing a pseudonoise linear recurring binary sequence of length 2r 2-1 comprising:

a shift register including a succession of r interconnected stages where r is an integer, each stage being in either a first binary state or a second binary state, each stage being responsive to a clock pulse to shift the binary state thereof to a succeeding stage, the rth and the (r-

     2)th stages being in said second binary state with all the other stages being in one of the two binary states; and

means coupled to the outputs of the ith, jth and rth stages of said shift register for performing a modulo 2 summation thereon and for supplying the summation as an input to the first stage of said shift register, the rth stage representing the last stage, the jth sTage representing any stage preceding the last stage and the ith stage representing a stage preceding the jth stage, i, j and r representing the exponents of terms of a tetranomial of degree r expressable as f(x) 1 + xi + xj + xr (1+ x)2 theta (x) wherein theta (x) represents a primitive polynomial of degree r- 2.

9. The arrangement as recited in claim 8 wherein said r stages are settable to an initial condition with all stages from the first stage to the (r- 3)th and the (r- 1)th stages in the same state and the (r- 2)th and the rth stages are in an opposite state.

10. The arrangement as recited in claim 9 wherein r is selected from a group of values consisting of 4, 5, 7, 9 through 13 and 15 through 34.

11. The arrangement as recited in claim 9 wherein r- 2 is equal to any value in a group of values consisting of 8, 13, 14, 16, 19, 24, 26, 27, 30 and 32.