Pseudo-random bit sequence generator

• US 8,745,113 B2
• Filed: 07/01/2009
• Issued: 06/03/2014
• Est. Priority Date: 05/07/2009
• Status: Expired due to Fees

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Canada Company
• Inventors: Yan, Junjie
• Primary Examiner(s): Do, Chat
• Assistant Examiner(s): JEON, JAE U
• Application Number:
  US12/458,122
• Publication Number:
  US 20100287224A1
• Time in Patent Office: 1,798 Days
• Field of Search: 708252-256
• 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 7/582 Pseudo-random number generators
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register
• CPC Class Codes: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators

Abstract

The present invention discloses a pseudo-random bit sequence (PRBS) generator which outputs the entire datapath, or entire pseudo-random bit sequence, over one single clock cycle. This is accomplished by removing redundancy, or any redundant exclusive-or gates from linear feedback shift registers; using logic to identify the critical path and optimal shift for the critical path; and dividing the datapath into several pipeline stages to increase the clock rate (i.e., transmission speed).

Claims

1. A pseudo-random bit sequence generator, comprising:

(a) a datapath comprising n-bits, wherein said datapath is divided into a plurality of independent datapath stages, each of said plurality of independent datapath stages comprising b-bits,

(b) a plurality of linear feedback shift registers, each of said plurality of linear feedback shift registers comprising a plurality of flip-flops serially connected via a corresponding plurality of exclusive-or gates;

(c) a plurality of combinational logic elements, wherein a plurality of present state data values from the plurality of linear feedback shift registers is input into the plurality of combinational logic elements, and whereby the plurality of combinational logic elements determines a plurality of next state data values and provides, during a single clock cycle, the plurality of next state data values to the plurality of said linear feedback shift registers as a plurality of new present state data values;

(d) a deterministic logic element, wherein said deterministic logic element is configured to;

identify a number of redundant exclusive-or gates from said plurality of exclusive-or gates;

remove said number of redundant exclusive-or gates by removing all even-numbered redundant exclusive-or gates from said plurality of exclusive-or gates or removing all-but-one odd-numbered redundant exclusive-or gates from said plurality of exclusive-or gates, thereby identifying a largest number of said plurality of exclusive-or gates for data to travel through;

determine an optimal bit-shift, wherein said optimal bit-shift is equivalent to the maximum number of said plurality of exclusive-or gates after said deterministic logic element has removed said number of redundant exclusive-or gates from said plurality of exclusive-or gates; and

generate a pseudo-random bit sequence when each of the plurality of linear feedback shift registers outputs one or more respective b-bits.

2. The pseudo-random bit sequence generator of claim 1, wherein at least one the plurality of independent datapath stages is a pipeline stage.

3. The pseudo-random bit sequence generator of claim 1, wherein said deterministic logic element is a software element.

4. The pseudo-random bit sequence generator of claim 1, wherein said deterministic logic element is a hardware platform.

5. A method for generating a pseudo-random bit sequence using a datapath comprising n-bits, wherein said datapath is divided into a plurality of independent datapath stages, each of said plurality of independent datapath stages comprising b-bits, the method comprising:

inputting a plurality of present state data values from a plurality of linear feedback shift registers into a plurality of combinational logic elements, wherein each of said plurality of linear feedback shift registers comprises a plurality of flip-flops serially connected via a corresponding plurality of exclusive-or gates;

determining using the plurality of combinational logic elements a plurality of next state data values and providing, during a single clock cycle, the plurality of next state data values to the plurality of said linear feedback shift registers as a plurality of new present state data values;

identifying, using a deterministic logic element, a number of redundant exclusive-or gates from said plurality of exclusive-or gates;

removing, using the deterministic logic element, said number of redundant exclusive-or gates by removing all even-numbered redundant exclusive-or gates from said plurality of exclusive-or gates or removing all-but-one odd-numbered redundant exclusive- or gates from said plurality of exclusive-or gates, thereby identifying a largest number of said plurality of exclusive-or gates for data to travel through;

determining, using the deterministic logic element, an optimal bit-shift, wherein said optimal bit-shift is equivalent to the maximum number of said plurality of exclusive-or gates after said deterministic logic element has removed said number of redundant exclusive-or gates from said plurality of exclusive-or gates; and

generating, using the deterministic logic element, a pseudo-random bit sequence when each of the plurality of linear feedback shift registers outputs one or more respective b-bits.

6. The method of claim 5, wherein at least one the plurality of independent datapath stages is a pipeline stage.

7. The method of claim 5, wherein said deterministic logic element is a software element.

8. The method of claim 5, wherein said deterministic logic element is a hardware platform.

9. The method of claim 5, wherein the plurality of combinational logic elements are configured for receiving the input plurality of present state data values, and wherein said receiving, said determining the plurality of next state data values, and said providing the plurality of next state data values are performed in an amount of time that is less than a period of a clock of the plurality of linear feedback shift registers.

10. The method of claim 5, wherein the plurality of combinational logic elements are configured to receive the input plurality of present state data values, and perform said determining the plurality of next state data values and said providing the plurality of next state data values without a clock input.

11. Pseudo-random bit sequence generation circuitry comprising:

(a) a datapath comprising n-bits, wherein said datapath is divided into a plurality of independent datapath stages, each of said plurality of independent datapath stages comprising b-bits,

(b) linear feedback shift register circuitry comprising flip-flops serially connected via a corresponding plurality of exclusive-or gates;

(c) combinational logic circuitry, wherein a plurality of present state data values from the linear feedback shift register circuitry is input into the combinational logic circuitry, and whereby the combinational logic circuitry determines a plurality of next state data values and provides, during a single clock cycle, the plurality of next state data values to the linear feedback shift register circuitry as a plurality of new present state data values;

(d) deterministic logic circuitry configured to;

identify a number of redundant exclusive-or gates from said plurality of exclusive-or gates;

remove said number of redundant exclusive-or gates by removing all even-numbered redundant exclusive-or gates from said plurality of exclusive-or gates or removing all-but-one odd-numbered redundant exclusive-or gates from said plurality of exclusive-or gates, thereby identifying a largest number of said plurality of exclusive-or gates for data to travel through;

determine an optimal bit-shift, wherein said optimal bit-shift is equivalent to the maximum number of said plurality of exclusive-or gates after said deterministic logic element has removed said number of redundant exclusive-or gates from said plurality of exclusive-or gates; and

generate a pseudo-random bit sequence when the linear feedback shift register circuitry outputs one or more respective b-bits.

12. The pseudo-random bit sequence generation circuitry of claim 11, wherein at least one the plurality of independent datapath stages is a pipeline stage.

13. The pseudo-random bit sequence generation circuitry of claim 11, wherein said deterministic logic circuitry comprises a software element.

14. The pseudo-random bit sequence generation circuitry of claim 11, wherein said deterministic logic circuitry is a hardware platform.

15. The pseudo-random bit sequence generation circuitry of claim 11, wherein the combinational logic circuitry is configured for receiving the input plurality of present state data values, and wherein said receiving, said determining the plurality of next state data values, and said providing the plurality of next state data values are performed in an amount of time that is less than a period of a clock of the plurality of linear feedback shift registers.

16. The pseudo-random bit sequence generation circuitry of claim 11, wherein the combinational logic circuitry is configured to receive the input plurality of present state data values, and perform said determining the plurality of next state data values and said providing the plurality of next state data values without a clock input.