RU2586575C1 - Modular polynomial computer of boolean function systems - Google Patents

Abstract

FIELD: computer engineering.

SUBSTANCE: invention can be used as a special-purpose calculator - a versatile class of logical calculations. Apparatus comprises a switch, 2^k memory blocks store values of expansion coefficients of polynomials, 2^n-k storage memories erection residues in variable i-th degree (i = 0, 1, …, 2^n-k-1) modulo P, multi-channel multiplexer allocation coefficient group, multi-channel multiplexer allocation group deductions, 2^n-k modulo P multipliers, a modulo P adder, n inputs feed Boolean variable device, control input feeder value of number of variables of decomposition, control input values feeder coefficients, control input of subtraction of feeder construction of a variable in i-th degree modulo P, d outputs of device for outputting Boolean functions.

EFFECT: reduced volume of equipment.

1 cl, 1 dwg

Description

The proposed device relates to computer technology and can be used as a specialized computer - universal in the class of logical computing.

Known modular computer systems of Boolean functions [1], containing a switch, the inputs of which are inputs of the device for supplying n Boolean variables, and the outputs from (k + 1) through n are connected to the inputs of the conjunction block, the outputs of which are connected to the inputs of each of 2 ^k blocks memory, the outputs of which are connected to the inputs of 2 ^nk multiplexers, where the i-th output of the j-th memory block is connected to the j-th input of the i-th multiplexer (i = 1, 2, ..., 2 ^nk ; j = 1, 2, ... 2 ^k), the control inputs of each of which are connected to the k first input of the switch and outputs connected to inputs mnogome deleterious adder, the outputs of which are the outputs of the calculation result dispenser Boolean functions.

The claimed device closest in essence to the technical solution is an arithmetic calculator of Boolean function systems [2], containing n inputs of Boolean variables, a switch, 2 ^k memory blocks for storing coefficient groups, n-k + 1 multiplexers for selecting a group of coefficients, a multi-place adder, d outputs issuing Boolean functions, the data inputs of the switch inputs are Boolean variables feed device and outputs a (k + 1) -th to n-th connected to data inputs of each of 2 ^k memory blocks storage of coefficients whose outputs are connected to the information inputs of each of (n-k + 1) multiplexers for selecting a group of coefficients, where the i-th output of the j-th memory block is connected to the j-th input of the i-th multiplexer (i = 1, 2, ..., n-k + 1; j = 1, 2, ..., 2 ^k ), the control inputs of each of which are connected to the k first outputs of the switch, and the outputs are connected to a multi-seat adder, d information discharge multiplexers, multi-channel multiplexer, 2 ^k blocks of memory storage addresses of information bits, the control input of the signal selection Nya Ullevi variables decomposition, which is a control input of the switch, and the control flow selection signal input realizable Boolean function device is a control input of each of 2 ^k memory blocks storing coefficients and each of 2 ^k memory blocks storing address information bits, outputs of each of which are connected to information the inputs of a multi-channel multiplexer, the control inputs of which are connected to the first k outputs of the switch, and the outputs 1 through d are connected to the address inputs d of the multiplex dividing the information category, respectively, the information inputs of each of which are connected to the outputs of the multi-place adder, and the outputs are outputs of the values of the Boolean functions of the device.

A disadvantage of the known device is the large volumes of equipment (in particular, the large dimension of the discharge grid of the arithmetic calculator of Boolean function systems).

The purpose of the invention is the reduction of equipment volumes (reduction of the discharge grid of the computer).

