Exercises in digital logic

Logical gates

The following three gates are the building blocks of digital logic.

The NOT gate is basically a transistor while the NAND and NOR gates consists of two transistors wired in clever ways.

Note that two NOT gates wired together negates each other.

Boolean algebra

We will adopt the convention that high voltage will be interpreted as 1 and low voltage (ground) will be interpreted as 0. We can now make an algebra, i.e. a way of computing with only these two values. It is called Boolean algebra in honour of George Boole, a British mathematician from the 19th century who invented such an algebra in his investigations on logic.

Truth tables

One way to define a Boolean function (i.e. a function that can only take on two values) is to specify a table listing the function value for every possible input. Such tables are commonly called truth tables because they are linked to logic. We simply define 0 as false and 1 as true and then many Boolean functions correspond to notions in logic. For instance if A denotes some proposition (for instance the sentence: '2+2=5') and B denotes another proposition ('It is raining now'), then A NAND B is false if and only if both A and B are true.

A	NOT
0	1
1	0

A truth table for Not.

A	B	NAND
0	0	1
0	1	1
1	0	1
1	1	0

A truth table for NAND. Note that as there are two inputs the table has 2^2=4 rows.

A	B	NOR
0	0	1
0	1	0
1	0	0
1	1	0

Truth table for NOR.

One could define (in a backward manner...) the AND function as the function computed by hooking a NAND gate up to a NOT gate. See below. In a similar fashion one could define OR.


One way of making an AND gate.	The symbols for AND and OR gates.

Problem 1

Make truth tables for AND and OR.

Basic functions

NAND gates can be used as building blocks for any logical function. As an example one could make the OR gate in the following manner. In Boolean algebra the AND function is often viewed as a form of multiplication whereas the OR function is a form of addition. Hence one can write expressions such as 'A+BC', which denotes 'A OR (B AND C)'. In fact using this notation all the usual laws of algebra applies (i.e. multiplication is distributive with respect to addition, both operations are associative, etc). This is the reason why it is called a Boolean algebra.

Making an OR gate out of NAND gates.

Only using NAND gates in building logical circuits have certain advantages, e.g. production costs are kept lower since the apparatus can be optimised for NAND gates, even though the total number of transistors used might be higher than if other gates were used.

Problem 2

Construct a circuit which computes AND by only using NAND gates.

Exclusive or

In the lecture you were presented with the exclusive or function defined by the following truth table:

A	B	XOR
0	0	0
0	1	1
1	0	1
1	1	0

Problem 3

Construct a circuit which computes the XOR of two input signals A and B. You may use any number and type of the gates you have seen so far, i.e. NOT, NAND, NOR, AND, OR.

Systems architecture

The figure displays a standard PC architecture.

´Legend

DRAM (dynamic random access memory) is the main memory of the PC. Programs and data being processed are kept here.
L2 Cache (level 2) is a small amount of SRAM (static RAM) and it much faster than DRAM. Level 1 cache is a part of the CPU and thus operates at the same speed. L2 Cache operates at half the speed of the CPU.
AGP (accelerated graphics port) is a special bus for high performance graphic cards. It is 64 bits wide, and operates at 66 MHz, but data can be transferred two times per clock cycle (at the rise and fall). It can interface directly to the main memory.
PCI (Peripheral Component Interconnect) is the interface for expansion cards (most graphic cards, TV tuner, etc.)
IDE is the interface to hard disks, floppy drives.

Memory

All data, be it programs or other kind of data, has to be kept in main memory in order for the CPU to process it. These days the CPU in a PC operates at 500 MHz or more. Due to various clever techniques (pipelining, superscalar architecture) the CPU is almost able to execute one instruction per clock cycle (it takes time to decode an instruction and actually execute it). That is, the CPU can roughly execute 500 million instructions per second. Fast DRAM operates at 100 MHz, i.e. it takes 10 nanoseconds to read from a memory address.

Problem 1

Instructions for the CPU have to be fetched from main memory. Assuming the above is all there is to memory and programs, can you say anything about such a system's performance?

Memory Bus

The memory bus handles all data going to and from main memory. It operates at 100 MHz and it is 64 bits wide. That means it can transfer 64 bits of data 100 million times a second. The Pentium III CPU is a 64-bit processor, which means that its basic data unit is 64 bits (i.e. 8 bytes).

Cache

Since programs have to be read from main memory, the CPU is kept idle waiting for data to arrive. Studies have shown that programs tend to have relatively small parts, which are active most of the time. To utilise this most CPUs have a small amount of very fast memory called a cache (the Pentium III processor from Intel has 32 Kb of L1 cache and 512 Kb L2 cache). Here resides the most recently loaded data from main memory. Each time the CPU wants to fetch something from main memory, it first checks to see if it already resides in the cache.

Updated 2003-10-27