Bài giảng Phương pháp giải mã vòng Meggitt

1Phương pháp giải mã vòng 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) = 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) Chứng minh định lý Meggitt • 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) = • = x. (u(x) mod g(x)) mod g(x) •
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 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 26.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 cách từ bit ei tới bit ej: • độ dài sai = j – i + 1 • Độ 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. • độ 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 ei(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ử ei(x) là đa thức gây sai không phát 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) • Để 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). 36.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 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. 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à: • Pud = 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: 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 4Phươ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)=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) • 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)] =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)] Syndrome của u(x) không bằng syndrome của e(x) • 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)] =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)] 5Syndrome 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 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)] =dư số[u(x)/g(x)]+dư số[xn-1/g(x)] =s(x)+dư số[xn-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)=u1xn-1+u2xn-2+...+un-1x+(u0+e0)=u(1)(x)+e0 s’(1)(x) =dư số[u’(1)(x)/g(x)] =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)] • 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 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 6Thiết kế mạch giải mã Meggitt • 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 • 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)=x3+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 0x2 x3x1x0 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 0x2 x3x1x0 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 0x2 x3x1x0 7Hoạ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 0x2 x3x1x0 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 0x2 x3x1x0 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 0x2 x3x1x0 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 0x2 x3x1x0 8Hoạ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 0x2 x3x1x0 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 0x2 x3x1x0 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 0x2 x3x1x0 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 0x2 x3x1x0 0 9Hoạ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 0x2 x3x1x0 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 0x2 x3x1x0 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 0x2 x3x1x0 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 0x2 x3x1x0 1