Digital Logic Level

Gates

• digital circuits have two values, high and low (normally 1 and 0 respectively)
• gates are small devices that can perform functions on this type of signal
• gates form the basis on which all digital computers are built
• the five basic gates used in computers are: NOT (inverters), AND, OR, NAND, NOR
• fig. 3-2 provides the symbols of the basic gates and their functional behavior
• note that NAND is just the AND functions output put through an inverter, similarly with NOR
• NAND and NOR gates require fewer transistors (thus smaller and simpler) than AND and OR, and therefore they are used instead

Boolean Algebra

• Boolean algebra is an algebra used to describe circuits built by combining gates
• Boolean functions may have n different variables (inputs). There are exactly 2ⁿ possible combinations
• by listing the possible input combinations in the rows of a table with 2ⁿ rows and the resulting output for each row, the function can be completely described. This is called a truth table (see fig. 3.2 and 3.3)
• inputs should be listed in numerical (base 2 order)
• an alternative to describing a circuit using a truth table is to use a Boolean algebraic function
• for every set of input values that produce an output of 1, combine all the inputs into an AND gate using the compliment (shown by placing a bar overhead the variable) on inputs that have the value 0
• combine all the AND gate outputs into a single OR gate – you now have an algebraic function to describe the circuit
• AND gates are represented by using the (× ) multiplication notation or implied when variables have no space between them
• OR gates are represented by using the (+) plus notation

• for example, the above table describes a 3 input circuit. The inputs are labeled A, B, C
• The first row produces an output of 1. We can rewrite this as

• The second row produces an output of 1 and can be written as

• The sixth row would be written as

- this technique is called SUM OF PRODUCTS (SOP)

• using the algebraic form, a possible implementation can be drawn. As an example, see how fig. 3-3(b) is derived from its expression. (DRAW THE ABOVE)
• to implement any Boolean circuit the following steps can be followed:

1. Write down the truth table for the function
2. Provide inverters to generate the complement of each input
3. Draw an AND gate for each term with a 1 in the resulting column
4. Wire the AND gates to the appropriate inputs
5. Feed the output of all the AND gates into an OR gate

• it is usually simpler and cheaper to represent circuits using just a single gate therefore NAND or NOR gates are usual used
• one approach is to perform the above 5 steps, then convert each gate with a two input gate equivalent then convert the AND, OR, and NOT gates with their equivalent (see fig. 3-4)
• for example, A+B+C+D = (A+B)+(C+D)

Circuit Equivalence

• the last step is to reduce the number of gates a circuit has, this can be accomplished using Boolean algebra
• the basic identities (see fig. 3-6) can help in reducing a circuit.
• for example the distributive law is applied to a circuit in fig. 3-5 (TRY TO REDUCE THE ABOVE EXAMPLE)
• note that De Morgan’s law is an important identity when converting SOP expressions to NAND or NOR equivalences (USE NAND GATES FOR THE EXAMPLE)
• fig. 3-7 demonstrates how De Morgan’s law is helpful in converting SOP circuit to NAND or NOR
• as an example, fig. 3-8 converts an XOR circuit from SOP to NAND gate equivalents. First step is to take the complements of the first two AND gates and complement the inputs to the OR gate (which create a net result of no change). Using fig. 3-7(a), it’s clear that the last gate is equivalent to another NAND gate which gives fig. 3-8(d)
• note that normally it is assumed that a 0 is represented by 0 volts in a circuit while a 1 is represented by 3.3 volts. This is known as positive logic
• negative logic is when 3.3 volts represents a 0 and 0 volts represents a 1 (see fig. 3-9 for an example of the OR function truth table in both forms)

Basic Digital Logic Circuits

• today’s circuits are usually built with modules which contain many gates
• Integrated Circuits (ICs or chips) are a group of gates on a piece of silicon.
• the outside packaging is made of plastic/ceramic with a number of pins (note: the packaging is MUCH larger than the actual silicon piece holding the gates)
• pins connect to an input or output from a gate (or to power/ground). See fig. 3-10
• packages with two rows of pins are called Dual Inline Packages (DIPs)
• chips are divided into classes:

SSI (Small Scale Integrated) circuit: 1 to 10 gates

MSI (Medium Scale Integrated) circuit: 10 to 100 gates

LSI (Large Scale Integrated) circuit: 100 to 100,000 gates

VLSI (Very Large Scale Integrated) circuit: >100,000 gates

• one further note: although we normally think of gates providing instantaneous response (as soon as a signal is placed on the input there is the corresponding signal at the output) there really is a finite gate delay which ranges from 1-10nsec

• circuits that are uniquely determined by the values at the inputs are known as combinational circuits
• memory circuits are NOT examples of such a circuit as they rely on what the previous state was in addition to the input values

Multiplexers

