This course focuses on source coding (lossless data compression) and channel coding (error correction coding), which are the
basic technologies for handling digital information.
Digital video, music / voice and characters have a certain kind of redundancy, and they can be compressed without deteriorating the quality of information,
It is known that how far it can be compressed, and that its limit is determined depending on "the amount of information" of individual data. Shannon theory gives its theoretical framework.
Error correction codes are also effective for correctly receiving information via erroneous communication channel in which occurrence of bit errors can not be avoided.
We will do problem exercises in each class.
Digital video, music / voice and characters have a certain kind of redundancy, and they can be compressed without deteriorating the quality of information,
It is known that how far it can be compressed, and that its limit is determined depending on "the amount of information" of individual data. Shannon theory gives its theoretical framework.
Error correction codes are also effective for correctly receiving information via erroneous communication channel in which occurrence of bit errors can not be avoided.
We will do problem exercises in each class.
In the first half of the course, we learn the principle of error correction, and the basic coding schemes such as parity code,
Hamming code, and cyclic redundancy code. Furthermore, we learn the concept of linear code and operations of encoding and
decoding with matrices.
In the second half of the course, we learn the principle of lossless data compression and representative source coding methods such as Huffman code. Furthermore, we learn self-information, average information and entropy, being the way to quantify the amount of information and a degree of uncertainty using occurrence probability.
In the second half of the course, we learn the principle of lossless data compression and representative source coding methods such as Huffman code. Furthermore, we learn self-information, average information and entropy, being the way to quantify the amount of information and a degree of uncertainty using occurrence probability.
- Being able to understand the principle of error correction coding, and being able to perform encoding and decoding operations of parity code, Hamming code and cyclic redundancy code.
- Being able to understand general trade-off between error correction capability and it transmission efficiency in error correction coding.
- Being able to understand the concept of linear code, and being able to perform encoding and decoding operations using matrices.
- Being able to understand the principle of cyclic redundancy code.
- Being able to understand the principle of lossless data compression, and the concept of average information and entropy. Being able to perform source coding using Huffman code.
| Class schedule | HW assignments (Including preparation and review of the class.) | Amount of Time Required | |
|---|---|---|---|
| 1. | Overview - Coding in digital system: Source coding and channel coding. - The principle of error correction - Modelling of erroneous channel * BSC(Binary Symmetric Channel) |
Reviewing a course of probability and statistics in high school curriculum. | 270minutes |
| 2. | Party check code - Single bit error detection with odd/Even parity check code - Single bit error correction with horizontal and vertical parity check code |
Reviewing the delivered handout entitled "Parity check code". | 270minutes |
| 3. | Metrics to evaluate error correction/detection capability and efficiency - Hamming distance - Minimum Hamming distance -Code rate |
Reviewing the delivered handout entitled "Metrics to evaluate error correction/detection capability and efficiency". | 270minutes |
| 4. | Linear code (Part I) - Encoding with a generator matrix - Decoding with a parity check matrix |
Reviewing the delivered handout entitled "Linear code (Part I)". | 270minutes |
| 5. | Linear code (Part II) - Hamming code - Encoding and decoding with Hamming code |
Reviewing the delivered handout entitled "Linear code (Part II) | 270minutes |
| 6. | Decoding error - Calculating probability of decoding error that occurs in BSC model |
Reviewing the delivered handout entitled "Decoding error" | 270minutes |
| 7. | Mid-term examination and lecture |
Reviewing the contents of classes from the first class to the 6th class. | 270minutes |
| 8. | Cyclic redundancy code (Part I) - Representation of codes by polynomials - Arithmetic operations of polynomials |
Reviewing the delivered handout entitled "Cyclic redundancy code (Part I)" | 270minutes |
| 9. | Cyclic redundancy code (Part II) - Generator polynomial - Encoding and decoding - Circuits for decoding using shift registros |
Reviewing the delivered handout entitled "Cyclic redundancy code (Part II)" | 270minutes |
| 10. | Source coding (Part I) - Principle of losssless data compression - Modelling of information source |
Reviewing the delivered handout entitled "Source coding (Part I)" | 270minutes |
| 11. | Source coding (Part II) - Kraft's inequality - Theoretical limit of lossless data comparession - Shannon- Fano coding - Huffman coding |
Reviewing the delivered handout entitled "Source coding (Part II)" | 270minutes |
| 12. | Source coding (Part III) - Block coding Quantifying information (Part I) - Self information |
Reviewing the delivered handout entitled "Source coding (Part III)" | 270minutes |
| 13. | Quantifying information (Part I) - Average information - Entropy - Source coding theorem |
Reviewing the delivered handout entitled "Quantifying information (Part II)" | 270minutes |
| 14. | End-term examination and lecture | Reviewing the contents of classes from the 8th class to the 13th class. | 270minutes |
| Total. | - | - | 3780minutes |
| Mid-term examination | End-term examination | Total. | |
|---|---|---|---|
| 1. | 15% | 25% | 40% |
| 2. | 15% | 30% | 45% |
| 3. | 15% | 15% | |
| Total. | 45% | 55% | - |
- Course that cultivates a basic problem-solving skills
| Work experience | Work experience and relevance to the course content if applicatable |
|---|---|
| N/A | N/A |
Last modified : Thu May 30 04:24:49 JST 2019