JPH06162134A - Multistage structuring device for logic circuit - Google Patents

Abstract

PURPOSE:To constitute a multistage logic circuit which is shown by a truth table by efficiently extracting factors and minimizing the scale of the logic circuit. CONSTITUTION:A rectangle extracted from the contents of a candidate factor storage device 12 by using a rectangle extracting device 13 is compared with a rectangle extracted by using a logical structure converting device 14 and the logic circuit is formed into multistage structure by using the comparison result. Further, the logical structure converting device 14 converts the logical structure of candidate factors stored in a candidate factor storage device 12.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a logic circuit multistage device, and more particularly to a device for converting a truth table into a multistage logical expression.

[0002]

2. Description of the Related Art A conversion from a truth table to a general multi-stage logical expression is performed by a logic circuit realized by the multi-stage logical expression as shown in FIG. This is to convert a truth table, which is a two-stage logic circuit that exists, into a logic circuit that has one or more stages of gates in the path from the input to the output. This conversion is done to reduce the size of the circuit as evaluated by the total number of inputs on each gate. Conventionally, the conversion from a truth table to a general multi-stage logical expression is repeated by selecting a factor that can be divided only by itself from the logical formula that realizes the two-stage logical circuit and dividing the logical formula by the factor. ("Reference: Earl K. Brayton, C. McMullen," The Decomposition and Factorization of Boolean Expressions ": Proceeding AIS CIS-82, 1982 (RK Bra.
yton and C.I. McMullen "The
decomposition and factori
zation of Boolean express
ions, “in Proc. ISCAS-82, 19
82) ").

In the above method, a factor that reduces the circuit size to the maximum is selected at that time, and division is performed by that factor. However, to select the factor that reduces the circuit size to the maximum, It is obtained by expressing the state of the logical expression of the circuit in a matrix form (FIG. 4) and selecting the largest rectangle from the matrix-shaped storage state (FIG. 5). In order to find the maximum rectangle, a method of enumerating all the rectangles and finding the largest rectangle among them can be considered, but this method requires a long calculation time and is not generally used.
Therefore, the following approximation method is used to search for a rectangle corresponding to a factor that reduces the circuit size to a maximum in a short calculation time. Step 1: Find the longest row in the horizontal direction,
_Set to ₁ . Step 2: Let the row length of R _{1 be} r ₁ . Among the rectangles having a row length of 2 and including a part of R ₁ , the one having the largest size is selected and designated as R ₂ . Step 3: Let the row length of R _{i be} r _i . Among the rectangles including a part of R _i and having a row length r _i +1 and having a maximum size, the rectangle is selected and designated as R _{i + 1} . Step 4: Continue Step 3 until R _{i + 1} is one row. Let R _r be the rectangle when there is one row. Step 5: Find the largest rectangle among R ₁ , R ₂ , ... R _r . Let this be R _max . Step 6: Find the longest line in the vertical direction,
_Set to ₁ . Step 7: Let the length of the column of C _{1 be} c ₁ . A rectangle having a column length of 2 including a part of C ₁ and having the largest size is selected and designated as C ₂ . Step 8: Let the length of the column of C _{i be} c _i . Among the rectangles including the part of C _i and having the column length c _i +1 and having the largest size, the one having the largest size is selected and designated as C _{i + 1} . Step 9: Continue Step 3 until C _{i + 1} has one column. Let C _c be the rectangle when there is one row. Step 10: Find the largest rectangle among C ₁ , C ₂ , ... C _c . _Let this be C _max . Step 11: Select one having a large R _max and C _max .

[0004]

In the above approximate solution method,
In the matrix-like logic state as given in FIG.
When the maximum long row or column in step 1 or step 6 is used as a starting point, the rectangle having the maximum weight as shown in FIG. 5 cannot be obtained, which reduces the circuit scale to the maximum. It is not possible to select a factor that causes

It is an object of the present invention to provide an apparatus for converting a logic circuit of a small scale with a short calculation time and a small calculation storage capacity when given a logical expression. In particular, it is intended to provide a device that solves the problem of the above approximation method, selects a factor that reduces the circuit size to the maximum, and divides the logic circuit using the factor to minimize the circuit. is there.

