tài liệu Lý thuyết Thông tin

Chia sẻ: Nguyen Quoc Huy | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

116
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đị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)”.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: tài liệu Lý thuyết Thông tin

Định lý Meggitt • Giả sử s(x) là syndrome của: • u(x) = u0xn-1 + u1xn-2 + ... + un-2x + un-1 thì syndrome Phương pháp giải mã pháp giải của u1(x) là s1(x) được tính theo công thức sau: • s1(x) = xs(x) mod g(x) vòng Meggitt Giáo viên thực hiện: Lê Thị Thanh Chứng minh định lý Meggitt 6.4 Khả năng sửa sai của bộ mã vòng (n,k) Với quy ước u1(x) là quay vòng trái của u(x). • 6.4.1 Độ dài sai • u(x) = u0xn-1 + u1xn-2 + ... + un-2x + un-1 • • 6.4.2 Khả năng dò sai u1(x) = u1xn-1 + u2xn-2 + ... + un-1x + u0 • • 6.4.3 Xác suất không dò được sai của các u1(x) mod g(x) = xs(x) mod g(x) = • 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ộ 1(x) mod g(x) = x.u(x) mod g(x) • u mã vòng (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= • Độ 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 ei ei+1 ... ej-1 ej ej+1 ...en-1) • = (00 ... 0 1 ei+1 ... ej-11 00 ... 0) • = (e0e1... ei-1 1 0 0 ... 0 1 ej+1 ...en-1) • Khi đó độ dài sai được định nghĩa là khoảng • Độ dài sai vòng được định nghĩa là khoảng cách từ bit ei tới bit ej: cách vòng từ bit ei đến 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ò hiện được → ei(x) cũng là đa thức mã (mâu được tất cả các mẫu sai nhỏ hơn hoặc bằng thuẫn). Do đó ta chỉ cần chứng minh định lý (n-k) bit. (kể cả độ dài sai vòng). với độ dài sai tuyệt đối. • Chứng minh: • Giả sử e(x) = E(x).xi với 0 ≤ i ≤ n-1 → vector • Bổ đề: “Nếu bộ mã vòng (n,k) có khả năng sai ứng với E(x) có độ dài ≤ (n-k) → bậc của phát hiện được đa thức gây sai e(x) thì sẽ E(x) ≤ (n-k-1) phát hiện được tất cả các đa thức gây sai • Để phát hiện được sai trong mã vòng thì ei(x) là đa thức dịch chuyển vòng i bit của 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). e(x) (i=1,n-1)”. 2
6.4.2 Khả năng dò sai (3/3) 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 • 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ẫu sai có độ dài bằng (n-k+1) là 2-(n-k-1)”. • Chứng minh: e(x) = E(x).xi • 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ố • E(x) có n-k+1 số hạng → E(x) có bậc n-k. nào của g(x). Vậy E(x).xi sẽ không chia hết • Khi không phát hiện được sai thì E(x) là đa cho g(x). thức mã có bậc n-k, mà đa thức mã bậc n-k • Vậy đa thức sai e(x) là dò được. 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 • Có 2(n-k-1) đa thức nhưng chỉ có một đa thức • Định lý 6.9: xác suất không dò được sai của E(x) = g(x) làm cho sai e(x) là không dò bộ mã vòng (n,k) là 2(k-n). được. Vậy xác suất không dò được sai của • Chứng minh: các mẫu sai có độ dài bằng (n-k+1) là: • Số đa thức gây sai: 2n – 1 • Pud = 1/ 2(n-k-1) = 2-(n-k-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
Nguyên lý giải mã Meggitt Phương pháp giải mã vòng Meggitt • Phương pháp này sửa sai cho tất cả các • Nguyên lý giải mã mẫu sai 1 bit • 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 Syndrome của u(x) không bằng syndrome của e(x) của e(x) • Quay vòng • Quay vòng u(x)=u0xn-1+u1xn-2+...+un-1 để được u(x)=u0xn-1+u1xn-2+...+un-1 để được u(1)(x)=u1xn-1+u2xn-2+...un-1x+u0 u(1)(x)=u1xn-1+u2xn-2+...un-1x+u0 Do u0xn+u0=u0(xn+1) chia hết cho g(x) nên: Do u0xn+u0=u0(xn+1) chia hết cho g(x) nên: s(1)(x) =dư số[u(1)(x)/g(x)] s(1)(x)=dư số[u(1)(x)/g(x)] =dư số[(u(1)(x)+u0xn+u0)/g(x)] =dư số[(u(1)(x)+u0xn+u0)/g(x)] =dư số[(u0xn+u(1)(x)+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ố[(u0xn+u1xn-1+u2xn-2+...+un- x+u0+u0)/g(x)] 1 =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) không bằng syndrome Syndrome của u(x) bằng syndrome của của e(x) e(x) =dư số[x(kg(x)+dư số[u(x)/g(x)])/g(x)] • Sửa sai bit đầu tiên: =dư số[x(kg(x)+s(x)])/g(x)] u(x) sửa sai bit đầu (cộng với e0=1) được u’(x) =dư số[xkg(x)/g(x)+dư số[xs(x)/g(x)] u’(x)=(u0+e0)xn-1+u1xn-2+...+un-1=u(x)+e0xn-1 =0+dư số[xs(x)/g(x)] Lúc đó syndrome của u’(x) là: =dư số[xs(x)/g(x)] 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)] thể tính syndrome s(1)(x) của u(1)(x) bằng cách dịch =s(x)+dư số[xn-1/g(x)] trái s(x) Syndrome của u(x) bằng syndrome của Thiết kế mạch giải mã Meggitt e(x) • Quay vòng trái u’(x) và tính syndrome của nó: Đóng từ xung n u’(1)(x)=u1xn-1+u2xn-2+...+un-1x+(u0+e0)=u(1)(x)+e0 u(x) 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 sửa sai 1 bit cho bộ Thiết kế mạch giải mã Meggitt 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 + • Mẫu sai sửa được là: 1000000 có syndrome là 7 6 5 4 3 2 1 (101) x0 x1 0x2 x3 Đóng • Các bit mang tin là 1101 thì tính được dư của từ xung 1101000 chia cho 1011 là 001 từ đó ta có từ mã là thứ 7 + + 3 2 1 1101001 • Giả sử sai bit thứ 5 thành 1101101 Mạch chia • Mạch giải mã sẽ sửa bit thứ 5 từ 1 thành 0 và lấy số dư chuyển tổ hợp 1101101 thành từ mã 1101001 Ngõ vào Ngõ ra =101 1 ≠101 0 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 1011011 101101 + + 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 0 1 0 1 1 0 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 10110 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 0 0 1 1 0 1 1 0 1 1 + + + + 3 2 1 3 2 1 1 0 0 0 0 1 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 101 10 + + 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 0 0 1 0 0 1 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 1 0 1 0 1 1 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 11 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 1 0 0 0 0 1 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 1 0 1 1 1 1 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 01011 0 0 0 0 0 1 0 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 0 1 0 0 1 0 0 0 9