RU2800190C1 - Device for forming pseudo-random complex numbers - Google Patents

Abstract

FIELD: computer engineering.

SUBSTANCE: for the formation of pseudo-random complex numbers, a pseudo-random number generator is additionally introduced, functioning in the final field GF(q), consisting of r capacity registers r-1 addition blocks in GF(q), r multiplication blocks in GF(q); a block for generating pseudo-random complex numbers comprising a block for multiplying by an imaginary unit i, an addition block; the outputs of the first and second pseudo-random number generators are connected respectively to the first and second inputs of the block for generating pseudo-random complex numbers, the first input of which is the first input of the addition block, the second input of which is the output of the block for multiplying by an imaginary unit i, and the input of the block for multiplying by an imaginary unit i is the second input of the pseudo-random complex number generation block; the output of the addition block is the output of the block for generating pseudo-random complex numbers.

EFFECT: increasing the productivity of the computing process by implementing calculations for the formation of pseudo-random complex numbers.

1 cl, 5 dwg

Description

The field of technology to which the invention belongs

The invention relates to computer technology and can be used to improve the efficiency of electronic computing equipment (such characteristics as performance, reliability, memory capacity, etc.).

State of the art

a) Description of analogues

It is known that to construct a pseudo-random sequence of length n=2 ^r -1, a primitive polynomial V(z) of degree r is required. For example, consider the polynomial

where r=4.

Polynomial (1) corresponds to a feedback shift register [MacWilliams F., Sloane N. Pseudo-random sequences and arrays, Proc. IEEE, 64, pp. 1715-1729, 1976; Lidl R., Niederreiter H. Introduction to finite fields and their applications, Cambridge: Cambridge Univ. Press, 1987], shown in figure 1.

The shift register consists of r cells (memory elements, flip-flops), each of which can contain 0 or 1 during device operation. At time t (the time is determined by some clock frequency), the contents of all cells are shifted by one cell (moved by one bit) to the right. Here, the contents of the cells corresponding to the members of the polynomial V(z) are summed up and fed into the leftmost cell. The sum is calculated modulo 2 and is implemented by the adder modulo 2, (logical element "EXCLUSIVE OR"), the output of which is determined by the conditions

0+0=1+1=0,

0+1=1+0=1.

As an example, consider a feedback shift register (Fig. 1), which at time t contains the numbers

a _t+3 , a _t+2 , a _t+1 , a _t ,

accordingly, at time t + 1, it will contain numbers (Fig. 2)

a _t+4 =a _t+1 +a _t , a _t+3 , a _t+2 , a _t+1 .

Thus, the feedback shift register generates an infinite sequence a ₀ , a ₁ , a ₂ , …, a _t , … satisfying the recursive relation

a _t+4 =a _t+1 +a _t ,

where t=0, 1, …; sign "+" - addition modulo 2. To start the process of functioning of the shift register with feedback, you must set the initial filling a ₀ , a ₁ , a ₂ , …, a _r-1 .

b) Description of the closest analogue (prototype)

The closest in its technical essence to the claimed technical solution and taken as a prototype is the device described in [M.A. Ivanov, B.V. Kliuchnikova, E.A. Salikov, A.V. Starikovskii. New class of non-binary pseudorandom number generators. - Proceedings of Intelligent Technologies in Robotics, Moscow, Russia, 2019, p. 255-262; RF patent No. 2740339, publ. 01/13/2021].

The considered device for obtaining pseudo-random sequences (a pseudo-random number generator operating in a finite field GF(q), where q is a prime number), consisting of r capacity registers r-1 addition blocks in GF(p), r multiplication blocks in GF(p), and the value by which multiplication occurs in the (i+1)th multiplication block is equal to the coefficient p _i ∈ GF(q), of the characteristic polynomial

where i=0, 1, 2, ..., r-1, P(z) is a polynomial of degree r, primitive over GF(p), in which the outputs of the r-th register are connected to the inputs of all multiplication blocks, the outputs of j-x multiplication blocks are connected to the first inputs of j-x addition blocks, the outputs of which are connected to the inputs of j-x registers, where j=1, 2, ..., r, the second inputs of all addition blocks form r control groups generator inputs, the outputs of the k-th registers are connected to the third inputs of the (k+1)-th addition blocks, the outputs of which are connected to the inputs of the (j+1)-th registers, where k=1, 2, ..., r.

The block diagram of the prototype device is shown in Fig. 3 for the case r=3,

where p _i ∈ GF(q), here 1 is the clock input of the generator, 2.1, 2.2, 2.3 - - bit registers, 3.1 and 3.2 - blocks of addition in the field GF(q), 4.1, 4.2, and 4.3 - blocks of multiplication by p ₀ , p ₁ , and p ₂ in the field GF(q).