[0006]

SUMMARY OF THE INVENTION A logic circuit multistage apparatus according to the present invention uses a conversion state storage unit for storing a conversion process from a truth table of the invention 1 to a multistage logical expression and an algebraic method from the logical expression. A logical expression dividing device that divides factors by factors, a candidate factor storage device that stores candidate factors in a matrix, a rectangular extraction device that selects a rectangular submatrix with the maximum weight from the candidate factor storage device, and the candidate factors. A logical structure conversion device for converting a logical structure of stored contents of a storage device; a factor conversion device for converting a rectangle in a matrix of candidate factors stored in the candidate factor storage device into a factor; and a control device for controlling these. A longest row removing device and a longest column removing device for efficiently structurally converting the contents of the candidate factor storage device of invention 2;
A logic circuit multistage device comprising a shortest-row removing device and a structure conversion device including a structure conversion control device for controlling the shortest-row removing device, and a smaller multistage circuit with less calculation time and smaller storage capacity. Realize to convert to.

In the logic circuit multi-stage device of the present invention, the rectangle extracting device selects from the candidate factor storage device a factor that approximately reduces the circuit scale to the maximum, and in parallel with this, the structure conversion device is a candidate. From the matrix-like storage state of the factor storage device, the longest row removing device, the longest column removing device, and the shortest row removing device are used for structural conversion, the storage contents of the candidate factor storage device are converted, and the converted candidate factor storage From the device, using a rectangle extractor, compare these two factors by selecting again the factor that approximately reduces the circuit size to the maximum, and select the factor that further reduces the circuit size,
By dividing the factor by using a logical divider, the logic circuit is multistaged and the circuit scale is reduced.

[0008]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, the present invention will be described with reference to the drawings. FIG. 1 is a block diagram showing an embodiment of a logical multistage device of the invention 1, and FIG. 2 is a block diagram showing an embodiment of a logical structure conversion device of the invention 2. The logical structure conversion device of FIG. 2 is shown in FIG.
It is one constituent element in the logic multistage device.

The truth table to be converted according to the first aspect of the invention is stored in the conversion state storage device 11, and the candidate factors in the process of conversion are stored in a matrix in the candidate factor storage device 12. By executing the extraction of the rectangular factors by the rectangular extraction device 13 with respect to the candidate factors stored in the candidate factor storage device 12, a rectangle having the largest circuit size can be obtained. The logical structure is converted by the logical structure conversion device 14 with respect to the candidate factors stored in 12.
The result of the rectangular factor extraction performed by the rectangle extraction device 13 due to the change in the logical structure of the candidate factor stored in the candidate factor storage device 12 is more than that before the logical structure conversion device 14 executes the logical structure conversion. Only when a rectangle with which a large circuit scale can be obtained is obtained, the rectangle is converted into a factor by the factor conversion device 15 and divided by the logical expression division device 16 to make the logic multistage. The control device 17 can also cause the logical structure conversion device 14 to repeatedly execute the conversion of the logical structure.

On the other hand, the logical structure conversion device of FIG. 2 receives a candidate factor from the candidate factor storage device 12 in the logical multistage device of FIG. 1 and causes the longest row deletion device 21 and the longest column deletion device 22 to obtain the longest row and column. Is deleted, and the shortest matrix removing device 23 deletes the rows and columns having only one in each row and each column, and transforms the logical structure of the candidate factor extracted from the candidate factor storage device 12. Further, the structure conversion control device 24 controls the entire logical structure conversion device 14.

