CHƯƠNG 5
Mã hóa kênh truyền
1
 Khái niệm về mã phát hiện sai và sửa sai.
– Cơ chế phát hiện sai của mã hiệu.
– Khả năng phát hiện và sửa sai.
– Hệ số sai không phát hiện được.
 Mã khối tuyến tính
– Định nghĩa
– Ma trận kiểm tra
– Mạch mã hóa
– Giải mã
– Syndrome và sự phát hiện lỗi
– Sửa lỗi
Nội dung
2
Vấn đề
3
Lỗi khi truyền dữ liệu trên một hệ thống truyền tin:
• Lỗi khi truyền tin là một điều khó tránh.
• Nguyên nhân: Do nhiễu bên ngoài xâm nhập, tác động
lên kênh truyền, làm thông tin truyền đi bị sai.
1 → 0
0 → 1
• Việc khắc phục và kiểm soát lỗi là một vấn đề hết sức
quan trọng.
Nguyên lý mã hóa kiểm soát lỗi
4
• Nguyên lý chung là thêm vào tập mã cần truyền một tập bit
kiểm tra nào đó để bên nhận có thể kiểm soát lỗi.
• Bên phát: Bổ sung thêm thông tin (thêm bit) vào bit cần gửi.

0
= 2
n
 Số từ mã mang tin: N = 2
k
.
 Số từ mã không dùng đến: 2
n
–2
k
(số tổ hợp cấm)
 Để mạch có thể phát hiện hết i lỗi thì phải thỏa mãn điều kiện:
 Trong đó E
Σ
= E
1
+ E
2
+ . . . + E
i
 E
1
, E
2
, . . E
i
là tập hợp các vector sai 1,2 . . .i lỗi.
 Để phát hiện và sửa hết sai 1 lỗi ta có:
6
Cơ chế phát hiện sai của mã hiệu.

, t
2
) được định nghĩa là số các thành
phần khác nhau giữa chúng.
 Ví dụ: t
2
= 0 1 0 0 0 1 1  d(t
1
, t
2
) = 3 chúng khác nhau ở vị trí 0, 1 và 3
 Khoảng cách Hamming giữa 2 vector mã t
1
, t
2
= trọng số của vector tổng t
1
 t
2
:
d(t
1
, t
2
)=w(t
1
 t
2
) .
t

định được hệ số sai không phát hiện được:
p’ = C
2
1
pqC
3
1
pq
2
+ C
2
2
p
2
C
3
2
p
2
q
nếu p = 10
-3
 p’  6p
2
= 6.10
-6
nghĩa là có 10
6
bit truyền đi,
10

• Cơ chế FEC (Forward Error Control): phát hiện và tự sửa sai sử dụng các
loại mã sửa lỗi.
 Khi có sai đơn (1 sai) người ta thường dùng các loại mã như: mã khối tuyến
tính, mã Hamming, mã vòng…
 Khi có sai chùm (> 2 sai) người ta thường dùng các loại mã như: mã BCH, mã
tích chập, mã Trellis, mã Tubor, mã Tubor Block, mã tổng hợp GC…
11
Vector sai – cô cheá söûa loãi
Mã khối tuyến tính
12
• Mã khối tuyến tính được xây dựng dựa trên các kết quả của đại số tuyến
tính là một lớp mã được dùng rất phổ biến trong việc chống nhiễu.
• Định nghĩa:
• Một mã khối có chiều dài n, k bit gồm 2
k
từ mã tuyến tính C(n,k) nếu
và chỉ nếu 2
k
từ mã hình thành một không gian vectơ k chiều 2
n
, gồm
tất cả các vectơ n thành phần trên trường Galois sơ cấp GF(2) ( bao
gồm 2 phần tử {0,1} với 2 phép tính + và *).
• Mã tuyến tính C(n,k) có mục đích mã hóa những khối tin (hay thông
báo) k bit thành những từ mã n bit. Hay nói cách khác trong n bit của
từ mã có chứa k bit thông tin.
• Ví dụ: C (7,4): Từ mã dài 7 bit. Thông tin cần truyền: 4 bit.
Cách biểu diễn mã – Ma trận sinh
13
• Mã tuyến tính C(n,k) là một không gian k chiều của không gian vectơ n

gagagaw
i
kk




























Cách mã hóa
14
• Nếu u = (a
0
,a
1
,…,a
k-1
) , với a
i
=0/1 và 0i k-1, là thơng tin
cần được mã hóa.
• Gọi t là từ mã phát đi: t = t
0
t
1
….t
n-1
, Với t
j
= 0
hoặc 1 và 0  j  k-1 thì từ mã w tương ứng với t được
hình thành bằng cách lấy t x G
w = t x G = a
0
g
0
+ a
1
g

.1 + u
3
.1 = u
0
+ u
2
+ u
3
= 1 + 0 +1 = 0
t
1
= u
0
.1 + u
1
.1 + u
2
.1 + u
3
.0 = u
0
+ u
1
+ u
2
= 1+ 1 +0 = 0
t
2
= u
0

