Skip to main content

Digital Systems:  2020-2021

Lecturer

Degrees

Preliminary ExaminationsComputer Science

Terms

Overview

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

**This detailed course structure is for informatuon only and may change in 2020/21**

  • 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]

Syllabus

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. Role of assemblers, compilers and linkers. Memory hierarchy. Simple operating system services: file systems, processes. Principles of networked services.

Reading list

  • Lecturer's notes and exercises.
  • S.A. Ward and R.H. Halstead, Computation Structures, MIT Press, 1990.
  • T. H. Cormen, E. E. Leiserson and R. L. Rivest, Introduction to Algorithms,The MIT Press, 1990.
  • J. L. Hennessy and D. A. Patterson, Computer Organisation and Design: the hardware/software interface, Morgan-Kaufmann