Skip to main content

Digital Systems:  2017-2018



Preliminary ExaminationsComputer Science



There are 16 lectures in HT and 8 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:

  1. Design small combinational and sequential circuits from logic gates.
  2. Understand the design of processors with simple architectures.
  3. Implement simple programs in assembly language.
  4. Understand the characteristics and limitations of computer arithmetic.
  5. Understand the rôles of interpreters, compilers, and assemblers.
  6. Be familiar with operating system services such as the file system, virtual memory, and simple network services.
  7. Distinguish between specification and implementation, and appreciate the use of rigorous correctness arguments.


  • 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, arithmetic-logic units. Ripple-carry adder; carry lookahead adder. [2]
  • Twos-complement integers; signed and unsigned arithmetic. [1]
  • CMOS as an example technology; transistors; inverter; nand; nor; exor; and; or. State, latches and flip-flips as primitives. [1]
  • Sequential circuits, simple pipelines and simple state machines. Synchronous design discipline; examples; limitations, hazards; alternative implementations of sequential circuits. [2]
  • Registers; random-access memory; register-transfer 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]
  • Floating-point arithmetic. [1]
  • Structured data; recursive data;  heap storage; serialization. [1]
  • Simple input/output; serial representations of data. Persistent storage; disk-like devices; tape-like devices. [2]
  • Concepts of caching; outline of virtual memory. [1]
  • Processes; kernel; kernel services; interprocesses communications. [1]
  • File store; UNIX-like file system; other examples for contrast. [1]
  • Packet-switched 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 carry-look ahead adder in Haskell; the other will use a MIPS simulator to run simple code related to exercises on compiling expressions.


Simple design of combinational and sequential circuits; standard design elements. Computer arithmetic for integers and floating-point 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, Prentice-Hall International, Third Edition, 1990.
  • M.M. Mano, Digital Design, Prentice-Hall 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, Morgan-Kaufmann, 2005 (Third edition).