[MUSIC] In order to efficiently implement combinational circuits, synthesis tools are essential. Today we will describe some of the principles that can be used to optimize circuits. Two practical questions are dealing with: redundant terms and Boolean function reduction. The concept of redundant term comes from the fact that some combinations of input signal values never occur or, if they occur, the value of the outputs doesn't matter, the so-called don't care values. Thus the corresponding minterms can be used or not to optimize the final circuit. Let us see an example: a BCD to 7-segment decoder. The circuit has four inputs that encode a decimal digit 0, 1, 2, and so on, up to 9, and it has seven outputs that control the segments, the seven segments of a one-digit display. We won't use the decimal point. The working of the circuit is defined by this table. Observe that the values of the function A, B, C, D, and so on, are defined for all inputs that encode decimal digits, but are not defined for other values of the inputs, so we could say that the values of the inputs for those input values do not matter. First, we could check that this circuit is well defined. For example, assume that the inputs encode digit 2. Then segments A, B, G, E, and D should be switched on and segments F and C must be switched off, so that what appears in the display is digit 2, and you can check that actually here A, B, D, E, G are equal to 1, and C and F are equal to 0. What can we do with the don't care values? The first option is to replace all don't care values by 0's, that is to say to define function A equal to 0 for all combination values that correspond to decimal number 10 to 15, and the same for all other functions, and so on. In this way, we get this new set of Boolean expressions. Now, let us define, for example, functions B and C in a different way. First, observe that for all input value combinations corresponding to digits 0 to 9 function B and C are compatible with the initial table. With this definition of the 'don't care' values this new expression is obtained, a much simpler boolean expression than this expression obtained by replacing all "don't care's" by zeroes. We can check that this is a correct expression: B is equal to 1 when x2 is equal to 0 (here, here, here, and here) and also for those input values; also when both x1 and x0 are equal to 0; so wecan add this 1 and this 1; and also when both x1 and x0 are equal to 1; So we get this 1 and this 1. So, we have checked that this is a correct expression for representing this function B and also that this function B is compatible with the initial definition. We can do the same in the case of function C. Once again, you can check that for all input values corresponding to digits 0 to 9 the new function C is compatible with the initial table. You can also check that this is correct expression to represent function C and that it is simpler than this other expression obtained by replacing all "don't care's" by 0's. Here is a summary of the complete optimization of this BCD to 7-segment decoder. If we give the value 0 to all "don't care's", we get this set of Boolean expressions and the corresponding circuit would have 35 logic gates. On the other hand, looking for an optimum choice of the "don't care's", we would obtain the following expressions and the corresponding circuit would include 26 gates. Now, some information about the synthesis tools, that is to say, software tools that generate optimized circuits. Starting from either logic expressions or from tables. Two basic concepts will be used: cubes and adjacency. First, what is a cube? The set of n-component binary vectors B·2**n can be considered as a cube of dimension n, actually as an hypercube. For example with n equal to 3, the set of eight binary vectors is this one and can be represented under the form of a cube. Then, a subset of of B·2**n defined by giving a constant value to some, for example, to m vector components, is a cube of dimension n-m. In this cube, if the first coordinate is equal to 0, then we get the following subcube of dimension 2, actually a square. Assume now that N is equal to four and consider the function F equal to a product of literals. This product is equal to 1 if x2 is equal to 1 and X0 is equal to 0, so that the set of points where F is equal to 1 is a cube, this one, of dimension 2. Thus we see that a cube is a set of points of B·2**n where a product of literals is equal to 1. Next point: how can we represent cubes, specially within our computer system? For that, we define an order of the variables, for example, n-1, n-2, down to 0. Then once an order has been defined, a cube can be represented by a sequence of n characters belonging to the set {0, 1, x}. Let us see an example with n = 4. The sequence 1x01 represents the set of binary vectors with four components such that x3 is equal to 1, x1 is equal to 0, and x0 is equal to 1. It corresponds to the product of literals x3·not(x1)·x0. Another example: the sequence x1x0 represents a cube with x2 equal to 1 and x0 equal to 0, and corresponds to this product of literals: x2·not(x0). So, the rule is very simple: "1" in the representation of a cube corresponds to a variable present in the normal form; "0" corresponds to an inverted variable, and "x" corresponds to a missing variable. The basic concept to optimize boolean expression is adjacency. Consider two cubes with n = 4, such as 1x11 and 1x01. Assume that the corresponding products (this one and this one) belong to the representation of some function f. I mean that f can be expressed as x3·x1·x0 + x3·not(x1)·x0 + other terms. As those products differ in only one variable, (x1 in the first one, not(x1) in the other one) the representation of F can be simplified, and we can replace the sum of those two terms by this term (x3·x0). In terms of cubes we have replaced the union of cubes 0x11 and 0x01 by cube 0xx1 and we say that 0x11 and 0x01 are adjacent cubes that can be merged. An example: consider a function f defined by a set of cubes of dimension 0 that means without "x". In fact, it's a set of minterms. Then, taking into account the adjacencies, we can merge some of these cubes. For example, this one 0010 and 0011 can e merged so that we get this new cube 001X because here we have 0 and here we have 1. In the same way 0110, this one, and 0111 can be merged and we get this cube; 0101 and this one can be merged and we get this cube. Those two cubes can also be merged and we get 0x1x, here, so that finally, this set of cubes is equivalent to this one 0x1x, here, 01x1, and this one, and to this set of cubes corresponds the following Boolean expression. Now, we are going to see an example of automatic simplification tool included within the VerilUOC desktop software. Within the menu "project" we select "analyze circuit". There are two ways to define functions, either by their truth tables or by means of Boolean xpressions. Let us first use the truth table method. As an example, we are going to use functions B and C of the 7-segment decoder. First we must define the input and output variables. The input variables are x3, x2, x1 and x0, and the output variables are B and C. Then, we use the table option. The truth table with our four inputs x3, x2, x1, x0 and the two outputs B and C has been generated. It remains to define the output values. For that we must click, or double-click, on the corresponding output values. For example, B is equal to 1, 1, 1, 1, and 1; then two 0's and three 1's. The other values that correspond to numbers 10 to 15 are don't care values. As regards C the values of the function are 1, 1, 0 and 1's. So we have defined the two functions B and C by their truth table. After that, we use the command "minimize" and we get the following result: the minimized expression of B is the expression we had obtained before, and the same in the case of the minimized expression of C. By the way, the colored diagram is a so-called Karnaugh map. It's a graphical method to minimize Boolean functions, but, that only can be used for up to 4-variable functions. With the command "build circuit" we can generate the corresponding circuit. We must choose the circuit name, for example, "my circuit", and then we get a circuit that implements B and C with logic gates and inverters. If we want, the circuit can be edited. For example, this program does not minimize the number of inverters. You can see that not(x1) is generated twice. So we could remove one of the inverters. We will add this connection and then we can remove this inverter, and those connections, and we get a circuit equivalent to the preceding one, but with one inverter less. This was the first method. Let us see the second method. For that we will use a 5-variable function f equal to not(a) + not(b) and not(c) + a and b and c + not(a) and d and e. Once again within the menu "project" we select "Analyze Circuit". Then we define the inputs, in this case a, b, c, d, and e, and the output f. Now we select the option "expression"; we must write the Boolean expression of f. For that, the complement is represented by an exclamation point. So we write not(a) + not(b) and not(c) (observe that the Boolean product is represented by an ampersand) + a and b and c + not(a) and d and e. The next command is "enter". You can observe that we have here the correct expression with the normal symbols of the complement and of the Boolean product. After that we can minimize this expression, and we get this new expression: not(a) + not(b)·not(c) + b·c. Actually, in the original initial expression, not(a) + not(a)·d·e is equal to not a by absorption and not(a) + a·b·c is equal to b·c so that this is a correct expression. You must confirm the new expression with the command "set as expression" and then, with the "build circuit" command, we can generate the corresponding circuit. We must give a name to the circuit, for example (because when we are original) "my circuit 2", and in this way we get a circuit made of logic gates. Summary: in this lesson we have introduced the concept of redundant terms and have deduced the corresponding optimization problem. We have defined the concept of cube and the relation between cubes and literal products, and finally tools to minimize Boolean expressions and to optimize circuits have been presented.
