327997111-Ch-6-Digital-Communications.ppt

Digital-Communications

1. Digital CommunicationsDigital Communications
Chapter 6
Channel Coding : PART I
Signal Processing Lab

2. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
2 page
Block Diagram of a DCS
2


3. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
3 page

4. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
4 page
Channel Coding
Transforming signals to improve communications performance by
increasing the robustness against channel impairments (noise, interference,
fading, ..)
Waveform coding: Transforming waveforms to “better” waveforms
Structured sequences: Transforming data sequences into “better”
sequences, having structured redundancy.
“Better” in the sense of making the decision process less subject to
errors

5. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
5 page
Code Rate and Redundancy

6. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
6 page

7. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
7 page
Why Using Error correction Coding

8. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
8 page
Linear Block Codes (cont’d)
A linear block code (n, k) transforms a block of k information
digits into a longer block of n coded digits.
A set of 2
k
n-tuples is called a linear block code if and only if, it
is a subspace of the vector space V
n of all n-tuples.

9. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
9 page

10. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
10 page
Linear Block Codes (cont’d)
A code is linear if any linear combination of codewords is a
codeword.
Encoder:

11. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
11 page
Linear Block Codes (cont’d)
Generator matrix
The rows of the generator matrix are linearly independent.
For a systematic code, the first (or last) k elements in the codeword are
information bits.

12. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
12 page
Vector subspace
A subset S of the vector space is called
a subspace if:
The all-zero vector is in S.
The sum of any two vectors in S is also in S.
Example:

13. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
13 page
Linear Block Codes (cont’d)
The Hamming Weight of vector U, denoted by w(U ), is the number of
non-zero elements in U.
The Hamming Distance between two vectors U and V is the number of
elements in which they differ.
The minimum distance of a block code is

14. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
14 page

15. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
15 page
Linear Block Codes (cont’d)
Error detection capability is given by
Error correcting-capability t of a code, which is defined as the
maximum number of guaranteed correctable errors per codeword,
is
1
min
de







2
1
mind
t

16. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
16 page
Linear Block Codes (cont’d)
For memoryless channels, the message error probability that
the decoder commits an erroneous decoding is
 p is the bit error probability over channel.
The decoded bit error probability is













n
tj
jnj
M
pp
j
n
P
1
)1(













n
tj
jnj
B
pp
j
n
j
n
P
1
)1(
1

17. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
17 page
Linear Block Codes (cont’d)
A matrix G is constructed by taking as its rows the
vectors on the basis

18. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
18 page
Linear Block Codes (cont’d)
Encoding in (n,k) block code

The rows of G are linearly independent.

19. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
19 page
Linear Block Codes (cont’d)
Example: Block code (6,3)

20. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
20 page
Linear Block Codes (cont’d)
Systematic block code (n,k)
For a systematic code, the first (or last) k elements in the codeword are
information bits.

21. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
21 page
Linear Block Codes (cont’d)
For any linear code we can find an matrix , H
(n-k)xn, which its
rows are orthogonal to rows of G:
H is called the parity check matrix and its rows are linearly
independent
For systematic linear block codes:
0
T
GH
][
T
knPIH


22. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
22 page

23. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
23 page
Linear Block Codes (cont’d)
Syndrome testing:
S is syndrome of r, corresponding to the error pattern e.

24. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
24 page
Linear Block Codes (cont’d)
Standard array
For row find a vector in of minimum weight which is
not already listed in the array.
Call this pattern and form the -th row as the corresponding
coset
,2........3,2
kn
i


n
V
i
e i

25. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
25 page
Linear Block Codes (cont’d)

26. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
26 page
Linear Block Codes (cont’d)
Standard array and syndrome table decoding
Calculate
Find the coset leader, , corresponding to S.
Calculate and corresponding .
Note that
If , error is corrected.
If , undetectable decoding error occurs.
T
rHS
i
eeˆ
erU ˆˆ
 mˆ
eeˆ
eeˆ
)e(eUee)(UerU ˆˆˆˆ


27. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
27 page
Hamming Codes

Hamming codes: subclass of linear block codes and
belong to the category of perfect codes (corrects
every 1-bit error).
From Standard Array:
mmnk
n
n





12
bitcheck parity of # is m where,1212 and
21n
error)]bit one of (# nerror) (zero [1
cordword) of #(2array) standard theof size(2
m
mk-n
k-n
k

28. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
28 page
Cyclic Block Codes
Cyclic codes are a subclass of linear block codes.
Encoding and syndrome calculation are easily
performed using feedback shift-registers.
Hence, relatively long block codes can be
implemented with a reasonable complexity.
BCH and Reed-Solomon codes are cyclic codes.
(372쪽 Table 6.4 참조)

29. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
29 page
Cyclic Block Codes (cont’d)
A linear (n,k) code is called a Cyclic code if all cyclic shifts of
a codeword are also a codeword.
Example:

30. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
30 page
Cyclic Block Codes (cont’d)
Algebraic structure of Cyclic codes implies expressing
codewords in polynomial form
Relationship between a codeword and its cyclic shifts:
Hence:

31. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
31 page

32. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
32 page
Properties of the Binary Cyclic Code
Generator polynomial
Every code polynomial can be expressed uniquely as
U is said to be a valid codeword if and only if g(x) divides into U(x)
without a remainder
The generator polynomial is a factor of
If g(x) is a polynomial of degree n-k and is a factor of
then, g(x) uniquely generates an (n,k) cyclic code.

p
p
XgXggXg  ...)(
10
)(XU
)(g)(m)( XXXU
)(Xg 1
n
X
1)(h)(.. 
n
XXXeig
1
n
X

33. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
33 page
Encoding in Systematic Form
Divide by g(x)
where
Using modulo-2 arithmetic
This is a valid codeword polynomial, since it is a polynomial of degree
n-1 or less, and when divided by g(x) there is a zero remainder

34. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
34 page

35. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
35 page

36. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
36 page

37. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
37 page

38. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
38 page
6.7.6 Error Detection and Correction
Thus the syndrome of the received polynomial Z(x) contains
the information needed for correction of the error pattern

39. Signal Processing Lab., http://signal.korea.ac.kr
Dept. of Elec. and Info. Engr., Korea Univ.
2025년 3월 7일
39 page