The disadvantage of the known device is the inability to implement calculations in which the formation of pseudo-random complex numbers.

Disclosure of invention

a) The technical result to which the invention is directed

The purpose of the proposed technical solution is to implement the process of calculating pseudo-random complex numbers.

b) A set of essential features

The technical result of the invention is achieved by the fact that:

This goal is achieved by the fact that in the device for the formation of pseudo-random complex numbers, consisting of r bit registers r-1 addition blocks in GF(q), r multiplication blocks in GF(q), and the value by which multiplication occurs in the (i+1)th multiplication block is equal to the coefficient p _i ∈ GF(q), of the characteristic polynomial

where r=0, 1, 2, …, r-1, P(z) is a polynomial of degree r, primitive over GF(q), in which the outputs of the r-th register are connected to the inputs of all multiplication blocks, the outputs of jx multiplication blocks are connected to the first inputs of jx addition blocks, the outputs of which are connected to the inputs of jx registers, where j=1, 2, …, r, the second inputs of all addition blocks form g groups of control inputs s of the generator, the outputs of the k-th registers are connected to the third inputs of the (k+1)-th addition blocks, the outputs of which are connected to the inputs of the (j+1)-th registers, where k=1, 2, ... r, a pseudo-random number generator is introduced, operating in the final field GF(q), where q is a prime number), consisting of r bit width registers r-1 addition blocks in GF(q), r multiplication blocks in GF(q), and the value by which multiplication occurs in the (i+1)th multiplication block is equal to the coefficient p _i ∈ GF(q), of the characteristic polynomial

where i=0, 1, 2, ..., r-1, G(z) is a polynomial of degree r, primitive over GF(q), in which the outputs of the r-th register are connected to the inputs of all multiplication blocks, the outputs of jx multiplication blocks are connected to the first inputs of jx addition blocks, the outputs of which are connected to the inputs of jx registers, where j=1, 2, ..., r, the second inputs of all addition blocks form g groups of control inputs generator, the outputs of the k-th registers are connected to the third inputs of the (k+1)-th addition blocks, the outputs of which are connected to the inputs of the (j+1)-th registers, where k=1, 2, ..., r; a block for generating pseudo-random complex numbers, containing a block for multiplying by an imaginary unit "i", an addition block; the outputs of the first and second pseudo-random number generators are connected respectively to the first and second inputs of the block for generating pseudo-random complex numbers, the first input of which is the first input of the addition block, the second input of which is the output of the block for multiplying by the imaginary unit "r", and the input of the block for multiplying by the imaginary unit "i" is the second input of the block for generating pseudo-random complex numbers; the output of the addition block is the output of the block for generating pseudo-random complex numbers, giving out the values

c) Causal relationship between features and technical result

Due to the introduction of a set of significant distinguishing features into a known object, into a device for generating pseudo-random complex numbers, it is possible to implement an algorithm for generating pseudo-random complex-valued numbers for the implementation of promising high-performance computing tools.

Evidence of compliance of the claimed invention with the conditions of patentability "novelty" and "inventive step"

The analysis of the prior art made it possible to establish that there are no analogues characterizing the totality of features that are identical to all the features of the claimed technical solution, which indicates the compliance of the claimed method with the patentability condition "novelty".

The results of the search for known solutions in this and related fields of technology in order to identify features that match the distinguishing features of the prototype of the claimed object showed that they do not follow obvious from the prior art. The prior art also did not reveal the fame of distinctive essential features that cause the same technical result that is achieved in the claimed method. Therefore, the claimed invention corresponds to the level of patentability "inventive step".

Brief description of the drawings

The claimed device is illustrated by drawings, which show:

- in Fig. 1 is a block diagram of a feedback shift register corresponding to a polynomial (1);

- in Fig. 2 is a block diagram of a feedback shift register that defines a recursive relationship;

- in Fig. 3 is a block diagram of the device of the prototype;

- in Fig. 4 - block diagram of the proposed device for the case r=3;

- in Fig. 5 - diagram of the block for generating pseudo-random complex numbers.

Implementation of the invention

The proposed device contains the first pseudo-random number generator over GF(q) (feedback shift register, g-PPC), the second pseudo-random number generator over GF(q), as well as a block for generating pseudo-random complex numbers.

