Định lý Meggitt
• Giả sử s(x) là syndrome của: • u(x) = u0xn-1 + u1xn-2 + ... + un-2x + un-1 thì syndrome của u1(x) là s1(x) được tính theo công thức sau:
• s1(x) = xs(x) mod g(x)
Phương phápháp p giảgiải i mã mã Phương ng Meggitt vòvòng Meggitt
Giáo viên thực hiện: Lê Thị Thanh
6.4 Khả năng sửa sai của bộ mã vòng (n,k)
Chứng minh định lý Meggitt
• 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
= x. (u(x) mod g(x)) mod g(x)
• 6.4.4 Xác suất không dò được sai của bộ
mã vòng
• Với quy ước u1(x) là quay vòng trái của u(x). • u(x) = u0xn-1 + u1xn-2 + ... + un-2x + un-1 • u1(x) = u1xn-1 + u2xn-2 + ... + un-1x + u0 • u1(x) mod g(x) = xs(x) mod g(x) = • • (cid:1) u1(x) mod g(x) = x.u(x) mod g(x) • (u1xn-1 + u2xn-2 + ... + un-1x + u0) mod g(x) = • = (u0xn + u1xn-1 + ... + un-2x2 + un-1x) mod
g(x)
• => u0(xn + 1) mod g(x) = 0
1
6.4.1 Độ dài sai
• Độ dài sai: Giả sử e = e0e1... en-1= • = (e0e1... ei-1 ei ei+1 ... ej-1 ej ej+1 ...en-1) = (00 ... 0 1 ei+1 ... ej-11 00 ... 0) • • Khi đó độ dài sai được định nghĩa là khoảng
• Độ dài sai vòng: giả sử e = e0e1... en-1= = (e0e1... ei-1 ei ei+1 ... ej-1 ej ej+1 ...en-1) • = (e0e1... ei-1 1 0 0 ... 0 1 ej+1 ...en-1) • • Độ dài sai vòng được định nghĩa là khoảng
cách vòng từ bit ei đến bit ej.
cách từ bit ei tới bit ej: • độ dài sai = j – i + 1
• độ 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)
6.4.2 Khả năng dò sai (2/3)
• Giả sử ei(x) là đa thức gây sai không phát
• Đị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).
hiện được → ei(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).xi 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)
• 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 ei(x) là đa thức dịch chuyển vòng i bit của e(x) (i=1,n-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).
2
6.4.2 Khả năng dò sai (3/3)
6.4.3 Xác suất không dò được sai
• 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).
• Đị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)”.
• Mặt khác, vì hệ số tự do của g(x) là khác không nên xi sẽ không chức một thừa số nào của g(x). Vậy E(x).xi sẽ không chia hết cho g(x).
• Vậy đa thức sai e(x) là dò được.
• 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
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).
• 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à:
• Pud = 1/ 2(n-k-1) = 2-(n-k-1)
• Chứng minh: • Số đa thức gây sai: 2n – 1 • Số đa thức mã khác không: 2k – 1 • Vậy xác xuất không dò được sai là: • Pud = 2k – 1 / 2n – 1 = 2k-n
3
Phương pháp giải mã vòng Meggitt
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
• Nguyên lý giải mã • Thiết kế mạch thực hiện giải mã
• Giả sử nhận được đa thức: u(x)=u0xn-1+u1xn-2+...+un-1 • Chọn một mẫu sai có thể sửa sai được e(x)=e0xn-1+e1xn-2+...+en-1 với e0=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)
Syndrome của u(x) không bằng syndrome của e(x)
• Quay vòng
• Quay vòng
u(x)=u0xn-1+u1xn-2+...+un-1 để được u(1)(x)=u1xn-1+u2xn-2+...un-1x+u0 Do u0xn+u0=u0(xn+1) chia hết cho g(x) nên: s(1)(x) =dư số[u(1)(x)/g(x)]
u(x)=u0xn-1+u1xn-2+...+un-1 để được u(1)(x)=u1xn-1+u2xn-2+...un-1x+u0 Do u0xn+u0=u0(xn+1) chia hết cho g(x) nên: s(1)(x)=dư số[u(1)(x)/g(x)]
=dư số[(u(1)(x)+u0xn+u0)/g(x)] =dư số[(u0xn+u(1)(x)+u0)/g(x)] =dư số[(u0xn+u1xn-1+u2xn-2+...+un-1x+u0+u0)/g(x)]
=dư số[(u(1)(x)+u0xn+u0)/g(x)] =dư số[(u0xn+u(1)(x)+u0)/g(x)] =dư số[(u0xn+u1xn-1+u2xn-2+...+un-
1x+u0+u0)/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)]
4
Syndrome của u(x) bằng syndrome của e(x)
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)]
• Sửa sai bit đầu tiên: u(x) sửa sai bit đầu (cộng với e0=1) được u’(x) u’(x)=(u0+e0)xn-1+u1xn-2+...+un-1=u(x)+e0xn-1 Lúc đó syndrome của u’(x) là: s’(x) =dư số[u’(x)/g(x)]=dư số[(u(x)+e0xn-1)/g(x)]
• Do đó khi đã có syndrome của u(x) là s(x) thì có
=dư số[u(x)/g(x)]+dư số[xn-1/g(x)] =s(x)+dư số[xn-1/g(x)]
thể tính syndrome s(1)(x) của u(1)(x) bằng cách dịch trái s(x)
Thiết kế mạch giải mã Meggitt
Syndrome của u(x) bằng syndrome của e(x)
Đóng từ xung n
u(x)
• Quay vòng trái u’(x) và tính syndrome của nó: u’(1)(x)=u1xn-1+u2xn-2+...+un-1x+(u0+e0)=u(1)(x)+e0 s’(1)(x) =dư số[u’(1)(x)/g(x)]
Bộ đệm
+
=dư số[(u(1)(x)+e0)/g(x)] =dư số[(u(1)(x)/g(x)]+dư số[e0/g(x)] =dư số[xs(x)/g(x)]+dư số[e0/g(x)] =dư số[(xs(x)+e0)/g(x)]
Thanh ghi syndrome
+
• 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 e0 vào bit trọng số thấp nhất
So sánh mẫu sai
1: khớp, 0: không khớp
5
Thiết kế mạch giải mã Meggitt
Thiết kế mạch giải mã Meggitt sửa sai 1 bit cho bộ mã vòng có g(x)=x3+x+1
• Giả sử bộ mã vòng có ma trận sinh là: g(x)=x3+x+1
với n=7, k=4, n-k=3
+
7
6
5
4
3
2
1
• 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
x0 x1 0x2 x3
+
+
Đóng từ xung thứ 7
3
2
1
1101000 chia cho 1011 là 001 từ đó ta có từ mã là 1101001
Mạch chia lấy số dư
Ngõ vào
Ngõ ra
• 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
=101
1
0
≠101
Mạch so sánh với 101
Hoạt động mạch giải mã Meggitt – xung 0
Hoạt động mạch giải mã Meggitt – xung 1
+
+
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1
7
6
5
4
3
2
1
7
6
5
4
3
2
1
x0 x1 0x2 x3 x0 x1 0x2 x3
+
+
+
+
0 0 0 1 0 0 1 0 0 1 1 0
3
2
1
3
2
1
010 011
0 0
6
Hoạt động mạch giải mã Meggitt – xung 2
Hoạt động mạch giải mã Meggitt – xung 3
+
+
1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1
7
6
5
4
3
2
1
7
6
5
4
3
2
1
x0 x1 0x2 x3 x0 x1 0x2 x3
+
+
+
+
1 1 0 0 1 1 0 1 1 0 1 1
3
2
1
3
2
1
001 100
0 0
Hoạt động mạch giải mã Meggitt – xung 4
Hoạt động mạch giải mã Meggitt – xung 5
+
+
1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0
7
6
5
4
3
2
1
7
6
5
4
3
2
1
x0 x1 0x2 x3 x0 x1 0x2 x3
+
+
+
+
0 1 1 0 1 1 0 1 1 1 1 1
3
2
1
3
2
1
100 100
0 0
7
Hoạt động mạch giải mã Meggitt – xung 6
Hoạt động mạch giải mã Meggitt – xung 7
+
+
0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1
7
6
5
4
3
2
1
7
6
5
4
3
2
1
x0 x1 0x2 x3 x0 x1 0x2 x3
+
+
+
+
1 1 1 0 0 1 0 0 1 1 1 0
3
2
1
3
2
1
101 110
0 0
Hoạt động mạch giải mã Meggitt – xung 8
Hoạt động mạch giải mã Meggitt – xung 9
+
+
0 1 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 11
7
6
5
4
3
2
1
7
6
5
4
3
2
1
x0 x1 0x2 x3 x0 x1 0x2 x3
+
+
+
+
1 1 0 0 1 1 0 1 1 1 1 1
3
2
1
3
2
1
001 100
0 0
8
Hoạt động mạch giải mã Meggitt – xung 10
Hoạt động mạch giải mã Meggitt – xung 11
+
+
0 0 0 1 0 1 1 1 011 0 0 0 0 1 0 1 0 1011
7
6
5
4
3
2
1
7
6
5
4
3
2
1
x0 x1 0x2 x3 x0 x1 0x2 x3
+
+
+
+
1 1 1 1 0 1 1 0 1 0 0 0
3
2
1
3
2
1
101 111
0 1
Hoạt động mạch giải mã Meggitt – xung 12
Hoạt động mạch giải mã Meggitt – xung 13
+
+
0 0 0 0 0 0 1 0 01011 0 0 0 0 0 0 1 1 001011
7
6
5
4
3
2
1
7
6
5
4
3
2
1
x0 x1 0x2 x3 x0 x1 0x2 x3
+
+
+
+
0 0 0 0 0 0 0 0 0 0 0 1
3
2
1
3
2
1
010 010
0 0
