Digital Systems: 20102011
Lecturer  
Degrees  
Term  Hilary Term 2011  Trinity Term 2011 (24 lectures) 
Overview
There are 8 lectures in HT and 16 in TT.This course covers the fundamentals of the electronic circuits that are used to build computers, and outlines the software components that support their use. From the functions of individual transistors, it constructs a complete implementation of a simple processor, explaining in a structured way how complex behaviours are built up from simpler parts. This is followed by an overview of the software components of a complete computer system. Students will gain an understanding of the factors that affect the performance of hardware, and how these factors change with changes of scale, for example in the size of the data that a computer system handles. They will also gain experience in the important technique of hierarchical specification, implementation and proof of correctness using logic and data representation.
Learning outcomes
After studying this course, undergraduates will be able to:
 Design small combinational and sequential circuits from logic gates.
 Understand the design of processors with simple architectures.
 Implement simple programs in assembly language.
 Understand the characteristics and limitations of computer arithmetic.
 Understand the rôles of interpreters, compilers, and assemblers.
 Be familiar with operating system services such as the file system, virtual memory, and simple network services.
 Distinguish between specification and implementation, and appreciate the use of rigorous correctness arguments.
Synopsis
 Overview; propositional logic; disjunctive and conjunctive normal forms. Concept of gate; adequacy of {AND, OR, NOT}; adequacy of NAND; Karnaugh maps. [2]
 Array circuits: multiplexers, demultiplexers, decoders; programmable logic arrays. [1]
 Combinational examples; arithmetic circuits, adders, arithmeticlogic units. Ripplecarry adder; carry lookahead adder. [2]
 Twoscomplement integers; signed and unsigned arithmetic. [1]
 CMOS as an example technology; transistors; inverter; nand; nor; exor; and; or. State, latches and flipflips as primitives. [1]
 Sequential circuits, simple pipelines and simple state machines. Synchronous design discipline; examples; limitations, hazards; alternative implementations of sequential circuits. [2]
 Registers; randomaccess memory; registertransfer design. Straightforward implementation of a subset of MIPS. [2]
 Simple programs; assembler. [1]
 Stack; evaluation of expressions. Simple control structures; subroutines; concept of interrupt/exception. [2]
 Alternative styles of processor architecture. [1]
 Floatingpoint arithmetic. [1]
 Structured data; recursive data; heap storage; serialization. [1]
 Simple input/output; serial representations of data. Persistent storage; disklike devices; tapelike devices. [2]
 Concepts of caching; outline of virtual memory. [1]
 Processes; kernel; kernel services; interprocesses communications. [1]
 File store; UNIXlike file system; other examples for contrast. [1]
 Packetswitched networking; elements of IP networking; routing. Network services such as the Domain Name Service; web services. [2]
There will be two practicals: one on simulating a carrylook ahead adder in Haskell; the other will use a MIPS simulator to run simple code related to exercises on compiling expressions.
Syllabus
Simple design of combinational and sequential circuits; standard design elements. Computer arithmetic for integers and floatingpoint numbers; basic error analysis. Register transfer level design of a simple microprocessor. Simple programming in assembly language. Rôle of assemblers, compilers and linkers. Memory hierarchy. Simple operating system services: file systems, processes. Principples of networked services.Reading list
 Lecturer's notes and exercises.
 S.A. Ward and R.H. Halstead, Computation Structures, MIT Press, 1990.

A.S. Tanenbaum, Structured Computer Organisation, PrenticeHall International, Third Edition, 1990. 
M.M. Mano, Digital Design, PrenticeHall International, 1984.  T. H. Cormen, E. E. Leiserson and R. L. Rivest, Introduction to Algorithms,
first edition only,The MIT Press, 1990.  J. L. Hennessy and D. A. Patterson, Computer Organisation and Design: the hardware/software interface, MorganKaufmann,
2005 (Third edition).