The first g-RRS is built on the basis of a primitive, irreducible (characteristic) polynomial (2), where p _i ∈ GF(q), and includes 1.1 - generator clock input, 1.2.1, 1.2.2, …, 1.2.r - - bit registers, 1.3.1, 1.3.2, ..., 1.3.r-1 - addition blocks in the field GF(q), 1.4.1, 1.4.2, ..., 1.4.r - respectively blocks of multiplication by p ₀ , p ₁ , ..., p _r-1 in the field GF(q); the second g-RRS is built on the basis of a primitive, irreducible (characteristic) polynomial (3), where ρ _i ∈ GF(q), and includes 2.1 - generator clock input, 2.2.1, 2.2.2, …, 2.2.r- -разрядные регистры, 2.3.1, 2.3.2, …, 2.3.r-1 - блоки сложения в поле GF(q), 2.4.1, 2.4.2, …, 2.4.r - соответственно блоки умножения на ρ ₀ , ρ ₁ , …, ρ _r-1 в поле GF(q), 3 - блок формирования псевдослучайных комплексных чисел (фиг. 5), содержащий блок 3.1 умножения на мнимую единицу «i», блок 3.2 сложения, причем выходы первого и второго q-РРС подключены соответственно к первому и второму входам блока 3 формирования псевдослучайных комплексных чисел, первый вход которого является первым входом блока 3.2 сложения, второй вход которого является выходом блока 3.1 умножения на мнимую единицу «i», причем вход блока 3.1 умножения на мнимую единицу «i» является вторым входом блока 3 формирования псевдослучайных комплексных чисел; the output of the addition block 3.2 is the output of the block 3 for generating pseudo-random complex numbers

Consider the algorithm of the device.

The construction of the first q-RRS is carried out according to a given primitive, irreducible (characteristic) polynomial (2), and a homogeneous recurrent equation constructed in accordance with it:

where n=0, 1, 2, …; p _j ∈ GF(q), 0≤j≤r-1; ⊕ is the symbol for addition mod q.

In the general case, after the first cycle of operation, the first q-PPC contains the filling: In general, the first q-PPC generates an infinite q-digit output sequence with a period q ^r -1 (with a non-zero initial state), and each non-zero state appears once per period. The generated segment of the output sequence of length q ^r -1 is a pseudo-random sequence (PRS) over GF(q).

In terms of linear algebra, the next element of the PSS obtained using (4) is calculated in accordance with the expression:

where T is the transposition symbol.

The construction of the second g-RRS is also carried out according to a given primitive, irreducible (characteristic) polynomial (3), and a homogeneous recurrent equation constructed in accordance with it:

where n=0, 1, 2, …; ρ _j ∈ GF(q), 0≤j≤r-1; ⊕ is the symbol for addition mod q.

After the first cycle of operation, the second g-PPC contains the filling: In this case, the second q-PPC generates an infinite output q-valued sequence with a period q ^r -1 (with a non-zero initial state), and each non-zero state appears once per period. The generated segment of the output sequence of length q ^r -1 is a pseudo-random sequence (PRS) over GF(q).

In terms of linear algebra, the next element of the PSS obtained using (5) can also be obtained in accordance with the expression:

where T is the transposition symbol.

Subsequence from the output of the first q-PPC are fed to the first input of block 3 for generating pseudo-random complex numbers (Fig. 5), in particular, to the first input of block 3.2 of addition. The first input of the addition block 3.2 corresponds to the real part (Re) of the complex number. Subsequence from the output of the second q-RRS goes to the second input of block 3 for the formation of pseudo-random complex numbers, in particular to the input of block 3.1 of multiplication by the imaginary unit "r". From the output of block 3.1 of multiplication by the imaginary unit "i" the sequence enters the second input of the block 3.2 addition. The second input of the addition block 3.2 corresponds to the imaginary part (Im) of the complex number. In block 3.2 of addition, the final formation of pseudo-random complex numbers is carried out

In the process of forming complex numbers in the addition block 3.2, real numbers can be formed when real numbers are received from the output of the block 3.1 of multiplication by the imaginary unit "i" in the addition block 3.2, that is In this case, numbers of the form are removed from the computational process.

In FIG. 4 shows a diagram of the proposed device for the case r=3, the first q-PPC is built on the basis of where p _i ∈ GF(q), and includes 1.1 - generator clock input, 1.2.1, 1.2.2 and 1.2.3 - -bit registers, 1.3.1 and 1.3.2 - addition blocks in the field GF(q), 1.4.1, 1.4.2 and 1.4.3 - respectively blocks of multiplication by p ₀ , p ₁ and p ₂ in the field GF (q); the second g-PPC is based on where ρ _i ∈ GF(q), and includes 2.1 - generator clock input, 2.2.1, 2.2.2 and 2.2.3 - -разрядные регистры, 2.3.1 и 2.3.2 - блоки сложения в поле GF(q), 2.4.1, 2.4.2 и 2.4.3 - соответственно блоки умножения на ρ ₀ , ρ ₁ , и ρ ₂ в поле GF(q), 3 - блок формирования псевдослучайных комплексных чисел, содержащий блок 3.1 умножения на мнимую единицу «i», блок 3.2 сложения, причем выходы первого и второго q-РРС подключены соответственно к первому и второму входам блока 3 формирования псевдослучайных комплексных чисел, первый вход которого является первым входом блока 3.2 сложения, второй вход которого является выходом блока 3.1 умножения на мнимую единицу «i», причем вход блока 3.1 умножения на мнимую единицу «i» является вторым входом блока 3 формирования псевдослучайных комплексных чисел; the output of the addition block 3.2 is the output of the block 3 for generating pseudo-random complex numbers