This goal is achieved by the fact that in a modular polynomial calculator of Boolean function systems containing a switch, the information inputs of which are n inputs of Boolean variables of the device, the control inputs of which are connected to the control input of the device for supplying the values of the number of decomposition variables, 2 ^k blocks of memory for storing the values of polynomial coefficients decompositions, the control inputs of which are connected to the control input of the device for supplying coefficient values, the information outputs of which connected to the information inputs of a multichannel multiplexer for selecting a group of coefficients, the control inputs of which are connected to the k first outputs of the switch, 2 ^nk memory blocks for storing values of residues of raising a variable to the ith degree (i = 0, 1, ..., 2 ^nk -1) are introduced by module P, the control inputs of which are connected to the control input of the device for supplying residues of raising the variable to the ith power modulo P, the information outputs of which are connected to the information inputs of the multi-channel group selection multiplexer the number of residues, the control inputs of which are connected to the nk second information outputs of the switch, 2 ^nk multipliers modulo P, where the inputs of the jth multiplier modulo P are connected to the jth information outputs of the multichannel coefficient group multiplexer and the multichannel residue group selection multiplexer (j = 1, 2, ..., 2 ^nk ), the outputs of which are connected to the inputs of the adder modulo P, d outputs of which are d outputs of the device for issuing the values of Boolean functions.

To represent a system of Boolean functions (SBF) f ₁ , ..., f _{d by an} interpolation polynomial, we interpret the values of the sets of variables of the SBF and the values of the functions on these sets as writing numbers in a binary number system and then in decimal:

As a result of this interpretation, we obtain the function F (X), the range and value of which are {0, 1, ..., s-1}, where s = 2 ⁿ .

The values of the argument X are equidistant interpolation nodes, which makes it possible to apply various interpolation methods to the interpreted form of the SBF record.

We use the Lagrange interpolation method to represent F (X) by a power polynomial:

or

and _i are the coefficients of the polynomial, (i = 0, 1, ..., s-1), s = 2 ⁿ .

Example 1. Consider the representation of SBF by the interpolation polynomial given by the truth table:

In decimal form, the truth table will take the form:

Construction of the IP by the Lagrange method:

Calculation of SBF values:

Let X = 11 (x ₁ = 1, x ₂ = 0, x ₃ = 1, x ₄ = 1), then:

and accordingly we obtain the values f ₁ = 1, f ₂ = 1, f ₃ = 1, f ₄ = 1.

Consider the representation of SBF in the modular interpolation polynomial form of the representation of a system of Boolean functions.

As

where M is a prime number, φ (M) is the Euler function, then the interpolation polynomial (1) takes the form:

where b _i ≡ a _i (mod Р), i = 0, 1, ..., s-1, P is a prime, P> s.

The advantage of the modular interpolation polynomial form of the SBF representation is a significant reduction in the coefficients. Consider the SBF from Example 1.

Example 2. Represent the polynomial P (X) modulo 17:

Z (X) = P (X) (mod 17),

Z (X) = 5 + 11X + 7X ² + 16X ³ + 11X ⁴ + X ⁵ + 16X ⁶ + 15X ⁷ + 4X ⁹ + 12X ¹⁰ + 5X ¹¹ + 9X ¹² + 15X ¹³ + 14X ¹⁴ + 8X ¹⁵ (mod 17 )

The resulting effect:

- transition to integer positive values of the coefficients;

- average reduction of the coefficients by 250 times.

Consider the expansion of the interpolation polynomial form of the representation of a system of Boolean functions in Boolean variables.

Example 3. Consider the truth table of a system of Boolean functions F (x ₁ , x ₂ , x ₃ ):

and interpret it as follows:

and accordingly in the decimal number system:

Construct interpolation polynomials for x ₁ = 0 and x ₁ = 1:

H (x ₁ = 0, X) = 5X ² -X ³ -7X + 3;

and accordingly the modular form will take the form:

H (x ₁ = 0, X) (mod 5) = 4X ³ + 3X + 3 (mod 5);

H (x ₁ = 1, X) (mod 5) = 3X ³ + 2X ² + 4X + 2 (mod 5).

Let x ₁ = 1, X = 2 (x ₂ = 1, x ₃ = 0):

H (x ₁ = 1, X = 2) (mod 5) = 3 · 2 ³ + 2 · 2 ² + 4 · 2 + 2 (mod 5) = 2 = (10) ₂ , then the values f ₁ = 1, f ₂ = 0.

