[MUSIC]. This lesson deals with the relation between programming language instructions and digital circuits. This relation justifies the use of hardware description languages, very similar to programming languages, and the availability of digital circuit synthesis tools. Actually, several programming language instructions have a straightforward translation in terms of digital components. Four examples will be given in this lesson. The "if then else" construct, the "case" statement, the loops "for loop", and the procedure calls. Let us start with the "if-then-else" instructions. Here is an example: it is a binary decision algorithm that computes the value of a switching function f of six variables, x0, x1, y0, y1, y2, and y3, and the algorithm is the following: the first condition "if x1 is equal to 0" then there is another internal "if" instruction that say that "if x0 is equal to 0" then f is equal to y0; else f is equal to y1. So we see that if x1 is equal to 0 and if x0 is equal to 0 then function f is equal to y0. If x1 is equal to 0 but x0 equal to the other value (the else part of the instruction) then the function is equal to y1. In the other case, if x1 is equal to 1, if x0 is equal to 0, then f is equal to y2, and in the other case, f is equal to y3. To this algorithm corresponds this circuit. The external if (if then else with end if here), this first if instruction correspond to the output multiplexer of this circuit. According to the value of x1, we choose between two branches within this circuit, and to every if-then-else, internal if-then-else instruction, correspond those multiplexers that, according to the value of x0 in both cases, chooses the value of the function f. So, there is an obvious relation between if "condition" then "some operation" else "other operation", between this type of construct and 2-to-1 multiplexers. A second example is the "case" statement. The same binary decision algorithm can be defined by a "case instruction". A second example is the "case" statement. The same binary decision algorithm can be defined by a "case" instruction: CCase x is when 00, f is equal to y0, when x is equal to 01, f is equal to y1 and so on, and to this instruction correspond a 4-to-1 multiplexer with a 2-bit input x that allows to choose for f one of those values, one of those input variables. "For loops" are associated with iterative structures. Consider the algorithmic definition of a 4-digit decimal adder. An example before: when we add, for example, 9,273 and 4,389 we use a step by step method. We add 3 and 9; this is 12; actually 1 and 2; we generate a carry equal to 1; Then we add 1, 7, and 8, equal to 16. Once again, there is a carry; 1 plus 2 plus 3 equal to 6. We see there is no carry, and finally 9 plus 4 equal to 13 and the obtained result is this. So, we start with an initial carry equal to 0 and then we repeat four times the same sequence of operations. We add one digit of x, one digit of y, and an incoming carry. If the result is greater than 9, we must subtract 10 and generate an outgoing carry, and that's all. The corresponding circuit has an iterative architecture. To the loop body, corresponds this component, and the complete circuit is made up of four components connected in series. The outgoing carry of one step, of one component, is connected to the incoming carry of the next component and this corresponds to the fact that, in the program, you can see that carry number i+1 is updated at step i. Now two comments about loop implementations. The first comment is that other sequential implementations will be seen later on. Another comment is that not any loop can be implemented in this way. An example is the case of while "some condition" loop, and then "some sequence of operations". If the maximum number of times that this condition will hold true is either unknown or is known, but is a very large number, a sequential implementation must be considered. The last example is the call to a function or to a procedure. Once again, let us see an example. Assume that some procedure MAC (multiply and accumulate) has been defined. It is a procedure whose parameters w, x and y are input parameters and z an output parameter, and it executes this operation: it adds to some number w the product of 2 numbers x and y. It allows, for example, to compute this type of expression: z is a sum of 8 products: x1·y1 + x2·y2 and so on, up to x8·y8, and the corresponding algorithm is this one. Initially, the first value of w is 0 and then we call 8 times the MAC procedure with parameters: the value of w, the corresponding values of x and y and the result of the operation; that means that at each step we compute a new value of w equal to the current value plus the product of two numbers, xi and yi. The corresponding circuit is an iterative one (this circuit); to the "for" loop corresponds this iterative structure and to every MAC procedure call corresponds a component that must be defined. This is another example of top-down hierarchical description. We say top-down because we start with a complete system, the top level in this case, and after that, we will have to develop the MAC component. in this example the "down" level of this hierarchical description. Now some comments. We have seen how some classical programming language instructions have a straightforward translation into digital components. First comment: that is the reason why hardware description languages, very similar to programming languages, have been defined. For example VHDL, Verilog, or even C/C++ with some additional time functions, objects and so on, and another comment: this relation between programming language instructions and digital components also explains how it has been possible to generate software packages able to translate programs to circuits. Summary of this lesson: we have seen that binary decision algorithms can be implemented with multiplexers, that case constructs can also be implemented with multiplexers. We have seen that loops correspond to iterative structures, and that procedure calls correspond to hierarchical descriptions. Finally, a conclusion about hardware description languages and synthesis tools. [BLANK_AUDIO]
