3/22/2010
1
CHƯƠNG 5: MÃ HÓA KÊNH
ðặng Lê Khoa
Email: dlkhoa@fetel.hcmuns.edu.vn
Facuty of Electronics & Telecommunications, HCMUS
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
ðiều chế mã lưới (Trellis Coded Modulation)
2
Sơ ñồ khối DCS
Format Source
encode
Format Source
decode
Channel
encode Pulse
modulate Bandpass
modulate
Channel
decode
Demod.
Sample
Detect
Channel
Digital modulation
Digital demodulation
3
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
4
Các loại mã hóa sửa sai
Mã lập (Repetition Code)
Mã khối tuyến tính (Linear Block Code), e.g.
Hamming
Mã vòng (Cyclic Code), e.g. CRC
BCH và RS Code
Mã chập (Convolutional Code)
Truyền thống, giải mã Viterbi
Mã Turbo
Mã LDPC
Coded Modulation
TCM
BICM 5
Mã lập
Recovered state
6
3/22/2010
2
Kiểm tra chẵn lẻ (Parity Check)
Thêm 1 bit ñể xor các bit có kết quả là 0
Dữ liệu truyền, sửa lỗi, không thể sửa lỗi
Kiểm tra hàng và cột
Ứng dụng: ASCII, truyền dữ liệu qua cổng nối
tiếp
7
Mã khối tuyến tính (Linear block codes)
Chuỗi bit thông tin ñược chia thành từng khối k bit.
Mỗi khối ñược encode thành từng khối lớn hơn có
n bit.
Các bit ñược mã hóa và gửi trên kênh truyền.
Quá trình giải mã ñược thực hiện ở phía thu.
Data block Channel
encoder Codeword
k bits n bits
rate Code
bits Redundant
n
k
R
n-k
c=
8
Linear block codes – cont’d
Khoảng cách Hamming giữa hai vector Uvà V, là
số các phần tử khác nhau.
Khoảng các tối thiểu của mã hóa khối là
Ví dụ: Tính khoảng cách Hamming của C1: 101101
và C2:001100
Giải: Vì =>d12=W(1000001)=2
=> Ta có thể giải mã ñể sửa sai bằng cách chọn
codewords có dmin
)()( VUVU,
⊕
=
wd
)(min),(min
min i
i
ji
ji
wdd UUU ==
≠
100001
001100
101101
=
⊕
9
Linear block codes – cont’d
Khả năng phát hiện lỗi ñược cho bởi:
Khả năng sửa lỗi t của mã hóa ñược ñịnh
nghĩa là số lỗi tối ña có thể sửa ñược trên 1 từ
mã (codeword)
−
=2
1
min
d
t
1
min
−= de
10
Linear block codes – cont’d
Encoding trong bộ mã hóa khối (n,k)
Các hàng của G thì ñộc lập tuyến tính.
mGU
=
kn
k
kn
mmmuuu
mmmuuu
VVV
V
V
V
⋅++⋅+⋅=
⋅=
2221121
2
1
2121
),,,(
),,,(),,,(
⋮
……
11
Linear block codes – cont’d
Example: Block code (6,3)
=
=
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
1
0
1
3
2
1
V
V
V
G
1
1
1
1
1
0
0
0
0
1
0
1
1
1
1
1
1
0
1
1
0
0
0
1
1
0
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
1
1
0
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
0
0
0
1
0
0
0
1
0
Message vector Codeword
12
3/22/2010
3
Linear block codes – cont’d
Mã hóa khối (n,k)
k phần tử ñầu tiên (hoặc cuối cùng) trong từ mã là các
bit thông tin.
matrix )(
matrixidentity
][
knk
kk
k
k
k
−×=
×=
=
P
I
IPG
),...,,,,...,,(),...,,(
bits message
21
bitsparity
2121
kknn
mmmpppuuu
−
==U
13
Linear block codes – cont’d
ðối với bất kỳ mã hóa khối tuyến tính, chúng
ta có một ma trận . Các hàng của
ma trận này trực giao với ma trận :
Hñược gọi là ma trận kiểm tra parity và các
hàng của chúng ñộc lập tuyến tính.
ðối với mã hóa khối truyến tính:
nkn ×− )(
H
G
0GH =
T
][
T
kn
PIH
−
=
14
Linear block codes – cont’d
Kiểm tra ñặc trưng:
Slà ñặc trưng của r, tưng ứng với error pattern e.
Format Channel
encoding Modulation
Channel
decoding
Format Demodulation
Detection
Data source
Data sink
U
r
m
m
ˆ
channel
or vectorpattern error ),....,,(
or vector codeword received ),....,,(
21
21
n
n
eee
rrr
=
=
e
r
eUr
+
=
TT
eHrHS ==
15
Linear block codes – cont’d
Mảng tiêu chuẩn
Hàng ñược tạo thành bằng cách cộng U
với pattern
kknknkn
k
k
22
2
22
2
2222
2
21
UeUee
UeUee
UUU
⊕⊕
⊕⊕
−−−
⋯
⋮⋱⋯⋮
⋯
⋯
zero
codeword
coset
coset leaders
kn
i
−
=2,...,3,2
i
e
16
Linear block codes – cont’d
Mảng tiêu chuẩn và ñặc trưng bảng giải mã
1. Tính
2. Tìm coset chính , tưng ứng với .
3. Tính và tưng ứng với .
Chú ý:
• Nếu , error ñược sửa.
• Nếu , bộ giải mã không thể phát hiện lỗi.
T
rHS =
i
ee =
ˆ
S
erU ˆ
ˆ+=
m
ˆ
)
ˆˆ
(
ˆ
ˆe(eUee)UerU ++=++=+=
ee =
ˆ
ee ≠
ˆ
17
Linear block codes – cont’d
Ví dụ: Mảng chuẩn cho mã (6,3)
010110100101010001
010100100000
100100010000
111100001000
000110110111011010101101101010011100110011000100
000101110001011111101011101100011000110111000010
000110110010011100101000101111011011110101000001
000111110011011101101001101110011010110100000000
⋯
⋯
⋮
⋮⋮⋮
Coset leaders
coset
codewords
18
3/22/2010
4
Linear block codes – cont’d
111010001
100100000
010010000
001001000
110000100
011000010
101000001
000000000
(101110)(100000)(001110)
ˆ
ˆ
estimated is vector corrected The
(100000)
ˆ
is syndrome this toingcorrespondpattern Error
(100)(001110)
:computed is of syndrome The
received. is (001110)
ted. transmit(101110)
=+=+=
=
===
=
=
erU
e
HrHS
r
r
U
TT
Error pattern Syndrome
19
Hamming codes
Là trường hợp riêng của linear block codes
Diễn tả theo hàm của một số nguyên .
Hamming codes
2
≥
m
t
mn-k
mk
n
m
m
1 :capability correctionError
:bitsparity ofNumber
12 :bitsn informatio ofNumber
12 :length Code
=
=
−−=
−=
20
Hamming codes
Example: Systematic Hamming code (7,4)
][
1011100
1101010
1110001
33 T
PIH ×
=
=
][
1000111
0100011
0010101
0001110
44×
=
=IPG
21
Mã hóa Hamming
Mã hóa: H(7,4)
Nhiều phép kiểm tra tổng
Message=[a b c d]
r= (a+b+d) mod 2
s= (a+b+c) mod 2
t= (b+c+d) mod 2
Code=[r s a tb c d]
Tốc ñộ mã: 4/7
Càng nhỏ, nhiều redundance bit, ñược bảo vệ tốt hơn.
Khác biệt giữa phát hiện và sửa lỗi
Message=[1 0 1 0]
r=(1+0+0) mod 2 =1
s=(1+0+1) mod 2 =0
t=(0+1+0) mod 2 =1
Code=[ 1 0 1 10 1 0 ]
22
Hamming codes
Example: Systematic Hamming code (7,4)
][
1011100
1101010
1110001
33 T
PIH ×
=
=
][
1000111
0100011
0010101
0001110
44×
=
=IPG
23
Ví dụ mã hóa Hamming
H(7,4)
Ma trận sinh G: ñầu tiên là ma trận ñơn vị 4x4
Dữ liệu truyền là vector p
Vector truyền x (G=[I/P])
Vector nhận r và vector lỗi e
24
3/22/2010
5
Sửa lỗi
Nếu không có lỗi, vector ñặc trưng (syndrome) z=zeros
Nếu có 1 lỗi ở vị trí thứ 2
Vector ñặc trưng z là
tương với cột thứ 2 của H. Vậy, lỗi ñuợc phát hiện ở vị trí
thứ 2 và có thể sửa lại cho ñúng.
25
ðộ lợi mã hóa (Coding Gain)
Tốc ñộ mã R=k/n, k: số symbol dữ liệu, n tổng
symbol
SNR từ và SNR của bit
Với một sơ ñồ mã hóa, ñộ lợi mã hóa tại một
sắc xuất lỗi bit ñược ñịnh nghĩa là sự khác biệt
giữa năng lượng cần thiết cho 1 bit thông tin ñã
mã hóa ñể ñạt ñược sắc xuất lỗi cho trước và
truyền dẫn không mã hóa
26
Ví dụ ñộ lợi mã hóa
27
Example of the block codes
8PSK
QPSK
[dB] /
0
NE
b
B
P
28
Cyclic code
Cyclic codes ñược quan tâm và quan trọng vì
Dựa trên cấu trúc ñại số và có thể ứng dụng rộng
rãi.
Dễ dàng thực hiện bằng thanh ghi dịch (shift register)
ðược ứng dụng rộng rãi trong thực nghiệm
Trong thực nghiệm, cyclic codes ñược sử dụng
ñể phát hiện lỗi (Cyclic redundancy check, CRC)
ðược sử dụng trong mạng chuyển mạch gói
Khi có 1 lỗi ñược phát hiện ở bộ nhận, chúng sẽ
ñược yêu cầu truyền lại.
ARQ (Automatic Repeat-reQuest)
29
Cyclic block codes
Một mã tuyến tính (n,k) ñược gọi là Cyclic
code nếu khi dịch vòng 1codeword thì ñó cũng
là codeword.
Ví dụ:
),...,,,,,...,,(
),...,,,(
121011
)(
1210
−−−+−−
−
=
=
inninin
i
n
uuuuuuu
uuuu
U
U
“i” cyclic shifts of U
UUUUU
U
=====
=
)1101( )1011( )0111( )1110(
)1101(
)4()3()2()1(
30