Mã chẵn lẻ
• Mã chẵn lẻ ban đầu được xây dựng rất đơn giản
• Cho trước bộ mã gồm các từ mã n bit nhị phân.
Một bit chẵn lẻ được thêm vào mỗi từ mã sao
9/30/2010
2
Huỳnh Văn Kha
tổng số bit một mỗi từ mã là chẵn (hoặc lẻ)
• Ví dụ bộ mã ban đầu là {00, 01, 10, 11}, thì bộ mã
chẵn lẻ thu được là {000, 011, 101, 110}
• Dễ dàng thấy rằng mọi sự truyền sai e bit, với e lẻ,
đều phát hiện được
• Gọi r1, r2, , rn là các bit của một từ mã, số bit 1
là chẵn được viết là r1 + r2 + + rn = 0 modulo 2
28 trang |
Chia sẻ: phuongt97 | Lượt xem: 756 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Lý thuyết thông tin - Chương 4: Mã sửa sai (Phần 2), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 4: Mã sửa sai
4.2 Ứng dụng lý thuyết nhóm cho
mã kiểm tra chẵn lẻ
Mã chẵn lẻ
• Mã chẵn lẻ ban đầu được xây dựng rất đơn giản
• Cho trước bộmã gồm các từmã n bit nhị phân.
Một bit chẵn lẻ được thêm vào mỗi từmã sao
9/30/2010
2
Huỳnh Văn Kha
tổng số bit một mỗi từmã là chẵn (hoặc lẻ)
• Ví dụ bộmã ban đầu là {00, 01, 10, 11}, thì bộmã
chẵn lẻ thu được là {000, 011, 101, 110}
• Dễ dàng thấy rằng mọi sự truyền sai e bit, với e lẻ,
đều phát hiện được
• Gọi r1, r2, , rn là các bit của một từmã, số bit 1
là chẵn được viết là r1 + r2 + + rn = 0modulo 2
ðịnh nghĩa (mã chẵn lẻ)
Cho hệ phương trình tuyến tính
9/30/2010
3
Huỳnh Văn Kha
Tập nghiệm của hệ trên gọi là một bộmã kiểm tra
chẵn lẻ (hay bộmã nhóm)
Chú ý:
Các aij, ri là các số 0, 1. Phép cộng, nhân theo
modulo 2 được định nghĩa như sau:
0 + 0 = 1 + 1 = 0; 0 + 1 = 1 + 0 = 1;
1.1 = 1; 1.0 = 0.1 = 0.0 = 0
Ma trận chẵn lẻ
• Ma trận A = [aij] gọi là ma trận kiểm tra chẵn lẻ
• Nếu A có hạng t và các cột j1, , jt là độc lập tuyến
tính thì có n – t = k các rj (j ≠ j1, , jt) có thể được
9/30/2010
4
Huỳnh Văn Kha
chọn tùy ý, và ta gọi là các bit thông tin
• Các bit thứ j1, , jt gọi là các bit kiểm tra
• Mỗi khi cho giá trị của các bit thông tin ta được
một từmã duy nhất
• Bộmã kiểm tra chẵn lẻ có 2k từmã
Ví dụ 1
• Cho hệ sau
9/30/2010
5
Huỳnh Văn Kha
• Có thể chọn r1, r2, r3 làm bit kiểm tra và r4, r5, r6
làm bit thông tin
• Cho r4 = 0, r5 = 1, r6 = 0. Ta được r1 = 1, r3 = 1, r2
= 1. Và từmã thu được là 111010
• Cho các giá trị khác cho r4, r5, r6 ta được 23 = 8 từ
mã. Toàn bộ từmã được cho trong bảng sau
Bộ mã kiểm tra chẵn lẻ trong vd1
r1 r2 r3 r4 r5 r6
w1 0 0 0 0 0 0
w2 0 0 1 0 0 1
9/30/2010
6
Huỳnh Văn Kha
w3 1 1 1 0 1 0
w4 1 1 0 0 1 1
w5 1 1 0 1 0 0
w6 1 1 1 1 0 1
w7 0 1 1 1 1 0
w8 0 0 0 1 1 1
Vector hiệu chỉnh
• Giả sử dãy bit r1, r2, , rn được truyền qua kênh nhị
phân đối xứng, dãy nhận được là r1’, r2’, , rn’
• Ta tính
9/30/2010
7
Huỳnh Văn Kha
• Và gọi vector cột c = (c1, c2, , cm)T là vector hiệu
chỉnh ứng với dãy v = (r1’, r2’, , rm’)
• Dưới dạng ma trận là c = AvT
• Chú ý vT là ký hiệu cho chuyển vị của v
Mẫu sai
• Giả sửw = (r1, r2, , rn) được truyền và dãy nhận
được là v = (r1’, r2’, , rn’)
• Dãy z = v –w = (r1’ – r1, r2’ – r2, , rn’ – rn) gọi
9/30/2010
8
Huỳnh Văn Kha
là mẫu sai của w và v
• Vector hiệu chỉnh của v là
c = A(zT + wT) = AzT + AwT = AzT
• Nếu z có giá trị 1 tại các bit thứ j1, j2, , je và 0 tại
các bit còn lại thì vector AzT là tổng các cột thứ j1,
j2, , je của A
Nhóm (Group)
Một nhóm là một tập hợp G trên đó có xác định
phép toán gọi là phép “cộng” thỏa mãn tính chất
1. a, b thuộc G thì a + b cũng thuộc G
9/30/2010
9
Huỳnh Văn Kha
2. (a + b) + c = a + (b + c) với mọi a, b, c trong G
3. Có phần tử 0 trong G sao cho a + 0 = 0 + a = a
với mọi a trong G
4. Với mỗi a trong G có phần tử -a trong G sao
cho a + (-a) = (-a) + a = 0
Nhóm G gọi là giao hoán nếu a + b = b + a, với mọi
a, b trong G
Nhóm và mã kiểm tra chẵn lẻ
• Gọi Bn là tập các dãy nhị phân chiều dài n với
phép cộng là cộng từng bit một theo mod 2. Thì
Bn là một nhóm
9/30/2010
10
Huỳnh Văn Kha
• Dễ dàng kiểm tra được rằng nếu S là bộmã kiểm
tra chẵn lẻ thì S là một nhóm, và gọi là nhóm con
của Bn
• Thật vậy, nếu w1, w2 là các từmã thì
A(w1 + w2)
T = Aw1
T + Aw2
T = 0
• Các tính chất khác được suy ra từ định nghĩa
phép cộng theo mod 2
ðịnh lý 4.4
Cho S là nhóm con của Bn. Thì S là một bộmã
kiểm tra chẵn lẻ, nghĩa là tồn tại ma trận kiểm tra
chẵn lẻ A sao cho các tập các từmã xác định bởi
9/30/2010
11
Huỳnh Văn Kha
A là S.
Như vậy một bộmã kiểm tra chẵn lẻ có thể đồng
nhất với một nhóm con của Bn
Chứng minh ñịnh lý 4.4
• Sắp các từmã thành ma trận M gồm s hàng, n
cột. Trong đó s là số từmã. Ví dụ:
9/30/2010Huỳnh Văn Kha
12
r1 r2 r3 r4 r5 r6
w0 0 0 0 0 0 0
w1 1 0 1 0 0 1
w2 1 1 0 0 1 0
w3 0 1 0 1 0 1
w4 0 1 1 0 1 1
w5 1 1 1 1 0 0
w6 1 0 0 1 1 1
w7 0 0 1 1 1 0
Chứng minh ñịnh lý 4.4
• Gọi k là hạng của M và m = n – k. Thì k chính là
số hàng tối đa độc lập tuyến tính, cũng là số cột
tối đa độc lập tuyến tính
9/30/2010Huỳnh Văn Kha
13
• Giả sử k hàng đó là w1, w2, , wk. Thì tất cả các
các từmã trong S có thể viết dưới dạng
• Ngược lại mỗi từmã có dạng trên đều thuộc S (do
S là nhóm)
• Mà các wi (i từ 1 đến k) độc lập tuyến tính. Vậy S
có 2k từmã
Chứng minh ñịnh lý 4.4
• Giả sử k cột cuối là độc lập tuyến tính. Khi đó m
cột đầu có thể viết dưới dạng tổ hợp tuyến tính
của k cột cuối
9/30/2010Huỳnh Văn Kha
14
• Hay
Chứng minh ñịnh lý 4.4
• Như vậy mọi từmã đều thỏa AwT = 0
• Mặc khác, do tập nghiệm của AwT = 0 có 2k phần
9/30/2010Huỳnh Văn Kha
15
tử nên tập nghiệm của AwT = 0 chính là S
• Đây là điều cần chứng minh
Ví dụ
• Xét ví dụ bên trên, ta sẽ tìm ma trận chẵn lẻ
tương ứng
• Có 8 = 23 từmã số hàng độc lập tuyến tính tối
9/30/2010Huỳnh Văn Kha
16
đa là 3
• Do w1, w2, w5 là họ độc lập tuyến tính tối đa
trong S nên ta chỉ cần tìm ma trận A thỏa cho ba
từmã này là đủ
• Xét ma trận Q gồm ba từmã này như sau
Ví dụ
• Ba cột cuối là độc lập tuyến tính, viết ba cột đầu
9/30/2010Huỳnh Văn Kha
17
thành tổ hợp tuyến tính của ba cột cuối như sau
• Cột đầu tiên
• Suy ra a1 = a2 = a3 = 1
Ví dụ
• Tương tự cho hai cột còn lại
9/30/2010Huỳnh Văn Kha
18
• Suy ra b1 = b2 = 1, b3 = 0 và c1 = c3 = 1, c2 = 0
Ví dụ
• Và như vậy
9/30/2010Huỳnh Văn Kha
19
• Ma trận A là
Lớp thương (coset)
• Cho S là nhóm con của nhóm G , thì lớp thương
ứng với phần tử z là một tập hợp mà các phần tử
của nó có dạng z + w, với w nằm trong S. Lớp
th ng ng v i z ký hi u là z + S
9/30/2010
20
Huỳnh Văn Kha
ươ ứ ớ ệ
• Ví dụ S = {0000, 0101, 1110, 1011}, thì
▫ 0110 + S = {0110, 0011, 1000, 1101}
▫ 1000 + S = 0110 + S
▫ 1111 + S = {1111, 1010, 0001, 0100}
▫ 0000 + S = S
• Các lớp thương hoặc rời nhau hoặc trùng nhau
Bảng các lớp thương
w0 w1 w2 w3
0000 0101 1110 1011
9/30/2010
21
Huỳnh Văn Kha
0110 0011 1000 1101
1111 1010 0001 0100
0010 0111 1100 1001
Bổ ñề 4.5
Cho bộmã chẵn lẻ S. Nếu có từmã wi và mẫu sai z
sao cho
d(wi + z, wi) ≤ d(wi + z, wj)
9/30/2010
22
Huỳnh Văn Kha
với mọi từmã wj.
Thì khi đó
d(w + z, w) ≤ d(w+ z, w’)
với mọi từmã w, w’
Ta thấy rằng một mẫu sai hoặc là luôn sửa được
hoặc là luôn không sửa được
Chứng minh bổ ñề 4.5
• Dễ dàng kiểm tra được rằng
d(v1 + v3, v2 + v3) = d(v1, v2)
• Do đó
9/30/2010
23
Huỳnh Văn Kha
ðịnh lý 4.6
Để xây dựng phương án giải mã cực tiểu khoảng
cách, thì trong mỗi lớp thương, ta chỉ cần chọn
các mẫu sai z có số ký tự 1 cực tiểu. Khi đó mỗi
9/30/2010
24
Huỳnh Văn Kha
dãy nhận được có dạng z + w (w là từmã) thì sẽ
được giải mã thành w
Chứng minh:
Ta có
Theo Bổ đề 4.5 ta có điều cần chứng minh
Ví dụ
w0 w1 w2 w3
0000 0101 1110 1011
9/30/2010
25
Huỳnh Văn Kha
1000 1101 0110 0011
0001 0100 1111 1010
0010 0111 1100 1001
ðịnh lý 4.7
Tất cả các dãy trong cùng một lớp thương của bộ
mã nhóm S đều có cùng một vector hiệu chỉnh
Hai dãy trong hai lớp thương khác nhau có các
9/30/2010
26
Huỳnh Văn Kha
vector hiệu chỉnh khác nhau
Dựa vào hai định lý 4.6 và 4.7 ta chứng minh được
định lý 4.8 sau. Định lý 4.8 cho phép việc giải mã
nhanh hơn. Đó là thay vì phải lưu trữ toàn bộ 2n dãy
nhị phân, ta chỉ cần lưu các vector hiệu chỉnh và các
mẫu sai tương ứng là đủ
ðịnh lý 4.8
Việc giải mã theo cách làm cực tiểu khoảng cách có
thể thực hiện theo cách sau
1. Với mỗi dãy v nhận được, ta tính các vector
9/30/2010
27
Huỳnh Văn Kha
hiệu chỉnh c tương ứng
2. Trong tất cả các dãy z thỏa AzT = c, giả sử z0 có
số ký tự 1 ít nhất, ta giảmã v thành v – z0
Ví dụ
Với ma trận kiểm tra chẵn lẻ
9/30/2010
28
Huỳnh Văn Kha
Lập bảng giải mã
Các file đính kèm theo tài liệu này:
- bai_giang_ly_thuyet_thong_tin_chuong_4_ma_sua_sai_phan_2.pdf