SU1608641A1 - Device for computing boolean functions - Google Patents

Abstract

The invention relates to the field of automation and computer technology and is intended for calculating Boolean functions in control and monitoring systems. The aim of the invention is to improve the performance of the device. The device for calculating Boolean functions contains two switches 1 and 2, a decoder 3, two groups of flip-flops 4 and 5, a program memory block 6, a HE 7 element, a trigger 8, a pulse driver 9, an AND 10 element, an EXCLUSIVE OR 11 element, and two adders 12 and 13, the group of elements is NOT 14, the group of elements is OR 15. The device allows the computation of Boolean functions by programs composed of three types of linear binary graphs (LBG), which allows choosing the algorithm that is most optimal by the number of commands and the minimum computation time . 2 ill., 2 tab.

Description

The invention relates to automation and computing and is intended to compute Boolean functions in control and monitoring systems.

The aim of the invention is to improve the performance of the device. - Figure 1 shows a block diagram of a device for calculating Boolean functions; Fig. 2 shows flowcharts of algorithms for calculating Boolean functions.

The device contains two switches 1 and 2, a decoder 3, two groups of triggers 4 and 5, a program memory block 6, a NOT 7 element, a trigger 8, a pulse shaper 9, an AND 10 element, an EXCLUSIVE OR 11 element, two adders 12 and 13, a group of elements is NOT 14, a group of elements is OR 15, a clock input 16, an input 17 of a logical zero setting, a group of information inputs 18, a group of outputs 19, an input 20 of an initial setting.

There are Boolean functions for which a program constructed from linear binary graphs (LBG) is not optimal by the number of instructions. For example, consider the function yo

 X2X1VX2XOVX2X1XO.

The LBG of this function is shown in Fig. 2a and consists of six vertices of conditional transitions. Dov and two operator vertices (the vertices of the assignment of the value of yo 0 and yo 1). The computation program constructed for this LBG consists of eight instructions, respectively. Table 1 presents the table of truth of the function yo.

We represent each set of values of the arguments X0, Xi, X2 by the natural number X in accordance with the formula

X i Xi 2. .

Now the calculation process can be

represented by an algorithm of the second kind (LBG 2). The LBG 2 of the function uo (fig. 26) contains four vertices (two vertices of the conditional transition and two vertices of the assignment of the values во О and уо 1), i.e. two times less than in LBG. Thus, for the function yo, the program based on LBG 2 is more optimal in the number of commands. The device operates as follows.

When the input 20 of the initial installation, a signal prohibits the operation of the device (on the negative front of the first, after the appearance of the prohibition signal, clock pulse) at the output of the trigger 8. the signal of setting the group of triggers 4 to the initial state is formed. At the same time, at the outputs of the group of triggers 4 will have

the place is a zero code, regardless of the arrival on their clock inputs of clock pulses, and the device will be in the waiting state. When a signal appears at input 5 and 20 of the initial installation of the device that permits operation of the device (on the negative front of the first clock pulse), the output of the trigger 8 will form. signal that permits the operation of the trigger-10 goopp 4.

Each command recorded in block 6 of the program memory contains the code for the boundary of the numeric interval: the code of the algorithm feature; the code of the attribute sign; code of the address of the com- mand 15, which the device will begin to perform in the next cycle; the address code of the result of the calculated function; permission code to write the result of the calculation of the logical function; The result code is the computation of a logical function.

The device can work both according to programs compiled by LBG, and according to programs compiled by LBG 2.

Moreover, if the feature code of the algorithm, 25 arriving at the control input of switch 1, is equal to Log.O, then the device implements the program set by the LBG, otherwise - by the LBG 2.

 The procedure for calculating Boolean functions is as follows.

The first program command, located in block 6 of the program memory, at the zero address, when the device is in the waiting states, can be a program command, compiled by LBG or LBG 2. Not breaking the community, consider first operation of the device according to the program compiled by the LBG. In this case, when forming at the outputs of block 6 of memory 40 programs of the first command, the signal corresponding to the value of the first interrogated argument of the first function arrives at the first input of the EXCLUSIVE OR 11 element. The choice of the polled argument 45 is as follows. The control input of the switch 1 is given a signal Log.O, while the second input of the adder 13 receives the code Ho, ... Xn,

