Transcript EKT 357 DCchapter 3_part 1x

Chapter 3: Channel Coding
(part 1)
EKT 357 Digital Communications
Coping with Transmission Errors
• Error detection codes
▫ Detects the presence of an error
• Error correction codes, or forward correction codes
(FEC)
▫ Designed to detect and correct errors
▫ Widely used in wireless networks
• Automatic repeat request (ARQ) protocols
▫ Used in combination with error detection/correction
▫ Block of data with error is discarded
▫ Transmitter retransmits that block of data
Chapter3: (part 1) Overview
• Channel coding definition
4
Introduction
• Diversity makes use of redundancy in terms of using
multiple signals to improve signal quality.
• Error control coding, as discussed in this lecture and
next, uses redundancy by sending extra data bits to
detect and correct bit errors.
• Two types of coding in wireless systems
▫ Source coding – compressing a data source using encoding of
information (as seen in chapter 2)
▫ Channel coding – encode information to be able to overcome bit
errors
• Now we focus on channel coding, also called error
control coding to overcome the bit errors of a channel.
Channel Coding in Digital Communication
Systems
Channel Coding - Definition
•
Class of signal transformations designed to improve
communication performance by enabling the
transmitted signals to better withstand channel
distortions such as noise, interference, and fading.
•
In digital communication systems an optimum
system might be defined as one that minimizes the
probability of bit error.
Channel coding - Definition
• Error occurs in the transmitted signal due to the
transmission in a non-ideal channel
▫ Noise exists in channels
▫ Noise signals corrupt the transmitted data
•
Channel coding can be divided into two major
classes:
1. Waveform coding by signal design
2. Structured sequences by adding redundancy
Waveform Coding
▫ deals with transforming waveform into “better
waveform” robust to channel distortion hence
improving detector performance.
• Examples:
▫
▫
▫
▫
Antipodal signaling
Orthogonal signaling
Bi-orthogonal signaling
M-ary signaling
Structured Sequences
▫ Deals with transforming sequences into “better sequences”
by adding structured redundancy (or redundant bits). The
redundant bits are used to detect and correct errors hence
improves overall performance of the communication
system.
• Examples:
▫ Linear codes
 Hamming codes
 Cyclic codes
Antipodal signals
• -Antipodal signals are:
▫ - mirror images,
▫ - the negatives of each other
▫ - or 180° apart.
• Example: Let s1 and s2 be two signals, where s1 = sinωt
and s2 = -sinωt
•
then the waveform representation of the two signals.
On the figure we can easily see that
s1 = -s2.
Orthogonal signals
• Orthogonal signals have no relationship with each
other.
• In geometrical vector representation, orthogonal
signals are mutually perpendicular to one other,
where:
▫ The direction of the vector is the direction of the
wave’s energy flow
▫ The length of the vector is the energy E of the wave,
which counted as
▫ In general, si waves are constituted as an orthogonal
set, if (and only if)
Antipodal & Orthogonal signals
• Example for vector representation of Antipodal
and Orthogonal signals
Orthogonal Code
• A one-bit data set can be transformed, using
orthogonal codewords of two digits each,
described by the rows of matrix H1 as follows:
Orthogonal Code
• To encode a 2-bit data set, we extend the
foregoing set both horizontally and vertically,
creating matrix H2.
Orthogonal Code
• The same construction rule to obtain an
orthogonal set H3 for a 3-bit data set.
Orthogonal Code
 Hk  1 Hk  1
Hk  

 Hk  1 Hk  1
• Each pair of words in each codeword set H1, H2,
H3, …, Hk, … has as many digit agreements as
disagreements. Hence, in accordance with
 1, for i  j
