Bài giảng Cơ sở Lý thuyết Truyền tin - Chương 6: Mã hóa kênh - Hà Quốc Trung

Cơ sở Lý thuyết Truyền tin-2004
Chương 4: Mã hiệu
Hà Quốc Trung1
1Khoa Công nghệ thông tin
Đại học Bách khoa Hà nội
Chương 6: Mã hóa kênh 0. 1/ 45
Chương 6: Mã hóa kênh
1 Khái niệm cơ bản
2 Mã tuyến tính
3 Mã vòng (CRC)
4 Mã chập
Chương 6: Mã hóa kênh 0. 2/ 45
1. Khái niệm cơ bản
1 Khái niệm cơ bản
Giới thiệu
Khoảng cách Hamming
2 Mã tuyến tính
3 Mã vòng (CRC)
4 Mã chập
Chương 6: Mã hóa kênh 1. Khái niệm cơ bản 3/ 45
1.1.Giới thiệu
Định lý Shannon 2 về mã hóa kênh có nhiễu: Nếu thông
lượng kênh lớn hơn tốc độ lập tin của nguồn thì có thể
truyền tin với sai số nhỏ tùy ý.
Định lý chỉ ra với một độ dư dương, sai số truyền tin có thể
nhỏ tùy ý.
Định lý chỉ ra cách thức mã hóa để có sai số đó
Các phương pháp mã hóa này đòi hỏi bảng đối chiếu (từ
điển mã) khổng lồ, kích thước tăng theo hàm mũ của chiều
dài từ mã
Các phương pháp mã hóa thực tế còn cách xa giới hạn của
Shannon (Xem phần mã hiệu)
Chương 6: Mã hóa kênh 1. Khái niệm cơ bản 4/ 45
Nguyên tắc sửa sai và phát hiện sai
Sửa lỗi và phát hiện lỗi phụ thuộc vào tính chất thống kê
của kênh và lỗi
Phân biệt hai loại lỗi
Lỗi độc lập thống kê: các lỗi xuất hiện riêng lẻ, không liên
quan lẫn nhau
Lỗi chùm: lỗi liên quan chặt chẽ với nhau, thường xuất hiện
cùng một lúc (đĩa cứng hỏng)
Cấu trúc của mã kênh phụ thuộc vào phân bố xác suất của
lỗi
Chương 6: Mã hóa kênh 1. Khái niệm cơ bản 5/ 45
Nguyên tắc phát hiện lỗi
Số từ mã nhỏ hơn số các tổ hợp mã có thể
Sử dụng các tổ hợp cấm để phát hiện việc truyền tin sai
Cần lựa chọn các từ mã và các tổ hợp bị cấm để
Hiệu quả: số lượng tổ hợp mã có thể không quá nhiều
Chính xác: đảm bảo sai số luôn sinh ra một tổ hợp cấm
Đảm bảo một từ mã không bị truyền sai thành một từ mã
khác
Khả năng phát hiện lỗi: tỷ lệ có tổ hợp cấm khi có lỗi
Phát hiện lỗi: chuyển đổi từ mã thành tổ hợp cấm L(M-L)
Tổng số lỗi: chuyển đổi một từ mã thành một từ mã bất kỳ
LM
Vậy khả năng phát hiện lỗi là: L(M−L)LM = 1− LM
Để khả năng phát hiện sai lớn, M  L, hay nói cách khác
từ mã phải có độ dài lớn hơn nhiều so với chiều dài tối ưu
Chương 6: Mã hóa kênh 1. Khái niệm cơ bản 6/ 45
Nguyên tắc sửa lỗi
Mục đích sửa sai: đảm bảo sai nhầm tối thiểu
Nguyên tắc: các ký hiệu được ánh xạ vào một từ mã. Từ
mã này do sai số biến đổi sẽ tạo ra các tổ hợp mã bị cấm.
Khi nhận được một tổ hợp mã, xác định tổ hợp mã này
thuộc về tập hợp các tổ hợp mã có thể của một ký hiệu đầu
nào để xác định ký hiệu đầu vào
Cần có điều kiện là lỗi không chuyển một từ mã này sang
tổ hợp mã (lỗi) của một từ mã khác
Chương 6: Mã hóa kênh 1. Khái niệm cơ bản 7/ 45
1.2.Khoảng cách Hamming
Số lượng các bít khác nhau giữa hai tổ hợp mã có cùng độ
dài
Khoảng cách giữa một từ mã và từ mã 0 gọi là trọng số
của một từ mã.
Phản ánh sự "gần" nhau của hai tổ hợp mã khi có nhiễu
Nhiễu biến một từ mã thành một tổ hợp mã cách từ mã một
khoảng nào đó
Nếu khoảng cách đủ nhỏ (số lỗi ít, số lượng các bít bị thay
đổi ít) để tố hợp mã không trùng với từ mã khác, mã hiệu
có khả năng phát hiện lỗi. Khoảng cách giữa các từ mã lớn
hơn số lỗi có thể
Nếu khoảng cách đủ nhỏ, để có thể phân biệt tổ hợp mã
thu được gần từ mã nào nhất, có thể sửa lỗi. Cần đảm bảo
khoảng cách giữa hai từ mã lớn hơn (thực sự) 2 lần số lỗi
có thể
Chương 6: Mã hóa kênh 1. Khái niệm cơ bản 8/ 45
1.2.Khoảng cách Hamming (Tiếp)
Ví dụ: Mã 00,01,10,11 không có khả năng phát hiện lỗi
Mã 0000,0011,1100,1111 có khoảng cách hamming giữa
các từ mã là 2, có thể phát hiện được 1 lỗi
Mã 000000,000111,111000,111111 có khoảng cách
hamming giữa các từ mã là 3, vậy có thể phát hiện 2 lỗi và
sửa một lỗi
Chương 6: Mã hóa kênh 1. Khái niệm cơ bản 9/ 45
1.3.Ví dụ về mã chống nhiễu
Mã lặp
Mã chẵn lẻ
Chương 6: Mã hóa kênh 1. Khái niệm cơ bản 10/ 45
1.4.Phân loại mã chống nhiễu
Mã khối
Mã luồng
Chương 6: Mã hóa kênh 1. Khái niệm cơ bản 11/ 45
1.5.Một số kiến thức toán học cơ bản
Trường
Không gian tuyến tính
Không gian đa thức
Chương 6: Mã hóa kênh 1. Khái niệm cơ bản 12/ 45
2. Mã tuyến tính
1 Khái niệm cơ bản
2 Mã tuyến tính
Định nghĩa, Phương pháp biểu diễn
Nguyên lý giải mã tuyến tính
Các giới hạn lý thuyết của mã tuyến tính
Mã Hamming tuyến tính
3 Mã vòng (CRC)
4 Mã chập
Chương 6: Mã hóa kênh 2. Mã tuyến tính 13/ 45
2.1.Định nghĩa, Phương pháp biểu diễn
Khái niệm: Mã hiệu gọi là tuyến tính nếu tập hợp các từ mã
đóng đối với phép cộng các từ mã
Xét các mã hiệu nhị phân đồng đều
Thực hiện phép tính cộng nhị phân trên mỗi cặp hai từ mã
00100+010111=011011. Phép toán có tính kết hợp và giao
hoán
Khi đó mã hiệu là tuyến tính nếu tổng hai từ mã luôn luôn là
một từ mã
Chương 6: Mã hóa kênh 2. Mã tuyến tính 14/ 45
Biểu diễn bằng ma trận sinh
Xét mã hiệu tuyến tính là một tập N từ mã, có độ dài n.
Luôn có một tập con của mã hiệu để
Tất cả các từ mã đều là tổ hợp tuyến tính của các từ mã
thuộc tập con này
Càc từ mã trong tập con độc lập tuyến tính (không là tổ hợp
tuyến tính của nhau)
Tập từ mã có tính chất như vậy, có độ dài tối thiểu k gọi là
cơ sở của mã hiệu
Có tối đa 2k tổ hợp tuyến tính của k từ mã. Do mã hiệu
đóng với phép cộng, N = 2k
Mã hiệu được đặc trưng bởi ma trận các từ mã cơ sở: ma
trận sinh, có k dòng và n cột. Mã hiệu được ký hiệu (k,n)
Các từ mã của mã hiệu là các tổ hợp tuyến tính của các
dòng trong ma trận sinh
Chương 6: Mã hóa kênh 2. Mã tuyến tính 15/ 45
Biểu diễn bằng ma trận sinh (Tiếp)
Ví dụ mã tuyến tính (5,2) 00000, 01101, 10110,11011 sinh
ra từ ma trận
G =
[
01101
10110
]
hoặc
[
10110
11011
]
hoặc
[
01101
11011
]
Ví dụ mã (5,3):
00000,10011,01010,11001,00101,10110,01111,11100 có
thể được biểu diễn bởi một trong các ma trận sinh
G =
 1001101010