.0 + u
1
.1 + u
2
.0 + u
3
.0 = u
1
= 1
t
5
= u
0
.0 + u
1
.0 + u
2
.1 + u
3
.0 = u
2
= 0
t
6
= u
0
.0 + u
1
.0 + u
2


1
1
0
0
0
1
0
0
0
0
1
0
0
0
1
1
1
0
1
0
0
1
0
1
1
0
1
1
g

• Mỗi ma trận sinh tương ứng với một cách mã hóa khác nhau.
16
Ma trận sinh
Cách giải mã
17
• Từ ma trận sinh ở ví dụ trước, gọi: u = (a
0
, a
1
, a
2
, a
3
) là thông
tin, w = (b
0
, b
1
, b
2
, b
3
, b
4
, b
5
, b
6
) là từ mã tương ứng.
• Ta có hệ phương trình liên hệ giữa u và w

b
4
= a
1
(5)
b
5
= a
2
(6)
b
6
= a
2
+ a
3
(7)














1
0
1
0
0
1
0
1
1
0
1
1
4
3
1
0
74
g
g
g
g
G
Cách giải mã (tt)
18
• Chọn bốn phương trình đơn giản nhất để giải các a
i
theo các b
1
• Chọn các phương trình (4), (5), (6), (7) ta giải được:
a




















1
1
0
0
0
1
0
0
0
0
1

có một trong hai dạng sau:
• Dạng 1: Từ mã bao gồm phần thông tin k bit đi trước và phần còn lại (gồm
n-k bit) đi sau (phần này còn được gọi là phần dư thừa hay phần kiểm tra)
• Dạng 2: Ngược lại của dạng 1, từ mã bao gồm phần kiểm tra đi trước và
phần thông tin đi sau.
.
k bit thông tin n - k bit kiểm tra
n - k bit kiểm tra k bit thông tin
Ma trận sinh hệ thống
20
• Ví dụ:














1
1
1
0
0

w = 0110100 → u = 0110
 


























  


knk
knk
kn
kk
kk
knkkknk
P
P
P
P
P
P
P
P
P
PIG
kn
xét mã khối tuyến tính C(7,4)có thông báo cần mã hóa
u = (u
0
, u
1
, u
2
, u
3
) & từ mã phát đi tương ứng
t = (t
0
, t

3’=1+3
4’=1+2+4
)7,4(
~
G
21
Cho tin cần phát đi: u = (u
0
, u
1
, u
2
, u
3
) = (1 0 1 1) ta tìm từ
mã phát đi theo 2 công thức 5 & 8 từ đó rút ra nhận xét
Ví dụ
(u
0
, u
1
, u
2
, u
3
)
1 1 0 1 0 0 0
0 1 1 0 1 0 0
1 1 1 0 0 1 0
1 0 1 0 0 0 1

1
= 1+0 = 1
t
2
= u
0
.0 + u
1
.1 + u
2
.1 + u
3
.0 = u
1
+ u
2
= 0+1 = 1
t
3
= u
0
.1 + u
1
.0 + u
2
.1 + u
3
.1 = u
0
+ u

2
= 1
t
6
= u
0
.0 + u
1
.0 + u
2
.0 + u
3
.1 = u
3
= 1
Vậy ta có từ mã phát đi t = (1 1 1 1 1 1 1) không có dạng mã khối
tuyến tính
22
(u
0
, u
1
, u
2
, u
3
)
1 1 0 1 0 0 0
0 1 1 0 1 0 0
1 1 1 0 0 1 0

.1 + u
3
.0 = u
0
+ u
1
+ u
2
= 1+ 0 + 1 = 0
t
2
= u
0
.0 + u
1
.1 + u
2
.1 + u
3
.1 = u
1
+ u
2
+ u
3
= 0+1+ 1 = 0
t
3
= u
0

.1 + u
3
.0 = u
2
= 1
t
6
= u
0
.0 + u
1
.0 + u
2
.0 + u
3
.1 = u
3
= 1
Vậy ta có từ mã phát đi: ( 1 0 0 1 0 1 1) có dạng mã khối tuyến tính
23
Ví dụ
24
• Dùng các phép biến đổi sơ cấp biển đổi các ma trận sinh
sau thành ma trận sinh hệ thống.
• Không phải mọi ma trận sinh đều có thể biến đổi thành ma
trận sinh hệ thống.





0
0
0
1
1
1
1
1
74
G














1
1
1
1
1
0

• → Nguyên lý khoảng cách Hamming tối thiểu.
 Không gian bù trực giao:
• Cho S là một không gian k chiều của không gian V n chiều. Gọi S
d
là tập
tất cả các vectơ v trong V sao cho:
• S
d
được chứng minh là một không gian con của V và có số chiều là n-k.
• S
d
được gọi là không gian bù trừ trực giao của S và ngược lại.
0,




vuSu