zij  
0, otherwise
• zij=0 (for i≠j), and each of the sets is orthogonal.
M-ary Signaling
• “M-ary” is derived from the word “binary”. M is
simply a digit that represents the number of
conditions possible.
• M-ary is Multilevel signaling.
M-ary Signaling
• M-ary signaling is the process when:
1. the processor accepts “n” bit at a time
2. Instructs the modulator to do one of M = 2n
long waveforms
Data rate 
samples
bits
X
second sample
1.Data rate = bit rate
2.Symbol rate = bit rate/n = Baud rate
Example 1
• What is the possible output for 16-QAM and
QPSK?
• What is the number of bit for 16-QAM and
QPSK?
Example 2
• An “M-ary” communication system transmit at a
rate of 1000 baud. What is the equivalent bits
per second for M=4, M=8, and M=16?
Chapter3: (part 1_cont’d) Overview
• Error Detection techniques
▫ Parity Check
▫ Cyclic Redundancy Check (CRC)
▫ Repetition
Parity Check
• Parity Check
▫ Very simple technique used to detect errors
• In Parity check, a parity bit is added to the data
block
▫ Assume a data block of size k bits
▫ Adding a parity bit will result in a block of size k+1
bits
• The value of the parity bit depends on the number
of “1”s in the k bits data block
Parity Bit
▫ If we have a message = 1010111
 k = 7 bits
▫ Adding a parity check so that the number of 1’s is even
 The message would be : 11010111
 k+1 = 8 bits
• At the receiver ,if one bit changes its values, then an
error can be detected
Parity Bit
• Parity bit appended to a block of data
• Even parity
▫ Added bit ensures an even number of 1s
• Odd parity
▫ Added bit ensures an odd number of 1s
• Example, 7-bit character [1000001]
▫ Even Parity
 ASCII A=01000001 OR 10000010
 ASCII T=11010100 OR 10101001
▫ Odd Parity
 ASCII A=11000001 OR 10000011
 ASCII T=01010100 OR 10101000
Parity Bit
• ASCII characters are stored one per byte (8 bits)
• The left or right most bit is called the parity bit
• A parity bit is an extra bit included with a
message to make the total number of 1’s either
even or odd.
Signal Transmission Algorithm
• A parity bit is generated and added to a data packet
for the purpose of error detection.
• In the even-parity convention, the value of the parity
bit is chosen so that the total number of '1' digits in
the combined data plus parity bit is an even number.
•
• Upon receipt of the packet (a sequence of bits), the
parity needed for the data is recomputed by local
hardware and compared to the parity bit received
with the data.
• If any bit has changed state, the parity will not
match, and an error will have been detected.
Parity Generator
• The circuit that generates the parity bit in the
transmitter is called a parity generator.
• XOR(even parity generator)
Parity Generator
• Example of 3 bits message for even parity
convention.
(Truth Table)
Parity Checker
• The Circuit that checks the parity in the receiver
is called a parity checker.
• XOR (even)
Parity Generator
• Odd parity?
Example 3
• Suppose you receive a binary bit word “0101”
and you know you are using an odd parity.
• Is the binary word error?
Example 4
• At the transmitter, we need to send the message
M= 1011100. We need to make the number of
one’s odd.
▫ What will be the transmitter code?
▫ What is the receiver code for
 Error and no error detected?
Probability of undetected error
• Assuming that the probability of j errors occurring in a
block of n bits is computed as follows:
• Where Pnd is the probability that a channel symbol is
received in error, and where
• The number of which j bits out of n may be in error.
Example 5
• Compute the probability of an undetected
message error, assuming that the probability of a
-3
channel symbol error is p = 10
Cyclic Redundancy Check (CRC)
• Uses more than a single parity bit.
▫ Adds m bit of ‘0’ frame check sequence.
• Procedure:
▫
▫
▫
▫
M = original data message ( n bits)
P = Predefined pattern (m+1)
Mm = M concatenated with m zeros
R
= remainder of dividing ( Mm / P )
Sender Operation
• Sender
 The transmitter performs the division Mm / P
 The transmitter then computes the remainder R
 It then concatenates the remainder with the message
“MR”
 Then it sends the encoded message over the channel
