Error correction & compression


This lab illustrates two extremely important fields in the realm of computer science and mathematics.

In transmission and storage mediums, data is subject to various types of noise, distortion, and interference. In other words, errors can be introduced, so that what is transmitted or retrieved from storage can be slightly (or sometimes not so slightly) different from the input.

The theory and practice of error-correcting coding is concerned with the protection of digital information against the errors that occur during data transmission or storage.

As information transfer by remote computing and development of massive information storage and retrieval systems witnesses tremendous growth, the importance of compressing data increases. Data compression is the representation of data by more efficient codes. Data compression results from the elimination of redundant fields of information while representing the data elements in the remaining fields with as few logical indicators as possible. Data compression is used to reduce storage requirements and overall program execution time. Execution time may decrease because, even though encoding/decoding requires additional program instruction, the retrieval of data requires fewer disk accesses.

There are two main subdivisions of data compression: lossless and lossy. In lossless data compression, data can be decoded to its original format without error. In lossy compression, the data cannot be decoded quite to its original form, but the small alteration of the data is considered to be a "negligible" variance in the information.

Links to the problem sets on this page will be available gradually corresponding to the course schedule.

Error correction & compression :

Part 1. Error detection and error-correcting codes. How a scratched CD can play flawlessly. ASCII Encoding. Hamming Code.

Part 2. The big sqze: lossless compression of texts. Lempel-Ziv algorithm. Image compression.