Skip to main content

Digital Systems:  2017-2018

Lecturer

Degrees

Preliminary ExaminationsComputer Science

Terms

Overview

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.

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, 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.

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. 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).

Feedback

Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.