“MR”.
Receiver Operation
• Receiver:
▫ The receiver receives the message MR
▫ It then performs the division of the message by the
predetermined pattern P, “ MR / P ”
 If the remainder is zero, then it assumes the message
is not corrupted “Does not have any error”. Although
it may have some.
 If the remainder is NON-zero, then for sure the
message is corrupted and contain error/s.
Division process
• The division used in the CRC is a modulo-2
arithmetic division.
• Exactly like ordinary long division, only simpler,
because at each stage we just need to check
whether the leading bit of the current three bits
is 0 or 1.
▫ If it's 0, we place a 0 in the quotient and
exclusively OR the current bits with zeros.
▫ If it's 1, we place a 1 in the quotient and exclusively
OR the current bits with the divisor.
Example 6
• Using CRC for error detection and given a
message M = 10110 with P = 110, compute the
following
▫ Frame check Sum (FCS)
▫ Transmitted frame
▫ Received frame and check if there is any error in
the data
Example 7
• Let M = 111001 and P = 11001
• Compute the following:
▫ Frame check Sum (FCS)
▫ Transmitted frame
▫ Received frame and check if there is any error in
the data
Repetition
-The simplest form of redundancy is: Repetition!
-A repetition code is a coding scheme that repeats the
bits across a channel to achieve error-free
communication.
Sender
Receiver
“0”
Did she say “1” ?
I said “0”
Sounded like “0”
One more time: “0”
Sounded like “0”
again
Repetition Code
The easiest way to increase accuracy is repetition. For
instance we can repeat the message 3 times.
Repeat every bit 3 times
0110 => 000,111,111,000
Error detected if all or any of 3 bits are not the same
000,100,111,000
Repetition Code
• Encoding rule:
Repeat each bit 3 times
Example:
1 . 0 . 1 .  111 . 000 . 111 .
• Decoding rule:
Majority vote!
Examples of received codewords:
110 . 000 . 111 .  1 . 0 . 1 . Error-free!
111 . 000 . 010 .  1 . 0 . 0 . Error!
Repetition Code
• Strategy : Majority rules
▫ 0110 => 000,111,111,000 => 000,110,111,000 =>
000,111,111,000
▫ Was it actually 0010 => 000,000,111,000 or
000,100,111,000?
45
Analysis of Repetition Code
• Error can go undetected only if 3 consecutive bits
are in error
• 0110 => 000,111,111,000 => 000,000,111,000
• If probability of one-bit error is p, then probability
of undetected error is p3
• E.g. one-bit error = 10-5 => undetected error =10-15
• (Assumes independence)
Analysis of Repetition Code
• The redundancy in repetition of bits is measured
by the efficiency or rate of the code, denoted by R:
•
R= (#information bits / # bits in codeword) x 100%
• For the 3-repetition code: R=33%
Example 8
• Calculate the rate of the code for the repetition
bits of 5 times and 7 times with the original code
of 3bits?
Analysis of Repetition Code
The catch is:
As the number of repetitions grows to infinity, the
transmission rate shrinks to zero!!!
This means: slow data transmission.
Is there a better (more efficient) error correcting code?
Probability of Incorrect Decoding
• Repeating each bit three times allows us to
correct one error in each group of three bits, but
not more errors.
• Suppose each bit has probability of being
received correctly, independently for each bit.
• The probability that a group of three repeated
bits will be decoded incorrectly is
3
2
▫ Pi=Pr( 0 errors) +Pr (1 error) = P + 3P (1-P)
Probability of Incorrect Decoding
• As n gets bigger, the decoding error probability goes
down. Here’s what happens with a 10% probability
of transmission error (p=0.1)
e
Number of repetitions
Probability of incorrect decoding
3
0.028
5
0.0086
7
0.002728
9
0.000892
• It seems that we can push the error probability as
close to zero as we wish by using more repetitions.
• If we let the number of repetitions grow and grow,
we can approach perfect reliability !