RU2373564C2 - Modular calculator of boolean function systems - Google Patents

Abstract

FIELD: information technologies.

SUBSTANCE: invention is related to computer engineering and may be used as a specialised calculator of Boolean functions systems. Goal defined is achieved due to provision of calculation of not the whole system of Boolean functions, represented in modular numerical normal form, but just one system of subfunctions, represented in modular numerical normal form, obtained as a result of decomposition applied to system of Boolean functions. Device comprises commutator, unit of conjunctions, 2^k memory units, where k is number of Boolean decomposition variables, 2^n-k multiplexers, summator.

EFFECT: reduced duration of calculations.

2 dwg, 3 ex

Description

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

A specialized computing device is known, including an adder whose output is connected to the second input of the result register, a register for storing Boolean variables, the output of which is connected to the conjunction block, registers for fixing the next rows of matrices describing the structure of the corresponding conjunction, the outputs of which are also connected to the block conjunctions, the output of which is connected to the third input of the result register, the output of which is the bus for issuing the calculation result (Malyugin V.D. Parallel logically e calculations by means of arithmetic polynomials. - M.: Science. Fizmatlit, 1997. - P.156-157).

A disadvantage of the known device is the long duration of the calculations.

Closest to the essence of the technical solution to the claimed device is a specialized computing device containing a conjunction block, the inputs of which are a bus for supplying values of Boolean variables, the outputs of which are connected to a memory block, the outputs of which are connected to the inputs of a switch, the outputs of which are connected to a multi-seat adder, the outputs of which are the outputs of the device issuing the result of the calculations (Malyugin V.D. Parallel logic calculations by means of arithmetic polynomials. - M.: Science.Fizmatlit, 1997. - P.154-155).

A disadvantage of the known device is the long duration of the calculations.

The purpose of the invention is to reduce the duration of the calculations.

This goal is achieved by the fact that in a specialized device for logical computing (SULV), containing a switch, the inputs of which are inputs of a device for feeding n Boolean variables, a conjunction block, the outputs of which are connected to the first memory block, a multi-place adder, the outputs of which are outputs of a device for outputting values Boolean functions, in order to reduce the computation time, 2 ^k -1 memory blocks are introduced, where k is the number of Boolean expansion variables, 2 ^nk multiplexers, while the inputs (k + 1) ... n of the switch connected to the inputs of the conjunction block, the outputs of which are connected to the inputs of the second, third and so on, 2 ^k- th memory blocks, respectively, the first outputs of the memory blocks are connected to the information inputs of the first multiplexer, the second outputs of the memory blocks are connected to the information inputs of the second multiplexer, and so on , (nk) -th outputs of memory blocks connected to the data inputs of 2 ^nk -th multiplexer, respectively, the outputs of the multiplexers are connected to the inputs of the adder bench, and the first, second and so on, k-th address in ode multiplexers connected respectively to the first, second and so on, k-m outputs of the switch.

The structural diagram of the proposed SULV is presented in figure 1. Let a system of Boolean functions (SBF) be given: f ₁ (x), f ₂ (x), ..., f _d (x) of n Boolean variables x = x ₁ , x ₂ , ..., x _n (x _i ∈ {0 , 1}, i = 1,2, ..., n):

where F (x) is the value taken by the d-output BF.

It is known that SBF (1) can be unambiguously represented in numerical normal form (CNF):

where α ₀ , α ₁ , α ₂ , ... α _n ∈Z, Z is the set of integers, F (x) when represented in binary notation is interpreted as the result of calculating the SBF.

Example 1. Let SBF (1) be given by the formulas:

then ChNF (2) will look like:

assigning the values x ₁ = 1, x ₂ = 1, x ₃ = 1, x ₄ = 1 to the Boolean variables, we obtain

SBF calculation result (3)

Since the number 9 in the binary notation is written as (01001) ₂ , then f ₁ (x) = 1, f ₂ (x) = 0, f ₃ (x) = 0, f ₄ (x) = 1, f ₅ (x) = 0 (the values of f ₁ (x) are in the lowest order (right), and f ₅ (x) is in the highest order on the left)).

It is known that SBF (1) can be uniquely represented on the basis of modular CNF (2) in the form:

,where d is the number of realized Boolean functions,

,

(mod 2 ^d ) - indicates that the calculation (5) is performed in the final ring

- получение наименьшего неотрицательного вычета от x по модулю 2^d.

- getting the smallest non-negative residue from x modulo 2 ^d .

Example 2. Let the CNF (4) SBF (3) be given, then the modular form (5) will have the form:

assigning the values of boolean variables: x ₁ = 1, x ₂ = 1, x ₃ = 1, x ₄ = 1, we get:

- результат вычисления СБФ (3).

- the result of the calculation of SBF (3).

It is known that any SBF, depending on n arguments, can be decomposed into variables and presented in the form:

Where

We generalize (7) for an arbitrary number of expansion variables, we obtain:

- степень аргументов x_k, p_k - двоичная переменная величина такая, чтоWhere

