CN106155629A - Random number high rate bioreactor device and its implementation - Google Patents

Abstract

The invention discloses a random number high-speed real-time processor and its implementation method, wherein the processor includes: a Toeplitz matrix construction module, which is used to construct an m×n Toeplitz matrix by using m+n-1 seed data, and It is decomposed into n/k sub-matrices of m×k, which are sequentially input to the matrix multiplication module; the original data preprocessing module is used to decompose the original data with a length of n into n/k sub-data with a length of k, input to the matrix multiplication module in turn; the matrix multiplication module is used to multiply the sub-matrix of m × k with the sub-data of k length to obtain the intermediate data with a length of m and input it to the accumulation module; A module for accumulating the intermediate data with a length of m for n/k times, and the obtained accumulation result is the processed final data. By adopting the solution disclosed in the present invention, the post-processing speed of data can be greatly improved.

Description

Random number high-speed real-time processor and its realization method

technical field

The invention relates to the technical field of data post-processing, in particular to a random number high-speed real-time processor and an implementation method thereof.

Background technique

Random numbers are a widely used basic resource. Random numbers with good performance have extensive and important applications in many fields such as quantum communication, cryptography, gaming industry, Monte Carlo simulation, numerical calculation, random sampling, etc. The device used to generate the random number sequence, that is, the random number generator usually first generates the original random data, and then after post-processing and purification, the random number sequence with good performance can be obtained.

The post-processing method of random numbers is usually implemented based on hash functions, and common hash functions include SHA, Universal ₂ , etc. The Toeplitz matrix is a type of Universal ₂ hash function. The post-processing algorithm based on this matrix is provable by information theory. It is widely used for random numbers with high security requirements, especially quantum random numbers. post-processing.

At present, the post-processing algorithm based on the Toeplitz matrix is usually implemented in software. The algorithm complexity is high, requiring a lot of CPU operations, and the processing speed is slow. Usually, it can only reach the order of 1Mbps, which is far from the actual needs. And because it needs to rely on the computer for offline processing, the random number generator device cannot be real-time and miniaturized.

Contents of the invention

The purpose of the present invention is to provide a random number high-speed real-time processor and its realization method, which greatly improves the post-processing speed of data.

The purpose of the present invention is achieved through the following technical solutions:

A high-speed real-time processor for random numbers, comprising:

Toeplitz matrix construction module, raw data preprocessing module, matrix multiplication module and accumulation module, wherein:

The Toeplitz matrix construction module is used to construct an m×n Toeplitz matrix using m+n-1 seed data, and decompose it into n/k sub-matrices of m×k, which are sequentially input to the matrix multiplication module ;

The raw data preprocessing module is used to decompose the raw data with a length of n into n/k sub-data with a length of k, and input them to the matrix multiplication module in turn;

The matrix multiplication module is used to multiply the m×k sub-matrix and the sub-data with a length of k to obtain intermediate data with a length of m and input it to the accumulation module;

The accumulating module is used for accumulating the intermediate data with a length of m for n/k times, and the obtained accumulating result is the processed final data.

The ratio of m to n is determined by the randomness of the original data, which is quantified by the minimum entropy H _∞ , which is defined as: H _∞ =-log ₂ P _max ; where P _max is the most likely outcome probability;

The relationship between m and n satisfies the following relationship: m/n≤H _∞ , and m≤n, both m and n are positive integers, and n is an integer multiple of k.

The multiplication in the matrix multiplication module is realized by a bitwise AND operation, and the addition in the accumulation module is realized by a bitwise OR operation.

The working clock of each module is the same system clock, and the clock signal is sent to each module through the global clock path, and the frequency of the clock affects the processing speed;

Each module takes the form of pipeline work under the control of the system clock:

The sub-matrix formation of m×k is performed synchronously with the input of the sub-data with a length of k, as the first stage of the pipeline;

The sub-matrix of m×k is multiplied with the sub-data of length k as the first stage of the pipeline;

The accumulation of intermediate data with a length of m is used as the first stage of the pipeline;

The result obtained at the end of a pipeline cycle is the final data of length m obtained by multiplying the m×n Toeplitz matrix with the original data of length n, and then enters the next pipeline cycle.

The Toeplitz matrix construction module, the original data preprocessing module, the matrix multiplication module and the accumulation module are all implemented in the FPGA by the hardware structure specified by the hardware description language or in other similar platforms with hardware parallel computing capabilities.

