Linear feedback shift register in a programmable gate array

• US 6,181,164 B1
• Filed: 05/13/1999
• Issued: 01/30/2001
• Est. Priority Date: 01/08/1999
• Status: Expired due to Term

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Miller, Andrew J.
• Primary Examiner(s): Nelms, David
• Assistant Examiner(s): Lam, David
• Application Number:
  US09/312,369
• Time in Patent Office: 628 Days
• Field of Search: 326/46, 326/40, 326/41, 326/37, 326/38, 326/39, 371/43.1, 371/37.7
• US Class Current: 326/46
• CPC Class Codes: H03K 19/1736 in which the wiring can be modified

Abstract

A linear feedback shift register in a programmable gate array. A first lookup table is configured as a shift register having n selectable taps and a shift-input. A second lookup table is configured as a parity generator and has inputs coupled to the n selectable taps and an output coupled to the shift-input of the shift register.

Claims

1. A linear feedback shift register in a programmable gate array, comprising:

a first lookup table configured as a shift register having n selectable taps and a shift-input, wherein n is an integer; and

a second lookup table configured as a parity generator having inputs coupled to the n selectable taps and an output coupled to the shift-input shift register.

2. The linear feedback shift register of claim 1, wherein:

the first lookup table also implements a multiplexer having an output and inputs coupled to the n selectable taps, and the shift register operable at a shift frequency at which data are shifted responsive to a first clock frequency, and the n taps are selectable at a select-frequency responsive to a second clock frequency that is m×

the first clock frequency, wherein m is an integer; and

the second lookup table is configured as an XOR function generator having at least two inputs and an output, wherein one of the inputs is coupled to the output of the multiplexer; and

further comprising

a flip-flop having a data input coupled to the output of the parity generator, an output coupled to an input of the XOR function generator, and clocked at the second clock frequency.

3. The linear feedback shift register of claim 2, wherein the second lookup table is further configured as a multiplexer having inputs coupled to receive reset-data and to the output of the XOR function generator, a selector input, and an output coupled to the data input of the shift register.

4. The linear feedback shift register of claim 1, further comprising a multiplexer having inputs coupled to receive reset-data and to the output of the XOR function generator, a selector input, and an output coupled to the data input of the shift register.

5. The linear feedback shift register of claim 1 having n-stages and m taps, further comprising a plurality of lookup tables, each implementing a respective shift register coupled to a respective n:

1 multiplexer and having a shift input coupled to the output of the parity generator, wherein a total of m lookup tables implement the shift registers and multiplexers, wherein m is an integer.

6. The linear feedback shift register of claim 5, wherein the n:

1 multiplexers have respective sets of selection inputs coupled to a plurality of programmable selection elements.

7. The linear feedback shift register of claim 5, wherein the second lookup table is configured to generate an XOR function of the m taps.

8. The linear feedback shift register of claim 5, further comprising a multiplexer having inputs coupled to receive reset-data and to the output of the parity generator, a selector input, and an output coupled to the data inputs of the shift registers.

9. The linear feedback shift register of claim 1, wherein the first lookup table comprises:

a plurality of memory cells, each having a respective input and output, wherein the input of a first one of the memory cells is coupled to the output of the parity generator, and the memory cells are serially coupled one to another; and

a multiplexer coupled to outputs of the memory cells.

10. The linear feedback shift register of claim 9, wherein the serial coupling of the memory cells is programmable.

11. An n-stage linear feedback shift register with m taps in a programmable gate array, comprising:

m n-stage shift registers, each shift register having n outputs and a respective data input, wherein m and n are integers;

m n;

1 multiplexers having data inputs respectively coupled to the outputs of the n-stage shift registers, each multiplexer having log n selection inputs, wherein the shift registers and multiplexers are implemented with respective look-up tables in the programmable gate array; and

a parity generator having inputs coupled to outputs of the multiplexers and having an output coupled to the data inputs of the shift registers.

12. The linear feedback shift register of claim 11, further comprising a plurality of programmable selection elements coupled to respective ones of the selection inputs of the multiplexers.

13. The linear feedback shift register of claim 12, further comprising a multiplexer having a first input coupled to receive output of the parity generator, a second input coupled to receive reset-data, a selector input, and an output coupled to the data inputs of the shift registers.

14. The linear feedback shift register of claim 11, further comprising a multiplexer having a first input coupled to receive output of the parity generator, a second input coupled to receive reset-data, a selector input, and an output coupled to the data inputs of the shift registers.

15. An n-stage linear feedback shift register with m taps in a programmable gate array, wherein n and m are integers, comprising:

an n-stage shift register having n outputs, a data input, and operable at a first frequency at which data are shifted responsive to a first clock frequency;

an n;

1 multiplexer having data inputs respectively coupled to the outputs of the shift register, log n selection inputs, and operable at a second frequency at which the inputs are selectable responsive to a second clock frequency that is m×

the first clock frequency, the shift register and multiplexer implemented with a look-up table in the programmable gate array;

a lookup table configured as an XOR function generator and having a first input coupled to output of the multiplexer, a second input, and an output coupled to the data input of the shift register; and

a flip-flop having a data input coupled to the output of the XOR function generator, an output coupled to the second input of the XOR function generator, and clocked at the second clock frequency.

16. The linear feedback shift register of claim 15, further comprising a multiplexer having a first input coupled to receive output of the XOR function generator, a second input coupled to receive reset-data, a selector input, and an output coupled to the data inputs of the shift registers.

17. A Gold-code generator comprising:

a first set of m₁ n-stage shift registers, each shift register having n outputs and a respective data input, wherein m₁ and n are integers;

a first set of m₁ n;

1 multiplexers having data inputs respectively coupled to the outputs of the n-stage shift registers, each multiplexer having log n selection inputs, wherein the first sets of shift registers and multiplexers implemented with respective look-up tables in the programmable gate array; and

a first parity generator having inputs coupled to outputs of the first set of multiplexers and having an output coupled to the data inputs of the first set of shift registers;

a second set of m₂ n-stage shift registers, each shift register having n outputs and a respective data input, wherein m₂ is an integer;

a second set of m₂ n;

1 multiplexers having data inputs respectively coupled to the outputs of the second set of n-stage shift registers, each multiplexer having log n selection inputs, wherein the second sets of shift registers and multiplexers are implemented with respective look-up tables in the programmable gate array;

a second parity generator having inputs coupled to outputs of the second set of multiplexers and having an output coupled to the data inputs of the second set of shift registers; and

an XOR gate having a first input coupled to an output of one of the first set of n;

1 multiplexers, a second input coupled to an output of one of the second set of n;

1 multiplexers and an output that provides the Gold-code.

18. The Gold-code generator of claim 17, further comprising:

a first multiplexer having a first input coupled to receive output of the first parity generator, a second input coupled to receive reset-data, a selector input, and an output coupled to the data inputs of the first set of shift registers; and

a second multiplexer having a first input coupled to receive output of the second parity generator, a second input coupled to the receive reset-data, a selector input, and an output coupled to the data inputs of the second set of shift registers.

19. The Gold-code generator of claim 18, further comprising:

a third multiplexer having a first input coupled to receive output of the XOR function generator, a second input coupled to receive reset-data, a selector input, and an output coupled to the data input of the first shift register; and

a fourth multiplexer having a first input coupled to receive output of the second XOR function generator, a second input coupled to receive reset-data, a selector input, and an output coupled to the data input of the first shift register.

20. A Gold-code generator, where m₁, m₂, and n are integers, comprising:

a first n-stage shift register having n outputs, a data input, and a first frequency at which data are shifted responsive to a first clock frequency, wherein n is an integer;

a first n;

1 multiplexer having data inputs respectively coupled to the outputs of the shift register, log n selection inputs, and a second frequency at which the inputs are selectable responsive to a second clock frequency that is m₁×

the first clock frequency, the shift register and multiplexer implemented with a first look-up table in the programmable gate array, wherein m₁ is an integer;

a second lookup table configured as an XOR function generator and having a first input coupled to output of the multiplexer, a second input, and an output coupled to the data input of the first shift register;

a first flip-flop having a data input coupled to the output of the second lookup table, an output coupled to the second input of the second lookup table, and clocked at the second clock frequency;

a second n-stage shift register having n outputs, a data input, and a first frequency at which data are shifted responsive to the first clock frequency;

a second n;

1 multiplexer having data inputs respectively coupled to the outputs of the second shift register, log n selection inputs, and a third frequency at which the inputs are selectable responsive to a second clock frequency that is m₂×

the first clock frequency, the second shift register and second multiplexer implemented with a third look-up table in the programmable gate array, wherein m₂ is an integer;

a fourth lookup table configured as an XOR function generator and having a first input coupled to output of the second multiplexer, a second input, and an output coupled to the data input of the second shift register;

a second flip-flop having a data input coupled to the output of the fourth lookup table, an output coupled to the second input of the fourth lookup table, and clocked at the second clock frequency; and

an XOR gate having inputs coupled to the outputs of the first and second multiplexers and an output that provides the Gold-code.