Linear feedback shift register

• US 5,090,035 A
• Filed: 01/22/1991
• Issued: 02/18/1992
• Est. Priority Date: 01/19/1990
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Murase, Makoto
• Primary Examiner(s): Miller, Stanley D.
• Assistant Examiner(s): Tran, Sinh N.
• Application Number:
  US07/644,259
• Time in Patent Office: 392 Days
• Field of Search: 377/64, 377/72, 377/73, 377/75, 377/76, 377/78, 377/80, 377/81
• US Class Current: 377/72
• CPC Class Codes: G01R 31/31813 Test pattern generators
• 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
• CPC Class Codes: G11C 19/00 Digital stores in which the information is moved stepwise, e.g. shift registers
• CPC Class Codes: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators

Abstract

A linear feedback shift register comprises a shift register formed of first to (n)th flipflops cascaded in such a manner that an output of a (i)th flipflop is connected to an input of a (i+1)th flipflop, where 2≦n and 1≦i≦(n-1). First to (n)th output terminals are connected to outputs of the first to (n)th flipflops, respectively, and a clock terminal connected to a clock input of each of the flipflops. First to (n-1)th multiplexors of a "1-out-of-2" type are connected at their first input to a common preset value input terminal. Second inputs of the first to (n-1)th multiplexors are connected to the outputs of the first to (n-1)th flipflops, respectively. Each of the first to (n-1)th multiplexors has a control input connected to an individual control terminal. First to (n-1)th exclusive-OR gates are cascaded in such a manner that a first input of a (n-1)th exclusive-OR gate is connected to the output of the (n)th flipflop, a first input of an (i)th exclusive-OR gate is connected to an output of an (i+1)th exclusive-OR gate, and an output of the first exclusive-OR gate is connected to an input of the first flipflop. A second input of the (i)th exclusive-OR gate is connected to an output of the (i)th multiplexor. With this arrangement, a generator polynomial generated by the linear feedback shift register can be modified by controlling the multiplexors through the individual control terminals.

Claims

1. A linear feedback shift register comprising a shift register formed of first to (n)th flipflops cascaded in such a manner that an output of a (i)th flipflop is connected to an input of a (i+1)th flipflop, where 2≦

n and 1≦

i≦

(n-1), first to (n)th output terminals connected to outputs of said first to (n)th flipflops, respectively, a clock terminal connected to a clock input of each of said flipflops, first to (n-1)th multiplexors of a "1-out-of-2" type each having a first input connected to a common preset value input terminal, said first to (n-1)th multiplexors having a second input connected to the outputs of said first to (n-1)th flipflops, respectively, to an individual control terminal, and a first set of exclusive-OR gates composed of first to (n-1)th exclusive-OR gates cascaded in such a manner that a first input of a (n-1)th exclusive-OR gate is connected to the output of the (n)th flipflop, a first input of an (i)th exclusive-OR gate is connected to an output of an (i+1)th exclusive-OR gate, and an output of the first exclusive-OR gate is connected to an input of the first flipflop, a second input of the (i)th exclusive-OR gate being connected to an output of the (i)th multiplexor, whereby a generator polynomial generated by the linear feedback shift register can be modified by controlling said multiplexors through said individual control terminals.

2. A linear feedback shift register claimed in claim 1 further including a second set of exclusive-OR gates composed of first to (n)th exclusive-OR gates arranged in such a manner that an output of an (i)th exclusive-OR gate of said second set of exclusive-OR gates is connected to the input of said (i)th flipflop, and a first input of the (i)th exclusive-OR gate of said second set of exclusive-OR gates is connected to receive an individual input signal, a second input of the first exclusive-OR gate of said second set of exclusive-OR gates being connected to receive the output of said first exclusive-OR gate of said first set of exclusive-OR gates, and a second input of the (i+1)th exclusive-OR gate of said second set of exclusive-OR gates being connected to receive the output of said (i)th flipflop.

3. A linear feedback shift register claimed in claim 2 wherein said first input of each (i)th exclusive-OR gate of said second set of exclusive-OR gates is connected to an output of a first AND gate having a first input connected to receive said individual input signal and a second input connected in common to a first control terminal.

4. A linear feedback shift register claimed in claim 3 wherein said second input of each (i)th exclusive-OR gate of said second set of exclusive-OR gates is connected to an output of a second AND gate having a first input connected in common to a second control terminal, said output of the (i)th flipflop being connected to a second input of said second AND gate whose output is connected to said second input of each (i+1)th exclusive-OR gate of said second set of exclusive-OR gates connected to the input of the (i+1)th flipflop, and the second input of said second AND gate whose output is connected to said second input of each first exclusive-OR gate of said second set of exclusive-OR gates connected to the input of the first flipflop being connected to receive the output of said first exclusive-OR gate of said first set of exclusive-OR gates.

5. A linear feedback shift register claimed in claim 4 wherein the second input of said second AND gate whose output is connected to said second input of each first exclusive-OR gate of said second set of exclusive-OR gates connected to the input of the first flipflop is connected to an output of a second multiplexor having a first input connected to the output of said first exclusive-OR gate of said first set of exclusive-OR gates, a second input of said second multiplexor being connected to a shift input and a control input of said second multiplexor being connected to a third control terminal.

6. A linear feedback shift register claimed in claim 5 further including an OR gate having first and second inputs connected to said first and second control terminals, respectively, and a third AND gate having a first input connected to an output of said OR gate and a second input connected to said clock terminal, an output of said third AND gate being connected in common to said clock input of each of said flipflop.

7. A linear feedback shift register claimed in claim 6 further including a second shift register of (n-1) stages having a serial input connected to said shift input, an output of each stage of said second shift register being connected to said control input of a corresponding multiplexor.

8. A linear feedback shift register claimed in claim 7 wherein said serial input of said second shift register is connected to an output of a fourth AND gate having a first input connected to said clock terminal and a second input connected to the output of said OR gate through an inverter.