Introduce key questions in the theory of signal transmission and quantitative analysis of signals, such as the notions of entropy and mutual information. Show the underlying algebraic structure. Apply the fundamental concepts to code theory, data compression and cryptography.
Curriculum
scheda docente
materiale didattico
Reliable transmission of information. Shannon's information content. Measures of information. Entropy, mutual information, informational divergence. Data compression. Error correction. Data processing theorems. Fundamental inequalities. Information diagrams. Informational divergence and maximum likelihood.
2. Source coding and data compression
Typical sequences. Typicality in probability. Asymptotic equipartitioning property. Block codes and variable length codes. Coding rate. Source coding theorem. Lossless data compression. Huffman code. Universal codes. Ziv-Lempel compression.
3. Channel coding
Channel capacity. Discrete memoryless channels. Information transmitted over a channel. Decoding criteria. Noisy channel coding theorem.
4. Further codes and applications
Hamming space. Linear codes. Generating matrix and check matrix. Cyclic codes. Hash codes.
R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
V. Guruswamy, A. Rudra, M. Sudan. Essential Coding Theory. Online draft, 2019.
R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
D.J.C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2004.
Programma
1. Introduction to information theory.Reliable transmission of information. Shannon's information content. Measures of information. Entropy, mutual information, informational divergence. Data compression. Error correction. Data processing theorems. Fundamental inequalities. Information diagrams. Informational divergence and maximum likelihood.
2. Source coding and data compression
Typical sequences. Typicality in probability. Asymptotic equipartitioning property. Block codes and variable length codes. Coding rate. Source coding theorem. Lossless data compression. Huffman code. Universal codes. Ziv-Lempel compression.
3. Channel coding
Channel capacity. Discrete memoryless channels. Information transmitted over a channel. Decoding criteria. Noisy channel coding theorem.
4. Further codes and applications
Hamming space. Linear codes. Generating matrix and check matrix. Cyclic codes. Hash codes.
Testi Adottati
T.M. Cover, J.A. Thomas. Elements of Information Theory. Wiley, 1991.R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
Bibliografia Di Riferimento
T.M. Cover, J.A. Thomas. Elements of Information Theory. Wiley, 1991.V. Guruswamy, A. Rudra, M. Sudan. Essential Coding Theory. Online draft, 2019.
R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
D.J.C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2004.
Modalità Erogazione
Frontal lectures with recitations.Modalità Frequenza
Class participation is advised but not compulsory.Modalità Valutazione
Oral exam.
scheda docente
materiale didattico
Reliable transmission of information. Shannon's information content. Measures of information. Entropy, mutual information, informational divergence. Data compression. Error correction. Data processing theorems. Fundamental inequalities. Information diagrams. Informational divergence and maximum likelihood.
2. Source coding and data compression
Typical sequences. Typicality in probability. Asymptotic equipartitioning property. Block codes and variable length codes. Coding rate. Source coding theorem. Lossless data compression. Huffman code. Universal codes. Ziv-Lempel compression.
3. Channel coding
Channel capacity. Discrete memoryless channels. Information transmitted over a channel. Decoding criteria. Noisy channel coding theorem.
4. Further codes and applications
Hamming space. Linear codes. Generating matrix and check matrix. Cyclic codes. Hash codes.
R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
V. Guruswamy, A. Rudra, M. Sudan. Essential Coding Theory. Online draft, 2019.
R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
D.J.C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2004.
Programma
1. Introduction to information theory.Reliable transmission of information. Shannon's information content. Measures of information. Entropy, mutual information, informational divergence. Data compression. Error correction. Data processing theorems. Fundamental inequalities. Information diagrams. Informational divergence and maximum likelihood.
2. Source coding and data compression
Typical sequences. Typicality in probability. Asymptotic equipartitioning property. Block codes and variable length codes. Coding rate. Source coding theorem. Lossless data compression. Huffman code. Universal codes. Ziv-Lempel compression.
3. Channel coding
Channel capacity. Discrete memoryless channels. Information transmitted over a channel. Decoding criteria. Noisy channel coding theorem.
4. Further codes and applications
Hamming space. Linear codes. Generating matrix and check matrix. Cyclic codes. Hash codes.
Testi Adottati
T.M. Cover, J.A. Thomas. Elements of Information Theory. Wiley, 1991.R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
Bibliografia Di Riferimento
T.M. Cover, J.A. Thomas. Elements of Information Theory. Wiley, 1991.V. Guruswamy, A. Rudra, M. Sudan. Essential Coding Theory. Online draft, 2019.
R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
D.J.C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2004.
Modalità Erogazione
Frontal lectures with recitations.Modalità Frequenza
Class participation is advised but not compulsory.Modalità Valutazione
Oral exam.
scheda docente
materiale didattico
Reliable transmission of information. Shannon's information content. Measures of information. Entropy, mutual information, informational divergence. Data compression. Error correction. Data processing theorems. Fundamental inequalities. Information diagrams. Informational divergence and maximum likelihood.
2. Source coding and data compression
Typical sequences. Typicality in probability. Asymptotic equipartitioning property. Block codes and variable length codes. Coding rate. Source coding theorem. Lossless data compression. Huffman code. Universal codes. Ziv-Lempel compression.
3. Channel coding
Channel capacity. Discrete memoryless channels. Information transmitted over a channel. Decoding criteria. Noisy channel coding theorem.
4. Further codes and applications
Hamming space. Linear codes. Generating matrix and check matrix. Cyclic codes. Hash codes.
R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
V. Guruswamy, A. Rudra, M. Sudan. Essential Coding Theory. Online draft, 2019.
R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
D.J.C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2004.
Programma
1. Introduction to information theory.Reliable transmission of information. Shannon's information content. Measures of information. Entropy, mutual information, informational divergence. Data compression. Error correction. Data processing theorems. Fundamental inequalities. Information diagrams. Informational divergence and maximum likelihood.
2. Source coding and data compression
Typical sequences. Typicality in probability. Asymptotic equipartitioning property. Block codes and variable length codes. Coding rate. Source coding theorem. Lossless data compression. Huffman code. Universal codes. Ziv-Lempel compression.
3. Channel coding
Channel capacity. Discrete memoryless channels. Information transmitted over a channel. Decoding criteria. Noisy channel coding theorem.
4. Further codes and applications
Hamming space. Linear codes. Generating matrix and check matrix. Cyclic codes. Hash codes.
Testi Adottati
T.M. Cover, J.A. Thomas. Elements of Information Theory. Wiley, 1991.R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
Bibliografia Di Riferimento
T.M. Cover, J.A. Thomas. Elements of Information Theory. Wiley, 1991.V. Guruswamy, A. Rudra, M. Sudan. Essential Coding Theory. Online draft, 2019.
R.E. Blahut. Algebraic Codes for Data Transmission. Cambridge University Press, 2003.
D.J.C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2004.
Modalità Erogazione
Frontal lectures with recitations.Modalità Frequenza
Class participation is advised but not compulsory.Modalità Valutazione
Oral exam.