Câu 36:Vấn đề dò lỗi ,khắc phục lỗi tại tâng liên kết .Trình bày các kỹ thuật kiểm tra chẵn lẻ ,checksum và CRC

1.1.1. * Tính chẵn lẽ (Parity)

Parity thì được sử dụng trong chuỗi  giao thức truyền thông tuần tự,  theo đó chúng ta chuyển một ký tự tại một thời điểm. ví dụ, nếu các bít thông tin 1 0 1 1 0 1 0

Sau đó bit bổ sung được thêm vào, được gọi là một bit parity(chẵn lẽ). bit chẵn lẽ có thể được thêm vào một cách như vậy mà tổng số 1 trở nên chẵn. Trong trường hợp này, nó được gọi là parity chẵn. Trong dòng bit ở trên, đã có 4 bit 1, do đó bit 0 được thêm vào như là một bit chẳn lẽ. Các dòng bit truyền là : 1 0 1 1 0 1 0 0 Trong trường hợp bit chẵn lẻ là bit lẻ, thì bit được thêm vào sẽ làm cho tổng số 1 trong dãy bit lẻ. Đối với bit chẵn lẽ là bit lẻ, các bit được thêm vào trong trường hợp trên là 1 và dòng bit truyền là : 1 0 1 1 0 1 0 1 Ở đầu bên nhận, từ 7 bit đầu tiên, bên nhận sẽ tính toán bit chẵn lẽ dự kiến. Nếu nhận được bit chẵn lẽ và tính toán tính chẵn lẽ là hợp lý, thì người ta cho rằng bên nhận nhận được chuỗi bit đúng.

1.1.2. Parity(chẵn lẻ) bit là một bit phụ được thêm vào chuỗi bit để kiểm tra lỗi. Trong parity chẵn, bit phụ sẽ làm cho tổng các số 1 trong chuỗi bit chẵn. Trong trường hợp parity lẻ, thì bit phụ sẽ làm cho tổng các số 1 trong chuỗi bit lẻ. parity bit được sử dụng trong truyền thông tuần tự. Checksum

 Giả sử bạn muốn gửi 2 ký tự C và U. Giá tri ASCII 7-bit cho những ký tự này là.

C    1 0 0 0 0 1 1

U    1 0 1 0 1 0 1

Ngoài ra để truyền những chuỗi bit này,biểu diễn nhị phân caủa tổng 2 ký tự này cũng được gởi.Giá trị của C là 67,của U là 85,tổng là 152. Biểu diễn nhị phân của 152 là 1 0 0 1 1 0 0 0. Chuỗi bit này cũng được gắn với chuỗi nhị phân gốc, tương ứng với C và U, trong khi truyền dữ liệu. Checksum của những bit thông tin được tính toán sử dụng số học nhị phân đơn giản. Checksum được sử dụng một cách rộng rãi bởi vì nó tính toán rất dễ dàng. Tuy nhiên checksum không thể nhận ra tất cả các lỗi. Vì thế, chuỗi bit truyền là

1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0

Khi đã nhận xong, checksum lại tính toán một lần nữa. Nếu tổng kiểm tra nhận được hợp với tổng kiểm tra tính toán. Sau đó bên nhận xác nhận đã nhận dữ liệu. Tổng kiểm tra không thể nhận ra tất cả lỗi. Ngoài ra nếu ký tự gửi đi trong lệnh khác,tức là,nếu chuối thay đổi, tổng kiểm tra sẽ giống nhau và do đó bên nhận xác nhận dữ liệu là đúng. Tuy nhiên, tổng kiểm tra được sử dụng chính bởi vì nó tính toán rất dễ dàng, Và nó cung cấp khả năng phát hiện ra lỗi khá tốt.

Chú ý: Checksum được sử dụng cho việc nhận lỗi trong giao thức TCP/IP để kiểm tra dù gói được nhận chính xác.Thuật toán khác được sử dụng cho việc tính toán của checksum.

1.1.3. CRC

CRC là kỹ thuật mạnh để phát hiện lỗi. Vì thế nó được dùng rộng rãi trong mọi hệ thống giao tiếp dữu liệu. Các bit bổ sung thêm vào các bit thông tin được gọi là các bit CRC. Những bit này có thể là 16 hoặc 32. Nếu các bit bổ sung là 16, CRC được biểu diễn như CRC-16.CRC-32 sử dụng 32 bit bổ sung. Đó là những tiêu chuẩn quốc tế cho việc tính toán của CRC-16 và CRC-32. Việc tính toán CRC là rất quan trọng, chương trình C tính toán CRC-16 và CRC-32 là trong vi dụ code dưới đây. Khi chương trình này được thi hành, các bit thông tin và CRC theo ký hiệu hệ thập lục phân sẽ được hiển thị.

