Bit sequence generator and apparatus for calculating a sub-rate transition matrix and a sub-rate initial state for a state machine of a plurality of state machines

Patent metadata

Field	Value
Publication number	US-9575726-B2
Application number	US-201013814234-A
Country	US
Kind code	B2
Filing date	Aug 3, 2010
Priority date	Aug 3, 2010
Publication date	Feb 21, 2017
Grant date	Feb 21, 2017

Abstract

A bit sequence generator for generating a bit sequence defined by a generating function and an initial state of the generating function comprising a plurality of state machines and a multiplexer. Each state machine of the plurality of state machines generates a time-interleaved bit sequence, wherein a state machine generates a bit of the time-interleaved bit sequence for a current time step based on at least one bit generated by the state machine for a preceding time step, the generating function of the bit sequence to be generated, and the initial state of the generating function and independent from a time-interleaved bit sequence generated by another state machine of the plurality of state machines. Further, a multiplexer selects successively one bit from each generated time-interleaved bit sequence in a repetitive manner to obtain the bit sequence defined by the generating function and the initial state of the generating function.

First claim

The invention claimed is:

1. A bit sequence generator comprising:
a multiplexer configured to output an output bit sequence by successively selecting a respective bit of the output bit sequence from a plurality of time-interleaved bit sequences, wherein the output bit sequence is defined by a generating function and an initial state of the generating function; and
a plurality of state machines coupled with the multiplexer and configured to generate the plurality of time-interleaved bit sequences, wherein each of the plurality of state machines is configured to generate a respective time-interleaved bit sequence of the plurality of time-interleaved bit sequence during a time step,
wherein a first state machine of the plurality of state machines is configured to generate a first time-interleaved bit sequence of the plurality of time-interleaved bit sequences by generating a respective bit of the first time-interleaved bit sequence during a corresponding time step based on a) at least one preceding bit generated by the first state machine during a preceding time step b) the generating function, and c) the initial state of the generating function, and independent from another time-interleaved bit sequence generated by another state machine of the plurality of state machines, wherein first time-interleaved bit sequence is generated in a first sub bit rate,
wherein further the first state machine comprises a serializer that is configured to: serialize a state sequence of the first respective state machine; select a respective bit of the first time-interleaved bit sequence from the state sequence; and provide the first time-interleaved bit sequence in a serial manner with an intermediate bit rate, wherein the intermediate bit rate is equal to the first sub bit rate multiplied with a first predefined number of bits of the first time-interleaved bit sequence.

2. The bit sequence generator according to claim 1 , wherein each respective time-interleaved bit sequence of the plurality of time-interleaved bit sequences comprises the first predefined number of bits.

3. The bit sequence generator according to claim 2 , wherein each respective time-interleaved bit sequence is generated in the first sub bit rate, wherein the multiplexer is configured to generate the output bit sequence with a full bit rate being equal to an integer multiple of the first sub bit rate.

4. The bit sequence generator according to claim 3 , wherein the integer multiple is equal to a product of the first predefined number and a number of state machines of the plurality of state machines.

5. The bit sequence generator according to claim 2 , wherein a respective state of each respective state machine of the plurality of state machines is defined by a respective state sequence that comprises a second predefined number of state bits, wherein each respective state sequence is generated by a respective state machine during a time step in a parallel manner, wherein each respective state sequence comprises a respective time-interleaved bit sequence.

6. The bit sequence generator according to claim 1 , wherein a second state machine of the plurality of state machines is configured to generate a second time-interleaved bit sequence of the plurality of time-interleaved bit sequences based on a first sub-rate transition matrix and a first sub-rate initial state, wherein the first sub-rate transition matrix and the first sub-rate initial state are based on the generating function and the initial state of the generating function.

7. The bit sequence generator according to claim 6 , wherein a third state machine of the plurality of state machines is configured to generate a third time-interleaved bit sequence of the plurality of time-interleaved bit sequences based on a second sub-rate transition matrix and a second sub-rate initial state, wherein the first and the second sub-rate transition matrixes are the same, and wherein the first and the second sub-rate initial states are different.

8. The bit sequence generator according to claim 1 , wherein the output bit sequence comprises a pseudorandom bit sequence.

9. The bit sequence generator according to claim 1 further comprising a circuit operable to calculate a first sub-rate transition matrix and a first sub-rate initial state for a second state machine of a plurality of state machines, wherein the circuit comprises a processor configured to: calculate a first sub-rate initial state based on the generating function, the initial state of the generating function, and a number of state machines of the plurality of state machines, and wherein the processor is further configured to calculate the first sub-rate transition based on the generating function, and the number of state machines.

10. The bit sequence generator according to claim 9 , wherein the processor is further configured to:
determine a full rate transition matrix based on the generating function;
calculate the first sub rate transition matrix based on the full rate transition matrix and the number of state machines; and
calculate the first sub-rate initial state based on the full rate transition matrix, the initial state of the generating function and the number of state machines.

11. The bit sequence generator according to claim 9 , wherein the processor is further configured to calculate a second sub-rate initial state for a third state machine of the plurality of state machines, wherein second third sub-rate initial state is different from the first sub-rate initial state.

12. The bit sequence generator according to claim 9 , wherein the processor is further configured to calculate a uniform sub-rate transition matrix for the plurality of state machines.

13. The bit sequence generator according to claim 9 , wherein the generating function comprises a polynomial function with an order of P, wherein the first sub-rate transition matrix is a square matrix with a second predefined number of rows, wherein the second predefined number is equal to, or larger than P.

14. The bit sequence generator according to claim 9 , wherein the processor is further configured to calculate the first sub-rate transition matrix according to
T =( Q N G MR Q P −1 0 N×(N−P) ),
wherein N is a number of rows of T, M is the number of state machines of the plurality of state machines, P is the order of the generating function, G is a full rate transition matrix and R is a number of bits of a bit sequence generated by the second state machine during a time step using the first sub rate transition matrix, wherein
Q N = ( e P ′ e P ′ ⁢ G M ⋮ e P ′ ⁢ G ( N - 1 ) ⁢ M ) wherein
e p ′=(0,0, . . . 0,1)ε B 1×P ,

and wherein

Q
P

=

(

e
P
′

e
P
′

⁢

G
M

Assignees

• Rivoir Jochen
• Advantest Corp

Inventors

• Rivoir Jochen

Classifications

• H03K3/64

  Generators producing trains of pulses, i.e. finite sequences of pulses · CPC title

• G06F2207/582

  Parallel finite field implementation, i.e. at least partially parallel implementation of finite field arithmetic, generating several new bits or trits per step, e.g. using a GF multiplier · CPC title

• G06F7/584 Primary

  using finite field arithmetic, e.g. using a linear feedback shift register · CPC title

• G06F7/58 Primary

  Random or pseudo-random number generators · CPC title

• H03K3/84 Primary

  Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators · CPC title