1
Phương Phương phápháp p giảgiải i mã mã
vòvòng Meggittng Meggitt
Giáo viên thực hiện: Lê Thị Thanh
Định lý Meggitt
• Giả sử s(x) là syndrome của:
• u(x) = u
0
x
n-1
+ u
1
x
n-2
+ + u
n-2
x + u
n-1
thì syndrome
của u
1
(x) là s
1
(x) được tính theo công thức sau:
• s
1
(x) = xs(x) mod g(x)
Chứng minh định lý Meggitt
• Với quy ước u
1
(x) là quay vòng trái của u(x).

• u(x) = u
0
x
n-1
+ u
1
x
n-2
+ + u
n-2
x + u
n-1
• u
1
(x) = u
1
x
n-1
+ u
2
x
n-2
+ + u
n-1
x + u
0
• u
1
(x) mod g(x) = xs(x) mod g(x) =
• = x. (u(x) mod g(x)) mod g(x)

•  u
1
(x) mod g(x) = x.u(x) mod g(x)
• (u
1
x
n-1
+ u
2
x
n-2
+ + u
n-1
x + u
0
) mod g(x) =
• = (u
0
x
n
+ u
1
x
n-1
+ + u
n-2
x
2
+ u
n-1

x) mod
g(x)
• => u
0
(x
n
+ 1) mod g(x) = 0
6.4 Khả năng sửa sai của bộ mã vòng (n,k)
• 6.4.1 Độ dài sai
• 6.4.2 Khả năng dò sai
• 6.4.3 Xác suất không dò được sai của các
mẫu sai
• 6.4.4 Xác suất không dò được sai của bộ
mã vòng
2
6.4.1 Độ dài sai
• Độ dài sai: Giả sử e = e
0
e
1
e
n-1
=
• = (e
0
e
1
e
i-1
e

i
e
i+1
e
j-1
e
j
e
j+1
e
n-1
)
• = (00 0 1 e
i+1
e
j-1
1 00 0)
• Khi đó độ dài sai được định nghĩa là khoảng
cách từ bit e
i
tới bit e
j
:
• độ dài sai = j – i + 1
• Độ dài sai vòng: giả sử e = e
0
e
1
e
n-1

=
• = (e
0
e
1
e
i-1
e
i
e
i+1
e
j-1
e
j
e
j+1
e
n-1
)
• = (e
0
e
1
e
i-1
1 0 0 0 1 e
j+1
e
n-1

)
• Độ dài sai vòng được định nghĩa là khoảng
cách vòng từ bit e
i
đến bit e
j
.
• độ dài sai vòng = n – (j – 1 – i – 1 + 1) =
• = n – j + i + 1)
6.4.2 Khả năng dò sai (1/3)
• Định lý 6.7: Bộ mã vòng (n,k) có thể dò
được tất cả các mẫu sai nhỏ hơn hoặc bằng
(n-k) bit. (kể cả độ dài sai vòng).
• Chứng minh:
• Bổ đề: “Nếu bộ mã vòng (n,k) có khả năng
phát hiện được đa thức gây sai e(x) thì sẽ
phát hiện được tất cả các đa thức gây sai
e
i
(x) là đa thức dịch chuyển vòng i bit của
e(x) (i=1,n-1)”.
6.4.2 Khả năng dò sai (2/3)
• Giả sử e
i
(x) là đa thức gây sai không phát
hiện được → e
i
(x) cũng là đa thức mã (mâu
thuẫn). Do đó ta chỉ cần chứng minh định lý
với độ dài sai tuyệt đối.

• Giả sử e(x) = E(x).x
i
với 0 ≤ i ≤ n-1 → vector
sai ứng với E(x) có độ dài ≤ (n-k) → bậc của
E(x) ≤ (n-k-1)
• Để phát hiện được sai trong mã vòng thì
phải chứng minh rằng e(x) không phải từ
mã, tức là e(x) không chia hết cho g(x).
3
6.4.2 Khả năng dò sai (3/3)
• Nhận xét: E(x) có bậc nhỏ hơn g(x); E(x) # 0
→ E(x) không chia hết cho g(x).
• Mặt khác, vì hệ số tự do của g(x) là khác
không nên x
i
sẽ không chức một thừa số
nào của g(x). Vậy E(x).x
i
sẽ không chia hết
cho g(x).
• Vậy đa thức sai e(x) là dò được.
6.4.3 Xác suất không dò được sai
• Định lý 6.8: ”Xác suất không dò được các
mẫu sai có độ dài bằng (n-k+1) là 2
-(n-k-1)
”.
• Chứng minh: e(x) = E(x).xi
• E(x) có n-k+1 số hạng → E(x) có bậc n-k.
• Khi không phát hiện được sai thì E(x) là đa
thức mã có bậc n-k, mà đa thức mã bậc n-k