The general form of the expansion of the modular interpolation form of the SBF representation in one variable takes the form:

Where

The general form of the expansion of the modular interpolation form of the SBF representation in k variables will take the form:

Where

The block diagram of the proposed device is presented in FIG. 1, which contains switch 1, memory blocks 2.1, ..., 2.2 ^k , memory blocks 3.1, ..., 3.2 ^k , multi-channel multiplexer 4, multi-channel multiplexer 5, multipliers modulo P 6.1, ..., 6.2 ^nk [3], modulo adder P 7 [4], the inputs of the device 8.1, ..., 8.n supply the values of Boolean variables x ₁ , x ₂ , ..., x _n , the control input of the device 9 supply the value of the number of decomposition variables, the control input of the device 10 supply of coefficient values, the control input devices 11 for feeding the values of the residues of raising a variable to the ith power modulo P, 12.1, ..., 12.d The results of the values of Boolean functions f ₁ , ..., f _d .

подключены к управляющему входу устройства 10 подачи значений коэффициентов, управляющие входы блоков памяти 3.1, …, 3.2^k хранения значений вычетов возведения переменной X в i-ю степень по модулю Р: $$X^{2^{n-k}-1}(\mathrm{mod}P),X^{2^{n-k}-2}(\mathrm{mod}P),\dots ,X^0(\mathrm{mod}P)(X=\mathrm{0,}\mathrm{1,}\dots ,P-1)$$

подключены к управляющему входу устройства 11 подачи значений вычетов возведения переменной X в i-ю степень по модулю Р, управляющие входы многоканального мультиплексора 4 выделения группы коэффициентов подключены к k первым выходам коммутатора 1, где 1-й управляющий вход многоканального мультиплексора 4 подключен к 1-му входу коммутатора 1 и так далее и k-тый управляющий вход многоканального мультиплексора 4 подключен к k-му выходу коммутатора 1, а информационные входы подключены к выходам блоков памяти 2.1, …, 2.2^k, где 1-е 2^n-k информационных входов многоканального мультиплексора 4 подключены соответственно к 2^n-k выходам блока памяти 2.1 и так далее и 2^k-е 2^n-k информационных входов многоканального мультиплексора 4 подключены соответственно к 2^n-k выходам блока памяти 2.2^k, управляющие входы многоканального мультиплексора 5 выделения группы вычетов подключены к n-k вторым выходам коммутатора 1, где k+1-й управляющий вход многоканального мультиплексора 5 подключен к k+1-му входу коммутатора 1 и так далее и n-й управляющий вход многоканального мультиплексора 5 подключен к n-му выходу коммутатора 1, а информационные входы подключены к выходам блоков памяти 3.1, …, 3.2^k, где 1-е 2^n-k информационных входов многоканального мультиплексора 5 подключены соответственно к 2^n-k выходам блока памяти 3.1 и так далее и 2^k-е 2^n-k информационных входов многоканального мультиплексора 5 подключены соответственно к 2^n-k выходам блока памяти 3.2^k, входы умножителей 6.1, …, 6.2^n-k по модулю Р подключены к информационным выходам многоканального мультиплексора 4 и многоканального мультиплексора 5, где 1-й вход умножителя 6.1 подключен к 1-му информационному выходу многоканального мультиплексора 4 и 2-й вход умножителя 6.1 подключен к первому информационному выходу многоканального мультиплексора 5 и так далее и 1-й вход умножителя 6.2^n-k подключен к 2^n-k-му информационному выходу многоканального мультиплексора 4 и 2-й вход умножителя 6.2^n-k подключен к 2^n-k информационному выходу многоканального мультиплексора 5, а выходы подключены к входам сумматора 7 по моду P, где выход умножителя 6.1 подключен к 1-му входу сумматора 7 и так далее и выход умножителя 6.2^n-k подключен к 2^n-k-му входу сумматора 7, выходы сумматора 7 являются выходами выдачи значений булевых функций f₁, …, f_d устройства.The inputs of the device 8.1, ..., 8.n supply Boolean variables x ₁ , x ₂ , ..., x _n are the information inputs of the switch 1, the control input of which is connected to the control input of the device 9 supply the value of the number of variables of decomposition, the control inputs of the memory blocks 2.1, ... , 2.2 ^k storing the values of the decomposition coefficients:

connected to the control input of the device 10 for supplying the coefficient values, the control inputs of the memory blocks 3.1, ..., 3.2 ^k storing the values of the residues of raising the variable X to the i-th degree modulo P: $$X^{2^{n-k}-\mathrm{one}}(\mathrm{mod}P),X^{2^{n-k}-2}(\mathrm{mod}P),...,X^0(\mathrm{mod}P)(X=0\mathrm{one,}...,P-\mathrm{one})$$

connected to the control input of the device 11 for feeding the residues of raising the variable X to the ith power modulo Р, the control inputs of the multi-channel multiplexer 4 for selecting a group of coefficients are connected to the k first outputs of switch 1, where the first control input of the multi-channel multiplexer 4 is connected to 1- th input switch 1 and so on and k-th control input multichannel multiplexer 4 is connected to the k-th switch output 1, while data inputs are connected to outputs of the memory blocks 2.1, ..., 2.2 ^k, where 1-e 2 input information ^nk a multichannel multiplexer 4 connected respectively to the two outputs of the storage unit ^nk 2.1 and so on and ^k 2 2 -e ^nk multichannel multiplexer data inputs 4 connected respectively to the two outputs of the storage unit ^nk 2.2 ^k, the multiplexer control inputs multichannel allocation group 5 are connected to the residue nk the second outputs of switch 1, where the k + 1st control input of the multi-channel multiplexer 5 is connected to the k + 1st input of the switch 1 and so on and the nth control input of the multi-channel multiplexer 5 is connected to the nth output of the switch 1, and the information inputs are connected to the outputs of the memory blocks 3.1, ..., 3.2 ^k , where the 1st 2 ^nk information inputs of the multichannel multiplexer 5 are connected respectively to the 2 ^nk outputs of the memory block 3.1 and so on and the 2 ^kth 2 ^nk information inputs of the multichannel multiplexer 5 are connected respectively to 2 ^nk outputs of the 3.2 ^k memory block, inputs of multipliers 6.1, ..., 6.2 ^nk modulo P are connected to the information outputs of multi-channel multiplexer 4 and multi-channel multiplexer 5, where the 1st input of multiplier 6.1 is connected to the 1st information output multi-channel channel multiplexer 4 and the 2nd input of the multiplier 6.1 is connected to the first information output of the multi-channel multiplexer 5 and so on and the 1st input of the multiplier 6.2 ^{nk is} connected to the 2 ^nk- th information output of the multi-channel multiplexer 4 and the 2nd input of the multiplier 6.2 ^{nk is} connected to 2 ^nk data output multichannel multiplexer 5 and outputs connected to inputs of the adder 7 through P mode, where the output of the multiplier 6.1 is connected to the 1st input of the adder 7 and so on and the output of the multiplier 6.2 is connected to 2 ^{nk nk-th} input of the adder 7 outputs adder 7 are output the output of the values of the Boolean functions f ₁ , ..., f _{d of the} device.

и с помощью управляющего сигнала, поступающего с управляющего входа устройства 11 подачи значений вычетов возведения переменной в i-тую степень по модулю P на управляющие входы блоков памяти 3.1, …, 3.2^k хранения значений вычетов возведения переменной в i-тую степень по модулю Р, осуществляется запись предвычисленных значений переменной X по модулю Р:

