Lecture

Coding Theorem: Proof and Properties

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

COM-404: Information theory and coding

The mathematical principles of communication that govern the compression and transmission of data and the design of efficient methods of doing so. ...

Description

This lecture covers the proof and properties of the coding theorem, focusing on maximizing the properties of lx and the achievable rate. Emre Telatar explains the concepts of channel coding and decoding, emphasizing the achievable rate and the encoding and decoding processes.

Instructor

Emre Telatar

I. Emre Telatar received the B.Sc. degree in electrical engineering from the Middle East Technical University, Ankara, Turkey, in 1986. He received the S.M. and Ph.D. degrees in electrical engineering and computer science from the Massachusetts Institute of Technology, Cambridge, in 1988 and 1992 respectively. In 1992, he joined the Communications Analysis Research Department at AT&T Bell Laboratories (later Lucent Technologies), Murray Hill, NJ. He has been at the EPFL since 2000. Emre Telatar was the recipient of the IEEE Information Theory Society Paper Award in 2001. He was a program co-chair for the IEEE International Symposium on Information Theory in 2002, and associate editor for Shannon Theory for the IEEE Information Theory Transactions from 2001 to 2004. He was awarded the EPFL Agepoly teaching prize in 2005. Emre Telatar's research interests are in communication and information theories.

Official source

Related concepts (29)

Noisy-channel coding theorem

In information theory, the noisy-channel coding theorem (sometimes Shannon's theorem or Shannon's limit), establishes that for any given degree of noise contamination of a communication channel, it is possible to communicate discrete data (digital information) nearly error-free up to a computable maximum rate through the channel. This result was presented by Claude Shannon in 1948 and was based in part on earlier work and ideas of Harry Nyquist and Ralph Hartley.

Decoding methods

In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, such as a binary symmetric channel. is considered a binary code with the length ; shall be elements of ; and is the distance between those elements. One may be given the message , then ideal observer decoding generates the codeword .

Error correction code

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code (ECC). The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors.

Coding theory

Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods.

Mathematical proof

A mathematical proof is a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms, along with the accepted rules of inference. Proofs are examples of exhaustive deductive reasoning which establish logical certainty, to be distinguished from empirical arguments or non-exhaustive inductive reasoning which establish "reasonable expectation".

Related lectures (64)

Fundamental Groups

Explores fundamental groups, homotopy classes, and coverings in connected manifolds.

Sparsest Cut: Bourgain's Theorem

Explores Bourgain's theorem on sparsest cut in graphs, emphasizing semimetrics and cut optimization.

Sparsest Cut: Leighton-Rao Algorithm

Covers the Leighton-Rao algorithm for finding the sparsest cut in a graph, focusing on its steps and theoretical foundations.

Compression: Prefix-Free Codes

Explains prefix-free codes for efficient data compression and the significance of uniquely decodable codes.

Proofs: Direct and Indirect Methods