duy nhất là g(x).
6.4.3 Xác suất không dò được sai
• Có 2
(n-k-1)
đa thức nhưng chỉ có một đa thức
E(x) = g(x) làm cho sai e(x) là không dò
được. Vậy xác suất không dò được sai của
các mẫu sai có độ dài bằng (n-k+1) là:
• P
ud
= 1/ 2
(n-k-1)
= 2
-(n-k-1)
6.4.4 Định lý 6.9
• Định lý 6.9: xác suất không dò được sai của
bộ mã vòng (n,k) là 2
(k-n)
.
• Chứng minh:
• Số đa thức gây sai: 2
n
– 1
• Số đa thức mã khác không: 2
k
– 1
• Vậy xác xuất không dò được sai là:
• P
ud
= 2

k
– 1 / 2
n
– 1 = 2
k-n
4
Phương pháp giải mã vòng Meggitt
• Nguyên lý giải mã
• Thiết kế mạch thực hiện giải mã
Nguyên lý giải mã Meggitt
• Phương pháp này sửa sai cho tất cả các
mẫu sai 1 bit
• Giả sử nhận được đa thức:
u(x)=u
0
x
n-1
+u
1
x
n-2
+ +u
n-1
• Chọn một mẫu sai có thể sửa sai được
e(x)=e
0
x
n-1
+e
1

x
n-2
+ +e
n-1
với e
0
=1
• So sánh syndrome của u(x) và syndrome
của e(x):
–Không khớp: tính syndrome của u
(1)
(x) từ
syndrome của u(x)
–Khớp: sửa sai và tính syndrome của
u’
(1)
(
x
)
t
ừ
syndrome
củ
a u(x)
Syndrome của u(x) không bằng syndrome
của e(x)
• Quay vòng
u(x)=u
0
x

n-1
+u
1
x
n-2
+ +u
n-1
để được
u
(1)
(x)=u
1
x
n-1
+u
2
x
n-2
+ u
n-1
x+u
0
Do u
0
x
n
+u
0
=u
0

(x
n
+1) chia hết cho g(x) nên:
s
(1)
(x) =dư số[u
(1)
(x)/g(x)]
=dư số[(u
(1)
(x)+u
0
x
n
+u
0
)/g(x)]
=dư số[(u
0
x
n
+u
(1)
(x)+u
0
)/g(x)]
=dư số[(u
0
x
n

+u
1
x
n-1
+u
2
x
n-2
+ +u
n-1
x+u
0
+u
0
)/g(x)]
Syndrome của u(x) không bằng syndrome
của e(x)
• Quay vòng
u(x)=u
0
x
n-1
+u
1
x
n-2
+ +u
n-1
để được
u

