Source Coding Theorem - Digital Communication

What is Source Coding Theorem?

The discrete memoryless source produces the code that has to be represented efficiently. It is one of the important problems in communications. There are code words representing these source codes.

Consider telegraphy where Morse code is used. The alphabets are represented by Marks and Spaces. If letter E is taken that is used mostly, it is denoted by “.” Whereas the letter Q that is used rarely is denoted by “--.-”

Below is the block diagram. Here Sk is the discrete memoryless source output and the bk is the source encoder output which is represented by 0s and 1s.

The encoded sequence is easily decoded at the receiver.

Consider the source has an alphabet with k different symbols and the kth symbol Sk occurs with the probability Pk, where k = 0, 1…k-1.

Sk is assigned with binary code work, by the encoder having length lk, is measured in bits.

Hence, the average code word length L of the source encoder is defined as L represents the average number of bits per source symbol

If Lmin=minimum possible value of L

Then coding efficiency is defined as With we will have η≤1

Moreover, the source encoder is efficient when η=1

For this, the value Lmin has to be determined.

The definition, “Given a discrete memoryless source of entropy H(δ), the average code-word length L for any source encoding can bounded as In simple terms, the code word (example: Morse code for the word QUEUE is -.- ..- . ..- . ) is always greater than or equal to the source code (QUEUE in example). This means, code word symbols are greater than or equal to the source code alphabets.

Therefore with Lmin=H(δ), the source encoder efficiency in terms of Entropy H(δ) can be written as This is known as noiseless coding theorem as it provides encoding which is error-free, also known as Shannon’s first theorem.

Digital Communication Topics