each bit of which is formed according to the formula Xi (X | v Zi), where Zi is the corresponding bit code of the boundary of the numeric interval, coming from the outputs of block 6 of program memory to the second inputs of the OR 15 group elements, Xi is the corresponding 55 argument of the calculated function .

In order for the value of the signal at the transfer output of the adder 13 to be equal to the value of the argument being polled, a log is written to the corresponding digit of the boundary code. G, in the remaining bits of this code - Log.O.

Suppose that it is necessary to apply an EXCLUSIVE or 11 signal to the first input of the element corresponding to the value of apf MeHTa Xi.

Then the code of the corresponding border of the 10TH interval is O ... O, 1.0 ... O, only in the 1st bit is recorded SG, in the remaining bits - Log.O.

At the same time, for you, the KOMMyTajopa ode 1 forms the code Xp ... Hni, 1, ii ... Ho, which steps on the second inputs of the adder 13, on the pi inputs of which the code Xn goes ... - ,, Ho . When these codes are added, the renal output of the adder 13 generates a signal corresponding to the value of Xi.

Thus, when a PS device is running, compiled by an LBG, the device allows the code to use the boundary of a numerical interval to form a signal at the transfer output of the adder 13, the value of which is equal to the value of the polled argument.

The first input of the EXCLUSIVE-: E or 11 signal is received, the value of the value is equal to the value of the polled argument, the second input of the EXCLUSIVE OR 11 element receives a signal of the attribute of this argument equal to Log.G, 1I argument enters the LBG algorithm with logging, and Log. About otherwise. If at the output of the EXCLUSIVE- || EE or 11 element, a signal of Log.1 is formed, (at the second inputs of the adder 12, a code is formed, corresponding to the number 1, and the first inputs of the adder 12 through the switch: TOJP 2 will receive a code from the outputs of the trigger 4 / Let us designate the number corresponding to DMy code A. Then at the output of adder 12 a code will be formed corresponding to the number

- one.

If at the output of the EXCLUSIVE OR 11 element a Log.O signal is generated, then at the outputs of the adder 12 a crossbar of the command address from block 6 of the program memory will be generated,

The code on the outputs of the adder 12 determines which command the device will execute in the c / eject clock. In the first case, the ETR will be the next order command, and in the second, the command whose code is written in n (1 is the command number of the command being executed.

After the appearance on the setup inputs X of the group of triggers 4 signals, allowing them to work on the clock inputs, on the positive edge of the first clock pulse, the code that occurs on the outputs of the adder 12. is recorded in the group of triggers 4. programs, a new command code is generated. In this case, if the value of the polled argument does not fully determine the value

function, then this command queries another argument of the same function. If the value of the function is completely determined by the value of the polled argument, then the result of calculating the function is written to one of the triggers of group 5, depending on the result address code that arrives at the address inputs of the decoder 3 from the program memory block 6, transition to the first command of the program calculating the following function. To proceed to the calculation of the next function in the command, which is used to record the result of the calculation, a zero code is written in the code field of the boundary of the numerical interval. The signal Log.O. is recorded in the attribute field of the argument. In the address field of the command, the code of the address of the command that is used for polling and analysis is recorded.

5 of the first argument of the next function, or the code of the address of the first command of the program for calculating the next function built on LEG 2.

The operation of the device according to the program compiled by .PBG 2.

A program of this type on adder 13 produces a sequential addition of the value of the vector X {Xn, ..., Ho} with the numbers Zi written in the code field of the boundary,

5 of the numerical interval, wherein Zi is an additional code of the boundary of the numerical intervals Zi, Zn-i, on which the calculated function takes opposite values. In addition, when

When executing a program compiled by the HLG 2, a log is recorded in the flag field of the algorithm of all commands of this program, with the exception of the value assignment commands. 1, in the sign field of the argument of the record 5, there is Log.O, the remaining half of the commands are

block 6 program memories are formed

the same as for programs built on LBG.

According to the commands of the program built

according to LBG 2, vector addition is performed

0 argument values with optional boundary code. This operation is equivalent to comparing the number corresponding to the vector of argument values and the border. If X Zi, then at the output of the transfer of the adder 13

5, the signal of Log.1 is formed and, by this signal, the device proceeds to the execution of the next order command. If X Zi, then at the output of the transfer of the adder 13 a signal Log.O. On this signal, the device proceeds to the execution of a command whose address is recorded in the address field of the command. The transition to the subsequent command is performed in the same way and in the other case as in the implementation of the program built on the LBG. The same can be said about the result recording commands — for all types of programs they are formed in a similar way.

After calculating all the logical functions for any type of program, the device can proceed to the calculation of the first function. To do this, in the address field of the command of the last two commands of the program, you must write the address of the first command of the program.

In addition, the device can stop the calculations, for which the address code of the last two commands of the calculation program is written with the address code of the additional, empty command, in the code field of the boundary of the numerical interval of which logic zeros are written, into the field of the algorithm feature and the attribute argument - Log.O in the field of the command address - the address of this command, in the field of the permission to output the result - Log.O,

In this case, the device will continuously execute this command before transferring it to the idle state with a signal from input 20 of the initial device setup.

Table 2 presents two programs for calculating the function:

OS X2X1VX2XOVX2X1XO.

At the same time, the first program (commands 0–7) is constructed from the LBG, and the second (commands 8–11) - from the LBG 2. The LBG and LBG 2 of this function (Fig. 2a, b) are constructed to compile the calculation programs.

The compilation program for LBG is compiled as follows (Table 2, commands O - 5).

Column 4 records the codes of the addresses of the arguments of the computed function in the order in which these arguments are located in the LBG; the code of the address of any variable is formed as follows, in that code bit, the number of which is identical to the number of the argument in question, is written 1, in the remaining bits -

in each row of column 5 is entered

in each row of column 6 is entered 1, if the argument, the address code of which is written in this row, is included in LBG c), this is written otherwise;

in each row of column 7 is written the address code of the command to execute which you must go to zero

the value of the expression that stands in the vertex LBG corresponding to this line; .

in each row of column 9 is written

what will be written in columns B and 10,

does not matter;

the next line in the order (command 6) records the command for writing the result of the function calculation by the single 0 value of the expression at the last LBG vertex, then writes the command for writing the opposite result (command 7).

Commands for recording the result are formed in the same way for any of the programs considered in the description. In this case, zero codes are written in columns 4, 5, 6, column 9 is written in 1, column 8 is the code of the number of the calculated function, column 10 is the corresponding value of the function, column 7 is entered into the code of the address of the command to which need to go after recording the result.

The compilation of a calculation program for 5 LBH 2 is performed as follows (commands 8 and 9 of table 2).

Column 4 records the additional codes for the boundaries of the numeric intervals;

in column 5 - 0c column

In each row of column 7, the address code of the command to execute which must go through the zero value of the expression, which corresponds to the vertex LBG 2 corresponding to this line, is written, and the LBG 2 vertex is assumed to take a zero value if the expression written in it is not satisfied; column 9 is written O; The 40 that will be recorded in columns 10 and -8 does not matter.

The result recording commands (commands 10 and 11 of table 2) are formed and interleaved in the same way as when creating the program

45 on LBG.

Consider the process of calculating v0 with the following values of the arguments X0 1.

Xl 1,

Commands 0–2 perform a successive interrogation of arguments X2, Xi, X0 and go to the next order command, since all these arguments have the value 1 and O. Team 3 performs a repeated analysis of X2 with 55 symptom 1, sinceX2-- 1 also forms a conditional transition to the .com command recorded

at 01112

At this address is the result recording command (command 7) at address O (i.e., a trigger with a zero address of a group of trigger O, MORE

SIGNS

Reho 1000 pr

1112

THAT

moat5 |. Since, according to this command, the inputs of the first and second terms of the adders

FORMS CODE X2. Xl, Ho and X2. Xl, (0

cooTt is natural (for our example, this is co-12 and LLC), then a zero-level signal is generated at the transfer output of sum 13. Since the attribute argument is equal and at the output of the EXCLUSIVE OR 11 element, a zero l is also formed. This signal is organized by the command 8 command located at the address. By this command, the condition 7 3 is measured (in binary codes S0112), this check is performed by stitching 13 on the adder 13 codes 1112 and 1012 (where 1012 is an additional code of the number 3)

In this case, the signal at the output of the transfer of the adder 13 will take a single value, since the sign of the argument is equal to O, the output signal of the EXCLUSIVE OR 11 element produces a signal of the unit level. On a signal, the device proceeds to the next command of the order 9. This command checks the status of 7 7 and, as in the previous command, the result of the comparison is carried out one to the next order of this command, the command calculates the result of the calculation address 01.

THIS

bad

By

catch it;

by p

re:

ten.

P)

Thus, the device allows you to perform a calculation using both programs built on LBG and LBG 2.

In addition, the device allows the implementation of programs using a mixed algorithm, an example of which is given in Fig. 2b for a function;

yi X1VX1X2XO.

The program for calculating this function, compiled by a mixed algorithm, is presented in Table 2 (commands 12–15). On figg, d two types of calculation algorithms are presented - LBG and LBG 2. Each of them consists of three conditional and two operator vertices. This means that to implement any of them, you need to use five commands. The mixed computational algorithm51 (let's call it LBG of the third kind or LBG 3) contains two conditional vertices and two (iterators, respectively, four commands are required for its implementation. For the first command (command 12, table 2), analyze the variable Xi, and The second command (command 13) checks the condition X 2: 5. The last two commands (14 and 15) are the result write instructions.

The ability to compile LBG 3 programs is provided by matching the variable value analysis commands and the conditional execution commands, More or equal.

Claims (1)

Invention Formula A device for calculating boolean functions, containing a program memory block, a decoder, two groups of flip-flops, a NOT element, a trigger, a pulse shaper, an AND element, an EXCLUSIVE0 ALTOR element, a Hibernation switch, the first adder, and the outputs of the result code of the program memory block are connected to the address inputs of the decoder , the building input of which is connected to the output of the element I, the first input of which is connected to the output of the recording result resolution of the program memory block, the second input of the element .1 is connected to the output of the pulse former, the input of which is single n a clock input of the flip-flop and the output of NOT circuit whose input is connected to the clock input of the device and the clock input triggers a first group in D inputs of which are connected to 5 trigger output, information input of which is connected to the input of the initial installation of the device, the outputs of which are connected to the outputs of the second group of triggers, the clock input of the 1st of which is connected to 0 by the 1st output of the decoder (i 1. p), the information inputs of the second group of flip-flops are connected to the output of the result value of the program memory block, the address inputs of which are connected to the triggers of the triggers 5 of the first group, the first input of the EXCLUSIVE element OR is connected to the output of the attribute of the argument of the program memory block, the outputs of the code of the address of the conditional transition of which are connected to the first 0 inputs of the first switch, the control input of which is connected to the output of the EXCLUSIVE OR element and to the input of the lower bit of the first term of the first adder, the inputs of the higher bits 5 of the first addend of which is connected to the installation input of the logical zero of the device, the inputs of the second addend of the first adder are connected to the output of the first switchboard, the second entrances of which are connected to the trigger outputs of the first group, the informational inputs of which are connected to the outputs of the first adder, characterized in that in order to improve performance, it contains a group 5 elements-NOT, a group of elements OR, the second switch and the second adder, and the input of the first term of the second adder is connected to the information inputs of the device group, the i-th information input of which is connected to the I-M element NOT group, the output of which is connected to the first input of the 1st element OR of the group, the output of which is connected to the 1st input of the first group of inputs of the second switch. The 1st bit of the second group of inputs of which is connected to the second input of the i-element of the OR group and With the 1st output of the code boundary of the numerical intervals of the program memory, the output of the attribute of the algorithm of which is connected to the control input of the second switch, the output of which is connected with the input of the second variable adder, the transfer output of which is connected to the second input of the EXCLUSIVE OR element. Table 1 Xi O O 1 1 O about 1 1 Ho o 1 o 1 o 1 about 1 Wo oh about about 1 1 1 1 about ten table 2