(1)
(x)=u
1
x
n-1
+u
2
x
n-2
+ u
n-1
x+u
0
Do u
0
x
n
+u
0
=u
0
(x
n
+1) chia hết cho g(x) nên:
s
(1)
(x)=dư số[u
(1)
(x)/g(x)]
=dư số[(u

(1)
(x)+u
0
x
n
+u
0
)/g(x)]
=dư số[(u
0
x
n
+u
(1)
(x)+u
0
)/g(x)]
=dư số[(u
0
x
n
+u
1
x
n-1
+u
2
x
n-2
+ +u

n-
1
x+u
0
+u
0
)/g(x)]
=dư số[(xu(x)+0)/g(x)]
=dư số[xu(x)/g(x)]
=dư số[x(kg(x)+dư số[u(x)/g(x)])/g(x)]
5
Syndrome của u(x) không bằng syndrome
của e(x)
=dư số[x(kg(x)+dư số[u(x)/g(x)])/g(x)]
=dư số[x(kg(x)+s(x)])/g(x)]
=dư số[xkg(x)/g(x)+dư số[xs(x)/g(x)]
=0+dư số[xs(x)/g(x)]
=dư số[xs(x)/g(x)]
• Do đó khi đã có syndrome của u(x) là s(x) thì có
thể tính syndrome s
(1)
(x) của u
(1)
(x) bằng cách dịch
trái s(x)
Syndrome của u(x) bằng syndrome của
e(x)
• Sửa sai bit đầu tiên:
u(x) sửa sai bit đầu (cộng với e
0

=1) được u’(x)
u’(x)=(u
0
+e
0
)x
n-1
+u
1
x
n-2
+ +u
n-1
=u(x)+e
0
x
n-1
Lúc đó syndrome của u’(x) là:
s’(x) =dư số[u’(x)/g(x)]=dư số[(u(x)+e
0
x
n-1
)/g(x)]
=dư số[u(x)/g(x)]+dư số[x
n-1
/g(x)]
=s(x)+dư số[x
n-1
/g(x)]
Syndrome của u(x) bằng syndrome của

e(x)
• Quay vòng trái u’(x) và tính syndrome của nó:
u’
(1)
(x)=u
1
x
n-1
+u
2
x
n-2
+ +u
n-1
x+(u
0
+e
0
)=u
(1)
(x)+e
0
s’
(1)
(x) =dư số[u’
(1)
(x)/g(x)]
=dư số[(u
(1)
(x)+e

0
)/g(x)]
=dư số[(u
(1)
(x)/g(x)]+dư số[e
0
/g(x)]
=dư số[xs(x)/g(x)]+dư số[e
0
/g(x)]
=dư số[(xs(x)+e
0
)/g(x)]
• Do đó khi đã có syndrome của u(x) là s(x) thì có thể tính
syndrome s’
(1)
(x) của u’
(1)
(x) bằng cách dịch trái s(x) và
cộng thêm e
0
vào bit trọng số thấp nhất
Thiết kế mạch giải mã Meggitt
Thanh ghi syndrome
So sánh mẫu sai
Bộ đệm
+
+
u(x)
1: khớp, 0: không khớp

Đóng từ xung n
6
Thiết kế mạch giải mã Meggitt
• Giả sử bộ mã vòng có ma trận sinh là: g(x)=x
3
+x+1
với n=7, k=4, n-k=3
• Mẫu sai sửa được là: 1000000 có syndrome là
(101)
• Các bit mang tin là 1101 thì tính được dư của
1101000 chia cho 1011 là 001 từ đó ta có từ mã là
1101001
• Giả sử sai bit thứ 5 thành 1101101
• Mạch giải mã sẽ sửa bit thứ 5 từ 1 thành 0 và
chuyển tổ hợp 1101101 thành từ mã 1101001
Thiết kế mạch giải mã Meggitt sửa sai 1 bit cho bộ
mã vòng có g(x)=x
3
+x+1
3 2 1
++
7 6 5 4 3 2 1
+
Mạch chia
lấy số dư
Mạch so sánh với 101
Ngõ vào Ngõ ra
=101 1
≠101 0
Đóng

từ
xung
thứ 7
0x
2
x
3
x
1
x
0
Hoạt động mạch giải mã Meggitt – xung 0
3 2 1
++
7 6 5 4 3 2 1
+
1 0 1 1 0 1 1
0000000
000
0
0
010
1 0 0
0x
2
x
3
x
1
x

0
Hoạt động mạch giải mã Meggitt – xung 1
3 2 1
++
7 6 5 4 3 2 1
+
1 0 1 1 0 1
0000001
001
0
0
011
1 1 0
0x
2
x
3
x
1
x
0
7
Hoạt động mạch giải mã Meggitt – xung 2
3 2 1
++
7 6 5 4 3 2 1
+
1 0 1 1 0
0000011
011

0
0
001
0 1 1
0x
2
x
3
x
1
x
0
Hoạt động mạch giải mã Meggitt – xung 3
3 2 1
++
7 6 5 4 3 2 1
+
1 0 1 1
0000110
110
0
0
100
0 1 1
0x
2
x
3
x
1

x
0
Hoạt động mạch giải mã Meggitt – xung 4
3 2 1
++
7 6 5 4 3 2 1
+
1 0 1
0001101
110
0
0
100
0 1 1
0x
2
x
3
x
1
x
0
Hoạt động mạch giải mã Meggitt – xung 5
3 2 1
++
7 6 5 4 3 2 1
+
1 0
0011011
110

0
0
100
1 1 1
0x
2
x
3
x
1
x
0
8
Hoạt động mạch giải mã Meggitt – xung 6
3 2 1
++
7 6 5 4 3 2 1
+
1
0110110
111
0
0
101
0 0 1
0x
2
x
3
x

1
x
0
Hoạt động mạch giải mã Meggitt – xung 7
3 2 1
++
7 6 5 4 3 2 1
+
1101101
100
1
0
110
1 1 0
0x
2
x
3
x
1
x
0
Hoạt động mạch giải mã Meggitt – xung 8
3 2 1
++
7 6 5 4 3 2 1
+
1011010
011
1

0
001
0 1 1
0x
2
x
3
x
1
x
0
1
Hoạt động mạch giải mã Meggitt – xung 9
3 2 1
++
7 6 5 4 3 2 1
+
0110100
110
11
0
100
1 1 1
0x
2
x
3
x
1
x

0
0
9
Hoạt động mạch giải mã Meggitt – xung 10
3 2 1
++
7 6 5 4 3 2 1
+
1101000
111
011
0
101
1 0 1
0x
2
x
3
x
1
x
0
1
Hoạt động mạch giải mã Meggitt – xung 11
3 2 1
++
7 6 5 4 3 2 1
+
1010000
101

1011
1
111
0 0 0
0x
2
x
3
x
1
x
0
0
Hoạt động mạch giải mã Meggitt – xung 12
3 2 1
++
7 6 5 4 3 2 1
+
0100000
000
01011
0
010
0 0 0
0x
2
x
3
x
1

x
0
0
Hoạt động mạch giải mã Meggitt – xung 13
3 2 1
++
7 6 5 4 3 2 1
+
1000000
000
001011
0
010
0 0 1
0x
2
x
3
x
1
x
0
1