A high-speed real-time processing method for random numbers, comprising:

Use m+n-1 seed data to construct an m×n Toeplitz matrix, and decompose it into n/k m×k sub-matrices;

Decompose the original data of length n into n/k sub-data of length k;

multiplying the sub-matrix of m×k by the sub-data of length k to obtain intermediate data of length m;

The intermediate data with a length of m is accumulated n/k times, and the obtained accumulation result is the processed final data.

The ratio of m to n is determined by the randomness of the original data, which is quantified by the minimum entropy H _∞ , which is defined as: H _∞ =-log ₂ P _max ; where P _max is the most likely outcome probability;

The relationship between m and n satisfies the following relationship: m/n≤H _∞ , and m≤n, both m and n are positive integers, and n is an integer multiple of k.

Multiplication is implemented with a bitwise AND operation, and addition is implemented with a bitwise OR operation.

The working clock of each step of the method is the same system clock, and each step adopts a pipeline working form under the control of the system clock:

The sub-matrix formation of m×k is performed synchronously with the input of the sub-data with a length of k, as the first stage of the pipeline;

The sub-matrix of m×k is multiplied with the sub-data of length k as the first stage of the pipeline;

The accumulation of intermediate data with a length of m is used as the first stage of the pipeline;

The result obtained at the end of a pipeline cycle is the final data of length m obtained by multiplying the m×n Toeplitz matrix with the original data of length n, and then enters the next pipeline cycle.

As can be seen from the technical solution provided by the present invention, the algorithm can greatly reduce the usage of FPGA hardware resources, so that large-scale Toeplitz matrix multiplication can be realized in the FPGA of limited resources; The feature of parallel computing can greatly improve the speed of data post-processing. At the same time, the random number high-speed real-time processor can be implemented not only in FPGA hardware, but also in ASIC, CPLD and other similar hardware. In addition, the data processing rate of the solution of the present invention reaches 4Gbps, and compared with the software-based implementation method, the rate is increased by three orders of magnitude.

Description of drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the following will briefly introduce the accompanying drawings that need to be used in the description of the embodiments. Obviously, the accompanying drawings in the following description are only some embodiments of the present invention. For Those of ordinary skill in the art can also obtain other drawings based on these drawings on the premise of not paying creative efforts.

Fig. 1 is the structural representation of the random number high-speed real-time processor that the embodiment of the present invention provides;

Fig. 2 is a flowchart of the operation of the random number high-speed real-time processor provided by the embodiment of the present invention.

detailed description

The technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some of the embodiments of the present invention, not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

FIG. 1 is a schematic structural diagram of a random number high-speed real-time processor provided by an embodiment of the present invention. As shown in Figure 1, it mainly includes: Toeplitz matrix construction module, raw data preprocessing module, matrix multiplication module and accumulation module.

Its working process is shown in Figure 2:

The Toeplitz matrix construction module 1 is used to construct an m×n Toeplitz matrix using m+n-1 seed data, and decompose it into n/k sub-matrices of m×k, which are sequentially input to matrix multiplication Module 3.

In the embodiment of the present invention, the Toeplitz matrix is a Universal ₂ -type hash function, represented by the following formula:

The characteristic of the Toeplitz matrix is that all diagonal elements in the matrix are the same, so an m×n Toeplitz matrix can be constructed using m+n-1 seed data, and each row of the matrix is shifted to the right of the previous row and a new one is added. obtained by the random number. The m+n-1 seed data constituting the Toeplitz matrix is an unbiased quantum random number sequence.

In the embodiment of the present invention, the ratio of m to n is determined by the randomness of the original data, and the randomness is quantified by the minimum entropy H _∞ , which is defined as: H _∞ =-log ₂ P _max ; where P _max is the maximum the probability of a likely outcome;

The relationship between m and n satisfies the following relationship: m/n≤H _∞ , and m≤n, both m and n are positive integers, and n is an integer multiple of k.

The original data preprocessing module 2 is used to decompose the original data with a length of n into n/k sub-data with a length of k, and input them to the matrix multiplication module 3 in sequence.

The matrix multiplication module 3 is used to multiply the m×k sub-matrix and the sub-data with a length of k to obtain intermediate data with a length of m and input it to the accumulation module 4; wherein the multiplication is performed by pressing Implementation of bit-AND operation.

The accumulation module 4 is used for accumulating the intermediate data with a length of m for n/k times, and the obtained accumulation result is the processed final data; the addition is realized by a bitwise OR operation.