В момент времени, соответствующий началу преобразования, на входы 8.1, …, 8.n коммутатора 1 поступают значения булевых переменных х₁, х₂, …, х_n. В коммутаторе 1 под воздействием управляющего сигнала, поступающего на его управляющий вход с управляющего входа устройства 9 подачи значения количества переменных разложения, выделяются переменные разложения с 1-й по k-тую, которые поступают на управляющие входы многоканального мультиплексора 4 выделения группы коэффициентов, который обеспечивает выделение группы коэффициентов из блоков памяти 2.1, …, 2.2^k в соответствии со значением переменных разложения х₁, х₂, …, х_k, где значениям переменных разложения х₁=0, х₂=0, х_k=0 соответствует группа коэффициентов

и так далее и х₁=1, х₂=1, …, x_k=1 соответствует группа коэффициентов

. Остальные n-k значений булевых переменных поступают на управляющие входы многоканального мультиплексора 5 выделения группы вычетов, который обеспечивает выделение группы вычетов возведения переменной X=(x_n-kx_n-k+1x_n)₂ в степени 2^n-k, 2^n-k-1, …, 1, 0 в соответствии со значениями переменных x_n-k, x_n-k+1, …, х_n, значениям переменных х_n-k=0, х_n-k+1=0, …, х_n=0 соответствует группа вычетовThe work of the modular polynomial calculator of systems of Boolean functions is carried out as follows. In the initial state, using the control signal from the control input of the device 10 for supplying the coefficient values to the control inputs of the memory blocks 2.1, ..., 2.2 ^k , the values of the coefficient groups of the decomposition polynomials are recorded

and using the control signal coming from the control input of the device 11 for supplying the values of the residues of raising the variable to the i-th degree modulo P to the control inputs of the memory blocks 3.1, ..., 3.2 ^k storing the values of the residues of raising the variable to the i-th degree modulo P, the pre-calculated values of the variable X are recorded modulo P:

At the moment of time corresponding to the beginning of the conversion, the values of Boolean variables x ₁ , x ₂ , ..., x _n are received at the inputs 8.1, ..., 8.n of switch 1. In the switch 1, under the influence of a control signal supplied to its control input from the control input of the device 9 for supplying the value of the number of decomposition variables, the decomposition variables from the 1st to the kth are allocated to the control inputs of the multi-channel multiplexer 4 for selecting a group of coefficients, which provides the selection of a group of coefficients from the memory blocks 2.1, ..., 2.2 ^k in accordance with the value of the decomposition variables x ₁ , x ₂ , ..., x _k , where the values of the decomposition variables x ₁ = 0, x ₂ = 0, x _k = 0 corresponds to PPA odds

and so on and x ₁ = 1, x ₂ = 1, ..., x _k = 1 corresponds to a group of coefficients

. The remaining nk values of Boolean variables go to the control inputs of the multichannel residue group selection multiplexer 5, which provides the allocation of the residue group of the variable construction X = (x _nk x _{n-k + 1} x _n ) ₂ to the power of 2 ^nk , 2 ^nk -1, ..., 1, 0 in accordance with the values of the variables x _nk , x _{n-k + 1} , ..., x _n , the values of the variables x _nk = 0, x _{n-k + 1} = 0, ..., x _n = 0 corresponds to the group of residues

и так далее и значениям переменных х_n-k=1, х_n-k+1=1, …, х_n=1 соответствует группа вычетов

Из многоканального мультиплексора 4 поступает группа коэффициентов разложения на 1-е входы умножителей 6.1, …, 6.2^n-k по модулю P, где на 1-й вход умножителя 6.1 по модулю Р поступает коэффициент

и так далее и на 1-й вход умножителя 6.2^n-k по модулю Р поступает коэффициент

Из многоканального мультиплексора 5 поступает группа вычетов возведения переменной X в i-тую степень i=(х_n-kх_n-k+1х_n)₂ на 2-е входы умножителей 6.1, …, 6.2^n-k по модулю Р, где на 2-й вход умножителя 6.1 по модулю Р поступает значение вычета

