Communicating
Efficiently
Coding Theory
The Problem
Sending data from one place to another
(through a channel) may yield errors.
● How do you detect such errors?
● How do you correct the errors?
Mind Test
“It tkaes a geart dael of cuoarge to satnd up to yuor
enimees, but a geart dael mroe to satnd up to yuor
freidns.”
-Dumbledore
Your Brain is a Code-cracking Machine.
For emaxlpe, it deson’t
mttaer in waht oredr the
ltteers in a wrod aepapr,
the olny iprmoatnt tihng is
taht the frist and lsat ltteer
are in the rghit pcale. The
rset can be a toatl mses
and you can sitll raed it
wouthit pobelrm.
Your Brain is a Code-cracking Machine.
● S1M1L4RLY, Y0UR M1ND
15 R34D1NG 7H15
4U70M471C4LLY
W17H0U7 3V3N
7H1NK1NG 4B0U7 17.
● http://www.livescience.co
m/18392-reading-jumbled-
words.html
Sending and Receiving
SENDER CHANNEL RECEIVER
Goal of technology in communication
To construct an information system that results
in
1. fast encoding of information
2. easy transmission of encoded messages
3. fast decoding of received messages
4. correction or errors produced in the channel
5. maximum transfer of information per unit
time
The Basic Problem of Coding Theory
Messages are transmitted over a
communication channel which is subject to
noise. But noise can distort messages resulting
in errors.
Goals of Coding Theory
● Error Detection
● Error Correction
HI, BOB! HI, COB!
1001 1000 10010 10000
1110 1011 11101 10110
1110 1010 11101 10100
HOW DO WE ACHIEVE THESE GOALS EFFICIENTLY?
Example
Messages:
YES → 00 NO → 11
YES ???
00 10
COMMUNICATION
FAILURE
What is coding theory?
CODING THEORY deals with
the design of error-correcting
codes for the reliable transmission
of information across noisy
channels.
Imperfect Transmission of Data
Data is usually transferred
in the form of a series of 0s
and 1s. However,
transmission of data is not
perfect.
Some Causes
An electric surge, cross-contamination from another data
stream, or human error can easily change some of the 0s to 1s
and vice versa.
Noise in Communication
Information media, such as
communication systems and
storage devices of data, are
not absolutely reliable in
practice because of noise or
other forms of introduced
interference.
Applications of Coding Theory
● Transmission of pictures from distant space
● Quality of sound in CDs
● Establishment of computer networks
● Communication through telephone lines
● Messaging through wireless communication
Applications of Coding Theory
When photographs are
transmitted to Earth
from deep space, error-
control codes are used
to guard against the
noise caused by
atmospheric
interruptions.
Applications of Coding Theory
Compact discs (CDs) use
error- control codes so
that a CD player can
read data from a CD
even if it has been
corrupted causing
imperfections on the CD.
Tasks of Coding Theory
● The goal of coding theory is
to improve the reliability of
digital communication by
devising methods that
enable the receiver to
decide whether there have
been errors during the
transmission (error
detection), and if there are,
to possibly recover the
original message (error
correction).
Terminologies
Source coding involves changing the message source, such as
a data terminal or the human voice, to a suitable code for
transmission through the channel.
The source encoder transforms the source output into a
sequence of symbols which we call a “message”.
An example of source coding is the ASCII code.
Terminologies
Bit – short for binary integer – 0 and 1
Codeword - a string of 0's and 1's representing an
actual message
Terminologies
Examples: Stop → 000
Go → 101
Wait → 110
000, 101, 110 are codewords
100, 111, 001, 010, 011 are NOT codewords
●
The LENGTH OF A CODEWORD is the number of
binary digits it has.
Terminologies
Code
- the collection or set of all codewords
EXAMPLE:
Stop → 000
Go → 101
●
Wait → 110
The code is C = {000, 101, 110}.
Terminologies
Encode
STOP
“message“ becomes a
“codeword“
STOP 000
SOURCE
ENCODER
000
Terminologies
Decode 000
“received word“ is
reverted back to a SOURCE
DECODER
“message“
000 STOP
STOP
ASCII CODE
Abbreviated from American Standard Code for
Information Interchange, is a character
encoding standard for electronic communication.
ASCII codes represent text in computers,
telecommunication equipment, and other devices.
Most modern character-encoding schemes are
based on ASCII, although they support many
additional characters.
7-bit ASCII CODE
A 1000 001 B 1000 010
E 1000 101 S 1010 011
I 1001 001 T 1010 100
O 1001 111 W 1010 111
U 1010 101 R 1010 010
Examples:
Encode the message “SAT“ using the 7-bit ASCII code table
shown above.
Decode 1010 011 1000 101 1010 100.
Decode 1000 010 1010 101 1010 011
Simple Codes
1. Parity Check Codes
The simplest form of error detection is parity,
where a single bit is appended to a bit string.
A bit string has odd parity if the number of 1s in
the string is odd.
A bit string has even parity if the number of 1s in
the string is even.
Illustration of a Communication Failure
Messages:
YES → 00
NO → 11
Received Message: 10
YES ???
00 10
COMMUNICATION
FAILURE
Parity Check Digit
INCLUDE A PARITY CHECK DIGIT 0 or 1
Messages:
YES → 000
NO → 111
YES ???
000 100
Parity Check
An error is detected because 100 does not mean
anything.
Compare the received word 100 and the code
word 000.
Compare the received word 100 and the code
word 111.
Which is the TRUE message sent? Which word is
“nearest“ to the received word?
Even Parity Code (An Example)
Three Messages
Stop → 000 000 0
Go → 111 111 0
Wait → 000 111 1
This is an even parity code.
C = {000 000 0, 111 111 0, 000 111 1}
Even Parity Code (An Example)
Three Messages
Suppose the message
Stop → 000 000 0 111 111 1 is received.
Go → 111 111 0 Is this acceptable?
Wait → 000 111 1 What do you think is the
original message?
2. Repetition Codes
The simplest possible error-correcting code is the
repetition code.
For instance, if we wanted to send the message
PROCEED, we could repeat each letter a certain
number of times and send, say,
PPPPPRRRRROOOOOCCCCCEEEEEEEEEEDDDDD.
Example
1. Encode the bit string 011001 by repeating each
bit twice.
Solution:
00 11 11 00 00 11
2. Encode the bit string 011 by repeating each bit
thrice.
Solution:
000 111 111
Repetition Codes (Majority decoding)
Consider a code where each bit is repeated 3 times.
Suppose we want to transmit the following bit string:
0110100. If no error is made during transmission, the
receiver gets
000 111 111 000 111 000 000.
Now assume that the receiver gets
000 111 110 000 111 000 010.
Has there been any error in this transmitted word?
How do you correct it?
Repetition Codes (Majority decoding)
Supposed the received word is
r = 000 111 110 000 111 000 010
Use the majority rule to decode, thus
D(r) = 000 111 111 000 111 000 000
Error Detection and
Error Correction
Hamming Distance
The Hamming distance between two words is the
number of differences in corresponding bits.
If x and y are two bits (binary strings) then their
hamming distance is denoted by d(x,y).
What is d(1010, 1100)?
What is d(101010, 111111)?
Nearest Neighbor Decoding
● Suppose that when a
codeword x from a code C is
sent, the bit string y is
received.
● If the transmission was error-
free, then y would be the same
as x. But if there are
transmission errors, then y
would not be the same as x.
How can we correct errors?
That is, how can we recover x?
Nearest Neighbor Decoding
One approach would be to compute the Hamming
distance between y and each of the codewords in C.
Then, to decode y, we take the codeword of minimum
Hamming distance from y, if such a codeword is
unique.
If the distance between the closest codewords in C is
large enough and if sufficiently few errors were made
in transmission, this codeword should be x. This type
of decoding is called nearest neighbor decoding.
Example
Given the code C = {0000 0000, 1000 1111, 1111 1111},
decode the received word
y = 1111 1010.
We find the hamming distance between the received
word y and each codeword x in C.
d(0000 0000, y) = 6, d(1000 1111, y) = 5,
d(1111 1111, y) = 2.
Example
By using the nearest neighbor decoding principle
we obtain
D(y) = 1111 1111
since this codeword is the nearest word to the
received word y.
0000 0000 y 1000 1111
d=6 2 5
1111 1111
Minimum Distance of a Code
The minimum distance of a code is the smallest
distance between any two distinct codewords in the
code.
Example:
Given C = {111, 110, 011}, we have
d(111, 110) = 1, d(111, 011) = 1, d(110, 011) = 2.
Therefore, the minimum distance of C is
d(C) = 1.
Detection and Correction Capability of a Code
Let C be a set of codewords and let 2e + 1
be its minimum Hamming distance . Then
It is possible to detect up to 2e errors.
It is possible to correct up to e errors.
Detection and Correction Capability of a Code
Minimum Error Detection/ Correction
Distance
1 No detection possible
2 1-error detecting
3 2-error detecting/
1-error correcting
4 3-error detecting/
1-error correcting
5 4-error detecting/
2-error correcting