In the embodiment of the present invention, the Toeplitz matrix construction module, the original data preprocessing module, the matrix multiplication module and the accumulation module are all realized by the hardware structure specified by the hardware description language in the FPGA or in other similar hardware parallel computing capabilities. platform implementation.

also. As shown in Figure 2, the working clock of each module is the same system clock, and the clock signal is sent to each module through the global clock path, and the frequency of the clock affects the processing speed;

Each module takes the form of pipeline work under the control of the system clock:

The sub-matrix formation of m×k is performed synchronously with the input of the sub-data with a length of k, as the first stage of the pipeline;

The sub-matrix of m×k is multiplied with the sub-data of length k as the first stage of the pipeline;

The accumulation of intermediate data with a length of m is used as the first stage of the pipeline;

The result obtained at the end of a pipeline cycle is the final data of length m obtained by multiplying the m×n Toeplitz matrix with the original data of length n, and then enters the next pipeline cycle.

In the embodiment of the present invention, the selection of parameters m, n, k and system operating clock frequency f is limited by the hardware resources used, and the real-time processing rate S is determined by parameter k and system operating clock frequency f, that is: S=f· k m/n.

The minimum entropy of the original random data to be processed in this embodiment: H _∞ >0.8 bits/bit.

In this embodiment, m=1024, n=1280, that is, m/n=0.8≤H _∞ . If k=80, one pipeline cycle is 16 clock cycles, that is, 16 clock cycles generate 1024-bit processed data on average.

The operating clock of each module is the same clock, and the clock signal is sent to each module through the global clock path. In this embodiment, the operating clock frequency f is selected as 62.5MHz, so in this example, the random number high-speed real-time processor based on FPGA and Toeplitz matrix The real-time processing rate has reached 4Gbps.

If higher-performance FPGA or ASIC, CPLD and other hardware are used for implementation, the parameter k and system operating clock frequency f can be larger, and the real-time processing rate can be higher.

On the other hand, in order to solve the problem of large fan-out of sub-matrix generators and original data during sub-matrix multiplication, the signals with large fan-out are latched into multiple registers of the same type at the entrance of the matrix multiplication module. When outputting, each register of the same type is only responsible for fanning out to a part of the load, thereby solving the problem of excessive fanning out; in addition, when programming hardware circuits, use timing constraints to meet the setup and hold time.

Another embodiment of the present invention also provides a high-speed real-time processing method for random numbers, which is implemented based on the aforementioned processor. See also accompanying drawing 2, it mainly comprises:

Use m+n-1 seed data to construct an m×n Toeplitz matrix, and decompose it into n/k m×k sub-matrices;

Decompose the original data of length n into n/k sub-data of length k;

multiplying the sub-matrix of m×k by the sub-data of length k to obtain intermediate data of length m;

The intermediate data with a length of m is accumulated n/k times, and the obtained accumulation result is the processed final data.

In the embodiment of the present invention, the ratio of m to n is determined by the randomness of the original data, and the randomness is quantified by the minimum entropy H _∞ , which is defined as: H _∞ =-log ₂ P _max ; where P _max is the maximum the probability of a likely outcome;

The relationship between m and n satisfies the following relationship: m/n≤H _∞ , and m≤n, both m and n are positive integers, and n is an integer multiple of k.

In the embodiment of the present invention, the multiplication is realized by a bitwise AND operation, and the addition is realized by a bitwise OR operation.

In the embodiment of the present invention, the working clocks of each step of the method are the same system clock, and each step adopts a pipeline working form under the control of the system clock:

The sub-matrix formation of m×k is performed synchronously with the input of the sub-data with a length of k, as the first stage of the pipeline;

The sub-matrix of m×k is multiplied with the sub-data of length k as the first stage of the pipeline;

The accumulation of intermediate data with a length of m is used as the first stage of the pipeline;

The result obtained at the end of a pipeline cycle is the final data of length m obtained by multiplying the m×n Toeplitz matrix with the original data of length n, and then enters the next pipeline cycle.

Those skilled in the art can clearly understand that for the convenience and brevity of description, only the division of the above-mentioned functional modules is used as an example for illustration. In practical applications, the above-mentioned function allocation can be completed by different functional modules according to needs. The internal structure of the device is divided into different functional modules to complete all or part of the functions described above.

