Bài giảng truyền dẫn - Chương 5: Mã sửa lỗi

Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 1 CHƯƠNG V Mà SỬA LỖI Những thông tin truyền từ A B như ta đã thấy thông thường bị sai: di(t) di(t) d’i(t) di(t) = (... , di-1 , di , di+1 ...) Sự sai số đó do nhiều nguyên nhân: đường dây truyền, lưu lượng truyền, loại mã dùng, loại điều chế, loại thiết bị phát, loại thiết bị thu... Thường sai số đó cho phép trong khoảng: 10-4 10-7 và nhóm sai phụ thuộc loại mạch. Thường có 2 cách: • Nếu bộ giải mã tự sửa được nó sẽ sửa trực tiếp. • Nếu bộ giải mã không tìm được sai thì cần phải truyền lại một bộ phận dữ liệu để thực hiện sự sửa sai. Người ta còn gọi cách đó là sửa sai bằng cách truyền lại và gọi tắt là ARQ (Automatic Repeat Request) 1. Các phương pháp phát hiện lỗi đơn giản 1.1. Truyền dư thừa Truyền dư thừa hay còn gọi là phương pháp truyền mỗi ký tự hai lần. Nếu như ở phía đầu thu hai ký tự nhận được kế tiếp nhau mà không giống nhau tức có lỗi truyền xuất hiện 1.2. Truyền phản hồi Đây là phương pháp đơn giản để phát hiện lỗi được sử dụng một thời khi người điều hành làm công việc truyền dữ liệu bằng trực tiếp gõ vào bàn phím. Truyền phản hồi yêu cầu đường truyền là song công, trong đó mỗi ký tự được truyền ngay sau khi gõ bản phím. Ở đầu thu, mỗi lần nhận đuợc một ký tự thì lập tức truyền ngược lại ký tự đó cho phía phát và ký tự đó cũng được hiển thị trên màn hình 1.3. Dùng mã lặp Mã lặp được cấu trúc như sau: Nếu như số phần tử “1” trong các phần tử thông tin là số lẻ thì các phần tử kiểm tra được lặp lại đúng các phần tử thông tin. Nếu như số phần tử “1” trong các phần tử thông tinlà số chẵn thì các phần tử kiểm tra là nghịch đảo của các phần tử thông tin Vd: Cho hai từ mã, mỗi từ mã có 5 phần tử thông tin là : 10110 và 10100 Từ mã lặp là: 1011010110 và 1010001011 1.4. Phương pháp kiểm tra chẵn lẻ Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 2 Đơn giản nhất là phương pháp VRC (Vertical Redundancy Check).Mỗi xâu bit biểu diễn một ký tự cần truyền đi được thêm vào một bit ( gọi là parity bit).Bit này có giá trị (tuỳ quy ước) là 0 nếu số lượng các bít 1 trong xâu là chẵn,và ngược lại. Bên nhận sẽ căn cứ vào đó để phát hiện lỗi Nhược điểm của VRC là không định vị được bit lỗi nên không thể tự sửa mà phải yêu cầu truyền lại. Mặt khác dùng phương pháp này có thể không phát hiện được các lỗi không phải là bit đơn ( chẳng hạn co 2 bit trong xâu cùng bị lỗi, giá trị của parity bit cũng không thay đổi). Để khắc phục, người ta dùng thêm phương pháp LRC (Longitudinal Redundancy Chech). LRC áp dụng kiểm tra parity bit cho từng khối các ký tự ( ví dụ cho vùng dữ liệu trong một frame).Kết hợp cả hai phương pháp VRC-LRC sẽ cho phép kiểm soát lỗi theo cả hai chiều, nâng cao hiệu quả đáng kể so với việc dùng riêng từng phương pháp. Hình 4-1 cho ví dụ minh họa kiểm soát lỗi theo cả 2 phương pháp VRC-LRC. 1.5. Mã phát hiện lỗi và sửa lỗi 1.6. Mã tuyến tính 1.6.1. Định nghĩa Ta có vectơ thông tin I của k bít i = (i1,i2,ik) khi đó ta tạo một từ mã có độ dài là n c = (i1, i2, ik, Ck+1, Cn) Ci € {0,1} 1.6.2. Tính chất 1.7. Mã vòng Việc nghiên cứu mã tuyến tính trên đây nhằm mục đích là sao ta có thể tìm một họ mã có đủ các tính chất sau: • mã hóa và giải mã đơn giản. • khả năng tìm và sửa lỗi độc lập theo các gói đã truyền. Ở phần trên chúng ta đã thấy việc kiểm tra theo VRC hoặc LRC còn những sai sót mà ta khó tránh khỏi, với mã VRC, nếu sai số theo chiều V là số chẳn bit thì bit kiểm tra cũng không có gì thay đổi. Tương tự ta có nếu số bit sai là 2n, ta cũng không thể phát hiện gì được. Mã vòng với kiểm tra CRC (Cyclic Redundancy Check) có nhiều hiệu quả hơn trong việc thông báo lỗi. 1.7.1. Định nghĩa Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 3 Mã vòng (n,k) là một mã tuyến tính (n,k) với sự hoán vị vòng của một từ mã là một từ mã. C= (Cn-1 , ... , C0) € C (Cn-2 , ... , C0 , Cn-1) € C Ta có thể viết một từ mã dưới dạng đa thức: C(x) = Cn-1Xn-1 + C1X + Co và theo định nghĩa trên ta có: C(X) € C Xi.C(X) modul (Xn + 1) € C 1.7.2. Đa thức sinh Sự nhận biết ma trận phát G của một mã vòng được đưa đến từ sự nhận biết của đa thức bậc n-k. Do sự chính xác của tính chất sau: Tính chất: Tất cả các từ mã vòng (n, k) là sự nhân của đa thức g(x) bậc (n-k) kết hợp từ dòng cuối của G và gọi là đa thức phát. Ví dụ: Với mã tuyến tính biểu diễn ở trên, ta có ma trận Vậy: g(x) = x3 + x + 1 1.7.3. Tạo mã CRC Phương pháp tạo CRC bao gồm việc dịch thông báo sang trái và chia cho một hàm cho trước với modul 2. Kết quả dư lại của phép chia chính là CRC và được truyền theo thông Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 4 báo. Bên thu sau khi nhận được thông báo người ta cũng đem chia cho hàm biết trước như bên phát. Nếu kết quả bằng 0, phép truyền không có sai số. Trong thực tế, nếu dùng cách kiểm tra CRC kết hợp với ARQ thì hiệu quả rất cao. Nếu dùng CRC với 16 bit thì có thể chỉ sai 1 bit khi ta truyền 1014 bit. Cách tính CRC gồm bốn bước. • Cho r bằng bậc của G(x), gắn r bit 0 vào cuối của frame, sau bit có trọng số thấp nhất, vì thế bây giờ nó bao gồm m+r bit, tương ứng với đa thức xrM(x). • Chia xâu bit tương ứng với xrM(x) cho G(x), dùng phép chia modulo 2. • Lấy xrM(x) trừ đi phần dư (luôn có số bit nhỏ hơn hoặc bằng r), dùng phép trừ modulo • Kết quả nhận được frame được tính checksum (checksumed frame) cần phải truyền đi - ta gọi nó là đa thức T(x). Ví dụ: cần tính CRC cho thông báo M(x) = 110101. Ta có thể biểu diễn M(x) dạng đa thức. Các phép tính CRC được thực hiện 4 bước sau với các phép tính thực hiện với modul 2. Bước 1: Chuyển thông báo nhị phân thành đa thức M(x) = (1).x5 + (1).x4 + (0).x3 + (1).x2 + (0).x1 + (1).x0 Bậc cao nhất là (n-1) = 5 M(x) = x5 + x4 + x2 + 1 Ta chọn độ dài của CRC. Nếu ta chọn CRC có độ dài là c bit. Ta chọn ra hàm G(x) = xc + 1. [Thường hàm G(x) cho trước tùy giá trị c, và có nơi gọi G(x) là P(x)]. Bước 2: Nhân M(x).xc/G(x) Ví dụ ta chọn c = 3 Ta có: Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 5 Bước 3: Thực hiện phép tính M(x).x0/G(x) với modul 2, ta có được: Bước 4: Lập T(x) Với T(x) = xc.M(x) + R(x) T(x) chính là bảng thông báo cần truyền đi. Ví dụ: Cần truyền thông tin 110101 1. Tạo M(x) M(x) = x5 + x4 + x2 + 1 Chọn C = 3 G(x) = x3 + 1 2. Tạo M(x) x3/G(x) 3. Tính Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 6 X8 4. Tính T(x) = xcM(x) + R(x) = x8 + x7 + x5 + x3 + x + 1 Thông tin cần truyền là: 1 1 0 1 0 1 0 1 1 1.7.4. Thu và kiểm tra CRC Để kiểm tra sai số khi truyền, bộ phận thu đem khối thông tin thu được chia cho G(x) theo modul 2. Nếu phần dư còn lại là 0, thì từ mã nhận được không sai, nếu phần dư khác o thì kết quả nhận được không đúng. Thử CRC Ta có: Và Ta có: Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 7 Mà Ví dụ ta có: 1.7.5. Mạch tạo mã CRC: Để tạo mã CRC người ta có thể dùng phần mềm, tuy nhiên trên thực tế để nhanh chóng hơn và giảm bớt thời gian sử dụng cho  P, người ta thường dùng phần cứng để tạo CRC và kiểm tra. Thao tác cộng MOD-2 và dịch có thể dùng một mạch ghi dịch phản hồi về một cổng EXOR. Số lượng cột của bộ ghi dịch phụ thuộc vào giá trị C đã chọn cho G(x) và cũng là số bit cho mã CRC. Error! Bookmark not defined. Mạch tạo CRC dùng bộ ghi dịch với G(x)=x3-1. Ví dụ : Ta cần truyền thông tin: M(x) = 1010001101 với hàm G(x) = x5 + x4 + x2 + 1 Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 8 Ta có mạch dịch và các bước thực hiện như hình vẽ. Error! Bookmark not defined. Mạch ghi dịch với hàm G(x) = x5 + x4 + x2 + 1. Người ta có thể tạo mã CRC dài 12 bit, 16 bit, 32 bit ... Vấn đề là chọn G(x) sao cho phù hợp. Thường cho 16 bit người ta chọn: G(x) = x16 + x15 + x2 + 1 Hoặc G(x) = x16 + x12 + x5 + 1 Error! Bookmark not defined. Mạch dịch với G(x) = x16 + x15 + x2 + 1. Mạch tạo CRC cho 16 bit như hình vẽ: Trong mạng Ethernet, người ta truyền 1500 bytes cần CRC là 32 bit. Và hàm G(x) được sử dụng là: G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 Và dùng Intel 82586 coprocessor on chip. Từ những ví dụ trên ta có thể nhận xét một cách máy móc rằng: để tạo ra mạch dịch với các cổng EXOR và các FF cho một hàm có sẵn ở đầu vào các thành phần x có giá trị 1 sẽ có cổng EXOR, tín hiệu vòng về sẽ được đưa đến các mạch EXOR đó, số lượng các FF trong bộ ghi dịch là C đã chọn của hàm G(x). 1.8. Mã Hamming 1.8.1. Giới thiệu Đây là một mã tuyến tính. Mã này được R. W Hamming đưa ra vào năm 1960. Mã Hamming sử dụng rộng rãi trong hệ truyền dữ liệu dùng kiểm tra lỗi phía trước FEC ( Forward Error Correction). Mã có khả năng sửa được một sai lỗi trong từ mã, sơ đồ cấu tạo đơn giản và xác định phần tử lỗi. 1.8.2. Trọng lượng và khoảng cách Hamming - Trọng lượng Hamming (Hamming weight) của véctơ từ mã v, ký hiệu là w(v) được định nghĩa là số thành phần khác 0 có trong v. - Khoảng cách Hamming (Hamming distance) của 2 vectơ từ mã có cùng chiều u và v, ký hiệu là d(u,v), được định nghĩa là số vị trí mà chúng có các giá trị khác nhau VD: u = 1001011 Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 9 v = 0100011 d(u,v) = 3 Khoảng cách Hamming của u và v cũng là trọng lượng Hamming của tổng u và v VD: u + v = 1101000 W(u+v) = 3 1.8.3. Tạo mã Hamming ™ Tạo mã Hamming C(7,4) - Vị trí các dấu trong từ mã: x y a3 z a5 a6 a7 Trong đó: x,y,z : Là các bít mang dấu kiểm tra a3,a5,a6,a7: Là các bít mang thông tin - Xác định các dấu kiểm tra theo các dấu mang thông tin x = a3 + a5 + a7 y = a3 + a6 + a7 z = a5 + a6 + a7 - Tạo mã: Xác định các dấu trong từ mã. Xác định các dấu kiểm tra theo tổng kiểm tr. Đặt các dấu kiểm tra vào từ mã. VD: ™ Mã Hamming mở rộng C(n,k) Trong đó: n: từ mã k: Dấu mang tin r = n – k: Dấu kiểm tra - Vị trí các dấu: x1,x2,..xn. - Các dấu kiểm tra : Nhận các vị trí 2i (i= 0,1,2,) 2i < n Các dấu còn lại là các dấu mang tin - Xác định các dấu kiểm tra theo phương pháp tổng kiểm tra sau: 24 23 22 21 20 Xác định các dấu 0 0 0 0 1 x1 0 0 0 1 0 x2 0 0 0 1 1 x3 0 0 1 0 0 x4 0 0 1 0 1 x5 0 0 1 1 0 x6 Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 10 0 0 1 1 1 x7 0 1 0 0 0 x8 0 1 0 0 1 x9 Tổng kiểm tra : 20 = x1 + x3 + x5 + x7 + x9 21 = x2 + x3 + x6 + x7 22 = x4 + x5 + x6 + x7 Nếu tổng kiểm tra vượt quá độ dài của từ mã thì không xử lý được. 1.8.4. Giải mã Hamming Mang từ mã nhận được tách thành các dấu mang tin và dấu kiểm tra Lập lại các tổng kiểm tra theo qui tắc sau: TKT 20 = x + a3 + a5 + a7 TKT 21 = y + a3 + a6 + a7 TKT 22 =z + a5 + a6 + a7 Nếu tất cả các tổng kiểm tra bằng 0 thì từ mã nhận được không sai. Nếu có ít nhất một TKT khác 0 thì từ mã nhận được có sai. Khi đó, lấy tất cả số thông tin của các TKT sai thì sẽ xác định được vị trí dấu sai VD: TKT 20 = 0 TKT 21 # 0 TKT 22 # 0 Vậy vị trí sai là bít a6 Bµi gi¶ng TruyÒn dÉn II Bé m«n HTTT & M¹ng 11