is the degree of arguments x _k , p _k is a binary variable such that

By attaching fixed values to the decomposition variables: 0 ... 0; 0 ... 1; ...; 1 ... 1, expansion (9) can be written as

Example 3. Let SBF be given (3). Expand each function in the variables x ₁ , x ₃ . Then SBF will look like:

и присвоим булевым переменным значения x₂=1, x₄=1, представим каждую систему подфункций в ЧНФ:Combine the decomposition subfunctions into systems

and assign the values x ₂ = 1, x ₄ = 1 to the Boolean variables, represent each system of subfunctions in the CNF:

and then in modular CNF:

соответствует результату вычисления F(x).Calculation result

corresponds to the result of calculating F (x).

Thus, to find the desired result, it is enough to calculate only one system of subfunctions represented by the modular CNF in accordance with the coordinates determined by the values of the decomposition variables. In this example, the coordinates of the subfunction system are the values of the decomposition variables x ₁ = 1, x ₃ = 1.

The proposed device SULV includes: inputs 6.1, ..., 6.n supply values of Boolean variables, switch 1, block 2 conjunctions, blocks 3.1, ..., 3.2 ^k memory, multiplexers 4.1, ..., 4.2 ^nk , adder 5, outputs 7.1, ..., 7d yields the values of Boolean functions: f _d (x), ..., f ₁ (x).

Inputs 6.1, ..., 6.n of supplying the values of Boolean variables x ₁ , x ₂ , ..., x _n , which are the inputs of the device, are also inputs of the switch 1, outputs (k + 1) ... n of which are connected to the inputs of block 2 of the conjunctions, the outputs of which are connected to the inputs of the blocks 3.1, ..., 3.2 ^{k of} memory, respectively, the first outputs of the blocks 3.1, ..., 3.2 ^{k of the} memory are connected to the information inputs of the multiplexer 4.1, the second outputs of the blocks 3.1, ..., 3.2 ^{k of} memory are connected to the information inputs of the multiplexer 4.2 and so further, (nk) -e outputs of blocks 3.1, ..., 3.2 ^{k of} memory are connected to the information inputs of the multiplexer 4.2 ^nk, respectively, the outputs of the multiplexers 4.1, ..., 4.2 ^{nk are} connected to the inputs of the multi-place adder 5, and the first, second, and so on, the k-th address inputs of the multiplexers 4.1, ..., 4.2 ^{nk are} connected respectively to the first, second, and so on, k -th outputs of the switch 1. The outputs 7.1, ..., 7.d of the multi-seat adder 5 are the outputs of the device for issuing the values of Boolean functions: f _d (x), ..., f ₁ (x). The proposed device operates as follows.

модулярных ЧНФ (11.1), (11.2),…,(11.2^k) соответственно, полученных в результате разложения (9). В момент времени, соответствующий началу преобразования, на входы 6.1,…,6.n коммутатора 1 поступают значения булевых переменных x₁,x₂,…,x_n. В коммутаторе 1 под воздействием внешних сигналов управления, в соответствии с заранее выполненным разложением (9) из состава поступивших переменных x₁,x₂,…,x_n выделяются переменные разложения x_i1,…,x_ik, которые поступают на адресные входы мультиплексоров 4.1,…,4.2^n-k, а остальные - информационные переменные x_ik+1,…,x_in - подаются далее на входы блока 2 конъюнкций. Блок 2 конъюнкций предназначен для вычисления конъюнкций: x_ik+1; x_ik+2; x_ik+1·x_ik+2;…; x_ik+1·x_ik+2·…·x_in, которые поступают на входы блоков 3.1,…,3.2^k памяти, с первых выходов которых коэффициенты

поступают на информационные входы мультиплексора 4.1, со вторых выходов блоков 3.1,…,3.2^k памяти коэффициенты

, значения соответствующих конъюнкций которых равны 1, поступают на информационные входы мультиплексора 4.2 и так далее, с (n-k)-x выходов блоков 3.1,…,3,2^k памяти коэффициенты

значения соответствующих конъюнкций которых равны 1, поступают на информационные входы мультиплексора 4.2^n-k. Общая задача мультиплексоров 4.1,…,4.2^n-k заключается в том, чтобы в соответствии со значениями булевых переменных x_i1…,x_ik, поступивших на адресные входы и определяющих параметр разложения, подать на входы многоместного сумматора 5 значения коэффициентов

одной из подсистем БФ, представленной в модулярной ЧНФ. После преобразований в многоместном сумматоре 5 на выходы устройства поступают вычисленные значения СБФ в следующем порядке: f_d(x), f_d-1(x), …, f₁(x).In the initial state, groups of coefficients are entered in blocks 3.1, ..., 3.2 ^{k of} memory:

modular CNFs (11.1), (11.2), ..., (11.2 ^k ), respectively, obtained as a result of decomposition (9). At the moment of time corresponding to the beginning of the transformation, the values of Boolean variables x ₁ , x ₂ , ..., x _n are received at inputs 6.1, ..., 6.n of switch 1. In switch 1, under the influence of external control signals, in accordance with the previously performed decomposition (9), the decomposition variables x _i1 , ..., x _ik are allocated from the input variables x ₁ , x ₂ , ..., x _n to the address inputs of multiplexers 4.1 , ..., 4.2 ^nk , and the rest - information variables x _{ik + 1} , ..., x _in - are then fed to the inputs of block 2 of the conjunctions. Block 2 conjunctions designed to calculate conjunctions: x _{ik + 1} ; x _{ik + 2} ; x _{ik + 1} · x _{ik + 2} ; ...; x _{ik + 1} · x _{ik + 2} · ... · x _in , which enter the inputs of blocks 3.1, ..., 3.2 ^{k of} memory, from the first outputs of which the coefficients

come to the information inputs of the multiplexer 4.1, from the second outputs of blocks 3.1, ..., 3.2 ^k memory coefficients

, the values of the corresponding conjunctions of which are equal to 1, go to the information inputs of the multiplexer 4.2 and so on, with (nk) -x outputs of the blocks 3.1, ..., 3.2 ^k memory coefficients

the values of the corresponding conjunctions of which are equal to 1, go to the information inputs of the 4.2 ^nk multiplexer. The general task of multiplexers 4.1, ..., 4.2 ^nk is to, in accordance with the values of the Boolean variables x _i1 ..., x _ik , received at the address inputs and determine the decomposition parameter, apply the coefficients to the inputs of the multi-seat adder 5

one of the subsystems of the BF presented in modular CNF. After transformations in the multi-place adder 5, the calculated SBF values are received at the device outputs in the following order: f _d (x), f _d-1 (x), ..., f ₁ (x).

The duration of the functioning of the VCA - prototype is defined as:

where T _to - the duration of the switch,

T _bq - the duration of the functioning of the conjunctions unit,

T _ротprot is the duration of the functioning of the multi-seat adder of the prototype,

T _ротprot = _{Δτ LE} 4dlog ₂ 2 ⁿ = Δτ _LE 4dn, where Δτ _LE is the delay time of one two-input logic element (LE), n is the number of Boolean variables, d is the number of realized Boolean functions.

The duration of the proposed SULV is defined as:

T _{∑ declared} - the duration of the operation of the multi-seat adder of the proposed SULV,

T _{аяв declaration} = _{Δτ LE} 4dlog ₂ 2 ^nk = Δτ _LE 4d (nk), where k is the number of Boolean expansion variables,

T _MS - the duration of the multiplexer,

T _MS = Δτ _LE (k + log ₂ (k + 1)).

From (11) and (12) it can be seen that the total of both the prototype and the proposed SULV is the sum of the durations T _k + T _bk = T _{k, bq} . The duration of the operation of the proposed device differs from the duration of the functioning of the prototype by a reduced duration of operation T _{аяв the} adder 5 is _declared . Assuming that the switch 1 is structurally a circuit of a series-connected multiplexer and a demultiplexer, and the conjunction unit 2 is constructed according to the principle shown in Fig. 2, the payoff ratio reducing the duration of the proposed SULV computation with respect to the prior art in view of the duration of operation T _MS multiplexer bude defined by the expression:

For example, with values: d = 10, n = 16, k = 1, the minimum gain in reducing the calculation time of the proposed SULV with respect to the prototype will be 6 percent, with values: d = 10, n = 16, k = 4, the gain will be 24 percent , with values: d = 10, n = 16, k = 8, the gain will be 48 percent. The resulting gain is achieved by providing a replacement for computing the entire SBF by computing only one system of subfunctions selected from the decomposition.

Claims (1)

A device for calculating Boolean functions, comprising a switch, the inputs of which are inputs of a device for supplying n Boolean variables, used to extract expansion variables of a system of Boolean functions, a conjunction block whose outputs are connected to the first memory block, a multi-input adder, the outputs of which are outputs of the value output device Boolean functions, characterized in that 2 ^k -1 memory blocks are additionally introduced, where k is the number of Boolean expansion variables, with 2 ^k memory blocks intended s for storing 2 ^k groups of coefficients of modular numerical normal forms obtained as a result of a previously performed decomposition of a system of Boolean functions, 2 ^nk multiplexers, while from (k + 1) to the n-th outputs of the switch are connected to the inputs of the conjunction block, the outputs of which connected to the inputs from the second to 2 ^k- th memory blocks, respectively, the first (nk) -th outputs of the memory blocks are connected to the information inputs of the first 2 ^nk- th multiplexer, the outputs of the multiplexers, which receive the values of the coefficients of one of the subs the system of Boolean functions, presented in modular numerical normal form, in accordance with the values of Boolean variables that determine the decomposition parameter, are connected to the inputs of the multi-input adder, the first to kth address inputs of the multiplexers are connected respectively from the first to kth outputs of the switch, on which values of Boolean variables are formed that determine the decomposition parameter.

Images