2023
Data Compression and Coding
Name: Data Compression and Coding
Code: INF13263M
6 ECTS
Duration: 15 weeks/156 hours
Scientific Area:
Informatics
Teaching languages: Portuguese
Languages of tutoring support: Portuguese
Regime de Frequência: E-learning
Sustainable Development Goals
Learning Goals
To acquire a global view of the lossless data compression problems and coding in noisy channels.
To understand the foundations of the Shannon information theory and the theoretical limits to data compression and channel capacity.
To know several common lossless data compression algorithms and channel coding algorithms.
To understand how information theory can be applied in other scientific areas.
To understand the foundations of the Shannon information theory and the theoretical limits to data compression and channel capacity.
To know several common lossless data compression algorithms and channel coding algorithms.
To understand how information theory can be applied in other scientific areas.
Contents
Introduction to the Shannon information theory.
Source-channel-Receiver.
Models for an information source: discrete memoryless source and sources with memory.
Markov chains. Stationary distributions.
Definition of entropy, conditional entropy and mutual information. Properties.
Source coding theorem.
Entropy encoding algorithms:
Shannon, Shannon-Fano and Huffman codes.
Shannon-Fano-Elias code and arithmetic coding.
Universal encoding algorithms:
Adaptive Huffman coding.
Lempel-Ziv codes: LZ77, LZ78, LZW.
Definition of channel capacity for discrete memoryless channels. Blahut and Arimoto algorithm.
Channel coding theorem.
Channel coding algorithms. Error detection and correction.
Parity check.
Repetition and Hamming codes.
Turbo codes and low density parity check codes (LDPC).
Introduction to lossy compression and rate-distortion theory.
Source-channel-Receiver.
Models for an information source: discrete memoryless source and sources with memory.
Markov chains. Stationary distributions.
Definition of entropy, conditional entropy and mutual information. Properties.
Source coding theorem.
Entropy encoding algorithms:
Shannon, Shannon-Fano and Huffman codes.
Shannon-Fano-Elias code and arithmetic coding.
Universal encoding algorithms:
Adaptive Huffman coding.
Lempel-Ziv codes: LZ77, LZ78, LZW.
Definition of channel capacity for discrete memoryless channels. Blahut and Arimoto algorithm.
Channel coding theorem.
Channel coding algorithms. Error detection and correction.
Parity check.
Repetition and Hamming codes.
Turbo codes and low density parity check codes (LDPC).
Introduction to lossy compression and rate-distortion theory.
Teaching Methods
The classes are divided into theoretical classes, where the theory and algorithms are presented, and practical classes, where the students solve problems both at the theoretical level and at the application level. The problems are solved in paper or computer.
The assessment is based on practical projects to be done at home, and written tests to be done during the semester or, alternatively, by a final exam.
Besides the lectures, the course is organized and supported in an electronic learning platform so that it is compatible with learning in tutorial or e-Learning methods.
The assessment is based on practical projects to be done at home, and written tests to be done during the semester or, alternatively, by a final exam.
Besides the lectures, the course is organized and supported in an electronic learning platform so that it is compatible with learning in tutorial or e-Learning methods.
Teaching Staff
- Miguel José Simões Barão [responsible]
