Bài giảng Truyền số liệu: Phần 2 - ĐH Sư Phạm Kỹ Thuật Nam Định

Chia sẻ: Mucnang222 Mucnang222 | Ngày: | Loại File: PDF | Số trang:83

Thêm vào BST

Báo xấu

43
lượt xem 3
download

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

Tiếp nối nội dung phần 1, nội dung Bài giảng Truyền số liệu: Phần 2 cung cấp cho người học các kiến thức như sau: Điều khiển liên kết dữ liệu; Mạng chuyển mạch, Mạng chuyển mạch kênh, Mạng chuyển mạch gói. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Truyền số liệu: Phần 2 - ĐH Sư Phạm Kỹ Thuật Nam Định

CHƯƠNG 5: ĐIỀU KHIỂN LIÊN KẾT DỮ LIỆU 5.1. Phát hiện lỗi và sửa sai Trong các hệ thống truyền dẫn số, lỗi xảy ra khi có một bit bị biến đổi giữa bên gửi và bên nhận. Có 2 dạng lỗi: Lỗi một bit và lỗi nhiều bit (burst) còn gọi là lỗi cụm. Hình 5. 1. Các dạng lỗi - Lỗi một bit: Chỉ có một bit bị sai trong một đơn vị dữ liệu (byte, ký tự, đơn vị dữ liệu, hay gói) Ví dụ: thay đổi từ 1 0 hoặc từ 0 1. 00000010 (STX: start of text) khi bị sai 1 bit dữ liệu nhận được 00001010 (LF: line feed) Hình 5. 2. Lỗi một bit Lỗi một bit ít xuất hiện trong phương thức truyền nối tiếp, mà thường xuất hiện trong truyền song song. - Lỗi cụm: có hai hoặc nhiều bit sai trong đơn vị dữ liệu. Hình 5.3. Lỗi nhiều bit (lỗi cụm) Lỗi cụm không có nghĩa là các bit bị lỗi liên tục, chiều dài của bệt tính từ bit sai đầu tiên cho đến bit sai cuối. Một số bit bên trong cụm có thể không bị sai. 114
Lỗi cụm thường xuất hiện trong truyền nối tiếp. Lỗi bit là không thể tránh khỏi trong quá trình truyền dẫn do nhiều nguyên nhân: đường truyền, lưu lượng truyền, loại mã đùng, loại điều chế, loại thiết bị phát, thiết bị thu, hay xuyên nhiễu và kết quả là một hoặc một số bit trong khung truyền bị lỗi. Để tăng xác suất thu đúng thông tin tại bên thu thì hệ thống cần sử dụng các biện pháp phát hiện và sửa sai tại đầu thu. Một số kỹ thuật thường được dùng: - Dùng bộ giải mã có khả năng tự sửa sai - Truyền lại một bộ phận của dữ liệu để thực hiện việc sửa sai, cách này gọi là ARQ - Automatic Repeat Request. Hình 5.4. Xử lý phát hiện lỗi Các phương pháp sửa lỗi đều dựa trên nguyên tắc sau: Khi một khung dữ liệu được truyền đi thì nó sẽ được chèn thêm một số bit kiểm tra gọi là mã phát hiện lỗi hay các bit kiểm tra. Mã này được tính toán như một hàm của các bit được truyền. Cụ thể, có một khối gồm k bit dữ liệu cần được truyền đi; từ khối bit này, người ta sử dụng một thuật toán phát hiện lỗi để tính ra mã phát hiện lỗi gồm (n – k) bit, với (n – k) < k, để đóng gói cùng dữ liệu tạo thành một khung gồm n bit truyền đi. Bên thu tách khung thu được thành k bit dữ liệu và (n – k) các bit kiểm tra. Sau đó, dựa vào k bit thông tin thu được, bên thu sử dụng thuật toán phát hiện lỗi tương tự như bên phát để tính toán lại các bit kiểm tra; đối chiếu với các bit kiểm tra thu được. Nếu chúng khác nhau thì kết luận quá trình truyền tin có lỗi. Nguyên tắc trên được thể hiện như sơ đồ hình 5.4. 115
5.1.1. Phƣơng pháp kiểm tra bit chẵn lẻ (parity bit) Phương pháp thông dụng nhất được dùng để phát hiện lỗi của bit trong truyền không đồng bộ và truyền đồng bộ hướng ký tự là phương pháp kiểm tra bit chẵn lẻ (parity bit). Với cách này máy phát sẽ thêm vào mỗi ký tự truyền một bit kiểm tra parity đã được tính toán trước khi truyền. Khi nhận được thông tin truyền, máy thu sẽ thực hiện các thao tác tính toán trên các ký tự thu được, và so sánh với bit kiểm tra parity thu được. Nếu chúng bằng nhau, được giả sử là không có lỗi, ở đây ta dùng từ giả sử, bởi vì cách này có thể không phát hiện được lỗi trong khi lỗi vẫn tồn tại trong dữ liệu. Nhưng nếu chúng khác nhau thì chắc chắn một lỗi xảy ra. Hình 5.5. Mạch tạo bit kiểm tra chẵn (VRC) của một dữ liệu 7 bit: 1100001 Hình 5.6. Mạch kiểm tra chẵn (VRC) của một dữ liệu 8 bit (11000011) Để tính toán bit parity cho một ký tự, số các bit trong mã ký tự được cộng module 2 với nhau và bit parity được chọn sao cho tổng số các bit 1 bao gồm cả bit parity là chẵn (even parity) hoặc là lẻ (odd parity). Trong bộ mã ASCII mỗi ký tự có 7 bit và một bit kiểm tra. Với kiểm tra chẵn giá trị của bit kiểm tra là 0 nếu số lượng các bit có giá trị 1 trong 7 bit là chẵn và có giá trị 1 trong trường hợp ngược lại. Với kiểm tra lẻ thì ngược lại. Thông thường người ta sử dụng kiểm tra chẵn và bit kiểm tra gọi là P. Giá trị kiểm tra đó cho phép ở đầu thu phát hiện những sai sót 116
đơn giản. Ví dụ 5.1: Kí tự Mã ASCII Bit kiểm tra P Từ mã phát đi A 1000001 0 10000010 E 1010001 1 10100011 Phương pháp kiểm tra bit chẵn lẻ chỉ phát hiện các lỗi đơn bit (số lượng bit lỗi là số lẻ) và không thể phát hiện các lỗi 2 bit (hay số bit lỗi là một số chẵn) 5.1.2. Kiểm tra tổng BSC (Block Sum Check) Khi các khối ký tự được truyền đi, xác suất một ký tự chứa lỗi bit gia tăng. Chúng ta có thể mở rộng các khả năng phát hiện lỗi từ một bit parity trên một ký tự (byte) bằng cách dùng một tập bit parity được tính từ toàn bộ khối ký tự trong khung. Với phương pháp này, mỗi ký tự trong khung được phân phối một bit parity như trên (parity hàng). Ngoài ra một bit mở rộng được tính cho mỗi vị trí bit (parity cột) trong toàn bộ khung. Tập các bit parity cho mỗi cột được gọi là ký tự kiểm tra khối, BCC (block check character) vì mỗi bit tạo nên ký tự này là tổng module 2 của tất cả các bit trong cột tương ứng. Ví dụ trong hình 5.7 dùng phương pháp kiểm tra lẻ cho các bit parity hàng, phương pháp kiểm tra chẵn cho các bit parity cột và giả sử khung chứa các ký tự in được. a) [ ] = ví dụ tổ hợp lỗi không phát hiện được Pr = Bit parity hàng 117
b) Hình 5.7. Ví dụ kiểm tra BSC: a) Các bit parity hàng và cột; b): Tổng bù 1 Trong ví dụ này thì, mặc dù các lỗi 2 bit trong một ký tự sẽ thoát khỏi kiểm tra parity theo hàng, nhưng chúng sẽ bị phát hiện bởi kiểm tra parity cột tương ứng. Tuy nhiên, điều này chỉ đúng khi không có lỗi 2 bit xảy ra trong cùng một cột tại cùng thời điểm. Xác suất xảy ra trường hợp này nhỏ hơn nhiều so với xác suất xảy ra lỗi 2 bit trong một ký tự. Việc dùng kiểm tra tổng khối cải thiện đáng kể các đặc trưng phát hiện lỗi của lược đồ kiểm tra chẵn lẻ. Một dạng khác của lược đồ trên dùng tổng bù 1 làm cơ sở cho kiểm tra tổng khối, thay vì dùng tổng module 2. Nguyên lý của lược đồ này minh họa trên hình 5.2 b. Trong lược đồ này, các ký tự trong khối cần truyền được xem như các số nhị phân không dấu. Trước hết, các số này được cộng với nhau dùng phép toán bù 1. Tất cả các bit trong kết quả được đảo ngược bit (mã bù 1) và kết quả đảo ngược được dùng như ký tự kiểm tra khối BCC (mã bù 1). Tại máy thu, tổng bù 1 của tất cả các ký tự trong khối, bao gồm cả ký tự kiểm tra được tính. Nếu không có lỗi xuất hiện thì kết quả sẽ bằng zero. Với phép toán bù 1, số nhớ cuối được dùng, là bất kỳ giá trị nào vượt ra ngoài vị trí bit có nghĩa lớn nhất được cộng vào tổng nhị phân hiện hữu. Zero trong phép bù 1 được biểu diễn bởi tất cả các bit nhị phân đều là 0 hoặc tất cả đều là 1. Từ hình 5.2 b, suy ra các đặc tính phát hiện lỗi của lược đồ này tốt hơn so với phương pháp tổng module 2. Tổng bù 1 được tính dễ dàng, nên được dùng như một phương pháp phát hiện lỗi trong một số ứng dụng yêu cầu hoạt động phát hiện lỗi chỉ được thực hiện bằng phần mềm. Ví dụ 5.2: Giả sử khối 16 bit sau được gửi đi dùng checksum 8 bit 10101001 00111001 Xác định các bit kiểm tra BCC và thực hiện việc kiểm tra khi bên thu thu đúng. 118
Giải: Tính toán các bit BCC: 10101001 00111001 Tổng 11100010 BCC 00011101 Chuỗi bit truyền đi 10101001 00111001 00011101 BCC Giả sử máy thu nhận được mẫu sau của ví dụ trên và không có lỗi, thì 10101001 00111001 Khi máy thu cộng ba phân đoạn lại: 10101001 00111001 00011101 Tổng 11111111 Kết quả không lỗi 5.1.3. Kiểm tra CRC (Cyclic Redundancy Check) Các mã trên đây khá thích hợp cho các ứng dụng trong đó xuất hiện các lỗi đơn bit ngẫu nhiên. Tuy nhiên, khi các khối lỗi xuất hiện, chúng ta phải dùng một phương pháp chắc chắn hơn. Một trong những loại mã phát hiện lỗi phổ biến nhất hiện nay là mã vòng dư thừa CRC (Cyclic Redundancy Check). Phương pháp kiểm tra tín hiệu bằng mã vòng được thực hiện như sau: Cách 1: Một từ mã được viết dưới dạng một đa thức C ( x)  Cn1 X n1  Cn2 X n2      C1 X  C0 (5.1) Tín hiệu cần phát đi trong khung gồm k bit sẽ được bên phát thêm vào (c = n-k) bit nữa để kiểm tra được gọi là Khung Check Sequence (FCS). Như vậy tín hiệu phát đi bao gồm n bit. Bên thu khi nhận được tín hiệu này sẽ đem chia cho một đa thức được gọi là đa thức sinh đã biết trước (bên phát và bên thu đều cùng chọn đa thức này). Nếu kết quả chia không dư coi như tín hiệu nhận được là đúng. Kết quả dư lại của phép chia chính là CRC . Bên thu sau khi nhận được thông báo cũng đem chia cho hàm biết trước như bên phát. Nếu kết quả bằng 0 quá trình truyền không gây sai số. Tính FCS gồm 4 bước: + Bước 1: Chuyển thông báo nhị phân thành đa thức M(x). Chọn hàm cho trước G(x) có bậc c, G( x)  X c  1 ( c chính là độ dài của CRC ) 119
+ Bước 2 : Nhân M (x) với X c M ( x) X c + Bước 3 : Thực hiện phép tính ta được phần nguyên và số dư G ( x) R( x) Q( x)  , R(x) chính là CRC (FCS ) . G ( x) + Bước 4 : Thành lập C (x) chính là thông báo cần truyền đi. C ( x)  X c  M ( x)  R( x) Ví dụ: Tín hiệu cần truyền là 110101 Ta có M ( x)  X 5  X 4  X 2  1 Chọn đa thức sinh G( x)  X 3  1 , có c  3 M ( x) X 3 R( x) Tính  Q( x)  G ( x) G ( x) X8 + X7 + X5 + X3 X3 + 1 X8 + X5 X5 + X4 + X + 1 X7 + X3 X7 + X4 X4 + X X3 +X X3 +1 X+1 Vậy R( x)  X  1 ; Q( x)  X 5  X 4  X  1 Thông tin cần truyền trên đường truyền là 110101011 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 module 2 nếu phần dư còn lại là không mã nhận được là đúng, nếu phần dư khác không mã nhận được là sai. Kiểm tra CRC : Ta có hàm phát đi: C ( x)  X c M ( x)  R( x) X c M ( x) R( x) Trong đó  Q( x)  , R(x) là đa thức dư G ( x) G ( x) Tại đầu thu ta thu được C ' ( x) đem giá trị thu được này chia cho đa thức sinh G(x) ta có: C ' ( x) X c M ( x)  R( x) X c .M ( x) R( x) R( x) R( x)     Q( x )   G ( x) G ( x) G ( x) G ( x) G ( x) R( x) R( x) C ' ( x) = Q( x )   (1  1) 2 mà (1  1) 2  0 →  Q( x) G ( x) G ( x) 120
Phần dư bằng 0 Ví dụ 5.3: Thông tin đã truyền đi là: 110101011 Thông tin nhận được là: 110101011. Thực hiện kiểm tra việc truyền tin không lỗi tại bên nhận. Giải: Kiểm tra việc truyền tin không lỗi tại bên nhận, điều này có nghĩa là truyền đúng tức là R(x) phải bằng 0 . Kiểm tra CRC như sau : Chuyển thông tin nhận được thành đa thức : 110101011 → X 8  X 7  X 5  X 3  X 1 Đa thức sinh mà cả bên thu và bên phát đều đã biết G( x)  X 3  1 đem đa thức nhận được chia cho đa thúc G(x) chắc chắn phần dư sẽ bằng 0 Thực hiện phép chia như sau : X8 + X7 + X5 + X3 + X + 1 X3 + 1 X8 + X5 X5 + X4 + X + 1 X7 + X3 X7 + X4 X4 + X3 + X X4+ X 3 X +1 X3 + 1 0 = R(x) Cách 2: Chúng ta có thể biểu diễn và xác định FCS trực tiếp từ các bit nhị phân theo cách dưới đây: Chúng ta định nghĩa: T = khung gồm n bit được truyền đi D = khối dữ liệu gồm k bit, k bit ở vị trí đầu của T F = mã kiểm tra FCS gồm (n – k) bit, (n-k) bit ở vị trí cuối của T P = mẫu gồm (n – k + 1) bit, đây là số chia được xác định trước Ta có thể biều diễn T như sau: T = 2n-kD + F F là chuỗi bit kiểm tra thêm vào sau các bit dữ liệu, và đảm bảo cho phép chia T/P không có dư. Thực hiện phép chia 2n-kD/P, ta có: 121
2n  k D R Q (5.2) P P Trong đó Q là thương, R/P là phần dư. Vì phép chia module 2 nên phần dư luôn ít hơn số chia 1 bit. Chúng ta lấy phần dư này làm FCS. Dưới đây, ta sẽ chứng minh R thỏa mãn điều kiện đảm bảo cho phép chia T/P không có dư. Thật vậy: T  2nk D  R T 2 n  k D  R 2n  k D R    (5.3) P P P P Thay biểu thức (5.2) vào (5.3), ta có: T R R Q  (5.4) P P P Tuy nhiên, một số nhị phân khi cộng module 2 với chính nó thì bằng 0. Do đó: T RR Q Q (5.5) P P Như vậy, phép chia T/P không có dư, hay T chia hết cho P. Qua đó, ta thấy, FCS dễ dàng được tạo ra bằng cách chia 2nk D cho P và sử dụng (n – k) bit phần dư làm FCS. Bên thu sẽ thực hiện chia T cho P, nếu dư bằng 0 thì kết luận khung không lỗi. Ví dụ 5.4: Cho bản tin cần truyền D = 1010001101 (10 bit) Mẫu P = 110101 (6 bit) Xác định khung cần truyền? Giải: FCS cần xác định gồm 5 bit. Do đó, n = 15. Bản tin được nhân với 25 : 101000110100000. Ta thực hiện phép chia module 2: 25D cho P: 122
Phần dư được cộng với 25D tạo thành chuỗi bit T = 101000110101110 được truyền đi. Tại bên thu, chuỗi bit T nhận được sẽ được chia cho P để kiểm tra. Nếu không có lỗi xảy ra thì phần dữ sẽ bằng 0. 5.1.4. Phát hiện và sửa sai theo Hamming Các phương pháp này được trình bày ở trên chỉ phát hiện lỗi truyền, không thể sửa sai. Phương pháp này được trình bày sau đây chỉ phát hiện lỗi sai mà còn có thể sửa sai cho một số bit nhất định. Hình 5.8 mô tả tổng quát quá trình xử lý phát hiện lỗi. Khi dữ liệu được đọc vào trong bộ nhớ, việc tính toán biểu diễn bởi hàm f được tiến hành trên dữ liệu này để tạo ra một mã sửa sai. Cả mã và dữ liệu được lưu giữ. Do đó, nếu một M bit từ (word) được lưu giữ, và mã có chiều dài là k bit thì kích thước thực sự được lưu giữ là M + K bit. 123
Khi các từ được lưu giữ được đọc ra, mã được dùng để phát hiện và có sửa lỗi. Một tập mới của K bit đã được tạo ra từ M bit dữ liệu và được so sánh với các bit dữ liệu và được so sánh với các bit mã đã lưu giữ. Sự so sánh sẽ cho ra một trong ba trường hợp: Tín hiệu báo lỗi Dữ liệu ra M Sửa lỗi Dữ liệu vào M M K Bộ nhớ f So sánh K K f Hình 5.8. Chức năng sửa sai 1. Không có lỗi. Các bit giữ liệu được gửi ra. 2. Có lỗi, và có khả năng sửa được. Các bit dữ liệu và các bit sai được nạp vào một bộ sửa lỗi, nó tạo ra một tập M bit đã sửa được gửi ra. 3. Một lỗi nhưng không thể sửa được. Đây là điều kiện để gửi thông báo. Một mã được đặc tính hoá bởi một số bit lỗi trong một từ mà nó có thể phát hiện lỗi và sửa sai. Các mã sửa sai đơn giản nhất là mã Hamming được phát minh bởi Richard Hamming tại Bell Laboratories.. Hình 5.9. Cơ sở của mã sửa lỗi Hamming 124
Hình 5.9 dùng lược đồ Venn để mô tả việc dùng mã này trên các từ 4 bit (M = 4). Với 3 vòng tròn giao nhau có 7 ngăn, gán 4 bit dữ liệu vào các ngăn trong, hình 5.9 a. Các ngăn còn lại được làm đầy với parity (bit kiểm tra chẵn lẻ). Mỗi bit parity được chọn sao cho tổng số bit 1 trong các vòng tròn là chẵn (hình 5.9 b). Do đó, vì vòng A bao gồm 3 bit dữ liệu 1, nếu bit parity là 1. Bây giờ, nếu một lỗi xảy ra thay đổi một trong các bit này (hình 5.9 c), sẽ dễ dàng nhận ra. Bằng cách kiểm tra các bit parity sẽ thấy sự trái ngược trong vòng tròn A và C. Chỉ một trong 7 ngăn vừa thuộc A vừa thuộc C nhưng không thuộc B. Sau đó có thể sửa lại bit trong ngăn này Để sáng tỏ hơn khái niệm này, tiếp theo có thể phát triển một mã có thể phát hiện và sửa sai các lỗi đơn trong các từ 8 bit. Khởi đầu cần xác định mã sẽ dài bao nhiêu. Xem hình 5.3, logic so sánh nhận hai giá trị K bit. Sự so sánh bit với bit được thực hiện bằng cách cộng module (xor) 2 ngõ nhập. Kết quả được gọi là syndrome. Do đó phải mỗi bit của syndrome là 0 hay 1 tuỳ vào sự giống hay khác nhau của vị trí bit của trong 2 ngõ nhập. Từ syndrome có chiều dài K bit và có giá trị trong dải từ 0 đến (2k -1). Giá trị 0 cho biết không có lỗi .Vì một lỗi có thể xảy ra trên bất kỳ M bit dữ liệu hay K bit kiểm tra nào, nên phải có: 2k-1>=M+K Bất đẳng thức này cho biết số bit cần thiết để sửa sai một bit bị sai trong một từ có M bit. Bảng 5.1 liệt kê số bit kiểm tra cần đối với chiều dài từ thay đổi. Từ bảng này, ta có thể thấy với từ 8 bit cần 4 bit cần 4 bit để kiểm tra. Để tiện dụng, Syndrom 4 bit với các đặc tính sau:  Nếu Syndrom chứa tất cả các bit 0, thì không có lỗi.  Nếu Syndrom chứa một và chỉ một bit đặt là 1 thì một lỗi xảy ra đối với một trong 4 bit kiểm tra. Không cần phải sửa.  Nếu Syndrom chứa nhiều hơn một bit 1 thì giá trị của sydrom chỉ vị trí của bit dữ liệu bị lỗi. Để sửa, bit dữ liệu này được đổi thành bit ngược lại. Bảng 5.1. Gia tăng chiều dài từ với sửa lỗi. Sửa lỗi đơn Sửa lỗi đơn/ Phát hiện lỗi kép Số bit dữ liệu Số bit kiểm tra %gia tăng Số bit kiểm tra %gia tăng 8 4 50 5 62,5 16 5 31,25 6 37,5 64 6 18,75 7 21,875 128 7 10,94 8 12,5 256 8 6,25 9 7,03 5 9 3,52 10 3,9 125
Các bit kiểm tra được tính toán như sau: C1 =M1  M2  M4  M5  M7 C2 =M1  M3  M4  M6  M7 C4 =M2  M3  M4  M8 C8 =M5  M6  M7  M8 Mỗi bit kiểm tra tính toán trên mối vị trí bit dữ liệu có số 1 nằm trong cột tương ứng. Do đó các vị trí 3,5,7,9 và 11 chứa 20, vị trí bit 3,6,7,10 và 11 chứa 21, vị trí bit 5, 6, 7, 12 chứa 22 và vị trí bit 9,10,11,12 chứa vị trí 23. Tổng quát, vị trí bit n được kiểm tra bởi các bit Ci sao cho  i  n Ví dụ, vị trí 7 được kiểm tra bởi các bit 4 và 1; và 7 = 4+2+1. Ví dụ 5.5 : Cho chuỗi bit dữ liệu là 0 0 1 1 1 0 0 1, và nếu vị trí bit 3 từ phải qua bị sai (thay vì 0 lại là 1) thì khi các bit kiểm tra mới được so sánh với các bit kiểm tra cũ, một từ Syndrom được hình thành: Kết quả này chỉ vị trí bit 6 từ vị trí bit 6 tử trái qua bị sai. Ví dụ 5.6: Cho chuỗi bit dữ liệu 01100101 được mã hóa theo mã sửa lỗi Hamming với các bit kiểm tra được tính toán như sau: C1 =M1  M2  M4  M5  M7 C2 =M1  M3  M4  M6  M7 C4 =M2  M3  M4  M8 C8 =M5  M6  M7  M8 Giả sử chuỗi bit dữ liệu trên khi truyền đi bị lỗi ở vị trí thứ 3 tính từ bit có trọng số lớn nhất MSB. Hãy sử dụng phương pháp phát hiện và sửa sai Hamming để sửa lỗi này? Giải: Giả sử chuỗi bit dữ liệu trên khi truyền đi bị lỗi ở vị trí thứ 3 tính từ bit có trọng số lớn nhất MSB nên dữ liệu thu được là: 01000101 126
Vị trí bit 12 11 10 9 8 7 6 5 4 3 2 1 Bit dữ liệu M8 M7 M6 M5 M4 M3 M2 M1 C8 C4 C2 C1 Bit kiểm tra 1 1 1 1 0 0 0 0 C80 1 0 0 0 1 1 1 0 C41 0 1 1 0 1 1 0 1 C20 0 1 0 1 1 0 1 1 C10 Từ được lưu 0 1 1 0 0 1 0 1 Từ thu được 0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 0 C81 1 0 0 0 1 1 1 0 C41 0 1 1 0 1 1 0 1 C21 0 1 0 1 1 0 1 1 C10 So sánh bit kiểm tra cũ với bit kiểm tra mới C8 C4 C2 C1 0 1 0 0 1 1 1 0 1 0 1 0 Kết quả có giá trị bằng 10 vậy vị trí bit thứ 10 bị sai, thực hiện sửa vị trí thứ 6 là bit 0 thành bit 1. Vậy chuỗi dữ liệu thu đúng phải là : 01100101. 5.2. Nén dữ liệu Chúng ta vẫn giả thiết rằng nội dung thông tin truyền đi bao gồm dữ liệu gốc dưới dạng chuỗi ký tự có chiều dầi cố định. Cho dù đây là trường hợp của nhiều ứng dụng truyền số liệu, vẫn còn có những trường hợp khác, trong đó dữ liệu được nén trước khi truyền đi, nén dữ liệu là một việc làm thiết yếu trong các dịch vụ truyền dẫn công cộng, ví dụ truyền qua mạng PSTN, vì trong các mạng các mạng như vậy việc tính cước dựa vào thời gian và cự ly truyền. Ví dụ chúng ta truyền dữ liệu qua mạng PSTN dùng tốc độ 4800 bps, thời gian truyền hết dữ liệu là 20 phút. Rõ ràng nếu dùng nén dữ liệu chúng ta có thể giảm một nửa số lượng dữ liệu truyền, và có thể tiết kiệm 50% giá tiền. Điều này tương đương với việc dùng tốc độ truyền 9600 bps nhưng không nén. Trong thực tế chúng ta có thể dùng một loạt các giải thuật nén khác nhau, mỗi giải thuật sẽ phù hợp với một loại dữ liệu. Vài modem thông minh sẽ cung cấp đặc trưng nén thích nghi tự động thực hiện các giải thuật nén phù hợp với loại dữ liệu đang được truyền 127
5.2.1. Nén nhờ đơn giản mã cho các chữ số Khi các khung chỉ bao gồm các ký tự số học đang được truyền, chúng ta có thể tiết kiệm đáng kể bằng cách giảm số bit trên mỗi ký tự từ 7 xuống 4 thông qua mã BCD, thay cho mã ASCII. 5.2.2. Nén theo mã hoá quan hệ Một phương pháp khác được sử dụng khi truyền dữ liệu số học kế tiếp chỉ khác nhau phần nhỏ về giá trị là chỉ gửi lượng khác nhau giữa các giá trị này cùng với một giá trị tham khảo. Điều này được gọi là mã hóa quan hệ và nó có thể đem lại hiệu quả đặc biệt trong các ứng dụng ghi nhân dữ liệu. Ví dụ nếu giám sát từ xa mực nước của dòng sông thường đọc mức nước theo các khoảng thời gian định trước. Để tối thiểu thời gian cần truyền thay vì truyền giá trị chỉ mức nước tuyệt đối, chúng ta chỉ cần truyền đi các giá trị khác nhau. 5.2.3. Nén bằng cách bỏ bớt các ký tự giống nhau Thông thường khi các khung gồm các ký tự có thể in đang được truyền thường xuất hiện chuỗi lặp lại các ký tự giống nhau. Thiết bị điều khiển tại máy phát sẽ quét nội dung của khung trước khi truyền nếu gặp một chuỗi ký tự liên tiếp giống nhau thì chúng sẽ được thay thế bởi tuần tự số và ký tự. 5.2.4. Nén theo mã hoá Huffman Phương pháp nén theo mã Huffman khai thác một đặc tính là không phải tất cả các ký hiệu trong một khung có cùng tần suất xuất hiện, ví dụ trong một khung bao gồm một chuỗi ký tự ,vài ký tự nào đó xuất hiện nhiều hơn các ký tự khác. Thay vì dùng một số bit nhất định trên một ký tự, chúng ta dùng một lược đồ mã hoá khác trong đó các ký tự xuất hiện thường xuyên được mã hoá với số bit ít hơn các ký tự có tần số xuất hiện thấp. Do đó lược đồ này là dạng mã hoá thống kê. Trước hết, chuỗi ký tự truyền đợc phân tích và các loại ký tự và tần suất xuất hiện đợc xác định. Hoạt động mã hoá sau đó liên quan đến việc tạo ra một cây không cân bằng trong đó một số nhanh (là các mã trong thực tế) ngắn hơn một số nhánh khác. Mức độ thiếu cân bằng là một ham của tần suất xuất hiện các ký tự, càng đợc trải rộng ra độ mất cân bằng trong cây càng lớn. Kết quả cuối cùng một cây được gọi là cây Huffman. 128
Hình 5.10. Cấu trúc cây mã Huffman a) Cây sau cùng với các mã; b) Sự dẫn xuất cây. Một cây Huffman là một cây nhị phân với các nhánh được gắn giá trị 0 hay 1. Xuất phát của cây thường là một đỉnh (hình học), trong thực tế được gọi là node gốc(root node), và một điểm tại đó một nhánh được rẽ ra coi như node nhánh (branch node). Điểm kết thúc của một nhánh gọi là node lá (leaf node), là các vị trí được gán cho các ký hiệu đang được mã hoá. Một ví dụ về Huffman được trình bày hình 5.9(a). Cây này tương ứng với các ký tự AAAABBCD. Khi mỗi nhánh chia ra, một giá trị nhị phân 0 hay 1 được gán cho mỗi nhánh mới: một giá trị nhi phân 0 cho nhánh trái và một giá trị nhị phân 1 cho nhánh phải. Mỗi từ mã được dùng cho mỗi ký tự (được ghi tại các node lá) được xác định bằng cách dò theo đờn dẫn từ node gốc đến node lá tương ứng và hình thành một chuỗi các 129
giá trị nhị phân nằm trên đường dẫn. Từ các mã này chúng ta có thể suy ra sẽ dùng: 4x1 + 2x2 + 1x3 + 1x3 = 14 bit để truyền chuỗi hoàn chỉnh AAAABBCD. Chúng ta cũng có thể suy ra lượng bit trung bình trên mỗi từ mã bằng lấy lượng bit trong mỗi từ mã nhận với xác suất xuất hiện rồi cộng toàn bộ lại. Cụ thể là : 1x0,5 + 2x0,25 + 3x0,125 + 3x0,125=1,75 bit/từ mã Lượng bit trung bình tối thiểu trên một từ mã theo lý thuyết để truyền chuỗi thông điệp được gọi là entropy H, của thông điệp này. Có thể tính toán H bằng cách dùng công thức suy ra từ luật Shannon: n H   Pi log 2 Pi bit/ từ mã (5.6) i 1 Trong đó n là số ký tự trong thông điệp và pi là xác suất xuất hiện của ký tự i trong thông điệp. Do đó thông điệp AAAABBCD, lượng bit trung bình tối thiểu trên một từ mã là : H= - (0,5log 2 0,5 + 0,25log 2 0,25 +0,125 log 2 0,125 +0,125 log 2 0,125)=1,75 bit/ từ mã Trong trường hợp này chúng ta có cùng kết quả khi dùng mã hoá Huffman. Dùng từ mã ASCII 7-bit sẽ cần 8x7=56 bit đề truyền toàn chuỗi thông điệp này, con số này nhiều hơn đáng kể so với 14 bit khi dùng mã hoá Huffman. Trong thực tế, điều này không phải là một so sánh chính xác vì với mã hoá Huffman, máy thu phải biết được tập ký tự biến đổi đang đợc truyền và các từ mã tương ứng, hay nói cách khác là cây Huffman. Một so sánh tốt hơn là xem sét số bit yêu cầu với mã hoá nhị phân thờng: bốn ký tự (A-D) cần hai bit cho mỗi ký tự, vậy cần truyền 8 ký tự. Rõ ràng, lượng tiết kiệm không đang kể. Nhìn chung mã hoá Huffman là hiệu quả nhất khi các ký tự dang truyền có phân bố tần số rộng và các chuỗi ký tự dài. Ngược lại, nó không phù hợp cho truyền dữ liệu mã nhị phân của máy tính vì các byte 8 bit thờng xuất hiện với tần số như nhau. Để diễn tả làm thế nào xác định cây Huffman trong hình 5.10a, chúng ta phải dùng thêm thông tin liên quan đến tần số xuất hiện mỗi ký tự nh liệt kê trong hình 5.10b. Các ký tự được liệt kê trong một cột theo thứ tự giảm dần của tham số định lượng. Chúng ta có thể suy ra cây như sau: Hai node lá đầu tiên phía dới danh sách C1 và D1 lần lượt được gán là nhánh 1 và nhánh 0 của một node nhánh. Sau đó hai node lá sẽ được thay thế bởi một node nhánh có định lượng bằng tổng hai node lá 2.1, cột mới được hình thành chứa node mới, sự kết hợp với các node còn lại từ cột đầu tiên, việc sắp xếp lại phải theo thứ tự định lượng giảm dần. Thủ tục này được lặp lại cho đến khi chỉ còn hai node. Để suy ra từ mã kết quả cho mỗi ký tự chúng ta bắt đầu với ký tự trong cột đầu tiên và sau đo tiến hành liệt kê các số trong nhánh 0 hay 1 khi chúng gặp phải. Do đó 130
cho ký tự A số nhánh là 1 trong cột cuối cùng trong khi cho ký tự C nhánh đầu tiên là 1 sau đó là 0 tại node nhánh 2 và cuối cùng là 0 tại node nhánh 4. Tuy nhiên, các từ mã bắt đầu tại gốc chứ không phải tại node là vì các từ mã thực tế là ký tự ngược của các số này. Sau đó cây Huffman được xây dựng dễ dàng từ tập từ mã. Chúng ta kiểm tra xem đây có phải là cây tối ưu và do đó là tập từ mã tối ưu hay không bằng cách liệt kê kết quả của tất cả các node nhánh và node là trong cây bắt đầu có định lượng nhỏ nhất và xử lý từ trái sang phải và từ đó lên trên các từ mã là tối ưu nếu danh sách kết quả ra tăng theo định lượng. Ví dụ 5.7: Một chuỗi thông điệp được truyền giữa hai máy tính PSTN. Các thông điệp bao gồm chỉ các ký tự từ A đến H. Phân tích cho thấy tần số xuất hiện của mỗi ký tự như sau: A và B = 0,25 C và D = 0,14 E,F,G and H =0,055 a) Dùng công thức Shannon để suy ra lượng bit trung bình tối thiểu trên một ký tự. b) Dùng mã hoá Huffman để suy ra một tập từ mã và chứng minh tập này là tối ưu bằng cách xây dựng cây mã Huffman tương ứng. c) Suy ra số bit trung bình trên một ký tự cho tập mã này và so sánh với: (i) Giá trị Shannon (ii) Các từ mã nhị phân có chiều dài cố đinh (iii) Các từ mã ASCII 7 bit Giải: a) Theo công thức Shannon: n Entropy H   Pi log 2 Pi . Do đó: H = -(2(0,25 log 2 0,25) + 2(0,14 log 2 0,14) + i 1 4(0,055log 2 0,055))=1+0,794 + 0,921 = 2,715 bit/ từ mã b) Việc suy ra bộ từ mã dùng mã hoá Huffman được trình bày trên hình 5.11 a. Trước hết các ký tự được liệt kê theo thứ tự trong số và hai ký tự dưới cùng của danh sách được gán nhanh (1) và (0). Tuy nhiên trong trường hợp này khi hai node kết hợp lại, trong số của node nhánh (0,11) lớn hơn trong số của hai ký tự E và F (0,055). Từ đó node nhánh này được chèn vào danh sách thứ hai có thứ tự cao hơn cả E và F. Thủ tục tương tự được lặp lại cho đến khi danh sách chỉ còn lại một node thì dừng. Cây Huffman tương ứng với tập mã được suy ra được biểu diễn trên hình 5.6 b, và đây là cây tối ưu vì tất cả các node nhánh và node lá đều gia tăng theo thứ tự số học. c) Số bit trung bình trong một từ mã dùng Huffman là: 2 (2 x 0,25) + 2 ( 3 x 0,14) + 4 (4 x 0,055) = 2,72 bit/ từ mã, bằng 99,8 % giá trị Shannon Dùng các từ mã nhị phân có chiều dài cố định: Từ A đến H có 8 ký tự do đó có 3 bit trong mỗi từ mã, bằng 90,7 % giá trị Huffman: 131
(b) Hình 5.11. Ví dụ mã hoá Huffman: a) Phát sinh từ mã; b) Cây mã Huffman. Dùng các từ mã ASCII 7 bit : 7 bit trong một từ mã, bằng 38,86 % giá trị Huffman. Vì ký tự trong dạng mã hoá này có số bit thay đổi, nên luồng bit nhận được phải được dich ra theo từng bit thay vì dịch theo ranh giới 8 bit cố định. Do thứ tự các bit được gán trong quá trình mã hoá mà các từ mã Huffman có một đặc tính duy nhất là các từ mã ngắn hơn sẽ không bao giờ trùng với phần đầu của một từ mã dài hơn. Ví dụ nếu 011 là một từ mã hợp lệ thì không có một từ mã nào dài hơn chứa 011 kể từ bit đầu. Chúng ta có thể kiểm chứng điều này từ các mã được suy ra từ ví dụ trên. Đặc tính này còn được gọi là đặc tính tiền tố (prefix), có nghĩa là luồng bit nhận được có thể bị giải mã một cách đơn giản bằng cách dò từng bit một cho đến khi tìm 132
thấy được từ mã hợp lệ. Một lưu đồ thuật toán giải mã thích hợp như hình 5.6. Giải thuật này giả sử ở máy thu đã có bảng mã và cũng giữ từ mã ASCII tương ứng. 5.3. Điều khiển luồng 5.3.1. Tổng quan Nếu số lượng dữ liệu truyền giữa hai thiết bị là nhỏ, thiết bị phát có thể truyền tất cả dữ liệu ngay tức thời vì máy thu có đủ tài nguyên để tiếp nhận dữ liệu. Tuy nhiên, trong nhiều tình huống truyền tin điều kiện này không thể có. Do đó chúng ta phải dùng kỹ thuật để đảm bảo máy thu không bỏ qua bất kỳ phần tử dữ liệu nào do không đủ tài nguyên để lưu giữ. Điều này hết sứ quan trọng khi hai thiết bị đang truyền tin thông qua mạng số liệu, khi mà rất nhiều mạng sẽ đệm số liệu trong các bộ đệm có kích thước giới hạn. Nếu hai thiết bị hoạt động với tốc độ khác nhau, chúng ta thường phải điều khiển số liệu ngõ ra của thiết bị tốc độ cao hơn để ngăn chặn trường hợp tắc nghẽn trên mạng. Điều khiển luồng thông tin giữa hai thiết bị truyền thường được gọi vắn tắt là điều khiển luồng (flow control). Như vậy, điều khiển luồng là tập hợp các thủ tục để giới hạn lượng dữ liệu mà bên phát có thể gửi đi trước khi nhận được tín hiệu xác nhận ACK. - Lưu lượng truyền này không được phép làm quá tải bên thu. - Thiết bị thu thông báo cho bên gửi biết về các giới hạn dữ liệu và có thể yêu cầu gửi ít hơn hay tạm dừng truyền. - Thiết bị thu còn có bước kiểm tra và xử lý dữ liệu trước khi sử dụng, điều này làm chậm đáng kể lưu lượng truyền dẫn, nên bên thu thường có thêm một khối nhớ tạm, thường được gọi là bộ nhớ đệm (buffer). 5.3.2. Các phƣơng pháp điều khiển luồng Có hai phương pháp được dùng là: dừng - và - chờ và cửa sổ trượt. Hình 5.12. Hai phương pháp dùng trong điều khiển lưu lượng 133