00101
 hoặc
 1001111001
11100

Chương 6: Mã hóa kênh 2. Mã tuyến tính 16/ 45
Ma trận kiểm tra/thử
Có 2n từ mã có chiều dài n. Các từ mã này tạo thành một
mã hiệu tuyến tính, biểu diễn bằng ma trận sinh (n,n)
Mã hiệu tuyến tính N từ mã chỉ sử dụng k cơ sở
Vậy n − k cơ sở còn lại có thể biểu diễn các từ mã trực
giao với cá từ mã của mã hiệu (không gian không của mã
hiệu), có thể dùng để kiểm tra một từ mã có (không) thuộc
mã hiệu ban đầu
Ma trận H của n − k cơ sở gọi là ma trận thử của mã hiệu.
Ma trận thử của một mã hiệu (n,k) là ma trận sinh của một
mã hiệu khác (n,n-k)
Chương 6: Mã hóa kênh 2. Mã tuyến tính 17/ 45
Ma trận kiểm tra/thử (Tiếp)
Mỗi từ mã M trực giao với tất cả các dòng B của ma trận
thử
n∑
1
mibi = 0
Từ đó
MHT = 0
là điều kiện cần và đủ để một chuỗi n ký hiệu là từ mã
Ví dụ (5,3):
00000,10011,01010,11001,00101,10110,01111,11100,
Không gian không gồm các từ mã a1,a2,a3,a4,a5 thỏa
mãn
a1+a4+a5 = 0;a2+a4 = 0;a1+a2+a5 = 0;a3+a5 = 0,a1+a3+a4 = 0; ....
hay
a1 + x + y = 0;a2 = a4 = x ;a3 = a5 = y
Chương 6: Mã hóa kênh 2. Mã tuyến tính 18/ 45
Ma trận kiểm tra/thử (Tiếp)
Vậy không gian không gồm 4 từ mã
00000,11010,10101,01111
Ma trận thử sẽ là[
11010
10101
] [
01111
10101
] [
11010
01111
]
Có thể kiểm tra được điều kiện trực giao
Chương 6: Mã hóa kênh 2. Mã tuyến tính 19/ 45
Dạng chuẩn tắc của mã tuyến tính
Trong các phép tính cộng giữa các từ mã, vị trí các bít
không có vai trò quan trọng. Có thể hoán vị các bít cho
nhau
Khi hoán vị các bit và thực hiện các phép biến đổi hợp lệ
với một ma trận sinh, có thể chuyển ma trận sinh về dạng
G′′ =
∣∣∣∣∣∣∣∣
10 . . .0p11p12 . . .p1n−k
01 . . .0p11p12 . . .p2n−k
. . .
00 . . .1p11p12 . . .pkn−k
∣∣∣∣∣∣∣∣
Một từ mã bất kỳ sẽ là tổ hợp tuyến tính của các hàng
trong ma trận sinh, với các hệ số nhị phân tùy ý
v = (a1,a2 . . . ,ak) sẽ có dạng
M = vG′′ = (a1,a2 . . . ,ak ,C1,C2, . . .Cn−k)
trong đó Cj =
∑k
1 aipij
Chương 6: Mã hóa kênh 2. Mã tuyến tính 20/ 45
Dạng chuẩn tắc của mã tuyến tính (Tiếp)
v = (a1,a2 . . . ,ak) được chọn một cách tùy ý, chính là
phần thông tin của một từ mã
Một từ mã trong mã hóa kênh sẽ gồm phần thông tin, và
một phần thông tin điều khiển, được tính bằng một tổ hợp
tuyến tính của phần thông tin thực sự
Ma trận sinh sẽ có dạng (Ik ,Pn−k), Ik là ma trận đơn vị
Nguyên tắc phát hiện lỗi: sau khi nhận được từ mã, tính lại
phần thông tin điều khiển rồi so sánh với kết quả nhận
được
Nguyên tắc sửa lỗi: xác định các khả năng có thể của từ
mã đã truyền đi rồi chọn từ mã thích hợp
Vấn đề lý thuyết: khối lượng thông tin điều khiển đủ đề phát
hiện một số lỗi xác định.
Lỗi có thể là lỗi đơn hoặc lỗi chùm
Chương 6: Mã hóa kênh 2. Mã tuyến tính 21/ 45
2.2.Nguyên lý giải mã tuyến tính
Bài toán phát hiện và sửa lỗi
Nhận được một chuỗi ký hiệu có độ dài n
Kiểm tra liệu chuỗi ký hiệu này có là một từ mã hay không
Nếu có, xác định vị trí lỗi
Công cụ: ma trận sinh, ma trận thử
với một từ mã M, có M .HT = 0
Vậy nếu M .HT 6= 0, đã có lỗi xảy ra: bài toán phát hiện lỗi
M .HT gọi là syndrom của chuỗi bít, được sử dụng để phát
hiện lỗi
Chương 6: Mã hóa kênh 2. Mã tuyến tính 22/ 45
Bảng lớp kề và sửa lỗi
Khi có lỗi xảy ra, một vài bít nào đó bị đổi vị trí. Một chuỗi
bít được nhận, sai khác với từ mã ban đầu 1 vài bít, biểu
diễn bằng vector sai số bằng hiệu của chuỗi bít thu được
và từ mã ban đầu
Lập bảng lớp kề của các từ mã. Các cột tương ứng với các
từ mã. Các hàng tương ứng với các vector lỗi có thể. Mỗi
hàng tạo ra một lớp kề của các từ mã tương ứng với các
vector lỗi
Việc xác định các vị trí lỗi chuyển thành việc xác định lớp
kề của chuỗi bít nhận được. Dễ thấy nhất là so sánh trong
bảng xem chuỗi bít lỗi nằm ở lớp kề nào.
Giá trị của syndrom thay đổi chỉ phụ thuộc vào vị trí của bít
lỗi. Vậy các chuỗi bít trong một hàng có syndrom giống
nhau.
Chương 6: Mã hóa kênh 2. Mã tuyến tính 23/ 45
Bảng lớp kề và sửa lỗi (Tiếp)
Ngược lại, Khi lập mã hiệu, cần đảm bảo với các vector lỗi
có thể, hai vector khác nhau cho hai lớp kề khác nhau, 2
syndrom khác nhau
Vậy có thể xác định vector lỗi bằng cách tính syndrom của
chuỗi bít và xác định lớp kề có syndrom đó.
Chương 6: Mã hóa kênh 2. Mã tuyến tính 24/ 45
Ví dụ
Cho mã hiệu 00000,00111,11001,11110
00000
00111
11001
11110
Ma trận sinh
11001
11110
Ma trận thử
00110
01011
10011
Bảng lớp kề cho một lỗi và một vài lỗi đúp
00000 00111 11001 11110 syndrom
00001 00000 00111 11001 11110 011
00010 00010 00101 11011 11100 111
00100 00100 00011 11101 11010 100
01000 01000 01111 10001 10110 010
10000 10000 10111 01001 01110 001
01100 01100 01011 10101 10010 110
11000 11000 11111 00001 00110 101
Các bộ 2 lỗi khác sẽ rơi vào các syndrom đã dùng
Vậy mã hiệu này sửa được 1 lỗi đơn và hai cấu hình lỗi kép
Chương 6: Mã hóa kênh 2. Mã tuyến tính 25/ 45
2.3.Các giới hạn lý thuyết của mã tuyến tính
Đánh giá bằng số ký hiệu tối đa có thể sửa (phát hiện)
được k
Sử dụng trọng số Hamming, quãng cách tối thiểu d giữa
các từ mã bằng với trọng số tối thiểu của từ mã
Để phát hiện lỗi k < d . Để sửa lỗi 2k < d
Giới hạn trên của d
d ≤ n.m
k−1(m − 1)
mk − 1
trong truờng hợp nhị phân
d ≤ n.2
k−1
2k − 1
Số bít cần dùng thêm để sửa một lỗi
mk(n + 1) ≤ mn
r + k + 1 ≤ mr
Chương 6: Mã hóa kênh 2. Mã tuyến tính 26/ 45
2.4.Mã Hamming tuyến tính
Nguyên tắc
Dùng mã có chiều dài 2r − 1, trong đó r bít sử dụng làm
thông tin điều khiển
Mã trận thử sẽ có kích thước (2r − 1)xr . Ma trận này không
có hai cột nào trùng nhau, do đó tổng hai cột bất kỳ luôn
luôn khác 0. Vậy tối thiểu 3 cột cộng lại mới có thể có cột 0
Điều kiện để v = (a1,a2 . . .an) là một từ mã:
n∑
1
aihij = 0∀j
tối thiểu 3 hệ số ai 6= 0 . Vậy trọng số tối thiểu của mã là 3,
quãng cách tối thiểu là 3, mã sửa được 1 lỗi
Chương 6: Mã hóa kênh 2. Mã tuyến tính 27/ 45
2.4.Mã Hamming tuyến tính (Tiếp)
Xét từ mã v khi chuyển đi bị sai một bít thành u = v + e.
Tính syndrom
uHT = (v + e)HT = eHT
chính là hàng của H tương ứng với vị trí của lỗi. Có 2r − 1
hàng, mỗi hàng có r ký hiệu Vậy có thể chọn H sao cho r ký
hiệu chính là số thứ tự của hàng
Chương 6: Mã hóa kênh 2. Mã tuyến tính 28/ 45
Ví dụ
Mã Hamming (7,4). Độ dài từ mã 7, số ký hiệu điều khiển
3, số ký hiệu thông tin 4. Ma trận thử có các cột là số thứ
tự của cột  0 0 0 1 1 1 10 1 1 0 0 1 1
1 0 1 0 1 0 1