и так далее и на 2-й вход умножителя 6.2^n-k по модулю Р поступает значение вычета Х⁰(Р). После преобразований в умножителях 6.1, …, 6.2^n-k значения вычислений поступают на входы сумматора 7 по модулю P, где после преобразований результат поступает на выходы устройства 12.1, …, 12.d выдачи значений булевых функций f₁, …, f_d, где младший разряд двоичного представления результата вычисления сумматора 7 соответствует значению f_d и подается на выход 12.d и так далее и старший разряд двоичного представления результата вычисления сумматора 7 соответствует значению f₁ и подается на выход 12.1.

and so on and the values of the variables x _nk = 1, x _{n-k + 1} = 1, ..., x _n = 1 corresponds to the group of residues

From the multichannel multiplexer 4, a group of decomposition coefficients for the 1st inputs of the multipliers 6.1, ..., 6.2 ^nk modulo P is received, where the coefficient is supplied to the 1st input of the multiplier 6.1 modulo P

and so on and the first input of the multiplier 6.2 ^nk modulo P receives the coefficient

From the multichannel multiplexer 5, a group of residues of raising the variable X to the ith degree i = (x _nk x _{n-k + 1} x _n ) ₂ comes to the 2 inputs of the multipliers 6.1, ..., 6.2 ^nk modulo P, where by 2- the first input of the multiplier 6.1 modulo P receives the value of the residue

and so on and to the 2nd input of the multiplier 6.2 ^nk modulo P, the residue value X ⁰ (P) is received. After the transformations in the multipliers 6.1, ..., 6.2 ^nk , the calculation values go to the inputs of the adder 7 modulo P, where after the transforms the result goes to the outputs of the device 12.1, ..., 12.d of outputting the values of the Boolean functions f ₁ , ..., f _d , where the youngest the bit of the binary representation of the calculation result of the adder 7 corresponds to the value of f _d and is fed to the output 12.d and so on and the high order bit of the binary representation of the calculation result of the adder 7 corresponds to the value of f ₁ and is fed to the output 12.1.

Thus, the technical effect is achieved through the implementation of the non-redundant polynomial form of representing the system of Boolean functions in the final field GF (P) by the hardware of multipliers modulo P and an adder modulo P, which reduces the number of bits of computing devices and memory by L times, where, in the case of the prototype, L is the number of redundant Boolean functions necessary to calculate the Boolean function in linear numerical form.

Literature

1. RU No. 2373564, 2009.

2. RU No. 2461868, 2012.

3. RU No. 1820377, 1993.

4. RU No. 2299461, 2007.

Claims (1)

A modular polynomial calculator of Boolean function systems, comprising a switch, the information inputs of which are n inputs of Boolean variables of the device, the control inputs of which are connected to the control input of the device for supplying the values of the number of decomposition variables, 2 ^k memory blocks for storing the values of the coefficients of the decomposition polynomials whose control inputs are connected to the control input of the device for supplying coefficient values, the information outputs of which are connected to the information inputs of many channel multiplexer group allocation coefficient control inputs of which are connected to the k first outputs of the switch, characterized in that the introduced 2 ^nk storage memory blocks erection of residues in the variable i-fifth degree, where i = 0,1, ..., ^nk 2 -1 for module P, the control inputs of which are connected to the control input of the device for feeding the residues of raising a variable to the ith power modulo Ρ, the information outputs of which are connected to the information inputs of a multi-channel multiplexer for selecting a group of residues, yayuschie whose inputs are connected to nk second information outputs of the switch, 2 ^nk multipliers, modulo P, where inputs j-th multiplier modulo Ρ connected to the j-th information outlets multichannel multiplexer allocation coefficient group and a multichannel multiplexer selection group residue, where j = 1 , 2, ..., 2 ^nk , the outputs of which are connected to the inputs of the adder modulo Ρ, d outputs of which are d outputs of the device for issuing the values of Boolean functions.

Images