The processing in the logic multistage device of FIG. 1 is executed in the following steps. Each step is a control device 17
Controlled by and executed in sequence. Step 1: Initialize the contents of each device and store the truth table in the conversion state storage device 11. Step 2: Store the logic state of the circuit in the candidate factor storage device 12. Step 3: The rectangle extraction device 13 executes rectangle extraction for the candidate factors stored in the candidate factor storage device 12, and selects the largest rectangle for this candidate factor. Step 4: The logical structure conversion device 14 executes the conversion of the logical structure for the candidate factors stored in the candidate factor storage device 12 to convert the matrix-shaped storage state in the candidate factor storage device 12. Step 5: The rectangle extraction device 13 executes rectangle extraction for the candidate factors stored in the candidate factor storage device 12, and if the number of 1's contained therein is larger than the rectangle obtained in step 3, , Go to step 7.
If not, go to step 6, and if the length or width of the obtained rectangle is 1 or less, go to step 7. If both rectangles have a vertical or horizontal length of 1 or less, the process ends. Step 6: The structure conversion device 14 again executes the conversion of the logical structure for the candidate factors stored in the candidate factor storage device 12, and the rectangle extraction device 13 executes the rectangle extraction. If the number of 1's contained in the rectangle is larger than the rectangle obtained in step 3, step 7
What. If not, go to step 6, and if the length or width of the obtained rectangle is 1 or less, go to step 7. Step 7: The factor conversion device 15 converts the rectangle into a logical expression that is a factor, the logical expression division device 16 performs division, writes the result in the conversion state storage device 11, and proceeds to step 2.

Further, the structure conversion device 14 of FIG. 2 executes the processing in the following steps for the candidate factors stored in the candidate factor storage device 12 which stores the data in a matrix. Step 1: The longest line deleting device 21 deletes the longest line from the candidate factors stored in the candidate factor storage device 12. Step 2: The longest column deleting device 22 deletes the longest column from the candidate factors stored in the candidate factor storage device 12. Step 3: The shortest matrix removing device 23 removes the rows and columns each having only one element in each row and each column.

Next, an example in which the logic multistage device of the present invention is effective will be shown. Suppose the following logical expression is given in the truth table.

[Equation 1] When this is expressed in a matrix so as to be stored in the candidate factor storage device 12, it becomes as shown in FIG. If a rectangle is extracted from this matrix-like candidate factor using a rectangle extracting device, a rectangle as shown in FIG. 6 cannot be obtained. However, when the structure conversion device of claim 1 is used, the structure is changed by the longest row deletion device, the longest column deletion device, and the shortest matrix deletion device of claim 2, and a rectangle as shown in FIG. 6 is obtained.

[0014]

As described above in detail with reference to the embodiments, according to the present invention, when a logical expression is given, the logical expression can be executed with a small calculation time and a small storage capacity. A device for converting into a circuit can be provided.

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of a logic multistage device of the present invention.

FIG. 2 is a block diagram showing an embodiment of the logical structure conversion device of the present invention.

FIG. 3 is a two-stage logic circuit (a) generated from a truth table;
A circuit (b) having a multi-stage by the logic multi-stage device of the present invention
It is a figure which shows an example of a relationship with.

FIG. 4 is a diagram showing an example of a matrix-shaped storage state represented by a candidate factor storage device.

FIG. 5 is a diagram showing an example of factors selected by a candidate factor storage device and a rectangle selection device.

FIG. 6 is a matrix diagram showing an example of solving a problem that cannot be solved by the conventional device.

Claims (2)

[Claims] 1. A conversion state storage device for storing a conversion process from a truth table to a multi-stage logical expression, a logical expression division device for dividing a factor from the logical expression by using an algebraic method, and a candidate factor in a matrix form. Storing a candidate factor storage device, a rectangle extracting device for selecting a rectangular submatrix having the maximum weight from the candidate factors stored in the candidate factor storage device, and converting the logical structure of the stored contents of the candidate factor storage device. A logic circuit multistage device comprising a logic structure conversion device and a factor conversion device for converting a rectangle in a matrix of candidate factors stored in the candidate factor storage device into a factor. 2. The logical structure conversion device receives a candidate factor from the candidate factor storage device, removes a longest row from a matrix in the candidate factor, a device removes a longest column from the matrix, and the matrix. 2. The logic circuit multi-leveling device according to claim 1, comprising a shortest matrix removing device for removing only one row and column.