Việc nhận lỗi sử dụng CRC là rất đơn giản. Ở bên truyền, CRC được thêm vào các bit thông tin. Khi việc nhận kết thúc, bên nhận tính toán CRC từ những bit thông tin và nếu CRC tích hợp CRC nhận, vậy thì người nhận biết được những bit thông tin là đúng. CRC-16 và CRC-32 là hai thuật toán tiêu chuẩn được sử dụng để tính chu kỳ kiểm tra dư thừa. Các bit CRC bổ sung (16 và 32) được nối thêm vào các bit thông tin ở bên phát. Tại phía thu, các CRC nhận được so sánh với ước tính. Nếu kết hợp hai, các bit thông tin được coi là đã nhận được một cách chính xác. Nếu hai không phù hợp, nó cho thấy rằng có những sai sót trong các bit thông tin.

a)                  Ph­ương pháp CRC:

Một xâu bít bất kỳ đ­ợc xem như­ một tập các hệ số (0 và 1) của một đa thức đại số. Nếu xâu gồm k bít thì đa thức t­ương ứng sẽ có bậc là k-1 gồm các số hạng từ x0 đến xk-1.

Ví dụ: 110001            x5 + x4 + x0 = x5 + x4 + 1

Phư­ơng pháp CRC sẽ xây dựng một xâu các bít kiểm tra và ghép vào xâu bít cần truyền, đư­ợc gọi là dãy Checksum. Dãy Checksum đ­ược xây dựng như­ sau:

* Chọn tr­ước một đa thức gọi là đa thức sinh G(x) có hệ số cao nhất và thấp nhất là 1

* Checksum đ­ược tìm thoả mãn điều kiện đa thức t­ương ứng với xâu ghép gồm xâu gốc và checksum phải chia hết (Modulo 2) cho G(x).

* Khi nhận đư­ợc xâu bít, để kiểm soát lỗi lấy đa thức nhận đ­ược chia (Modulo 2) cho đa thức sinh G(x). Nếu không chia hết thì chắc chắn có lỗi, tr­ường hợp ng­ược lại chư­a khẳng định là không có lỗi.

b)Thuật toán CRC

Giả sử đa thức sinh đư­ợc chọn là G(x) có bậc là r

Xâu bít cần truyền t­ương ứng với đa thức M(x) có bậc m .

Các b­ước để xây dựng dãy Checksum nh­ sau:

Ø       Thêm r bits 0 vào cuối xâu bits cần truyền xâu ghép sẽ gồm đư­ợc tìm thoả mãn điều kiện đa thức tư­ơng ứng với xâu ghép gồm (m + r) bits tư­ơng ứng với đa thức xr M(x).

Ø       Chia Modulo 2 xâu bits t­ương ứng xr M(x) cho xâu bít t­ương ứng với G(x).

Ø       Lấy số bị chia ở b­ước trên trừ đi Modulo 2 cho số d­.

Kết quả sẽ là xâu bít đư­ợc truyền đi ( xâu gốc ghép với Checksum). Ký hiệu đa thức tư­ơng ứng cho xâu đó là P(x). Rõ ràng P(x) chia hết cho G(x).

   Khi nhận, giả sử xâu bít nhận đ­ược có đa thức t­ương ứng là Q(x) chia modulo 2 cho G(x).

   Giả thiết rằng Q(x) =  P(x) + E(x), trong đó E(x) đ­ược gọi là đa thức lỗi.

Ví dụ.

Giả sử xâu gốc là 1101011011 suy ra M(x) = x9 + x8 + x6 + x4 + x3 + x + 1

có bậc m = 9; Chọn 10011 t­ương ứng G(x)= x4 + x + 1 (r=4).

+ B­ước1. Xâu gốc ghép 4 bits 0 ta đ­ợc 11010110110000.

+ B­ước 2. Chia modulo 2

  11010110110000 /(modulo2) 10011 ta đ­ược thư­ơng là 1100001010 và phần d­ là 1110.

+Bư­ớc 3. Xâu cần truyền là

 11010110110000 - (modulo2) 1110  = 11010110111110 là P(x)

Theo ph­ương pháp này việc lựa chọn đa thức sinh chuẩn G(x) sẽ giúp cho việc phát hiện lỗi rất hiệu quả.

  Hiện nay ngư­ời ta xây dựng 3 đa thức sinh chuẩn quốc tế:

  CRC – 12 =  x12 + x11 + x3 + x2 + x + 1

   CRC – 16 = x16 + x15 + x2 + 1

   CRC – CCITT = x16 + x12 + x5 + 1