[MUSIC] We concluded the preceding lesson with a statement of the main objective of this course, that is the synthesis of digital circuits. Given the circuit specification and given a set of available components, how can we implement the circuit? In this lesson, we will give a partial answer this question in the case of the so-called combinational circuits, and first let us define the concept of switching functions. A switching function is a binary function of binary variables. In other words, an n-variable switching function associates a binary value (could be 0 or 1) to any n-component binary vector. Then we call combinational circuit at the digital circuits like this one, that implement a set of switching functions: m functions of n variables, but in such a way that at any time, the output signals only depend on the input signals at the same time. "At the same time" is the important point in this case, and perhaps it's interesting to give an example of a system that is not combinational. This is an example of a previous lesson. We had defined the working of a boiler controller by means of a table, this table, that gives the value of an output ONOFF in function of the temperature measured by the sensor. Actually, this is not a combinational system. Why? If you only know that the temperature is equal to 20 degrees, you cannot decide, with this table, whether the output signal is equal to ON or to OFF. You say that the system doesn't change its state. So that the value of ONOFF is not a function of the value of the input "temp" at the same time. The system must have some kind of internal memory. Now, let us see a first example of combinational circuit. Consider a circuit that computes the sum of two 4-bit numbers, x and y, plus an incoming carry bit. Thus, x and y are natural numbers belonging to the set 0, 1, 2, and so on up to 15, and the maximum value of z, on the output of the adder, is 15 + 15 + 1 that is to say 31, and 31 in binary is 11111, so that the result of the addition is a 5-bit number. Furthermore, z4 will be considered as an outgoing carry. The result, the complete result consists of this carry out (or z4) and four bits z3, z2, z1 and z0. The function of the circuit could be defined by this very simple algorithm: we compute the sum of X, Y and the incoming carry. If the result is greater than 1111, in binary, that is 15 in decimal, then we compute the difference between s and 16, and this will be the value of bits 3 down to 0 of the output z, and the carry out, the outgoing carry, must be equal to 1. Else, if s is not greater than 15, then bits 3 downto 0 of z are equal to s, and the outgoing carry is equal to 0. A first way to implement this adder is to compute in advance all the results for all combinations of value of x, y and carryIN, and to store all those results within a read only memory. Then, the input values, x, y, and carryIN are used as address bits of of the memory, and the memory outputs are the outputs of the circuit. Here is the table that defines this combinational circuit. This type of table is often called a truth table. For every value of x, let us say this one, 1111, every value of y, let us say this one, 1101, and every value of the carryIN, for example 1, we compute the result of the sum, in this case 15 + 13 + 1 equal to 29, and you can check that this vector represents 29, so that the output carry will be equal to 1, and the output z (3 downto 0) will be equal to 1101. Then, all those values are stored within a read only memory addressed by 9 address bits that are the circuit inputs. Observe that this is a very large table and a rather large read only memory. It has 2 to the 9 rows (512 rows) and it has 5 bits per word or per row of the table, in total, 2,560 bits. Thus, this is a very simple synthesis method. Any combinational circuit with n inputs and m outputs can be implemented by a read-only memory that stores 2 to the n words with m bits per word, so that, in total, the number of bits to be stored is m times 2 to the n. But this general method is also generally inefficient in terms of cost, for example, in terms of silicon area within an integrated circuit. The former example was a good one because we needed a ROM storing more than 2,000 bits, to implement a rather simple function. Now we propose you a little quiz. Let us see now another method based on the structural hierarchical description. A 4-bit adder can be decomposed into four 1-bit adders, in this way, and each of those 1-bit adders implements the operation we carry out at each step when adding with pencil and paper. Let us see an example. Assume that we compute 1101, in decimal 13, plus 0111, in decimal 7, and perhaps with an input carry, an incoming carry equal to 1. Then we compute. 1 + 1 + 1 = 3; 3 in binary is 11; then 1 + 0 + 1 is 2; in binary, 10; 1 + 1 + 1 is 3; in binary, 11, and finally 1 + 1 = 2; in binary, 10. So, the result is this one that represents in decimal 16 + 4 + 1 that is obviously 21. Then it remains to synthesize a 1-bit adders, and this 1-bit adder can be defined by a table that defines the outputs corresponding to all input combinations: outputs c0 and z in function of the value of x,y and ci. We could store those values, those ones, in a read-only memory. But we could also use logic gates. But first, remember the working of some of the main logic gates: an AND gate is a circuit that generates an output equal to 1 if all its inputs are equal to 1. In the case of a 2-input AND gate, the output z will be equal to 1 if x and y are equal to 1. In the other case, the output is equal to 0. This is a general definition. A 3-input AND gate generates 1 if its three inputs are equal to 1, and so on. Now, an OR gate: an OR gate generates an output 1 when one of its inputs, at least one, is equal to 1. So, in this case, it generates a 1; in this case, in this one, and in this one. In this case, the output is equal to 0. Once again it is a general definition. A 3-input OR gate generates 1 if at least one of its three inputs is equal to 1. Finally, we already know that an inverter inverts its inputs, that is, if x is equal to 0 z will be equal 1 and, conversely, if x is equal to 1 z will be equal to 0. Consider again the table. This table could be defined by the following statement, a kind of logic algorithm. We are going to synthesize function c0. Then we could say that c0 is equal to 1 if and only if x y ci is equal to 0 1 1, or if x y ci is equal to 1 0 1, or if x y ci is equal to 1 1 0, or if x y ci is equal to 1 1 1. Furthermore, observe that a condition like this one (x y ci equal to 0 1 1) is equivalent to x is equal to 0, and y is equal to 1, is and ci equal to 1. Finally, observe also that a condition like x is equal to 0 is equivalent to inverse of x is equal to 1. Then, a logic circuit made up (this one) of AND gates, OR gates, and inverters, can easily be deduced from this logic algorithm. Every AND gate corresponds to one of the four conditions. For example, this first condition can be implemented by this AND gate and this inverter. Actually, when will be equal to 1, this output on the first AND gate? It will be equal to 1 if its three inputs are equal to 1, that means if the inverse of x is equal to 1, if y is equal to 1, and if ci is equal to 1. It's exactly the first condition. In the same way, the second condition corresponds to this AND gate output. The third, to the third AND gate and the fourth to the fourth AND gate. Finally the four conditions are gathered by means of a 4-input OR gate, so that finally c0 is equal to 1 if one of the four conditions holds true. An important comment: the two last conditions here could be replaced by this condition, a simpler one. Actually, we say that the first condition, here, says that x and y must equal to 1 1 and ci equal to 0, and the other one says that x and y must be equal to 1 1, and ci equal to 1, so that we could replace this condition by this one, that is to say, x y equal to 1 1, independently of the value of ci. Then the corresponding circuit, with this new definition of the function c0, the circuit if the following with the same condition x y ci equal to 0 1 1, x y ci equal to 1 0 1, and, in this case, x and y equal t0 1 1. The corresponds circuit has less gates than before: there are only three AND gates instead of four; one of the AND gates, this one, has two inputs instead of three, and the output OR gate has only three inputs. A conclusion is that in order to detect this type of optimization, we need some tool, a tool that helps us to minimize the number of gates, and this tool is Boolean Algebra, and Boolean Algebra will be the topic of another lesson. We now propose as an exercise the synthesis, with logic gates, of function z of the 1-bit adder. Here is a solution. We can define as before a kind of logic algorithm, and look for the value of the input to which correspond 1's of the function: z is equal to 1 when x y ci are equal to 0 0 1, when they are equal to 0 1 0, when they are equal to 1 0 0, and also when the three inputs are equal to 1. The corresponding circuit is this one. The first AND gate detects this condition: x equal to 0, y to 0, and ci to 1. The second AND-gate, detects this second condition: x y ci equal to 0 - observe that this input comes from this inverter - y equal to 1 and ci equal to 0, and so on. with this method, without any kind of optimization, the input AND gates will have as many inputs as the number of inputs of the circuit. In this case, the circuit has three inputs and all the AND gates have three inputs. Which is the number of AND gates? The number of AND gates is equal to the number of 1's of the function, in this case four 1's, and which is the number of OR gate inputs? The same as the number of AND gates that is to say, the same as the number of 1's of the function. As regards the inverters, the number of inverters is equal to the number of inputs of the circuit, because you must invert at most once every circuit input. What have we seen today? We have defined the concept of combinational circuit and have seen two kinds of implementation. A first one using a read only memory, generally an inefficient method, and a second one using logic gates.