The above is only a preferred embodiment of the present invention, but the scope of protection of the present invention is not limited thereto. Any person familiar with the technical field can easily conceive of changes or changes within the technical scope disclosed in the present invention. Replacement should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be determined by the protection scope of the claims.

Claims (9)

1. a random number high rate bioreactor device, it is characterised in that including:

Toeplitz matrix construction module, initial data pretreatment module, matrix multiple module and accumulator module, wherein:

Described Toeplitz matrix construction module, is used for using the Toeplitz square of m+n-1 seed data one m × n of structure Battle array, and it is broken down into the submatrix of n/k m × k, it is sequentially inputted to matrix multiple module；

Described initial data pretreatment module, for the initial data of a length of n being decomposed into the subdata of n/k a length of k, It is sequentially inputted to matrix multiple module；

Described matrix multiple module, for being multiplied the submatrix of described m × k with the subdata of described a length of k, it is thus achieved that length For the intermediate data of m and be input to accumulator module；

Described accumulator module, for carrying out cumulative n/k time by the intermediate data of described a length of m, it is thus achieved that accumulation result be Final data after process.

A kind of random number high rate bioreactor device the most according to claim 1, it is characterised in that

The ratio of m Yu n is determined by the randomness of initial data, and described randomness is by minimum entropy H_∞Quantifying, it is defined as: H_∞ =-log₂P_max；Wherein, P_maxProbability for the most possible result occurred；

M Yu n meets following relation: m/n≤H_∞, and m≤n, m Yu n are positive integer and n is the integral multiple of k.

A kind of random number high rate bioreactor device the most according to claim 1, it is characterised in that described matrix multiple module In multiplication realized by step-by-step and computing, the addition in described accumulation module is realized by step-by-step or computing.

A kind of random number high rate bioreactor device the most according to claim 1, it is characterised in that

The work clock of each module is same system clock, and clock signal sends into modules by global clock path, time The speed that the frequency influence of clock processes；

Each module takes the working forms of streamline under system clock control:

The submatrix of m × k becomes the input of the subdata with a length of k Tong Bu to carry out, as the one-level of streamline；

The submatrix of m × k becomes the one-level as streamline that is multiplied with the subdata of a length of k；

The cumulative one-level as streamline of the intermediate data of a length of m；

The result obtained at the end of one Cycle time is exactly that the Toeplitz matrix of m × n is multiplied with the initial data of a length of n After the final data of a length of m that obtains, enter next Cycle time afterwards.

A kind of random number high rate bioreactor device the most according to claim 1, it is characterised in that described Toeplitz matrix Constructing module, initial data pretreatment module, matrix multiple module and accumulator module all in FPGA by hardware description language The hardware configuration of regulation realizes or realizes at other similar platforms with hardware concurrent computing capability.

6. a random number high rate bioreactor method, it is characterised in that including:

Use the Toeplitz matrix of m+n-1 seed data one m × n of structure, and be broken down into the sub-square of n/k m × k Battle array；

The initial data of a length of n is decomposed into the subdata of n/k a length of k；

The subdata of the submatrix of described m × k with described a length of k is multiplied, it is thus achieved that the intermediate data of a length of m；

The intermediate data of described a length of m is carried out cumulative n/k time, it is thus achieved that accumulation result be the final data after process.

A kind of random number high rate bioreactor method the most according to claim 6, it is characterised in that

The ratio of m Yu n is determined by the randomness of initial data, and described randomness is by minimum entropy H_∞Quantifying, it is defined as: H_∞ =-log₂P_max；Wherein, P_maxProbability for the most possible result occurred；

M Yu n meets following relation: m/n≤H_∞, and m≤n, m Yu n are positive integer and n is the integral multiple of k.

A kind of random number high rate bioreactor method the most according to claim 6, it is characterised in that multiplication by step-by-step with Computing realizes, and addition is realized by step-by-step or computing.

A kind of random number high rate bioreactor method the most according to claim 6, it is characterised in that each step of the method Work clock is same system clock, and each step takes the working forms of streamline under system clock control:

The submatrix of m × k becomes the input of the subdata with a length of k Tong Bu to carry out, as the one-level of streamline；

The submatrix of m × k becomes the one-level as streamline that is multiplied with the subdata of a length of k；

The cumulative one-level as streamline of the intermediate data of a length of m；

The result obtained at the end of one Cycle time is exactly that the Toeplitz matrix of m × n is multiplied with the initial data of a length of n After the final data of a length of m that obtains, enter next Cycle time afterwards.