Background
A pseudo-random sequence is a deterministic sequence with some random character, with good randomness and correlation function close to white noise, and with predictable certainty and repeatability. These characteristics make the pseudorandom sequence widely used in important technical fields such as communication, radar, navigation and cryptography. The regularity and randomness of the pseudorandom sequence make it widely used in wireless communication as a spreading code and a scrambling code.
Today's research on pseudorandom sequences falls into two broad categories: one is a multi-bit pseudo-random sequence generator. The other is a 1-bit pseudo-random sequence generator, and the pseudo-random sequences used by the spreading codes and the scrambling codes in the wireless communication are both 1 bit.
Pseudo-randomThe sequencer is determined by the characteristic polynomial and the initialization value. The pseudo-random sequence generator signature polynomial of order M is as follows: f (x) ═ 1+ g0+g1x+g2x2+…gm-1xm-1The register initial state may be any value other than all 0's. The m-sequence may be generated by an LFSR structure. giThe feedback connection of the shift register is determined. There are two structures of LFSRs. One is a Galois LFSR structure as shown in FIG. one. By rj(i) Indicating the output state of the jth D flip-flop at the ith moment. Comprises the following steps:another is a fibonacci LFSR structure, as shown in fig. 2. Likewise with rj(i) Indicating the output state of the jth D flip-flop at the ith moment. Is provided withBoth of the above two structures are serial pseudo-random sequence generator structures. The generated pseudo-random sequence is denoted as rm-1(0),rm-1(1),rm-1(2),rm-1(3),rm-1(4)…。
At present, a commonly used pseudo-random sequence generator adopts a serial linear feedback shift register architecture, but with the increase of wireless communication bandwidth, the communication rate reaches G bits/second, and the serial pseudo-random sequence generator is far from reaching such a high rate. It is important to study the pseudo-random sequence generator for any parallel operation.
Disclosure of Invention
The invention provides a design method of a parallel pseudo-random sequence generator based on an FPGA (field programmable gate array). according to a Fibonacci LFSR (Linear feedback Shift register) structure, any parallel pseudo-random sequence generator is obtained through research.
The technical scheme of the invention is as follows: and obtaining a one-step shift matrix by using the generating polynomial, performing a series of matrix operations by using MATLAB according to the one-step shift matrix and the initial value to obtain an initialization logic and a feedback logic of the register group, and building a hardware logic according to the initialization logic and the feedback logic.
A design method of a parallel pseudo-random sequence generator based on an FPGA (field programmable gate array) comprises the following specific steps:
s1, obtaining a one-step transfer matrix from the Fibonacci LFSR structure according to the generator polynomial
S2, according to the parallel row number w and the polynomial order number m, w D triggers are used in total, each m D triggers are divided into a group, the number of the last group of D triggers is less than or equal to m, wherein w is more than or equal to 2, and m is more than or equal to 2;
s3, calculating an initialization matrix and a w-step shift matrix of each group of D triggers by using MATLAB;
and S4, designing a digital circuit according to the initialization matrix and the w-step shift matrix.
Furthermore, when W is larger than or equal to m, ceil (W/m) m D triggers are needed,
when w is less than or equal to m, the first w registers in the m registers are selected by w bit parallel output.
The invention has the beneficial effects that:
the invention can realize the pseudo-random sequence generator with any parallel number and generating polynomial, and is particularly suitable for the generation and design of spread spectrum codes or scrambling codes in high-speed parallel baseband processing. The generator has the characteristics of random parallel lines, less occupied logic resources and high clock running frequency, uses less D triggers, only needs an exclusive-OR gate for feedback logic, and has high clock running speed.
Detailed Description
The present invention will be described with reference to the accompanying drawings.
As shown in fig. 1 and 2, the generated pseudo-random sequence is represented as: r ism-1(0),rm-1(1),rm-1(2),rm-1(3),rm-1(4) …, wherein the output of the Fibonacci LFSR structured pseudorandom sequence can also be expressed as follows: r ism-1(0),rm-2(0),rm-3(0)…r1(0),r0(0),rm-1(m),rm-2(m),rm-3(m)…r1(m),r0(m) …, i.e., at the same time, the fibonacci LFSR structure can output m consecutive pseudo-random sequences in parallel.
As shown in figure 3 of the drawings,
considering w is 8-bit parallel output, the output of each D flip-flop at the next moment should be the last w sample value of the corresponding serial output. At the ith moment, the output states of m D triggers of the Fibonacci LFSR structure are just w bits and output m bits in front in parallel. At the next time, the feedback logic is used to make each register turn to the state at the next time w.
According to the Fibonacci LFSR structure, obtaining a one-step transfer matrix:
let R (i) be [ R ]1(i) r2(i) … rm(i)]TThen, the first step is executed,wherein,representing k H matrix multiplications.
When w is less than or equal to m, the w-bit parallel output only needs to select the first w registers in the m registers. According to HwAnd carrying out feedback logic design. Such as: IEEE802.11ad scrambling code generation formula f (x) 1+ x4+x7。
And 8 paths of parallel output are carried out, and an 8-step shift matrix is obtained by using MATLAB as follows:
according to an 8-step transfer matrix, D flip-flop r1The feedback logic is designed as follows:
when W is larger than or equal to m, ceil (W/m) m D triggers are needed. Dividing the D flip-flops into N ceil (W/m) groups, wherein each group comprises m, and the N register groups are represented as follows: r1,R2,R3,…RNWherein R isn＝[rn1rn2… rnm]And N is 1,2 … N. The output state of the nth group of flip-flops at the ith moment is represented as: rn(i)＝[rn1(i) rn2(i) … rnm(i)]。
Each set of registers requires separate initialization logic for register initialization, and also requires separate logic for w-step state transitions.
Initializing the register, and expressing the serial fibonacci LFSR structure output as: x (0), x (1), x (2), x (3), x (4) …
The first set of registers is initialized to the initialization value INIT ═ I of the pseudorandom sequence0,I1,I2......Im-1]And using a w-step transfer matrix HwThe transfer logic is designed. And (3) output selection: [ r ] of1m… r12r11]TThen the set of register outputs are:
with m-step transfer matrix HmInitializing the next set of registers, again using the w-step transfer matrix HwThe transfer logic is designed, and the output of the register can be obtained by the same way:
thus, for the nth set of registers, the (n-1) × m step transfer matrix H is used(n-1)*mInitializing the register by using a w-step transfer matrix HwThe transfer logic is designed.
And finally, in the n groups of registers, taking the state outputs of the first w D triggers to obtain w paths of parallel pseudorandom sequence outputs.
OUT＝[r1m… r12r11… … … …rnm… rn2rn1… … … …rnm… rN(N*m-w+1)]T
As the number of parallel numbers increases, the logic resources consumed by the initialization matrix and the transfer matrix of the register set to be computed may increase significantly. Selecting MATLAB to first obtain initialization matrix H(n-1)*mAnd a transfer matrix Hw. N m x m order matrices are derived, followed by register bank initialization logic and feedback logic consisting of exclusive or gates only. This greatly reduces hardware overhead. The combinational logic maximum path is theoretically m 1 exclusive ors, and the maximum path does not increase with the increase of the parallel number. Therefore, with this scheme, high-speed parallel pseudorandom sequences can be generated.
This scheme is implemented using Verilog, using ceil (W/m) m reg variables, with inputs including clk, rst, m-bit initial values init, init _ valid. init _ valid lasts one clock cycle. The init _ valid is used as a MUX selection signal input by the D trigger, when the MUX selection signal is valid, the gating initialization logic initializes the register group, and when the init _ valid is valid, the gating w-step transfer logic is connected to the input end of the D trigger. And finally, selecting the first w D triggers as output.