The claimed invention can be carried out using the means and methods described in the available sources of information. This allows us to conclude that the claimed invention complies with the signs of "industrial applicability".

Example. Consider a generator of pseudo-random complex numbers. Let the first q=3 RPC be given, which generates a 3-digit PRS of maximum length over the field GF(3 ³ ). The generator is built on a primitive polynomial

which corresponds to a recursive equation of the following form:

Considering that p ₂ =0, p ₁ =1, p ₀ =2 we get

If as the initial data of the register (initial filling) we write: then the following SRP will take place at the output of the generator:

Received PSP elements arrive at the first input of block 3 for the formation of pseudo-random complex numbers, in particular, at the first input of block 3.2 of addition.

Let the second q=5 RPC be given, which generates a 5-digit PSS of maximum length over the field GF(5 ² ). The generator is built on a primitive polynomial

G(z)=z ² -ρ ₁ z-ρ ₀ =z ² -4z-3,

which corresponds to a recursive equation of the following form:

Considering that ρ ₁ =4, ρ ₀ =3 we get

If as the initial data of the register (initial filling) we write: then the following SRP will take place at the output of the generator:

Further, the calculated elements of the SRP arrive at the second input of block 3 for the formation of pseudo-random complex numbers, in particular, at the input of block 3.1 of multiplication by the imaginary unit "w", in which the following elements of pseudo-random complex numbers are formed

Then, from the output of the block 3.1 of multiplication by the imaginary unit "w", the elements are fed to the second input of the addition block 3.2, in which the final formation of a sequence of pseudo-random complex numbers (the indicated sequence) is carried out:

At the same time, in the process of forming complex numbers, the resulting real numbers are removed

The above example showed that the claimed device for generating pseudo-random complex numbers is functioning correctly, technically feasible and allows solving the problem.

Claims (5)

Device for generating pseudo-random complex numbers, consisting of r capacity registers r-1 addition blocks in GF(q), r multiplication blocks in GF(q), and the value by which multiplication occurs in the (i+1)th multiplication block is equal to the coefficient p _i ∈ GF(q), of the characteristic polynomial where i=0, 1, 2, …, r-1, P(z) is a polynomial of degree r, primitive over GF(q), in which the outputs of the r-th register are connected to the inputs of all multiplication blocks, the outputs of jx multiplication blocks are connected to the first inputs of jx addition blocks, the outputs of which are connected to the inputs of jx registers, where j=1, 2, …, r, the second inputs of all addition blocks form r groups of control inputs generator, the outputs of the k-th registers are connected to the third inputs of the (k+1)-th addition blocks, the outputs of which are connected to the inputs of the (j+1)-th registers, where k=1, 2, ..., r, characterized in that a pseudo-random number generator is introduced, operating in a finite field GF(q), where q is a prime number consisting of r registers of capacity r-1 addition blocks in GF(q), r multiplication blocks in GF(q), and the value by which multiplication occurs in the (i+1)th multiplication block is equal to the coefficient p _i ∈ GF(q), of the characteristic polynomial where i=0, 1, 2, …, r-1, G(z) is a polynomial of degree r, primitive over GF(q), in which the outputs of the r-th register are connected to the inputs of all multiplication blocks, the outputs of jx multiplication blocks are connected to the first inputs of jx addition blocks, the outputs of which are connected to the inputs of jx registers, where j=1, 2, …, r, the second inputs of all addition blocks form r groups of control inputs s generator, the outputs of the k-x registers are connected to the third inputs of the (k+1)-x addition blocks, the outputs of which are connected to the inputs of the (j+1)-x registers, where k=1, 2, ..., r; a block for generating pseudo-random complex numbers, containing a block for multiplying by an imaginary unit "i", an addition block; the outputs of the first and second pseudo-random number generators are connected respectively to the first and second inputs of the block for generating pseudo-random complex numbers, the first input of which is the first input of the addition block, the second input of which is the output of the block for multiplying by the imaginary unit "i", and the input of the block for multiplying by the imaginary unit "i" is the second input of the block for generating pseudo-random complex numbers; the output of the addition block is the output of the block for generating pseudo-random complex numbers, giving the value