Pseudo-random bit sequence generator

• US 20100287224A1
• Filed: 07/01/2009
• Published: 11/11/2010
• Est. Priority Date: 05/07/2009
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Avalon Microelectronics, Inc. (Intel Corporation)
• Inventors: Yan, Junjie
• Granted Patent: US 8,745,113 B2
• Time in Patent Office: Days
• 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, said plurality of independent datapath stages each comprising b-bits,

(b) one or more of a plurality of linear feedback shift registers for each of said plurality of independent datapath stages, said linear feedback shift registers comprising a plurality of flip-flops, wherein each of said plurality of flip-flops are serially connected via a plurality of exclusive-or gates;

(c) one or more of a plurality of combinational logic elements, wherein a present state data value from one of said linear feedback shift registers is input into one or more of said combinational logic elements, whereby one or more of said combinational logic elements determines a next state data value and outputs said next state data value back to said linear feedback shift register as a new present state value;

(d) a deterministic logic element, wherein said deterministic logic element identifies a number of redundant exclusive-or gates from said plurality of exclusive-or gates, whereby said deterministic logic element removes 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 the largest number of said plurality of exclusive-or gates for data to travel through;

(e) a optimal bit-shift as determined by said deterministic logic element, 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

(f) a pseudo-random bit sequence, wherein said pseudo-random bit sequence is generated when each of said plurality of linear feedback shift registers output b-bits from the system, whereby the b-bits output from each of said plurality of linear feedback shift registers are concatenated to produce n-bit datapath output from the system each clock cycle.

2. The pseudo-random bit sequence generator of claim 1, wherein said independent datapath stages are pipeline stages.

3. The pseudo-random bit sequence generator of claim 1, wherein said datapath is output once per clock cycle, whereby said pseudo-random bit sequence is output once per clock cycle.

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

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