\documentclass[11pt]{article} \setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in} \setlength{\topmargin}{0.0in} \setlength{\headheight}{0in} \setlength{\headsep}{0.5in} \setlength{\textwidth}{6.5in} \setlength{\textheight}{8.5in} \setlength{\parindent}{0in} \setlength{\parskip}{0.1in} \usepackage{times} \usepackage{psfig} \usepackage{fancyheadings} \begin{document} \newcommand{\hsp}{\hspace{0.035in}} \pagestyle{fancy} \cfoot{Digital Logic: \thepage} \title{Introduction to Digital Logic} \author{Norman Matloff \\ University of California at Davis \\ \copyright{} 1999, 2003, N.S. Matloff} \date{October 8, 2003} \maketitle \tableofcontents \newpage \section{Overview} As you know, all information inside a computer is processed and stored as 0-1 bits. Here we will look at the basic building blocks used to manipulate this 0-1 information. \section{Combinational Logic} The term {\bf combinational logic} refers to circuitry that \underline{transforms} bits, as opposed to \underline{storing} bits. For example, the ALU portion of a CPU transforms data, e.g. transforming two input word-sized bit strings into an output which is the sum of the two inputs. \subsection{A Few Basic Gates} \subsubsection{AND Gates} A basic AND gate has two inputs and one output.\footnote{Versions with {\bf fan-in} of more than two, i.e. having more than two inputs, exist too.} Let's call the two inputs X and Y, and the output Z. Then Z = 1 if and only if X = 1 \underline{and} Y = 1, hence the name ``AND.'' The AND operation is represented in {\bf boolean equation} settings by multiplication, i.e. we write \begin{equation} Z = X \hsp Y \end{equation} As you can see, this equation does succinctly summarize the AND operation: For example, if X and Y are both 1, then since $1 \times 1 = 1$, then Z will be 1 too. If on the other hand, for instance, X = 1 but Y = 0, Z will be 0. The standard symbol for an AND gate is \vspace{0.2in} \par \psfig{file=and.eps} % \includegraphics{and.pdf} \par Note that for any X (0 or 1), \begin{equation} 0 \hsp X = 0 \end{equation} and \begin{equation} 1 \hsp X = X \end{equation} \subsubsection{OR Gates} Again, a basic OR gate will have two inputs, but in this case Z = 1 if and only if X = 1 \underline{or} Y = 1 (which includes the case in which both X and Y are 1). The boolean equation is \begin{equation} Z = X + Y \end{equation} where the `+' is standard addition except that 1 + 1 is taken to be 1. The standard symbol for an OR gate is \vspace{0.2in} \par \psfig{file=or.eps} % \includegraphics{or.pdf} \par Note that for any X (0 or 1), \begin{equation} 0 + X = X \end{equation} and \begin{equation} 1 + X = 1 \end{equation} \subsubsection{NOT Gates} A NOT gate has one input X and one output Z, with the output being the logical negation of the input. In other words, an input of 1 produces an output of 0, and vice versa. In boolean equations, a NOT operation is indicated by an overbar: \begin{equation} Z = \overline{X} \end{equation} The standard symbol for a NOT gate is: \vspace{0.2in} \par \psfig{file=not.eps} % \includegraphics{not.pdf} \par \subsubsection{NAND Gates} Here there are two inputs X and Y, and one output Z. The term ``NAND'' stands for ``not-and,'' meaning that Z = 1 if the statement ``X = 1 \underline{and} Y = 1'' is \underline{not} true. The boolean equation is \begin{equation} Z = \overline{(X \hsp Y)} \end{equation} The standard symbol for a NAND gate is \vspace{0.2in} \par \psfig{file=nand.eps} % \includegraphics{nand.pdf} \par Note that the little circle here means ``not.'' Obviously, if on the day on which we shopped at the Gates 'R Us store they were out of NAND gates, we could synthesize a NAND by using an AND together with a NOT: \vspace{0.2in} \par \psfig{file=and_not.eps} % \includegraphics{and_not.pdf} \par But of course, this would not be so desirable as using a real NAND. The synthesized version would probably have more transistors than the real one, and thus would be slower and take up more space on a chip, thus reducing the total number of gates we could put on the chip. \subsubsection{NOR Gates} Again, inputs X and Y, output Z, with Z being equal to 1 if the statement ``X = 1 or Y = 1'' is \underline{not} true. The boolean equation is \begin{equation} Z = \overline{(X + Y)} \end{equation} The symbol for a NOR gate is: \vspace{0.2in} \par \psfig{file=nor.eps} % \includegraphics{nor.pdf} \par Again, the same effect could be synthesized by leading the output of an OR into a NOT. \subsubsection{XOR Gates} Here we have inputs X and Y, output Z, with Z being equal to 1 if the statement ``X = 1 or Y = 1 but not both'' is true. The term used for this is ``exclusive-or,'' abbreviated to XOR. The boolean equation is \begin{equation} Z = \overline{X}Y + X\overline{Y} \end{equation} The symbol for an XOR gate is: \vspace{0.2in} \par \psfig{file=xor.eps} % \includegraphics{xor.pdf} \par Again, the same effect could be synthesized by using two NOT gates, two AND gates and an OR gate. \subsection{Some MSI Combinational Components} ``MSI'' stands for ``medium-scale integration.'' We are integrating a moderate number of gates to form some frequently used building blocks. \subsubsection{Multiplexors} A multiplexor, or MUX, selects one of its data inputs and copies that input to the output, with the selection being made according to its address input. As a simple example, consider a MUX having two 1-bit data inputs, D1 and D0. To indicate which one we want to be copied to our output, we need another input, A; A = 1 will mean we want D1, and A = 0 will mean we want D0. Let's call the output Z. Then the equation for Z is \begin{equation} Z = A \hsp D1 + \overline{A} \hsp D0 \end{equation} (Make \underline{SURE} this makes sense to you.) While it won't be drawn here, you should be able to see above that we could construct this MUX by using two AND gates, one NOT, and one OR. A MUX with four data inputs, D3, D2, D1 and D0 would need two selector bits, A1 and A0, and the output would be \begin{equation} Z = A1 \hsp A0 \hsp D3 + A1 \hsp \overline{A0} \hsp D2 + \hsp \overline{A1} \hsp A0 D1 + \overline{A1} \hsp \overline{A0} \hsp D0 \end{equation} (Again, make \underline{SURE} this makes sense to you.) \subsubsection{Decoders} This is best explained by example, say for a 3-to-8 decoder. Let's call the 3-bit input lines X2, X1 and X0, and the output lines Z7, Z6, ..., Z1 and Z0. The 3-bit input can be considered the binary coding for one of the numbers 0-7. The output lines then tell us which one of the numbers 0-7 is represented by the input. For example, suppose X2 = 0, X1 = 1 and X0 = 1, representing the number 3; then Z3 will be 1, to indicate that fact, and all the other Zi will be 0. Building a decoder from gates is quite straightforward from the equations, which themselves are also straightforward. For instance, from the example above you can see that the equation for Z3 is \begin{equation} Z3 = \overline{X2} \hsp X1 \hsp X0 \end{equation} \subsection{Examples} \subsubsection{Half Adder} Here we will design logic to add two 1-bit numbers A and B together. Let's call the sum bit Sum. But note also that there may be a carry generated (this will happen if both addends are equal to 1); we will call this Cout, for ``carry output.'' The logic will look like this: \vspace{0.2in} \par \psfig{file=halfaddr.eps} % \includegraphics{halfaddr.pdf} \par (The dark circles represent wire connections. If two lines cross in the picture but there is no dark circle at their intersection, then they do \underline{not} touch each other. \subsubsection{Full Adder} A full adder has one more input than does a half adder. We will call this input Cin, for ``carry in.'' The reason we need this extra input is that we will be using a full adder as a building block to do multi-bit addition. For example, consider the following addition of two 3-bit numbers, 011 and 001: \begin{verbatim} 11 011 001 --- 100 \end{verbatim} Let's refer to the bit positions as 2, 1 and 0, from left to right. The point then is that the addition at position 0 resulted in a carry into position 1 (shown in the picture), and that carry must be incorporated into the sum performed at position 1. That carry would be the Cin for position 1 (and the Cout for position 0). We will not draw the logic, but here are the equations (remember, we are now back to a single bit, even though the logic will be used below as a building block for a multi-bit adder): \begin{equation} Sum = \overline{A} \hsp \overline{B} \hsp Cin + \overline{A} \hsp B \hsp \overline{Cin} + A \hsp \overline{B} \hsp \overline{Cin} + A \hsp B \hsp Cin \end{equation} \begin{equation} Cout = \overline{A} \hsp B \hsp Cin + A \hsp \overline{B} \hsp Cin + A \hsp B \hsp \overline{Cin} + A \hsp B \hsp Cin \end{equation} Let's use the following (not standard) symbol for a full adder: \vspace{0.2in} \par \psfig{file=fablock.eps} % \includegraphics{fablock.pdf} \par \subsubsection{2-Bit Adder} We can put two full adders together to form a 2-bit adder, i.e. logic which will add together two 2-bit inputs, producing a 2-bit sum and a possible carry: \vspace{0.2in} \par \psfig{file=2bitaddr.eps} % \includegraphics{2bitaddr.pdf} \par Here (A1,A0) forms the first 2-bit addend, and (B1,B0) forms the second. The sum is (S1,S0), and the carry (into bit position 3) is C. Note that a constant 0 is hardwired into the Cin input of the full adder on the right. \subsection{Timing} The delay of a typical gate is on the order of 10 nanoseconds (ns), i.e. 10 billionths of a second.\footnote{It can be faster than this, depending on the {\bf technology} used, meaning the type of electronics used to implement the gate. Since we do not address anything at the electronics level here, we will not pursue this any further.} This sounds extremely fast, almost beyond human imagination, but in view of the fact that computers perform tens of millions of operations per second, gate delays do add up into tangible amounts of time, and thus directly affect the overall speed of the machine. To get the fastest machine, digital logic must be optimized. In other words, even though several sets of gates may be equivalent in effecting a certain function (say addition), their timings may differ considerably, and it is desire to find an optimal set. Many techniques, such as {\bf Karnaugh maps}, exist to do this. Note that in the 2-bit adder example above, the overall delay is approximately double the delay of a single full adder, since the left full adder must wait for the outputs of the right one to be valid; before that time, the outputs of the left one are garbage. There are other adder designs, such as {\bf carry-lookahead adders}, which aim to circumvent this problem. \section{Sequential Logic} Sequential logic \underline{stores} data. Registers in a CPU, RAM and so on store data. \subsection{Latches and Flip-Flops} We first look at the {\bf S-R latch}. It has two inputs, R and S, and two outputs, Q and $\overline{Q}$. Its function is that of a 1-bit memory, with Q being the bit currently stored.\footnote{$\overline{Q}$ is then the negation of the bit being stored. Since this is generated anyway, due to the nature of the logic used in construction we get it ``for free,'' and thus might as well formally make it one of the outputs. That way if $\overline{Q}$ happens to be needed elsewhere in our machine, we would be able to save a NOT gate there.} Whenever we want to store a new bit in the latch, replacing the old one, we simply pulse a 1 on R or S momentarily, depending on whether we want to store a 0 or a 1 in the latch. (R and S stand for ``reset'' and ``set.'') As long as R and S stay at 0, the stored value will remain as is. An S-R latch can be constructed as follows: \vspace{0.2in} \par \psfig{file=srlatch.eps} % \includegraphics{srlatch.pdf} \par Suppose, for instance, that currently Q = 1, and we wish to change Q to 0. That would mean momentarily pulsing the R line to 1. Let's see that this does indeed work: Since Q = 1, $\overline{Q}$ will be 0. Thus the two inputs to the upper NOR gate will be 1 (from R) and 0 (from $\overline{Q}$), making the output 0. In other words, Q does change to 0, as desired. What about $\overline{Q}$? It will stay at 0 for a short time, but as soon as Q changes to 0 and feeds that value back into the lower NOR, the output of that lower NOR will now be 1 (since S = 0). In other words, $\overline{Q}$ does indeed change to 1. But that is not the end of the story, for we must make sure that those new values of Q and $\overline{Q}$ are \underline{maintained}. Well, the feedback nature of the circuit has exactly that result. For example, after $\overline{Q}$ changes to 1, that ensures that the output of the upper NOR gate is 0 (regardless of what R is), so Q will indeed continue to stay at 0. Similarly, you should check that the design ensures that $\overline{Q}$ will stay at 1, until such time as S is pulsed. {\bf Flip-flops} are like latches, except that they are {\bf clocked}, so that they accept new input only at certain times. A clock is a crystal device that pulses at regular intervals, sending 1,0,1,0,1,.... For example, a 1 gigaherz PC has a clock which pulses 1 billion times per second.\footnote{Of course, the faster the clock, the faster the machine. However, in choosing the clock speed, we have to account for all gate delays, signal propagation times along wires, and so on, so that all signals reach their destinations within one clock cycle. In other words, we must choose the clock cycle to accommodate the longest delay in the overall circuit. Actually, if the designer is extremely careful, it may be possible to exceed this limitation, but you can see that one cannot arbitrarily increase clock speed on a given chip.} Flip-flops, by virtue of having clocked input acceptance, allow the designer much more convenient control as to when we allow Q to change, as you will see below. A D flip-flop can be constructed as follows: \vspace{0.2in} \par \psfig{file=dff.eps} % \includegraphics{dff.pdf} \par The D input (``data'') is the new value to be stored at the time of the clock pulse. You should ``walk through'' an instance of the operation of this circuit, again say where the value 1 had been stored originally (Q = 1), but in which we want the new value to be 0 (D = 0). Trace through the sequence of events which will occur when the clock pulse comes; you will find that $\overline{Q}$ is the first to change, becoming 1, with its feedback into the upper-right NAND making Q change to 0, as desired. Keep in mind the role of the clock here. At many times the value at D will be garbage, and we don't want it to affect Q. The only time that it can affect Q is when the clock pulses. That already gives us a bit more control, but even more importantly, we can design our circuit so that the clock pulse itself is not connected to the clock input of a flip-flop, but rather that pulse is AND-ed with some other wires that represent conditions under which the input data D is valid. That way we insure that Q will change only when D is valid. You will see an example of this later in this tutorial, where we build a RAM circuit. \subsection{Edge-Triggering} Many flip-flops are {\bf edge-triggered}. What this means is that they are designed in such a way that an input value (labeled D in the picture above) will have effect on the flip-flop only during a narrow window of time, specifically the time during which the clock pulse is rising or falling.\footnote{These are called the {\bf leading edge} and {\bf trailing edge} or {\bf falling edge} of the clock pulse.} This is done to avoid feedback problems in complex circuits. The output of a flip-flop may be routed through a series of gates and ultimately fed back in to the same flip-flop as an input. For instance, consider the Intel assembly-language instruction\footnote{Using the UNIX syntax, i.e. AT\&T.} \begin{verbatim} addl %ebx, %eax \end{verbatim} (If you have not worked with Intel machines before, this instruction adds the values in the EAX and EBX registers, and stores the sum back into EAX.) Suppose EAX and EBX originally contain the values 5 and 2, respectively. The new value in EAX should be 7. But if the circuitry were poorly designed, the addition might continue, with the 7 being added to 2, thus putting 9 into EAX, and so on. By limiting the sensitivity of flip-flops\footnote{Again, remember that registers are made up of flip-flops.} to very narrow windows of time, this feedback problem cannot occur. \subsection{Example: A 2-Bit Ripple Counter} Recall that an n-bit string can represent (unsigned) integers in the range 0, 1, 2, ..., $2^n - 1$. An n-bit {\bf ripple counter} is simply a counter, which will continually cycle through these values. For example, a 2-bit ripple counter will cycle through 0, 1, 2, 3, 0, 1, 2, 3, 0,..., or in bit form, 00, 01, 10, 11, 00, 01, 10, 11, 00, ... We can construct such a counter from two D flip-flops, two half adders, and a clock: \vspace{0.2in} \par \psfig{file=2bitrctr.eps} % \includegraphics{2bitrctr.pdf} \par (In the DFF boxes, the two left inputs are D and Clk, while the two right outputs are Q and $\overline{Q}$.) Note the following: \begin{itemize} \item the constant 1 is hard-wired as one of the inputs to the right-hand half adder \item we are ignoring the $\overline{Q}$ outputs of the flip-flops \item the outputs are R1 and R0; e.g. when the count is 2, we will have R1 = 1 and R0 = 0, since 10 is the binary representation of 2 \item the input labeled Clk does not actually have to be connected to a clock, and in most applications will not be; instead, the input will simply be a line which we have arranged (elsewhere in the circuit) to pulse to a 1 every time some particular event of interest occurs \end{itemize} \subsection{Example: Tracking Counts Mod and Div 5} The circuit to be designed here will have an input line like a ripple counter does, but instead of tracking the raw count c of the number of times the input line is pulsed, we will track c mod 5 and c div 5. Here is the circuit: \vspace{0.2in} \par \psfig{file=moddiv5.eps} % \includegraphics{moddiv5.pdf} \par The input line is visible at the left of the picture. Its quiescent state is 0, but sometimes pulses, i.e. 1s, come in on that line. (The pulses might come at regular intervals, such as from a clock, or at irregular times, depending on what application we needed this circuit for, i.e. depending on what we are counting.) The output pins are M0, M1 and M2, which contain c mod 5, and D0, D1, D2 and D3, which contain c div 5 (though only up to 15 for the latter). There are two boxes labeled CTR; these are 4-bit ripple counters. The pins labeled C in them are for clearing, i.e. resetting; if this pin is pulsed, all bits of the ripple counter will be reset to 0. Similarly, there is an ``init'' input at the top of the picture, to clear both the mod and div counters. The box labeled DCD is a 3-to-8 decoder. Its output pins are {\bf active low}, meaning that 0 means ``yes'' and 1 means ``no.'' For example, let's label these pins Z7,Z6,...,Z0 from left to right. Then Z7 will be equal to 0 if and only if the three input pins contain 111, the binary representation of 7. Whenever the mod counter reaches 4, Z4 will be 0, which means that the output of the NOT gate we've connected to Z4 will be 1. This 1 is then ANDed with the circuit's input line. So, the next time the input line is pulsed---which will be a count which is a multiple of 5---a pulse will be felt at the c div 5 counter. That counter will then increment, exactly what we want. Note that the gate delay in DCD is helping us here. When the count is 4, the next pulse will change the count momentarily to 5 (and the rest of the circuit will change that to 0). However, even when the count first becomes 5, Z4 will still be equal to 0 (indicating a count of 4, not 5) for a short period of time equal to the gate delay in DCD. This delay is good, because when the pulse comes at count 4, we want Z4 to stay at 0 long enough so that it makes CTR increment. This illustrates the delicate timing issues which can arise in digital circuits. \section{Bus-Based Circuits} A {\bf bus} is a set of parallel wires used for transfer of data among various components. You are already familiar with the idea of a {\bf system bus} for a computer, which connects components such as the CPU, memory and I/O devices.\footnote{In this context, the term {\bf bus} often connotes not just the wires themselves, but also standards for the roles played by the wires, electrical characteristics, and so on.} Since several components are attached to the same bus, how do we make sure that only one of them actually is connected to the bus at a time? The answer is that we use {\bf tri-state buffers} which can connect a component to a bus, or electrically isolate the component away from the bus. To illustrate this, consider the design of a very simple CPU which, for simplicity of exposition, will have only two registers, R0 and R1, each only one bit wide, implemented as a DFF: \vspace{0.2in} \par \psfig{file=regfile.eps} % \includegraphics{regfile.pdf} \par In each register, the upper left input is for data, the lower left for the clock, and output is out the right side. Again, keep in mind that the bus shown here is \underline{inside} the CPU, different from the system bus; the purpose of the bus here is for data transfer from one register (the {\bf source}) to another (the {\bf destination}). (There also would be an ALU, etc., but we do not show other items here.) We see data (D) and address (AS, AD) lines here, just as we would for a system bus. However, due to the simple nature of our example, in which our word size is only one bit (!), we only need one data line; if we had say, 32-bit words, we would need 32 data lines, D31,D30,...,D0. Similarly, since we have only two registers, we only need one address line for the source register, and one for the destination register; if we had say, 16 registers, we would need four address lines each for source and destination. I have chosen the name ``AS'' for ``address of source,'' and ``AD'' for ``address of destination,'' thinking of R0 and R1 having addresses 0 and 1, respectively. What is new here, though, is the presence of triangles which look like NOT gates but are instead tri-state buffers; the latter are distinguished from the former by the presence of an extra input line coming in at the \underline{side} of the triangle, i.e. entering at a sloped leg of the triangle: \vspace{0.2in} \par \psfig{file=tristate.eps} % \includegraphics{tristate.pdf} \par The operation is very simple: If C = 1, then the input A is copied to B. If C = 0, then B is entirely unaffected by A. Suppose we wish to copy the contents of R1 to R0. Then we will put 1 on the AS line and 0 on the AD line. What will happen when the clock pulse comes? Look at the tri-state buffer just below and to the right of R1. Its input (``A'') is R1's Q value, i.e. the valued stored in register R1. Since AS = 1, the tri-state buffer will allow its input to flow through, i.e. R1 will be copied to the D line. Meanwhile, R0 will \underline{not} be copied to the D line, because the input to R0's tri-state buffer is 0. (The little circle to the left of that buffer represents an inverter, i.e. a NOT gate. Since AS = 1, the inverter converts the signal inputted to R0's tri-state buffer to a 0.) Of course, that is what we want; we would have chaos if both R0 and R1 were copied to D at the same time. You should now verify on your own that because we put 0 on the AD line, when the clock pulses, the value on the D line (which was from R1, as we saw above) will flow into R0. So we will indeed have copied R1 to R0, as desired. You might be wondering what will control which values go onto AS and AD. Well, recall that a CPU executes machine language instructions. Each instruction is implemented by a portion of the CPU's {\bf control unit}, a combinational circuit which has as its input the op code from the current instruction, and which has AS and AD (among other things) as its output. Let us add an ALU to the two-register, one-bus system depicted above: \vspace{0.2in} \par \psfig{file=busalu.eps} % \includegraphics{busalu.pdf} \par We do not have room to show the connecting lines, gates and tri-state buffers; suffice it to say that they are similar to those shown earlier. (You should try drawing some for yourself, though, as a check of your understanding.) For simplicity, we are continuing to assume a one-bit word size. The ALU has two inputs on its left, and one output on its right. Again, remember that the ALU is a combinational circuit, for example performing addition, using properly-chosen gates as we have seen before. Note that we have added two new registers, R2 and R3. They are known as {\bf private registers}, ``private'' in the sense that they will not be visible to the programmer, i.e. this CPU's assembly/machine language instructions are not capable of specifying using these registers. Instead, R2 and R3 will serve as temporary storage cells which save data destined for the ALU. As you can see, I've designed their Q outputs to feed into the ALU, rather than being connected back to the D bus line as with R0 and R1. Now consider a machine instruction ADD R0,R1 for this hypothetical CPU, meaning that the old value of R0+R1 will now become the new value of R0. This instruction would require three clock cycles: \begin{quote} first clock: copy of R0 clocked into R2 second clock: copy of R1 clocked into R3 third clock: tri-state buffer connecting the output of the ALU to D enabled, D clocked into R0 \end{quote} There are also inputs, again not shown, to the ALU determining which operation we want to perform, e.g. add, subtract, logical-and, logical-or, etc. Thus in the third clock cycle the control logic would also be putting the code for ``add'' on the control inputs to the ALU.\footnote{Though I have not set it up this way here, in most designs even a ``move'' operation is done through the ALU; in the case here, then, during the first and second clock cycles the control logic would put the code for ``move'' onto the ALU's control input lines.} During the third cycle we would also enable the connection from the output of the ALU to the bus. Note that this also means that there needs to be circuitry which counts clock pulses. How could we make this faster? Suppose we had two buses (duplicating both data and address lines), rather than one, with all components (the registers and the ALU) connected to both buses. Then we could load both R2 and R3 at the same time, i.e. during the same clock cycle: R0 would be copied to R2 via the first bus, while at the same time, R1 would be copied to R2 via the second bus. During the second cycle we would enable the output from the ALU to a bus, say the first one, and enable the input to (in this example) R0. The instruction ADD R0,R1 would then take only two clock cycles, rather than three---a 33\% speedup! And by adding a third bus, we could get the time down to only one cycle.\footnote{And eliminate the need to have R2 and R3.} Now all of this is somewhat oversimplified (we have not accounted for time needed to fetch the instruction from memory and decode it, etc.), but you can at least begin to see the principle here---a classic computer science time/space tradeoff. If we are willing to use greater amounts of precious \underline{space} on the CPU chip (more buses take up more room), we can reap a savings in \underline{time}. With this example, the need for edge-triggering or some other anti-feedback mechanism\footnote{Such as {\bf master-slave} flip-flops.} should be more apparent. It would be worthwhile for you now to go back and review that section earlier in this document. \section{Example: Memory Chips and Systems} To illustrate the principles developed here, we will consider the design of simple memory chips and memory systems. \subsection{An SRAM Memory Chip} First consider the design of a ``4x2'' memory chip, meaning that it contains four two-bit words. (This is much, much smaller than the sizes of typical commercial memory chips, but the principles are the same.) We will call the four words Word 0, Word 1, Word 2 and Word 3. (Remember, though, that these are word numbers within this chip, not within a system constructed from this chip and others; more on this later.) The chip will have the following pins: address pins A1 and A0 (two pins encode $2 ^ 2 = 4$ addresses), which indicate which of the four words is to be accessed; data-in pins DI1 and DI0 (for writing data to the chip); data-out pins DO1 and DO0 (for reading data from the chip); a write-enable pin WE, used to inform the chip that we wish to write to it; an output-enable pin OE, used to inform the chip that we wish to read from it; and a chip-select pin CS, to inform the chip that it, rather than some other memory chip, will be involved in the current memory transaction. Again, the ``4x2'' designation for this chip means that the chip contains four words, each two bits wide. Note that this might be a quite different viewpoint than that held by the CPU of our system. The CPU might, say, view an ``8x4'' \underline{system} would consist of eight four-bit words. The memory for such a system could then be constructed by using in combination four 4x2 chips, as we will do later. (The CPU, though, would be unaware of the chip structure of the system.) The use of separate pins for data input and output here is not standard, but simplifies the design somewhat. If we were to have a single set of pins for both functions (as we will assume later), the design below could be modified in a straightforward way. To design this chip, let us first design a one-bit cell which will serve as the basic building block for the chip: \vspace{0.2in} \par \psfig{file=bit.eps} % \includegraphics{bit.pdf} \par Here there is a D flip-flop, which will hold the stored bit, together with three inputs, IN, WL and WR, and one output, OUT. When we write data to this bit, the data will come in on the IN line, and the WR line will be 1. When we read data from the bit, it will come out the OUT line, and WR will be 0. Recall that the flip-flop is clocked, and responds to pulses (their leading or trailing edges), rather than to levels of a signal. In our case here, it is likely that the WR line will send such pulses, because it will be the result of AND-ing with a clock. Suppose for example that our system bus (which connects the CPU to memory) contains a W line and a CLOCK line. We could AND those two lines together, and feed the result into WR. Then if the CPU asserts the W line, when the clock pulse occurs, that pulse will appear on WR as well, and have leading and trailing edges. WL (``word line'') has the following function. As you will see below, our full memory chip will consist of a 4x2 array of the one-bit cells we are now examining. Each row of that array consists of one word within the memory chip, i.e. one address within the chip. The WL line for the two bits of a given word will go to 1 when we wish to access that word. If WL is 0, then you can see from the diagram above that no data will be allowed into or out of the bit cell; note the role of the tri-state device for the latter case. By the way, note that if WR is 1, i.e. we are doing a write to this bit cell, data actually {\it is} allowed out of the cell, which seems wrong. However, this will be remedied by other tri-state devices in the chip as a whole. Now here is our design for that chip: \vspace{0.2in} \par \psfig{file=sram.eps} % \includegraphics{sram.pdf} \par As mentioned earlier, the main part of the chip consists of a 4x2 array of the bit cells designed above. The top row is Word 0 of the chip, the row just below it is Word 1, and so on. A 2-to-4 decoder at the middle left of the diagram selects the proper row of bit cells, i.e. the proper word, depending on which address is desired. The design is straightforward. Let us confirm, for instance, that if CS is 0, no data will be allowed into or out of this chip. First, note that if CS is 0, then the inputs to WR in the bit cells will also be 0; thus no data will be allowed into any bit cell, exactly as planned. Second, note that if CS is 0, the inputs to the two tri-state devices near the DO1 and DO0 pins will also be 0, insuring that no data flows out of the chip. Again, all of this is important; we will be connecting several of these chips to a system bus, and must insure that we do not have data from two chips flowing onto the same bus lines at the same time. Consistent with our earlier comment on the 1-bit cell design, the WE input here would likely be set up as the AND-ing together of, say, W and CLOCK lines in the system bus. The same comment applies to our memory system in the following subsystem (even though the CLOCK line is not drawn). \subsection{A Memory System} Now, let us see how a memory system can be constructed from memory chips. Again for simplicity, we will continue to assume 4x2 chips,\footnote{For even more simplicity, we now assume that each data pin does both input and output.} and we will assume an overall system of eight four-bit words.\footnote{Remember, the CPU will see only the latter, and not know how the system breaks down in terms of chips.} Here is how we can construct the system from 4x2 chips: \vspace{0.2in} \par \psfig{file=memsyst.eps} % \includegraphics{memsyst.pdf} \par The bus here is a system bus, not the buses internal to CPUs and memory chips which we have discussed earlier. The CPU and I/O devices are also connected to this bus, but are not shown here, nor is the CLOCK line shown. We are assuming that no direct memory-to-memory access is possible; all reads from and writes to memory are performed by the CPU. Let's call the four chips I, II, III and IV, from left to right. By inspecting which chip pins are connected to bus lines D3-D0, you can see that chips I and III contain the lower two bits of each four-bit word, while chips II and IV contain the higher two bits. By noting the connections of bus line A2 to the CS pins of the chips, you can see that of the entire address space 0-7, {\bf now speaking from the CPU/system viewpoint}, chips I and II contain system words 0-3, and chips III and IV contain system words 4-7. Suppose, for example, we have a C program with an {\bf int} variable {\bf x}, and that the address of {\bf x} happens to be 3 in this system. Then {\bf x} will be stored in chips I (lower 2 bits of {\bf x}) and II (upper 2 bits of {\bf x}). If the C source code has something like \begin{verbatim} x = 5; \end{verbatim} then on, say, an Intel CPU the compiler will produce code like \begin{verbatim} movl $5, x \end{verbatim} In executing this instruction, the CPU will put 011 on lines A2, A1 and A0, and put 0101 on D3-D0, and so on. \subsection{Memory Interleaving} The four-chip system in the above example is said to be {\bf high-order interleaved}, which means that the most significant (``high-order'') bits of the address determine which chips (in this case a chip pair) a given address is stored in. With {\bf low-order interleaving}, the least significant bits are used instead. Note that (think about this and make sure you understand it) in a high-order interleaved system consecutive addresses are stored within the same chip (until we reach a chip boundary) while in the low-order case consecutive addresses are stored in consecutive chips (mod the number of chips). \subsection{DRAMs} The kind of memory chip described above, in which each 1-bit cell is implemented as a flip-flop, are known as {\bf static} RAM (SRAM). By contrast, the bit cells in {\bf dynamic} RAM (DRAM) chips consist of tiny capacitors, rather than flip-flops; a charged capacitor represents a 1, while a discharged one represents a 0. The term {\bf static} refers to the fact that each flip-flop in an SRAM continuously maintains itself (as noted when first discussed flip-flops in this tutorial); it will not change as time passes, until we want it to change. Except for the structure of individual bits, the connections between the bits in a DRAM is very similar to that of an SRAM. One difference, though, arises from the fact that a bit in a DRAM will lose its charge as time passes, so it must be periodically refreshed, i.e. recharged, by additional circuitry. The refresh operation of a DRAM also brings some reduction in system performance, as a bit (or row of bits) is not accessible during the time it is being refreshed. On the other hand, the simplicity of DRAM bit cells means that we can fit more bit cells on a chip, thus saving cost. \section{Example: A Simple CPU} As another illustration of how these principles can be used, we will examine the design of a simple CPU: \vspace{0.2in} \par \psfig{file=cpu.eps} % \includegraphics{cpu.pdf} \par We will assume 8 registers. (Only one of them is shown here, but the others all have the same connections as the one shown.) All data accessed by the program will be in the registers, unlike most CPUs, in which data can be either in registers or in memory. The program itself is in memory. Neither the memory nor the clock are considered part of the CPU. Let's review some terms first: A CPU has a special register, typically called a Program Counter (PC), which specifies the address in memory of the next instruction to be executed. At the beginning of a fetch-execute cycle, the CPU will fetch the instruction from memory which is pointed to by the PC, depositing the instruction in the Instruction Register (IR). There the instruction will be decoded, meaning that the digital logic in the CPU will execute the instruction according to the {\bf op code} and {\bf operands} specified in the instruction. In our case here, the latter are specified in terms of which two registers will be used as sources for the instruction, and which one is to be the destination. Thus each of these register fields will be 3 bits wide. The execution of the instructions is performed mainly by the Arithmetic and Logic Unit (ALU). While execution is being performed, the PC is also being incremented by 1 (except in the case of a branch), to prepare the PC for the next instruction when this one is done. Referring to the two ALU inputs and its outputs as src1, src2 and dst, respectively, let us set up these op codes: \begin{verbatim} 0000 dst = src1 0001 dst = src1 + src2 0010 dst = src1 - src2 0011 dst = src1 AND src2 0100 dst = src1 OR src2 0101 dst = NOT src1 0110 if N go to branch target 0111 if Z go to branch target 1000 go to branch target \end{verbatim} This design features three buses. (Keep in mind that these are {\it internal CPU buses}, not a system bus which connects a CPU to memory and I/O devices. Also, note that we have a direct connection here between the CPU and memory, instead of using a bus.) The top two buses lead to the ALU as inputs, while the third bus carries output from the ALU. Note the box labeled ``N,Z'' in the figure. This calls for some more review. Recall that CPUs have a register dedicated to {\bf condition codes} (some RISC CPUs allow any register to be used for this), which record certain facts about the output of the last ALU operation: The N (``negative'') bit states whether the ALU output was negative, while the Z (``zero'') bit records whether that output was 0. In both cases, 1 means yes and 0 means no; for instance, Z = 1 means ``Yes, the output was 0.'' The condition codes are used for conditional branches. On Intel-CPU machines, for instance, consider the code \begin{verbatim} subl %ebx, %eax jnz t \end{verbatim} The first instruction subtracts the EBX register from the EAX register. This will be done by the CPU, and the N and Z bits will record the result, which in turn will be used by the second instruction, JNZ: It says, ``If the Z bit is not set, then jump to T.'' Now, let's look at the design.\footnote{The diagram does not indicate which lines are inputs and which are outputs. Here is a guide: Observe that in IR, each of the register fields is input to a decoder (3-to-8), the outputs of which control which register is copied to the first bus, which one is copied to the second bus, and which register will be loaded with the ALU output on the third bus. The ``op'' section of IR is input to the ALU, to control what operation the latter does. Ins: Left, right of R; left and bottom of ALU; left of N,Z; left bottom of IR; right of memory; top and right of MUX; left of add 1; bottom of DCDRs. Outs: Right of ALU; right of N,Z; bottom of R; top of DCDRs; top, and bottom right of IR; left of MUX; top of memory; left of PC; right of add 1.} The MUX must provide the PC either with the incremented previous PC value, or the branch target (T in our example above), depending on (a) the op code (i.e. what kind of branch we are doing, if any) and (b) the values of N and Z. Though not shown here, the ``op'' and N,Z lines feed into some gates just above the MUX, which decide which control selector signal to feed into the MUX. Study this diagram carefully, and think about how to implement the details. \end{document}