Để quá trình mã hóa đơn giản chọn các ký hiệu điều khiển
ở vị trí 1, 2, 4; Các từ mã sẽ có dạng
v = (x , y ,a3, z,a5,a6,a7)
Các ký hiệu thử được tính theo vHT = 0
z + a5 + a6 + a7 = 0⇒ z = a5 + a6 + a7
y + a3 + a6 + a7 = 0⇒ y = a3 + a6 + a7
x + a3 + a5 + a7 = 0⇒ x = a3 + a5 + a7
Từ công thức trên có thể lập ra bảng các từ mã
Phát hiện lỗi đơn giản: giá trị của 3 bít điều khiển là vị trí
lỗi, nếu là 0,1,2, 4 không có lỗiChương 6: Mã hóa kênh 2. Mã tuyến tính 29/ 45
Mã Hamming sửa lỗi chùm
Lỗi chùm: một chuỗi bít liên tiếp bị lỗi
Giải quyết bằng mã hamming?
Chương 6: Mã hóa kênh 2. Mã tuyến tính 30/ 45
3. Mã vòng (CRC)
1 Khái niệm cơ bản
2 Mã tuyến tính
3 Mã vòng (CRC)
Khái niệm
Tính chất
Mã hóa
Giải mã
4 Mã chập
Chương 6: Mã hóa kênh 3. Mã vòng (CRC) 31/ 45
3.1.Khái niệm
Là mã tuyến tính, thường dùng để phát hiện lỗi
Tất cả các hoán vị của một từ mã là một từ mã
a1,a2, . . .an là từ mã thì an,a1,a2 . . .an−1 cũng là từ mã
Dựa vào tính chất vòng, sẽ biểu diễn mã vòng bằng một từ
mã+một mã gốc.
Biểu diễn mã vòng: đa thức
an−1xn−1 + an−2xn−2 + . . .+ a1x + a0
Tuyến tính định nghĩa trên phép cộng và phép nhân đa
thức
Phép cộng đa thức: phép cộng đa thức thông thường định
nghĩa trên trường hữu hạn các ký hiệu (modulo m)
Phép nhân đa thức: nhân 2 đa thức có bậc tối đa n-1, được
một đa thức có bậc tối đa 2n − 2. Chia đa thức này cho
xn − 1 rồi lấy phần dư làm kết quả
Chương 6: Mã hóa kênh 3. Mã vòng (CRC) 32/ 45
3.1.Khái niệm (Tiếp)
Định nghĩa phép cộng và nhân như trên để đảm bảo tính
đóng của hai phép tính trong tập hợp các từ mã có độ dài n,
tạo thành từ một bảng chữ cái có m ký hiệu
Xét từ mã a1,a2, . . .an biểu diễn bằng đa thức
a1xn−1 + a2xn−2 + . . .+ an
Nhân đa thức với đa thức x được
a1xn + a2xn−1 + . . .+ anx
Chia cho xn − 1
a1(xn − 1) + a1 + a2xn−1 + . . .+ anx
a2xn−1 + . . .+ anx + a1
chính là đa thức của từ mã a2, . . .an,a1
Vậy phép nhân với x là phép dịch từ mã một ký hiệu
Chương 6: Mã hóa kênh 3. Mã vòng (CRC) 33/ 45
3.1.Khái niệm (Tiếp)
Lần lượt nhân từ mã với x2, x3, . . . , xk−1 có k từ mã
Theo tính chất tuyến tính, có thể tổ hợp các từ mã này tạo
ra mã hiệu (n,k) có 2k từ mã, tuyến tính. Ngược lại?
Tất cả các từ mã của một mã vòng đều chia hết cho một
đa thức
Chương 6: Mã hóa kênh 3. Mã vòng (CRC) 34/ 45
3.2.Tính chất
1 Nếu M(x) là một từ mã, P(x) là một đa thức bậc tối đa
n − 1, thì M(x)P(x) cũng là một từ mã
2 Nếu một mã vòng (n,k), G(x) là một từ mã khác không biểu
diễn bởi đa thức có bậc nhỏ nhất thì:
Bậc của G là n-k
Tất cả các từ mã là kết quả của phép nhân G(x) với một đa
thức bậc k
Tất cả các từ mã bậc n-k là G(x) nhân với một hằng số
Ký hiệu đầu tiên của G khác không
Đa thức G(x) gọi là đa thức sinh của mã hiệu
Chương 6: Mã hóa kênh 3. Mã vòng (CRC) 35/ 45
3.2.Tính chất (Tiếp)
3 Nếu C là một mã vòng với đa thức sinh
G(x) = a1 + a2x + . . .+ an−k+1X n−k thì ma trận k × n sau
là ma trận sinh của mã hiệu
a1 a2 . . . an−k+1 0 0 0 . . . 0
0 a1 a2 . . . an−k+1 0 0 . . . 0
0 0 a1 a2 . . . an−k+1 0 . . . 0
. . . . . . . . . . . . . . . . . . . . . . . . . . .
0 0 0 . . . 0 a1 a2 . . . an−k+1