• a multiplexer is a circuit with 2ⁿ data inputs, one data output and n control lines (see fig. 3-11)
• a multiplexer works by selecting (gating) one of the data input lines, allowing that data value to pass to the output
• selection is done by setting the control lines with the binary number of the data input line
• for example, in fig. 3-11, if the control lines A, B, C are set to 110, seven of the AND gates (gates 0 to 5 and gate 7) will output 0 and gate 6 will have the value 0 or 1 depending on the data value on input line 6
• it is easy to configure any circuit with a multiplexer. Set each data input line on the multiplexer to a 0 (ground) or a 1 (Vc) based on the output found in the truth table of the desired circuit
• for example, using the example in the notes, there are 3 control lines needed, which gives 8 data input lines. The input lines would be fixed to 1,1,0,0,0,1,0,1 (based on the outputs reading from top to bottom).
• multiplexers can be used for parallel-to-serial data conversion (HOW?)
• inverse of the multiplexer is a demultiplexer which takes a single input signal and outputs it on one of 2ⁿ lines depending again on the value of the n control lines

Decoders

• a decoder is a circuit that takes an n-bit number as input and uses that to select one of 2ⁿ output lines (see fig. 3-13)
• decoders are often used in chip selection on memory units. For example, if your memory module was made up of 8 chips, using fig. 3-13 where the outputs are connected to one of the 8 chip selection inputs (if the chip select = 1 then that chip is selected), the high 3 bits of an incoming address could be used to select which memory chip to use

Comparators

• a comparator compares two input words for equality
• comparators can be built using XOR gates, when two inputs are equal the output is 0, if they are different the output is 1 (see fig. 3-14)

• arithmetic circuits are more specialized circuits than those of the previous section and include shifters, adders, and the ALU

Shifters

• a shifter takes an input word from a parallel set of inputs and outputs the result shifted by 1 bit place
• fig. 3-16 shows an 8 bit shifter that has 8 input lines (D₀ – D₇) and eight output lines (S₀ – S₇)
• to see how it works, imagine the input word = 10110110 and that C=1. Notice that the right AND gates will have a 1 from input C while the left AND gates will have a 0 because they are fed the inverse of C. The result is that the value at the right AND gate will pass through the AND gate and show up in the output but shifted by 1. (TRY IT, WHAT HAPPENS WHEN C=0?)

Adders

• basic circuit for doing integer addition is the adder
• it is easy to develop the adder circuit applying the rules for making any circuit, start with the truth table (see fig. 3-17 (a)), create your SOP circuit, simplify using the Boolean identities (TRY IT)
• fig. 3-17 (b) shows the half adder circuit. The half adder takes two inputs and calculates the sum and the carry
• a full adder uses 3 inputs, A, B and the Carry from the previous adder circuit (see 3-18) {note: full adder actually equals 2 half adders put together}
• by putting together 16 full adder circuits together a 16-bit adder is created
• this type of adder is known as a ripple carry adder because each adder circuit must wait for the previous adder to compute it’s result and pass the carry to the next adder circuit thus a delay is incurred
• by splitting a 16-bit word into two parts, the upper half and lower half and duplicate the upper half circuit we can reduce the delay. One upper half circuit will assume that the carry from the lower half is 0 and perform the calculation on the upper half of the word based on this assumption. Similarly the 2^nd upper half circuit will assume the carry from the lower half is 1. Since the computation is done in parallel, performance is improved by a factor of 2. The result will be taken from the correct upper half.
• by repeating the above, performance continues to be improved and the resulting circuit is known as a carry select adder

Arithmetic Logic Unit (ALU)

• the ALU performs AND, OR, NOT and sum of two words
• in a similar fashion to the adder circuit, the ALU is built up of single bit ALUs (see fig. 3-19)
• A decoder is used to select which of the 4 functions to use on the word inputted (HOW?)
• ENA/ENB are used to force either input (A or B) to 0
• INVA is used to invert A (B is inverted by selecting the inverse function)
• a 1-bit ALU is known as a bit slice allowing designers to build an ALU of any size. Fig. 3-20 shows how an 8-bit ALU can be constructed out of 8 bit slices.
• note that the INC signal is simplify incremented A by 1

Clocks

• clocks provide a means to synchronize circuits
• a clock is a circuit that emits a series of pulses with a precise pulse width and interval between pulses
• clock cycle time is the interval between corresponding edges of two consecutive pulses
• frequencies between 100MHz and 500MHz are common and correspond to clock cycles of (????HOW MANY??)
• to provide finer resolution than a basic clock cycle a circuit using a delay can be used (see fig. 3-21 (a))
• by using both the primary signal and the delay signal 4 distinct time references become available (see fig. 3-21 (b)

1. Rising edge of C1
2. Falling edge of C1
3. Rising edge of C2
4. Falling edge of C2

• by tying different events to each of the references a finer sequencing can be achieved
• by adding more secondary lines with different delays, further refinement can be made
• similarly, if time intervals are more important (i.e. events happen not on the edge of a signal but any time the signal is high or low), the above circuit can provide 4 distinct intervals (WHAT ARE THEY?)
• finally, clock signals are symmetric however by using two offset signals and ANDing them together an asymmetric pulse can be made (see fig. 3-21 (c))