BÀI 4: MÃ HÓA KÊNH (Channel coding)
Đặng Lê Khoa
Email:danglekhoa@yahoo.com
dlkhoa@fetel.hcmuns.edu.vn
Facuty of Electronics & Telecommunications, HCMUNS Facuty of Electronics & Telecommunications, HCMUNS
1
Nội dung trình bày
• Mã hóa kênh ( Channel coding ) • Mã hóa khối (Block codes) + Mã lập (Repetition Code) + Hamming codes + Cyclic codes
* Reed-Solomon codes • Mã hóa chập (Convolutional codes)
+ Encode + Decode
2006-02-16 2 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Sơ đồ khối hệ thống DCS
Format
Source encode
Channel encode
Pulse modulate
Bandpass modulate
Digital modulation
Digital demodulation
C h a n n e l
Format
Detect
Source decode
Demod. Sample
Channel decode
2006-02-16 3 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Channel coding là gì?
• Tín hiệu truyền qua kênh truyền sẽ bị ảnh hưởng bởi nhiễu, can nhiễu, fading… là tín hiệu đầu thu bị sai. • Mã hóa kênh: dùng để bảo vệ dữ liệu không bị sai bằng cách thêm vào các bit dư thừa (redundancy). • Ý tưởng mã hóa kênh là gởi một chuỗi bit có khả
năng sửa lỗi
• Mã hóa kênh không làm giảm lỗi bit truyền mà chỉ làm
giảm lỗi bit dữ liệu (bảng tin)
• Có hai loại mã hóa kênh cơ bản là: Block codes và
Convolutional codes
2006-02-16 4 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Định lý giới hạn Shannon
• Đối với kênh truyền AWGN, ta có
C: channel capacity (bits per second) B: transmission bandwidth (Hz) P: received signal power (watts) No: single-sided noise power density (watts/Hz)
Eb: average bit energy Rb: transmission bit rate
C/B: bandwidth efficiency
2006-02-16 5 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Galois field
•
Binary field : – Tập {0,1}, thực hiện phép cộng và phép nhân 2 thì
kết quả cũng thuộc trường.
Addition
Multiplication
0
00
110
101 011
000 010 001 111
– Binary field còn được gọi là Galois field, GF(2).
2006-02-16 6 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Cách tạo trường Galois
Dùng các thanh ghi dịch Chọn các giá trị khởi tạo (đa thức) để sinh ra chuỗi dài nhất
2006-02-16 7 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Galois Field Construction
0000
0
0001
0 1
1
GF(24) with p(x) = 1 + x +x4
1
2
0010 0100
3
1000
1
0011
2
0110
4
1
1100
3 2 3
1
1
2
1011 0101
2 3 4 5 6 7 8
3
1010
9
1
2
0111
10
1110
11
3 2 3 2
1
1111
12
3 2
1
1101
13
3
1
1001
14
Facuty of Electronics & Telecommunications, HCMUNS
8
Block codes
• Block codes là loại forward error correction (FEC) -> cho
phép tự sửa sai ở đầu thu
• Trong block codes, các bit parity được thêm vào bảng tin
để tạo thành code word hoặc code blocks.
• Khả năng sửa lỗi của block code phụ thuộc vào code
distance
• Block codes có tính chất tuyến tính => kết quả phép tính
số học giữa các phần tử luôn là một phần tử thuộc trường.
2006-02-16 9 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Block codes (tt)
• Luồng thông tin được phân thành từng khối k bits. • Mỗi khối được mã hóa thành khối lớn hơn có n bits. • Các mã này được điều biến và gởi qua kênh truyền. • Quá trình sẽ thực hiện ngược lại ở đầu thu
Data block
Codeword
Channel encoder
k bits
n bits
n-k
Redundant
bits
R
Code rate
c
k n
2006-02-16 10 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Distance of code
Là số phần tử khác nhau của 2 vector Ci và Cj
Nếu code là nhị phân, thì khoảng cách này gọi là khoảng
cách Hamming
101101
001100
100001
=>d12=W(1000001)=2
Ví dụ: Tính khoảng cách Hamming của C1: 101101 và C2 :001100 Giải: Vì => Ta có thể giải mã để sửa sai bằng cách chọn
codewords có dmin
2006-02-16 11 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Repetition Code
Facuty of Electronics & Telecommunications, HCMUNS
12
Repetition Code (tt)
• Truyền: • Nhận :
Facuty of Electronics & Telecommunications, HCMUNS
13
Repetition Code (tt)
Facuty of Electronics & Telecommunications, HCMUNS
14
Linear block codes –cont’d
mapping
kV
nV C
– A matrix G is constructed by taking as its rows the
Bases of C
vectors on the basis, .
,
}
,
kV
v
v
11
12
1
n
V
1
v
v
v
22
n
G
21
V
k
v
v
2 v
k
1
k
2
kn
VV ,{ 1 2 v
2006-02-16 15 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Linear block codes – cont’d
• Encoding in (n,k) block code
U
mG
u
)
(
)
,
,
,
,
( uu , 1
, mm 1 2
m k
n
2
V 1 V 2
– The rows of G, are linearly independent.
V k
u
)
,
,
( uu , 1
2
m 2
V 2
m 1
V 1
n
m 2
V k
2006-02-16 16 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Linear block codes – cont’d
• Example: Block code (6,3)
Message vector
Codeword
V
1
1
0
1
0
0
1
G
V
0
1
1
0
1
0
2
V
1
0
1
0
0
1
3
0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1
0 1 0 1 1 0 1 0
0 1 1 0 0 1 1 0
0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 1
2006-02-16 17 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
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.
IPG [
]
k identity
matrix
kk
I
k
(
kn
)
matrix
k P k
U
,...,
u
)
(
,...,
,...,
p
)
uu , ( 1
2
n
mm , 1 2
kn
2
pp m , , k 1
parity
bits
message
bits
2006-02-16 18 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Linear block codes – cont’d
• For any linear code we can find an matrix , such that its rows are orthogonal to the rows of :
(H
kn
)
n
G
• H is called the parity check matrix and its rows are
linearly independent.
• For systematic linear block codes:
GH T
0
T
IH [
P
]
kn
2006-02-16 19 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Linear block codes – cont’d
U
m
Data source
Format
Modulation
Channel encoding
channel
Data sink
Format
Channel decoding
Demodulation Detection
r
mˆ
eUr
• Syndrome testing:
– S is syndrome of r, corresponding to the error pattern e.
r
,....,
)
received codeword or vector
e
(
,....,
)
error
pattern
or vector
rr ,( 2 1 ee , 2 1
r n e n
T
T
rHS
eH
2006-02-16 20 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Linear block codes – cont’d
•
Standard array
kn
i
,...,3,2
–
–
row as the corresponding
2 nV For row , find a vector in of minimum weight which is not already listed in the array. th:i ie Call this pattern and form the coset
zero codeword
k
U 1 e
U 2 U
e
U 2 U
e
k
2
2
2
2
coset
2
e
e
U
e
U
kn
kn
kn
k
2
2
2
2
2
coset leaders
2006-02-16 21 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Linear block codes – cont’d
•
Standard array and syndrome table decoding
1. Calculate
TrHS
2.
ie
e ˆ S Find the coset leader, , corresponding to .
mˆ 3. Calculate and corresponding . ˆ e
ˆ rU
ˆ ˆ e)UerU
ˆ (eUe
(
)ˆ e
– Note that e ˆ e e ˆ e
• •
If , error is corrected. If , undetectable decoding error occurs.
2006-02-16 22 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Linear block codes – cont’d
• Example: Standard array for the (6,3) code
codewords
000000 000001
110100 110101
011010 011011
101110 101111
101001 101000
011101 011100
110011 110010
000111 000110
000010 000100
110111 110011
011000 011100
101100 101010
101011 101101
011111 011010
110001 110111
000101 000110
001000 010000
111100 100100
coset
100000 010001
010100 100101
010110
Coset leaders
2006-02-16 23 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Linear block codes – cont’d
Error pattern Syndrome
U
(101110)
transmit
ted.
000000 000001
000 101
r The
(001110) syndrome
is received. r is of
computed
:
000010 000100
011 110
T
T
rHS
(001110)
H
(100)
001000 010000
001 010
correspond
ing
to
this syndrome
is
Error ˆ e
pattern (100000)
100000 010001
100 111
corrected
vector
is
estimated
The ˆ rU
ˆ e
(001110)
(100000)
(101110)
2006-02-16 24 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Hamming codes
• Hamming codes
– Hamming codes are a subclass of linear block codes and
belong to the category of perfect codes.
– Hamming codes are expressed as a function of a single integer
.
m
2
Code length
n
:
1
m
m
1
m
2m of informatio n bits : 2 k n-k of parity bits : correction capability : 1 t
Number Number Error
– The columns of the parity-check matrix, H, consist of all non-zero
binary m-tuples.
2006-02-16 25 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Hamming codes
• Example: Systematic Hamming code (7,4)
H
[
I
TP
]
33
1110001 1101010 1011100 0001110
G
[
P
I
]
44
0010101 0100011 1000111
2006-02-16 26 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
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.
2006-02-16 27 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Cyclic block codes
• A linear (n,k) code is called a Cyclic code if all cyclic
“i” cyclic shifts of U
shifts of a codeword are also a codeword. ,...,
U
u
)
,
uuu ( , 1
i )(
U
0 u (
2 u
,
1 n u ,...,
,
,
,...,
u
)
in
in
1
uuu , 1
0
2
n
1
in
1
– Example:
( 1101 )
U
)1(
)2(
)3(
)4(
U
( 1110
)
U
(
0111
)
U
( 1011
)
U
( 1101 )
U
2006-02-16 28 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Cyclic block codes
• Algebraic structure of Cyclic codes, implies expressing codewords in
polynomial form
2
n
1
U
(
X
)
u
...
degree
n- )1(
XuXu 1
2
0
Xu n 1
• Relationship between a codeword and its cyclic shifts:
2
n
1
n
U XX (
)
XuXu
...,
0
1
Xu n 2
Xu 1 n
n
u
Xu n 2
Xu 1 n
0
n
)1(
n
u XuXu n 1 1 U
2 1 n ... 1 ( X )
)1
X
u
(
n
1
)1(
n
U
(
X
)
u
(
X
)1
n
1
– Hence:
U
()1(
X
)
U XX (
)
modulo (
nX
)1
By extension
i
n
U
i ()(
X
)
X
U
(
X
)
modulo
(
X
)1
2006-02-16 29 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Cyclic block codes
•
Basic properties of Cyclic codes: –
Let C be a binary (n,k) linear cyclic code 1. Within the set of code polynomials in C, there
( Xg
)
X
r
(
)
r
X
g
g
(
is a unique monic polynomial with g n . minimal degree is called the generator polynomials. ) Xg 1
0
1. Every code polynomial in C, can be X )
gm ( X ()
expressed uniquely as
r Xg ... ( XU ) U X ( ) ( Xg )
2. The generator polynomial is a factor of
1nX
2006-02-16 30 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Cyclic block codes
X h ()
X
1
• The orthogonality of G and H in polynomial g ( ) form is expressed as . This means is also a factor of
( Xh
)
nX 1nX
, ii
,...,1
k 1. The row , of generator matrix is
" i
"1
formed by the coefficients of the cyclic shift of the generator polynomial.
g
0
0
g
(
X
)
g r
g 1 g
g
0
r
)
G
g 1
g
g
g 1
0
k
g XX ( 1 g
(
X
X
)
r
0
g
g
0
g 1
r
2006-02-16 31 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
•
Cyclic block codes Systematic encoding algorithm for an (n,k) Cyclic code: 1. Multiply the message polynomial by
( Xm
)
knX
1. Divide the result of Step 1 by the generator polynomial
. Let be the reminder.
( Xg
)
( Xp
)
1. Add to to form the codeword
)
X kn m
( X
)
(Xp )
( XU
2006-02-16 32 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
•
Cyclic block codes Example: For the systematic (7,4) Cyclic code with generator polynomial
3
g
1)
X ( Find the codeword for the message
1.
XX 1011 )
(m
n
k ,7
,4
kn
3
2
3
m
( 1011 )
m
(
X
1)
X
X
kn
3
3
2
3
3
5
6
X
m
(
X
)
X
m
(
X
)
X
1(
X
X
)
X
X
X
kn
Divide
X
m
(
X
)
g by
(
X)
:
3
5
6
3
X
X
X
XX
1()
X
2 3 XX 1( ) (X) q quotient
generator
(X)
g
1 X remainder (
p
)
Form
:
the codeword polynomial 3
3
5
6
(
X
1)
X
X
X
(
p
X
U U
X (
X m ) ) )1 1 0 1 0 0 1( parity bits
message
bits
2006-02-16 33 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Cyclic block codes
–
Find the generator and parity check matrices, G and H, respectively.
2
3
g
(
X
11)
X
0
X
X
1
(
,
,
)
( 1101 )
gggg , 1
2
0
3
0001011 0010110
Not in systematic form. We do the following:
G
row(3)
0101100 1011000
row(1) row(1)
row(3) row(2)
row(4)
row(4)
0001011
1101001
G
H
0010110 0100111
0111010 1110100
1000101
33I
TP
P
44I
2006-02-16 34 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Cyclic block codes
• Syndrome decoding for Cyclic codes:
– Received codeword in polynomial form is given by
r
(
X
)
U
(
X
)
e
(
X
)
Error pattern
Received codeword
– The syndrome is the reminder obtained by dividing the received
polynomial by the generator polynomial.
g ()
X
X
X
q
S
r
)
)
(
)
(
(
X Syndrome – With syndrome and Standard array, error is estimated.
• In Cyclic codes, the size of standard array is considerably
reduced.
2006-02-16 35 Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
Example of the block codes
BP
8PSK
QPSK
0NEb / [dB] Lecture 9 Facuty of Electronics & Telecommunications, HCMUNS
2006-02-16 36
