Undergraduate Teaching

Engineering Tripos Part IIB, 4F5: Advanced Information Theory and Coding, 2020-21

Engineering Tripos Part IIB, 4F5: Advanced Information Theory and Coding, 2020-21

Not logged in. More information may be available... Login via Raven / direct.

PDF versionPDF version

Module Leader

Dr J Sayir

Lecturer

Dr J Sayir

Lecturer

Dr Albert Guillén i Fàbregas

Timing and Structure

Lent term. 16 lectures. Assessment: 100% exam

Prerequisites

3F7 assumed, 3F1, 3F4 useful but not necessary

Aims

The aims of the course are to:

  • Learn about applications of information theory to hypothesis testing as well as refinements of source and channel coding theorems through error exponents.
  • Introduce students to the principles of algebraic coding and Reed Solomon coding in particular
  • Give students an overview of cryptology with example of techniques that share the same mathematical background as algebraic coding.

Objectives

As specific objectives, by the end of the course students should be able to:

  • have gained an appreciation for the connection between information-theoretic concepts and fundamental problems in statistics
  • have a good understanding of the derivations of error exponents for data compression and transmission
  • have a good understanding of the fundamental connections between hypothesis testing and information theory
  • have gained a practical understanding of the algebraic fundamentals that underlie channel coding and cryptology
  • understand the properties of linear block codes over finite fields
  • be able to implement encoders and decoders for Reed Solomon codes
  • have gained an overview of methods and aims in cryptology (including cryptography, crypt- analysis, secrecy, authenticity)
  • be familiar with one example each of a block cipher and a stream cipher
  • be able to implement public key cryptosystems, in particular the Diffie-Hellman and Rivest- Shamir-Adleman (RSA) systems

Content

  1. This course will introduce students to applications of information theory and coding theory in statistics, information storage, and cryptography.

    The first part of the course will discuss applications of information theory to universal data compression, statistics, and inference.

    The second part of the course will expand linear coding principles acquired in 3F7 to non-binary codes over finite fields. After establishing the algebraic fundamentals, we will cover Reed-Solomon coding, a technique used in a wide range of communication and storage systems (hard disks, blu ray discs, QR codes, USB mass storage device class, DNA storage, and others.)

    The final part of the course will introduce the discipline of cryptology, which includes cryptography, the essential art of ensuring secrecy and authenticity, and cryptanalysis, the dark art of breaking that secrecy. The course will cover a number of methods to provide secrecy, ranging from mathematically provable secrecy to public key methods through which computationally secure communication links can be established over public channels.

 

Information theory and statistics (7-9L, Dr Albert Guillén i Fàbregas)

  • Binary hypothesis testing, probability of error, error exponents, Stein's lemma
  • M-ary hypothesis testing, probability of error
  • Source coding, optimum fixed-rate coding, error exponents
  • Method of types and duality
  • Channel coding, connection with hypothesis testing, perfect codes, error exponents

Introduction to practical number theory and algebra (2-3L, Dr Jossy Sayir)

  • Elementary number theory
  • Groups and fields, extension fields
  • 3 equivalent approaches to multiplication in extension fields
  • Matrix operations and the Discrete Fourier Transform

 

Algebraic Coding (3L, Dr Jossy Sayir)

  • Linear coding and the Singleton Bound
  • Distance profiles and MacWilliams Identities
  • Blahut’s theorem
  • Reed Solomon (RS) codes
  • Encoding and decoding of RS codes

 

Introduction to Cryptology (2L, Dr Jossy Sayir )

  • Overview of cryptology
  • Stream ciphers, examples
  • Block ciphers, examples
  • Public key cryptography, basic techniques

 

Further notes

 

 

 

Examples papers

Examples papers consist of a recommended list of problems to solve in the lecture notes.

Coursework

none

Booklists

 

  • Information Theory:
    • Elements of Information Theory, T. M. Cover & J. A. Thomas, Wiley-Interscience, 2nd Ed, 2006.
    • Information Theory: Coding Theorems for Discrete Memoryless Systems, I. Csiszàr & J. Körner, Cambridge University Press, 2nd Ed. 2011.
  • Coding theory:
    • The Theory of Error-Correcting Codes, F. J. MacWilliams & N. J. A. Sloane, North Holland.
    • Algebraic Codes for Data Transmission, Richard E. Blahut, Cambridge University Press, 2003 (Online 2012)

 

Please refer to the Booklist for Part IIB Courses for references to this module, this can be found on the associated Moodle course.

Examination Guidelines

Please refer to Form & conduct of the examinations.

UK-SPEC

The UK Standard for Professional Engineering Competence (UK-SPEC) describes the requirements that have to be met in order to become a Chartered Engineer, and gives examples of ways of doing this.

UK-SPEC is published by the Engineering Council on behalf of the UK engineering profession. The standard has been developed, and is regularly updated, by panels representing professional engineering institutions, employers and engineering educators. Of particular relevance here is the 'Accreditation of Higher Education Programmes' (AHEP) document which sets out the standard for degree accreditation.

The Output Standards Matrices indicate where each of the Output Criteria as specified in the AHEP 3rd edition document is addressed within the Engineering and Manufacturing Engineering Triposes.

Last modified: 01/09/2020 10:37