4 Điều kiện cần và đủ để một đa thức G(x) có thể sinh ra
một mã hiệu là tồn tại một đa thức bậc k H(x) sao cho
G(X )H(X ) = 0
Có nghĩa là G(X ) phải là thừa số của Dn − 1. H(X) còn gọi
là đa thức kiểm tra của mã hiệu.
Chương 6: Mã hóa kênh 3. Mã vòng (CRC) 36/ 45
3.2.Tính chất (Tiếp)
5 Điều kiện cần và đủ để một tổ hợp mã P(x) là từ mã
P(X )H(X ) = 0
Chương 6: Mã hóa kênh 3. Mã vòng (CRC) 37/ 45
3.3.Mã hóa
Theo phương pháp mã tuyến tính nếu các ký hiệu mang
thông tin tạo thành tổ hợp s(k ký hiệu), từ mã tương ứng sẽ
được tạo ra bằng cách M = sG ⇔ M(x) = sG(x)
Sử dụng đại số đa thức
Nếu s(x) là thông tin cần chuyển, chọn tổ hợp mã M(x) sao
cho
M(x) = xn−ks(x)− r(x)
Trong đó r(x) là số dư của phép chia xn−ks(x) cho đa thức
sinh p(x)
xn−ks(x) = p(x)q(x) + r(x)
M(x) có đúng n ký hiệu
k ký hiệu đầu là của s(x), vì r(x) có bậc tối đa n-k
M(x) là từ mã vì
M(x) = xn−ks(x)−r(x) = p(x)q(x)+r(x)−r(x) = p(x)q(x)
Chương 6: Mã hóa kênh 3. Mã vòng (CRC) 38/ 45
3.4.Giải mã
Nếu không có lỗi
Phát hiện lỗi: căn cứ vào số dư của đa thức thu được: đa
thức syndrom
Sửa lỗi (nhị phân):
lập ra các lớp kề
tính syndrom cho mỗi lớp kề
Căn cứ vào syndrom thu được để phát hiện vị trí lỗi
Các đa thức hay sử dụng
Hamming
Golay
Parity Check
Sửa lỗi / phát hiện và truyền lại
Chương 6: Mã hóa kênh 3. Mã vòng (CRC) 39/ 45
4. Mã chập
1 Khái niệm cơ bản
2 Mã tuyến tính
3 Mã vòng (CRC)
4 Mã chập
Khái niệm
Mã hóa
Biểu diễn
Giải mã
Chương 6: Mã hóa kênh 4. Mã chập 40/ 45
4.1.Khái niệm
Trường hợp sử dụng
Nếu kênh có hệ số nhiễu nhỏ: Sử dụng nhiều ký hiệu,
nhiều mức tín hiệu, xử lý tức khắc từng ký hiệu
Nếu kênh có hệ số nhiễu lớn: dùng càng ít ký hiệu càng tốt,
xử lí một khối các ký hiệu nhận được, dùng tất cả các thông
tin của đầu ra kênh tin, sử dụng các tiêu chuẩn thống kê
Phép toán chập: Nhiều ký hiệu của nguồn đầu vào được
đưa tuần tự vào các bộ biến đổi. Kết quả của các phép
biến đổi được tổng hợp lại thành đầu ra
Mã chập biến đổi các ký hiệu nguồn thành các ký hiệu đầu
ra sử dụng một bộ nhớ
Khác với các phương pháp mã hóa đã học, mã chập mã
hóa một số lượng tùy ý các ký hiệu cùng một lúc
Chương 6: Mã hóa kênh 4. Mã chập 41/ 45
4.1.Khái niệm (Tiếp)
Tốc độ lập tin đầu ra của mã chập nhỏ hơn tốc độ lập tin
đầu vào: 1/R
Chương 6: Mã hóa kênh 4. Mã chập 42/ 45
4.2.Mã hóa
Nguyên tắc
Sử dụng một thanh ghi dịch để lưu trữ các ký hiệu đầu vào
Sử dụng các mạch logic để tính toán các ký hiệu đầu ra
Sử dụng bộ dồn kênh để xếp các ký hiệu đầu ra vào một
chuỗi tuần tự
Chương 6: Mã hóa kênh 4. Mã chập 43/ 45
Bằng đa thức
Lấy D là biến của các đa thức, phép nhân đa thức với D
biểu diễn phép dịch sang phải một ô, một ký hiệu, thì
s(D) = s0 + s1D + s2D2 + . . .+ skDk + . . .
x i(D) = x i0 + x i1D + x i2D2 + . . .+ x ikDk + . . .
Chương 6: Mã hóa kênh 4. Mã chập 44/ 45
Bằng đa thức (Tiếp)
Biểu diễn theo đặc trưng xung của từng modul: đầu ra
hi(D) tương ứng với đầu vào 10000 . . .000 . . .
xi(D) = hi(D)s()D
Trong ví dụ trên
h1(D) = 1+ D2,h2(D) = 1+ D + D2
Các trạng thái của bộ mã hóa
e1(D) = Ds(D)
e2(D) = De1(D) = D2s(Ds)
x1(D) = (1+ D2)s(D)
x2(D) = (1+ D + D2)s(D)
Chú ý: giới hạn của mã chập: số trạng thái là hàm mũ của
số ô nhớ
Chương 6: Mã hóa kênh 4. Mã chập 45/ 45
Biểu diễn bằng đồ thị (Trellis)
Thiết bị mã hóa là một thiết bị có nhớ: Biểu diễn đồ thị
thích hợp
Trục tung: các trạng thái có thể
Trục hoành: các mốc thời gian
Các liên kết giữa các điểm: chuyển đổi trạng thái của hệ
thống tương ứng với các ký hiệu và các trạng thái tương
ứng
Các thông tin bổ sung: các ký hiệu đầu ra
Chương 6: Mã hóa kênh 4. Mã chập 46/ 45
4.4.Giải mã
Xét nguồn không nhớ và kênh không nhớ. Giả sử dữ liệu
truyền đi là XN , dữ liệu nhận được là YN . Cần tìm một
chuỗi X̂N sao cho xác suất lỗi tối thiểu (P(XN 6= X̂N) tối
thiểu), tức là
P(X̂N |YN) ≥ P(XN |YN)∀XN
, tức là
P(YN |XN)P(XN)
cực đại Với điều kiện nguồn không nhớ, P(XN) = const ,
P(YN |XN) =∏N1 P(YNi |XNi ) Vậy cần tìm giá trị tối thiểu
của
∑N
1 − logP(YNi |XNi )
Bài toán giải mã tối ưu chuyển về bài toán tìm đường đi
ngắn nhất trong Trellis, với các trọng số của đường đi là
− logP(YNi |XNi )
Chương 6: Mã hóa kênh 4. Mã chập 47/ 45
Thuật toán Viterby
Bài toán tìm đường ngắn nhất trong đồ thị
Độ phức tạp NP
chỉ có các lời giải gần đúng
Đặc biệt: Trellis. VD 1000 ký hiệu
Dựa trên cơ sở khẳng định
Trong một treliss, nếu Ek+1 là đường đi tối ưu thì Ek là
đường đi tối ưu
Giải thuật Viterby giảm độ phức tạp xuống còn tuyến tính
Chương 6: Mã hóa kênh 4. Mã chập 48/ 45