Các loại mã trong truyền dữ liệu

khi được chuyển đổi thành các tín hiệu số để truyền đi Một yếu tố quan trọng trong hệ thống thông tin là độ chính xác, thiếu yếu tố này hệ thống xem như không có giá trị sử dụng, nên kèm theo bản tin thường phải thêm vào các từ mã có khả năng phát hiện lỗi và thậm chí sửa được lỗi. Ngoài ra, nếu số lượng bit dùng để mã hóa cùng một đối tượng càng ít thì với cùng vận tốc truyền, lượng thông tin truyền của hệ thống càng lớn mà lại hạn chế được khả năng xảy ra lỗi. Do đó việc giảm số lượng bit dùng mã hóa cũng là một vấn đề cần được quan tâm. Chương này bàn đến một số phương pháp mã hóa dữ liệu phổ biến để tạo các loại mã có khả năng phát hiện lỗi, phát hiện và sửa lỗi, các loại mã nén. 3.1 MÃ NHỊ PHÂN CỦA CÁC CHỮ SỐ Để biểu diễn các chữ và số người ta dùng các mã nhị phân. Một số nhị phân n bit biểu thị được 2n ký tự (chữ, số, các dấu hiệu ....) Các bộ mã phổ biến trong truyền dữ liệu là : mã Baudot, mã ASCII và mã EBCDIC 3.1.1 Mã Baudot Là bộ mã nhị phân dùng 5 bit để biểu diển chữ số và một số dấu hiệu. Bảng 3.1 Bộ mã Baudot Mã Chữ Dấu/Số Mã Chữ Dấu/Số _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 2 110001001101 110100101000 010110010110 010101100110 101111001001 0011100110 00011 01101 A B C D E F G H I J K L M N O P - ? : $ 3 ! & # 8 ' ( ) . , 9 0 11101 01010 10100 00001 11100 01111 11001 10111 10101 10001 11111 11011 00100 00010 01000 00000 Q R S T U V W X Y Z LTRS FIGS SPC CR LF NULL 1 4 BELL 5 7 ; 2 / 6 " LTRS FIGS SPC CR LF NULL Với n = 5 chỉ có 25 = 32 mã khác nhau, không đủ để biểu diển các ký tự chữ và số nên một số mã phải biểu thị cả hai và chúng được phân biệt bằng cách kèm theo ký tự FIGS hoặc LTRS ở trước. Thí dụ: mã của đoạn văn NO. 27 có dạng như sau : LTRS N O FIGS . SPC 2 7 11111 00110 00011 11011 00111 00100 11001 11100 Khi dùng mã Baudot để truyền bất đồng bộ, số bit stop luôn luôn là 1,5 3.1.2 Mã ASCII Là bộ mã thông dụng nhất trong truyền dữ liệu. Mã ASCII dùng số nhị phân 7 bit nên có 27 = 128 mã, tương đối đủ để diễn tả các chữ, số và một số dấu hiệu thông dụng. Từ điều khiển dùng trong các giao thức truyền thông thường lấy trong bảng mã ASCII. Khi truyền bất đồng bộ dùng mã ASCII số bit stop là 1 hoặc 2. Bảng 3.2 trình bày mã ASCII cùng các từ điều khiển. * Từ điều khiển trong văn bản: BS (Back space): chỉ cơ chế in hay con trỏ được dời lui một vị trí. Nó có thể được dùng để in 2 ký tự ở một vị trí (thường dùng để gạch dưới) hay để in đậm một ký tự (in 1 ký tự 2 lần ở cùng vị trí). Trên màn hình (CRT) chữ sau sẽ thay cho chữ trước. HT (Horizontal Tab): chỉ cơ chế in hay con trỏ được dời tới vị trí tab kế cận hay vị trí dừng. LF (Line Feed): chỉ cơ chế in hay con trỏ được dời xuống đầu dòng kế. VT (Vertical Tab): chỉ cơ chế in hay con trỏ được dời đến dòng kế của chuỗi dòng đã đánh dấu. FF (Form Feed): chỉ cơ chế in hay con trỏ được dời đến điểm bắt đầu của trang (màn ảnh) sau CR (Cariage Return): chỉ cơ chế in hay con trỏ được dời đến điểm bắt đầu trên cùng một dòng Bảng 3.2 Mã ASCII Bit 765→ 000 001 010 011 100 101 110 111 Bit 4321↓ 0 1 2 3 4 5 6 7 _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 3 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0 1 2 3 4 5 6 7 8 9 A B C D E F NULL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI DLED C1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US SP ! " # $ % & ` ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^(↑) _(←) ' a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~ DEL Thí dụ: ký tự D là 1000100 = 44H Ý nghĩa các từ trong bảng mã ASCII * Từ điều khiển trong truyền thông SOH (Start of Heading): bắt đầu của phần đầu bản tin. Nó có thể chứa địa chỉ, chiều dài bản tin hay dữ liệu dùng cho kiểm tra lỗi. STX (Start of Text): bắt đầu văn bản đồng thời kết thúc phần đầu. Thường đi đôi với ETX. ETX (End of Text): kết thúc văn bản EOT (End of Transmission): chấm dứt truyền ENQ (Enquiry): yêu cầu một đài xa tự xác định (identify itself). ACK (Acknowledge) : từ phát bởi máy thu để báo cho máy phát đã nhận bản tin đúng. NAK (Negative Acknowledgment): từ phát bởi máy thu để báo nhận bản tin sai. SYN (Synchronous/Idle): dùng bởi một hệ thống truyền đồng bộ để thực hiện đồng bộ. Khi không có dữ liệu để phát, máy phát của hệ thống đồng bộ phát liên tục các từ SYN ETB (End of Transmission Block): chỉ sự chấm dứt một khối của bản tin. * Information separator FS (File Separator), GS (Group Separator), RS (Record Separator), US (United Separator): Dùng cho sự phân cách. Chữ đầu chỉ thành được phân cách (F: File, G: Group, R: Record (bảng ghi), U: Unit (đơn vị)) * Miscellaneous (Linh tinh) NUL (Null): ký tự rổng, dùng lấp đầy khoảng trống khi không có dữ liệu BEL (Bell): dùng khi cần báo sự lưu ý. SO (Shift Out): chỉ các tổ hợp mã theo sau được thông dịch bởi ký tự ngoài tập hợp ký tự chuẩn cho tới khi gặp từ Shift In. SI (Shift In): chỉ tập hợp mã theo sau được thông dịch bởi ký tự chuẩn. DEL (Delete): dùng bỏ từ SP (Space): khoảng cách từ DLE (Data Link Escape): dùng để chỉ sự thay đổi nghĩa của các từ theo sau. Nó có thể cung cấp một sự điều khiển phụ, hay cho phép gửi ký tự dữ liệu có một tổ hợp bit bất kỳ. DC1, DC2, DC3, DC4 (Device Control): từ dùng cho sự điều khiển thiết bị. CAN (Cancel): chỉ dữ liệu đặt trước nó không có giá trị, do dò được lỗi. EM (End of Medium): chỉ sự kết thúc về mặt vật lý của một card, băng hay môi trường khác. SUB (Substitute): thay thế một từ bị lỗi hoặc không có giá trị ESC (Escape) : từ tăng cường để cung cấp một mã mở rộng. _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 4 3.1.3 Mã EBCDIC (Extended BCD Information Code) Là bộ mã 8 bit được dùng rộng rãi trong hệ thống thông tin dùng máy tính IBM. Bảng 3.3 trình bày mã EBCDIC và các ký tự điều khiển. Vì mã ký tự chiếm 8 bit nên muốn dùng parity phải dùng bit thứ 9 (các thanh ghi trong các USART thường có 8 bit) do đó mã EBCDIC thường được dùng trong những chức năng đặc biệt như trong các ứng dụng đồ họa. Bảng 3.3 Mã EBCDIC High Lơw 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 NULL DLE DS SP & 0 1 SOH DC1 SOS a J A J 1 2 STX DC2 FS SYN b k s B K S 2 3 ETX DC3 c l t C L T 3 4 PF RES BYP PN d m u D M U 4 5 HT NL LF RS e n v E N V 5 6 LC BS ETB UC f o w F O W 6 7 DEL IL ESP EOT g p x G P X 7 8 CAN h q y H Q Y 8 9 RLF EM i r z I R Z 9 A SMM CC SM ! ‘ : B VT $ # C FF IFS DC4 * % @ D CR IGS ENQ NAK ( ) , E SO IRS ACK + = F SI IUS BEL SUB ? “ Các mã điều khiển không có trong ASCII là : PF Punch Off CC Cursor Control LC Lower Case IFS Interchange File Separator UC Upper Case IGS Interchange Group Separator RLF Reverse Line Feed IUS Interchange Unit Separator SMM Start of Manual Message IRS Interchange Record Separator RES Restore DS Digit Selector NL New Line SOS Start of Significance ID Idle BYP Bypass SM Set Mode RS Reader Top PN Punch On 3.2 CÁC MÃ PHÁT HIỆN LỖI Nhằm phát hiện lỗi người ta thêm vào dòng dữ liệu các bit kiểm tra. Phương pháp này gọi chung là kiểm tra lỗi dư thừa (Redundancy error check methode), từ dư thừa được dùng vì các bit thêm vào không phải là phần thông tin cần gửi đi. 3.2.1 Kiểm tra chẵn lẻ - Dùng kiểm tra chẵn lẻ để dò ra một bit sai: _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 5 Đây là phương pháp kiểm tra đơn giản nhất, bằng cách thêm vào sau chuỗi dữ liệu (thường là một ký tự) một bit sao cho tổng số bit 1 kể cả bit thêm vào là số chẵn (hoặc lẻ), ở máy thu kiểm tra lại tổng số này để biết có lỗi hay không. Phương pháp đơn giản nên chất lượng không cao, nếu số lỗi là chẵn thì máy thu không nhận ra. - Dùng kiểm tra chẵn lẻ để dò sai hai bit: Vì mỗi lần thực hiện kiểm tra chẵn lẻ cho phép dò ra một bit lỗi nên ta có thể nghĩ rằng nếu thực hiện nhiều phép kiểm tra đồng thời cho phép dò được nhiều lỗi. Thí dụ, để dò ra 2 lỗi của một chuỗi dữ liệu có thể thực hiện hai phép kiểm tra, một với các bit chẵn và một với các bit lẻ. Cho chuỗi dữ liệu: 01101000 Lần lượt thực hiện kiểm tra chẵn với các bit ở vị trí 1, 3, 5, 7 và các bit ở vị trí 2, 4, 6, 8. Gọi P1 và P2 là các bit kiểm tra: P1=0+1+1+0 = 0 và P2=1+0+0+0 = 1. Chuỗi dữ liệu phát: 01101000 01. Máy thu dò ra lỗi khi 2 bit liên tiếp bị sai. Tuy nhiên, nếu hai bit sai đều là 2 bit chẵn (hoặc 2 bit lẻ) thì máy thu cũng không dò ra. - Dùng kiểm tra chẵn lẻ để dò ra một chuỗi bit sai: Đôi khi nhiễu làm sai cả một chuỗi dữ liệu (ta gọi là burst errors), để dò ra được chuỗi bit sai này, người ta bắt chước cách lưu và truyền dữ liệu của máy tính (lưu từng bit của một byte trong các chip riêng để truyền trên các đường khác nhau và nơi nhận sẽ tái hợp) để thực hiện việc kiểm tra. Chuỗi dữ liệu sẽ được chia ra thành các khung (frames), thực hiện kiểm tra cho từng khung, thay vì phát mỗi lần một khung, người ta phát các tổ hợp bit cùng vị trí của các khung, nhiễu có thể làm hỏng một trong các tổ hợp này và chuỗi bit sai này có thể được nhận ra ở máy thu. Thí dụ dưới đây minh họa cho việc kiểm tra phát hiện chuỗi dữ liệu sai: Gửi Nhận Số khung (hàng) 1 2 3 4 5 6 7 8 9 10 Số cột 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 2 3 4 5 Bit parity của từng hàng 1 0 1 1 0 0 0 1 1 0 6 → Nhiễu tác đông vào cột 4, làm cho tất cả các bit = 0 → Số khung (hàng) 1 2 3 4 5 6 7 8 9 10 Số cột 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 2 3 4 5 Bit parity của từng hàng 1 0 1* 1 0* 0* 0 1* 1* 0 6 Máy thu dò ra các khung có lỗi (các bit parity có dấu *) nhưng không xác định được cột nào bị sai do đó phải yêu cầu máy phát phát lại tất cả các cột - Kiểm tra khối: Một cải tiến của kiểm tra chẵn lẻ là kiểm tra khối (Block Check Character, BCC). Bản tin được viết thành khối và việc kiểm tra chẵn lẻ được thực hiện theo cả 2 chiều dọc (Vertical Redundancy Check, VRC) và ngang (Longitudinal Redundancy Check, LRC) Gọi các bit của mỗi ký tự là bij (i=1,....., n là thứ tự các bit trong ký tự ; j=1,...., m là thứ tự của ký tự) _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 6 Rj là bit parity của ký tự thứ j, giả sử chọn parity chẵn, ta có : Rj = b1j + b2j + ...........+ bnj Ci là bít parity của tất cả bít thứ i Ci = bi1 + bi2 + ...........+ bim + Tập hợp các bit Ri (j = 1,.......,m) dùng kiểm tra chiều dọc và tập hợp các bit Ci (i = 1,......,n) dùng kiểm tra chiều ngang. (H 3.1) cho ta dạng của khối dữ liệu có thực hiện kiểm tra chẵn theo chiều ngang và dọc. bit 1 2 . . . . . . . bit n Parity Character 1 B11 B21 . . . . . . . Bn1 R1 10110111 ↓VRC Character 2 B12 B22 . . . . . . . Bn2 R2 11010111 00111010 11110000 10001011 Character m B1m B2m . . . . . . . bnm Rm 01011111 Parity check char. C1 C2 . . . . . . . Cn Cn+1 01111110 ←LRC (H 3.1) Phương pháp kiểm tra khối cho phép phát hiện và sửa một lỗi vì xác định được vị trí của lỗi đó, chính là giao điểm của hàng và cột có bit sai. Máy thu có khả năng phát hiện hai lỗi sai trên cùng một hàng hoặc cột nhưng không xác định được vị trí bit lỗi. Ví dụ hai bit 1 và 3 của ký tự thứ nhất cùng sai thì bit kiểm tra VRC không phát hiện được nhưng bit LRC thì thấy ngay. Nếu bây giờ có thêm các bit 1 và 3 của ký tự thứ 5 cùng sai thì máy thu sẽ không phát hiện được, như vậy cũng còn trường hợp không phát hiện được lỗi nếu số lỗi là một số chẵn theo những vị trí xác định nào đó, tuy nhiên trường hợp này rất hiếm xảy ra. Tóm lại, dùng kiểm tra chẵn lẻ cho phép phát hiện lỗi trong một số trường hợp, tuy nhiên hiệu suất phát sẽ bị giảm và chỉ được dùng trong các hệ thống có vận tốc truyền thấp (bất đồng bộ). Trong các hệ thống truyền đồng bộ người ta hay sử dụng mã CRC , mã này cho phép dò lỗi rất hiệu quả và hiệu suất truyền cũng cao. 3.2.2 Kiểm tra dư thừa theo chu kỳ Để cải thiện hơn nửa việc kiểm tra lỗi người ta dùng phương pháp kiểm tra dư thừa theo chu kỳ (Cyclic Redundancy Check, CRC) Nguyên tắc tạo mã CRC : Xét khung dữ liệu gồm k bit và nếu ta dùng n bit cho khung kiểm tra FCS (Frame check sequence) thì khung thông tin kể cả dữ liệu kiểm tra gồm (k+n) bit sao cho (k+n) bit này chia đúng cho một số P có (n+1) bit chọn trước (dùng phép chia Modulo-2). Ở máy thu khi nhận được khung dữ liệu, lại mang chia cho số P này và nếu phép chia đúng thì khung dữ liệu không chứa lỗi * Nhắc lại một số tính chất của phép toán Mod-2 : - Phép cộng Mod-2 là phép cộng nhị phân không nhớ, dưới đây là thí dụ về phép cộng và phép nhân 1111 11001 + 1010 x 11 _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 7 0101 11001 11001 101011 - Phép cộng Mod-2 được thực hiện bởi cổng EX-OR - Phép trừ Mod-2 giống như phép cộng - Nhân Mod-2 một số với 2n tương ứng với dời số đó n bit về bên trái và thêm n bit 0 vào bên phải số đó, thí dụ 11001* 23 = 11001000 - Phép chia Mod-2 được thực hiện giống như phép chia thường nhưng nhớ là phép trừ trong khi chia được thực hiện như phép cộng. 3.2.2.1. Xác định mã CRC dùng thuật toán Mod-2 Gọi T = (k+n) bit là khung thông tin được phát , với n < k M = k bit dữ liệu, k bit đầu tiên của T F = n bit của khung FCS, n bit cuối của T P = (n+1) bit, số chia trong phép toán Số T được tạo ra bằng cách dời số M sang trái n bit rồi cộng với số F : T = 2nM + F Chia số 2nM cho P ta được : 2n P RQ P M += Q là số thương và R là số dư Vì phép chia thực hiện với số nhị phân nên số dư luôn luôn ít hơn số chia 1 bit. Ta dùng số dư này làm số F, nghĩa là : T = 2nM + R. Ở máy thu khi nhận được khối dữ liệu, mang chia cho P, kết quả số dư sẽ = 0 : P RRQ P R P RQ P T ++=++= Vì R + R = 0 nên T/P = Q Như vậy dùng số dư R của phép chia 2nM cho P làm ký tự kiểm tra trong khung FCS thì chắc chắn T sẽ chia đúng cho P nếu bản tin không có lỗi. Thí dụ: Cho M = 1010001101 (10 bit) P = 110101 (6 bit) Số phải tìm R (5 bit) cho khung FCS được xác định như sau : - Nhân M với 25 cho : 101000110100000 - Thực hiện phép chia cho P 1101010110 110101 ⏐101000110100000 110101↓⏐⏐⏐⏐ 0111011⏐⏐⏐⏐ 110101↓↓⏐⏐ 00111010⏐⏐ 110101↓↓ 00111110⏐⏐ 110101↓↓ 00101100⏐ 110101↓ 0110010 110101↓ _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 8 0001110 ← R Ta có R = 01110, cộng với 25M, sẽ cho số T phát đi là : T = 101000110100000 + 01110 = 101000110101110 Nếu bản tin không có lỗi T phải chia đúng cho P. Thực hiện phép chia T/P ta thấy số dư = 0 Tóm lại, để có một khung FCS n bit , người ta phải dùng một số P có n+1 bit để tạo số R có n bit dùng cho khung FCS. P được gọi là đa thức sinh (generator polynomial), dạng của nó do các giao thức qui định, tổng quát P phải có bit đầu và bit cuối là bit 1. 3.2.2.2. Dùng phép biểu diễn đa thức Để thấy quá trình hình thành mã CRC, ta có thể dùng phép biểu diễn một số nhị phân dưới dạng một đa thức của biến x với hệ số là các số nhị phân và bậc của x là giá trị chỉ vị trí của số nhị phân đó. Ví dụ số nhị phân 110101 có thể biểu diển bởi 1.x5 + 1.x4 + 0.x3 + 1. x2 + 0.x1 + 1.x0 = x5 + x4 + x2 + 1 Chú ý mã số n bit cho bậc cao nhất của đa thức là n-1 Quá trình hình thành mã CRC thực hiện như sau : - Gọi M là đa thức biểu diễn thông tin cần truyền P là đa thức sinh, bậc n (chứa n+1 bit) Thực hiện phép chia xn P(x) R(x) Q(x) P(x) M(x) += Khung thông tin truyền đặc trưng bởi T(x) = xn M(x) + R(x) Lưu ý là nhân M(x) với xn tương đương với việc dời M(x) sang trái n bit - Ở máy thu thực hiện phép chia T(x) cho P(x) số dư phải bằng không P(x) R(x) P(x) R(x) Q(x) P(x) T(x) ++= Q(x) P(x) R(x) 1)(1Q(x) =++= Lấy lại thí dụ trên, bản tin 1010001101 tương ứng với đa thức M(x) = x9 + x7 + x3 + x2 +1 Số chia P = 110101 (6 bít) tương ứng với đa thức P(x) = x5 + x4 + x2 +1 x5M(x) = x14 + x12 + x8 + x7 + x5 Thực hiện phép chia : x9 + x8 + x6 + x4 + x2 +x x5 + x4 + x2 +1 ⏐ x14 + x12 + x8 + x7 + x5 x14 + x13 + x11 + x9 x13 + x12 + x11 + x9 + x8 + x7 + x5 x13 + x12 + x10 + x8 x11 + x10 + x9 + x7 + x5 x11 + x10 + x8 + x6 x9 + x8 + x7 + x6 + x5 x9 + x8 + x6 +x4 x7 + x5 + x4 x7 + x6 + x4 + x2 x6 + x5 + x2 x6 + x5 + x3 + x x3 + x2 + x = R(x) _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 9 R(x) = x3 + x2 + x tương ứng với 01110 3.2.2.3. Khả năng dò sai của mã CRC Một lỗi xảy ra ở một vị trí nào đó trong khung dữ liệu làm đảo bit ở vị trí đó của khung, điều này tương đương với phép tính EX-OR bit đó và bit 1 (vì 0+1=1 và 1+1=0). Nếu gọi E là một khung có số lượng bit bằng với khung dữ liệu, trong đó chỉ các vị trí của bit lỗi = 1 và các bit khác = 0 thì khung thông tin Tr nhận được có thể viết. Tr = T + E. Thí dụ: T = 11010111010 Dạng đa thức: T(x) = x10 + x9 + x7 + x5 + x4 + x3 + x Giả sử bản tin sai ở các bit x7 , x5 và x4 Khung E có dạng: E = 00010110000 E(x) = x7 + x5 + x4 Khung dữ liệu nhận được: Tr = 11000001010 Tr(x) =x10 + x9 + x3 + x Lưu ý phép cộng Modulo 2, tương ứng với phép toán EX-OR, nên x7+x7=(1+1)x7 = 0 Ta có P E P T P ET +=+ Máy thu không nhận ra lỗi khi nào Tr(x) chia đúng cho P(x), hay chỉ khi E(x) chia đúng cho P(x). Vậy với điều kiện nào thì E(x) chia hết cho P(x) ? Ta sẽ xét một số trường hợp cụ thể: @- Giả sử bản tin chỉ sai một bit, đa thức E(x) có dạng xi, i là một số nguyên, E(x) chia đúng cho P(x) chỉ khi P(x) cũng có dạng xn. Người ta đã chọn P(x) có ít nhất là 2 số hạng nên E(x) không thể chia đúng cho P(x). Vậy Mã CRC luôn luôn cho phép máy thu dò ra một bit sai. @- Giả sử bản tin sai một chuỗi, nhưng có tổng số bit sai là số lẻ: đa thức E(x) chứa số lẻ bit 1 nên E(1) =1. Mặt khác, giả sử (x+1) là thừa số của P(x), ta có thể viết P(x) = (x+1)*H(x), H(x) là một đa thức. Ta cũng giả sử lỗi này không được dò ra, nghĩa là E(x) chia đúng cho P(x), hay E(x) = P(x)*K(x). Thay P(x) = (x+1)*H(x) vào E(x) được E(x) = (x+1)*H(x)*K(x), biểu thức này cho E(1) = 0. Điều này trái với giả thiết ở trên, hay nói cách khác, máy thu sẽ dò ra lỗi nếu ta chọn P(x) sao cho chia đúng cho (x+1). Vậy Máy thu sẽ luôn luôn dò ra lỗi gồm nhiều bit và có tổng số bit lỗi là số lẻ nếu ta chọn P(x) chia đúng cho (x+1). @-Giả sử nhiễu làm sai một đoạn dữ liệu có chiều dài m ≤ bậc n của P(x) Giả sử chuỗi bit sai có vị trí từ thứ i đến thứ i+m-1, E(x) có dạng: E(x) = xi+m-1 + . . . . +xi = xi*(xm-1+ . . . +1) P(x) 1)....(xx P(x) E(x) 1mi ++∗= − P(x) không là thừa số của xi nên E(x) chỉ chia đúng cho P(x) khi xm-1+ . . . +1 chia đúng cho P(x). Vì m ≤ n hay m-1<n nên phép chia trên không thể là phép chia đúng. Vậy Máy thu luôn luôn dò ra lỗi nếu chuỗi dữ liệu sai có chiều dài ≤ bậc của P(x) @-Đoạn dữ liệu sai có chiều dài m >n _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 10 Từ kết quả trên P(x) 1)....(xx P(x) E(x) 1mi ++∗= − Nhưng bây giờ m-1 ≥ n nên xm-1+ . . . +1 có thể chia đúng cho P(x). Vậy vấn đề là có bao nhiêu cơ hội để điều này xảy ra. - Trường hợp m-1 = n hay (m=n+1). Vì bậc của P(x) là n nên để có phép chia đúng P(x) phải có dạng xn+ . . . . . +1 với các số hạng giữa xn và 1 phải hoàn toàn giống với các số hạng của xm-1+ . . . . . +1 thì máy thu không dò được lỗi. Có n-1 số hạng giữa xn và 1 nên có 2n-1 tổ hợp và nếu các tổ hợp này có xác suất xảy ra như nhau thì xác suất máy thu không nhận được lỗi sẽ là 1/2n-1. - Trường hợp m>n+1, ta chấp nhận kết quả xác suất này là 1/2n. Lấy thí dụ mã CRC-32 (n=32), xác suất không dò ra một lỗi có chiều dài >33 bit là 1/2.1032 (tương đương với khả năng dò ra lỗi là 99,99999998%). Tóm lại với n càng lớn việc máy thu không dò ra lỗi càng rất khó xảy ra. 3.2.2.4. Mạch tạo mã CRC. Thuật toán mod 2 được thực hiện bởi cổng EX-OR. Dời bit được thực hiện bởi thanh ghi dịch. Quan sát phép tính chia mod.2 của số 2nM cho P(x) để có R(x) ta thấy đây là sự kết hợp của sự dời bit của số 2nM với phép cộng Mod.2 của số P(x). Trong thí dụ trên, để tạo mã CRC với P(x) = 110101, người ta dùng mạch (H 3.2): Cho chuỗi dữ liệu là số 2nM (gồm 15 bit, 101000110100000) vào mạch, sau 15 lần dời bit, kết quả trên các thanh ghi dịch chính là R(x). Mạch tạo mã trong trường hợp này gồm 5 thanh ghi dịch, ký hiệu A(x5), B(x4), C(x3), D(x2), E(x) . Mạch tạo mã CRC được thực hiện như sau: - Thanh ghi dịch chứa n bit, bằng với chiều dài của khung FCS. - Có nhiều nhất n cổng EX-OR. - Sự có mặt hay không của cổng EX-OR tương ứng với sự có mặt của số hạng lũy thừa bậc n trong đa thức P(x) (Riêng bậc cao nhất (n) của đa thức không kể ) (H 3.2 ) A B C D E Dữ liệu vào _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 11 Bắt đầu Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 7 Bước 8 Bước 9 Bước 10 Bước 11 Bước 12 Bước 13 Bước 14 Bước 15 0 0 0 0 0 1* 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0* 1Ë 1 1 1 1 1 0 1 0 1 0 0 0 1 0 Ë1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 1 0* 0Ë 1 0 1 1 1 1 0 1 1 0 1 0 1 0 Ë0 1 0 1 1 1 1 0 1 1 0 1⎫ 0⏐ 1⏐ 0⏐ 0⏐ 0*⎬ Bản tin để gửi 1⏐ 1⏐ 0⏐ 1⎭ 0⎫ 0⏐ 0⎬ 5 bit 0 thêm vào 0⏐ 0⎭ 14444444244444443 số dư - Trong thí dụ trên P =110101 = x5 + x4 + x2 + 1, nên mạch chứa ba cổng EX-OR ở các vị trí tương ứng với 1, x2 và x4 (x5 ứng với thanh ghi dịch cuối cùng FFA). Đường hồi tiếp từ x5 về x4 , x2 và 1 (x0) để thực hiện phép cộng Mod-2 với số P(x) như nói trên. - Trong 5 bước đầu tiên, các bit có trọng số lớn của M(x). 2n xuất hiện ở ngã ra các FFD một cách bình thường. - Từ bước thứ 6 các kết quả phải kể đến tác dụng của cổng EX-OR, thí dụ ở bước thứ 6 ở ngõ ra E chính là cộng Mod-2 của tín hiệu vào (bit 0) và tín hiệu ngã ra A trước đó (bit 1), tức thực hiện EX-OR hai bit 0 và 1 ta được bit 1. Ngã ra D (bit 0) EX-OR với ngã ra A (bit 1) để được bit 1 ở ngã ra C. Ngã ra B(bit 0) EX-OR với ngã ra A (bit 1) để được bit 1 ở ngã ra A. Trên hình vẽ các bit EX-OR với bit ở ngã ra A được đánh dấu. Tương tự như thế, sau 15 lần dịch (bước 15), dữ liệu ở ngã ra các FF chính là mã CRC (số dư R = 01110). Ngã ra A là MSB. Có 4 đa thức P(x) được dùng để tạo mã CRC thông dụng: CRC_12 = x12 +x11 + x3 + x2 + x + 1 CRC_16 = x16+x15 + x2 + 1 CRC_CCITT = x16+x12 + x5 + 1 CRC_32 = x32+ x26+ x23+ x22 + x16+ x12 + x11+ x10+ x8+ x7 + x5 + x4 + x2+ x +1 CRC_12 dùng truyền với ký tự 6 bit và khung FCS dài 12 bit. CRC_16 & CRC_CCITT dùng truyền ký tự 8 bit và khung FCS dài 16 bit. (ở Mỹ và Âu châu). CRC_32 Dùng trong mạng cục bộ (LAN) và một số ứng dụng của DOD (Department Of Defense). 3.2.3 Mã Hamming Mã Hamming là một bước phát triển của kiểm tra chẵn lẻ và có khả năng sửa sai do xác định được vị trí lỗi. Số lượng bit của mã Hamming tùy thuộc số lượng bit của chuỗi dữ liệu. Ta có thể lý luận như sau để xác định số lượng bit của mã Hamming. Gọi m là số bit của chuỗi dữ liệu và n là số bit của mã Hamming, tổng số bit phát đi là m+n - Với n = 1 ta xác định được 1 trong 2 kết quả : chuỗi dữ liệu sai hoặc đúng nhưng không biết vị trí lỗi. - Với n = 2, 1 trong 4 trường hợp xảy ra: 2 phép kiểm tra đều cho kết quả đúng, 2 phép kiểm tra đều cho kết quả sai, phép kiểm tra thứ nhất sai, phép kiểm tra thứ hai đúng và ngược lại. 4 trường hợp này cho phép kết luận được 1 bit sai ở 1 trong 3 vị trí. _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 12 - Với n=3, có 8 khả năng xảy ra và ta có thể kết luận được 1 bit sai ở 1 trong 7 vị trí. - Với số n bất kỳ, có 2n khả năng xảy ra và ta có thể kết luận được 1 bit sai ở 1 trong 2n -1 vị trí. Vậy để có thể phát hiện 1 lỗi tại 1 vị trí cụ thể thì số n nhỏ nhất được chọn phải thỏa: 2n - 1 ≥ Ù m + n hay 2n ≥ Ù m + n + 1 Các bit của mã Hamming chèn vào vị trí 2n và dùng cho kiểm tra chẵn lẻ. Các bit khác là bit thông tin (dữ liệu). Dưới đây là một ví dụ để thấy cách xác định mã Hamming: Giả sử chuỗi dữ liệu cần truyền gồm 4 bit như sau : 1 0 1 0 Với m = 4 , ta chọn n = 3, bất đẳng thức trên được thỏa Gọi các bit của mã Hamming là H1 H2 và H4 (1, 2, 4 là các vị trí mà ta sẽ đặt 3 bit của mã Hamming vào dòng dữ liệu). Gọi các bit dòng dữ liệu là X3, X5, X6, X7. Tổ hợp các bit dữ liệu và bit mã, ta đươc 1 2 3 4 5 6 7 H1 H2 X3 H4 X5 X6 X7 Giả sử ta chọn Parity chẵn, các bit mã sẽ được xác định như sau: H1⊕ X3⊕ X5⊕X7 = 0 H1 = X3⊕ X5⊕X7 =1 ⊕ ( 0 ⊕ 0 ) = 1 ⊕ 0 = 1 Tương tự: H2 = X3⊕ X6⊕X7 =1 ⊕ (1 ⊕ 0 ) = 1 ⊕ 1 = 0 H4 = X5⊕ X6⊕X7 =0 ⊕ (1 ⊕ 0 ) = 0 ⊕ 1 = 1 Bản tin bao gồm bit mã trở thành: 1 0 1 1 0 1 0 Ở máy thu để kiểm tra người ta thực hiện các phép toán: C1 = H1⊕ X3⊕ X5⊕X7 C2 = H2⊕ X3⊕ X6⊕X7 C4 = H4⊕ X5⊕ X6⊕X7 Nếu C1= C2 = C4 = 0, không có lỗi xảy ra Nếu C1 = 1, C2 = C4 = 0, một trong các bit ở vị trí 1, 3, 5, 7 bị lỗi. Nhưng C2 = C4 = 0 có nghĩa là các bit ở vị trí 2, 3, 6, 7 và 4, 5, 6, 7 đã đúng. Vậy bit sai phải ở vị trí 1 Lý luận tương tự ta có các trường hợp khác. Thí dụ nếu C1= C2 = C4 = 1 thì bit lỗi là bit ở vị trí 7 Thí dụ bản tin nhận được là 1 0 1 1 1 1 0 Mạch dò sai sẽ tính C1 , C2 , C4 như sau: C1 = H1⊕ X3⊕ X5⊕X7 = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1 C2 = H2⊕ X3⊕ X6⊕X7 = 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0 C4 = H4⊕ X5⊕ X6⊕ X7 = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1 Vì chỉ bit X5 thuộc cả C1 và C4 nên bit sai là bit thứ 5 Quan sát tổ hợp C4 C2 C1 ta thấy C4 C2 C1 = 101 = (5)10 . Như vậy giá trị có được của tổ hợp này cho ta biết vị trí bit sai cần sửa chữa. Nếu tổ hợp này bằng 0 chứng tỏ bản tin nhận đúng. Mã Hamming có thể được phát triển để dò ra hai bit sai và sửa được một bit lỗi. 3.3 MÃ NÉN DỮ LIỆU Một vấn đề cũng luôn được quan tâm trong truyền dữ liệu là làm thế nào để giảm thiểu số bit cần thiết để truyền một bản tin. - Như ta đã biết, phương pháp điều chế vi phân, ngoài tác dụng tốt về mặt đồng bộ còn có tác dụng giảm số bit đi rất nhiều nếu thông tin có tính lặp lại. _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 13 - Một phương pháp khác là mã hóa Run Length. Phương pháp này cho phép người ta phát đi các mã thay cho các chuỗi ký tự có tính lặp lại kèm theo mã điều khiển báo cho bên thu số lần lặp lại, nhờ mã này mà bên thu có thể tạo lại toàn bộ chuỗi thông tin đã truyền. - Mã đồ họa trong hệ thống Videotex dùng một bảng mã hình học để phát đi các đồ họa của máy tính hoặc hình ảnh video. Mỗi hình được phát đi là tập hợp các hình cơ bản với vị trí, màu sắc và kích thước xác định. Các hình cơ bản là các vòng tròn, hình chữ nhật....Điều này làm giảm rất nhiều số bit cần thiết so với việc phải phát đi từng tọa độ và màu của từng điểm trên màn hình 3.3.1 Mã Huffman Mã Huffman lợi dụng xác suất xảy ra của các ký tự khác nhau mà gán các từ mã ngắn cho các ký tự có xác suất xảy ra lớn và ngược lại. Thí dụ, thay vì dùng 7 bit để mã tất cả các ký tự như mã ASCII, người ta chỉ gán 2 bit cho chữ E và 10 bit cho chữ Z, bởi lẻ, trong tiếng Anh xác suất xuất hiện chữ E rất lớn so với xác suất xuất hiện chữ Z. Mã này còn có tên Mã phụ thuộc tần số (frequency dependent code) Với phương pháp này số bit trung bình dùng cho mỗi ký tự sẽ giảm. Nhưng do các mã dài ngắn khác nhau, để máy thu phân biệt được, người ta phải chọn các từ mã ngắn sao cho không trùng với các bit đầu của các từ mã dài hơn. Gọi là tính tiền tô (prefix property). Giải thuật Huffman: Dưới đây là các bước tạo mã Huffman - Tương ứng với mỗi dữ kiện liên kết một cây nhị phân chứa duy nhất một nút. Ở mỗi cây ghi tần số xuất hiện mà ta gọi là trọng lượng của cây. - Tìm hai cây nhẹ nhất. Nếu có nhiều hơn hai, ta chọn ngẫu nhiên hai cây trong số các cây có trọng lượng nhẹ nhất, ghép chúng lại thành một cây đơn với nút gốc mới. Tổng trọng lượng hai cây này là trọng lượng của cây mới. - Lặp lại các bước cho tới lúc chỉ còn một cây duy nhất. Các cây ban đầu trở thành các lá của cây nhị phân cuối cùng này. Ta biết rằng đối với cây nhị phân thì chỉ có một đường duy nhất từ gốc cho tới lá. Với mỗi lá, đường từ gốc đến nó chính là mã Huffman tương ứng. Mã này xác định bằng cách ghi trị 0 cho nhánh bên trái và 1 cho nhánh bên phải (hoặc ngược lại). Thí dụ 1: Thiết lập mã Huffman cho các ký tự A, B, C, D, E với tần số xuất hiện lần lượt là 0,25; 0,15; 0,10; 0,20; 0,30. (H 3.3a) là cây với 5 nút đơn ban đầu và trọng lượng tương ứng. (H 3.3b) ghép 2 cây B và C thành một cây mới với trọng lượng là tổng trọng lượng cây B và C (0,25) Bước tiếp theo ta có thể ghép cây mới hình thành với cây D hay cây A với D. (H 3.3c) ghép cây mới với D để được một cây trọng lượng là 0,45. (H 3.3d) ghép cây E và A Cuối cùng, ghép hai cây mới tạo để được một cây duy nhất, Ghi trị 0 và 1 vào các nhánh (H 3.3e). _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 14 (H 3.3) Ta được bảng mã sau: Ký tự Mã A B C D E 01 100 101 11 00 Chiều dài trung bình của từ mã có thể tính như sau: 0,25*2 + 0,15*3 + 0,10*3 + 0,20*2 + 0,30*2 = 2,25 bít/ký tự Do có sự chọn ngẫu nhiên khi các dữ kiện có cùng trọng lượng nên kết quả có thể cho các bảng mã khác nhau. Tuy nhiên, kết quả cuối cùng của các bộ mã khác nhau phải cho cùng chiều dài trung bình của từ mã. Thí dụ 2: Mã hoá giá trị nhiệt độ trong khoảng từ 20° C đến 30° C với xác suất cho trong (H 3.4). Thay vì thực hiện các cây nhị phân như trên, ta có thể dựa vào xác suất của các giá trị nhiệt độ mà lập một đồ họa để thực hiện việc mã hóa sao cho các giá trị có xác suất lớn sẽ dùng từ mã ngắn nhất có thể có. Các sự kiện (là các giá trị nhiệt độ) được liệt kê theo xác suất giảm dần (H 3.4a) Ta bắt đầu bằng cách gán hai bít 0 và 1 cho 2 sự kiện có khả năng xảy ra ít nhất, sau đó hai sự kiện này được tổ hợp thành một sự kiện có xác suất bằng tổng hai xác suất của hai sự kiện đó, các sự kiện được sắp xếp theo thứ tự giảm dần và thủ tục lặp lại từ dưới lên và từ trái sang phải cho đến khi hai sự kiện cuối cùng được kết hợp. Từ mã của các sự kiện được viết bằng cách dò theo các đường của sơ đồ theo chiều ngược lại, từ phải qua trái. Cuối cùng ta có bảng mã (H 3.4b) Từ mã trung bình: 0,21*2 + 0,17*3 + 0,15*3 + 0,12*3 + 0,1*3 + 0,06*4 + 0,05*4 + 0,04*5 + 0,03*6 + 0,02*6 =3,18 bít/sự kiện Số bit dùng mã hóa đã giảm khoảng 20%. Một ưu thế của phương pháp Huffman là có thể lập trình để thực hiện việc mã hóa. Trở lại Thí dụ 1, bây giờ giả sử chuỗi ký tự được phát đi là A B E C A D B C, tương ứng với chuỗi bit 01100001010111100101, máy thu khi nhận được chuỗi dữ liệu sẽ thực hiện việc giải mã như thế nào ? Nhờ vào tính tiền tố của các mã, máy thu sẽ lần lượt đọc các bit cho tới khi gặp một chuỗi con các bit tương ứng với một mã sẽ dừng lại, giải mã ký tự này, sau đó tiếp tục đọc chuỗi dữ liệu kế tiếp để tìm ra ký tự thứ hai. . . _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 15 (a) (b) (H 3.4) 3.3.2 Mã Run length Mã Huffman tuy có làm giảm số bit truyền đi nhưng nó đòi hỏi dữ liệu phải được tập hợp thành từng nhóm hay ký tự để xác định tần số lặp lại của các nhóm hay ký tự này. Việc này đôi khi rất khó thực hiện đối với một số loại dữ liệu thí dụ như dữ liệu từ một bản fax, tín hiệu mã hình ảnh . . . Lấy thí dụ trường hợp bản fax, dữ liệu được phát đi không phải là các ký tự mà là các bit tương ứng với điểm sáng tối trên tờ giấy, như vậy phải có một kỹ thuật phù hợp để nén chuỗi dữ liệu này, đó chính là mã Run length. Mã Run length được tạo ra bằng cách quan sát chuỗi bit 0 (hoặc 1) liên tiếp và thay thế chiều dài chuỗi bit này bởi một số nhị phân. Ở máy thu khi nhận được các số nhị phân sẽ thay các số này bởi các bit 0 (hoặc 1) đồng thời chèn các bit khác loại vào. Thí dụ ta phải tạo mã Run length cho chuỗi dữ liệu sau bằng cách dùng số 4 bit thay cho số bit 0 liên tiếp: Dòng dữ liệu 0 . . . 0 1 0 . . . 0 1 1 0 . . . 0 1 0 . . . 0 1 1 0 . . . 0 91 bit Số bit 0 liên tiếp 14 9 20 30 11 Run length (nhị phân) 1110 1001 0000 1111 0101 1111 1111 0000 0000 1011 40 bit Run length (thập phân) 14 9 0 15 5 15 15 0 0 11 Nhận xét cách tạo mã : - 1 bit 1 giữa các chuỗi bit 0 sẽ không được mã, máy thu tự động chèn bit 1 này vào khi phục hồi dữ liệu. - Nếu có 2 bit 1 liên tiếp, ta xem như có 1 chuỗi gồm không bit 0 giữa 2 bit 1 này và phải được thay thế bởi số 0000. - Nếu số số 0 nhiều hơn 15 ta phải dùng 2 số nhị phân thay cho chuỗi này (20=15+5; 30=15+15). Ở máy thu khi gặp chuỗi bốn bit 1 nó phải hiểu là phải lấy tổng số này với các số phía sau, nếu số sau cùng cũng gồm 4 bit 1, máy thu phải được báo bằng chuỗi 4 bit 0 theo sau (trường hợp sau số 30) - Nếu chuỗi dữ liệu bắt đầu bằng bit 1 thì máy phát sẽ gửi đi 4 bit 0 đầu tiên. - Ở cuối bản tin máy phát sẽ gửi tín hiệu báo chấm dứt bản tin và nhờ đó máy thu biết cách xử lý cho trường hợp bản tin kết thúc bởi chuỗi bit 0 hay bit 1. Kỹ thuật nén này chỉ có hiệu quả khi chuỗi dữ liệu chứa rất nhiều một loại bit. _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 16 Ngoài ra, kỹ thuật nén Run length cũng được dùng mã hóa các chuỗi ký tự giống nhau bằng cách thay mỗi chuỗi ký tự liên tiếp bằng con số chỉ độ dài đứng trước ký tự đó. Thí dụ, với chuỗi HHHHHFFFFFFFFYYYYYYYYYYYYYGGGGGGGGGG Sẽ có mã là: 5H8F13Y10G 3.3.3 Mã vi phân (Differential encoding) Còn gọi là mã tương đối (Relative encoding) Trong nhiều trường hợp, các dữ liệu liên tiếp nhau thay đổi rất ít . Thí dụ trường hợp mã tín hiệu hình ảnh trong kỹ thuật video, do phải xử lý 30 bán ảnh (khung) trong một giây để tạo ảnh động, nên chi tiết của các ảnh không khác nhau bao nhiêu, thay vì phải nén tín hiệu từng khung người ta nghĩ tới việc xác định sự khác nhau của các khung liên tiếp, mã thông tin này và gửi đi. Nguyên tắc của mã vi phân như sau: khung thứ nhất được phát đi đồng thời lưu ở bộ đệm của máy phát và thu. Máy phát sẽ so sánh khung thứ hai với khung thứ nhất này, mã sự khác biệt và phát đi dưới dạng một khung. Máy thu khi nhận khung thứ hai, nhờ các mã chỉ sự khác biệt mà so sánh với khung thứ nhất (đã lưu trước đó) để tái tạo khung thứ hai, đồng thời nó lưu khung thứ hai này trong bộ đệm và quá trình tiếp tục với các khung mới. (H 3.5) là một thí dụ minh họa. 5 7 6 2 8 6 6 3 5 6 6 5 7 5 5 6 3 2 4 7 8 4 6 8 5 6 4 8 8 5 5 1 2 9 8 6 5 5 6 6 5 5 2 9 9 6 8 9 5 1 Khung thứ nhất 5 7 6 2 8 6 6 3 5 6 6 5 7 6 5 6 3 2 3 7 8 4 6 8 5 6 4 8 8 5 5 1 3 9 8 6 5 5 7 6 5 5 2 9 9 6 8 9 5 1 Khung thứ nhì 5 7 6 2 8 6 6 3 5 6 6 5 8 5 5 6 3 3 3 7 8 4 6 8 5 6 4 8 8 5 5 1 3 9 7 6 5 5 8 6 5 5 2 9 9 6 8 9 5 1 Khung thứ ba 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 Khung phát đi là sai biệt giữa khung thứ nhì và khung thứ nhất 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 Khung phát đi là sai biệt giữa khung thứ ba và khung thứ nhì (H 3.5) Dữ liệu gồm các số nguyên được biểu diễn trong một khung 2 chiều, chúng không mang một ý nghĩa cụ thể nào, mục đích của thí dụ là để hiểu cách tạo mã. Khung thứ nhất chứa một tập hợp các số nguyên và khung thứ hai chứa một tập hợp các số nguyên khác khung thứ nhất một ít. Trong hình, các khung nằm dưới khung thứ hai và thứ ba là khung chứa các mã vi phân, số 0 chỉ không có sự khác biệt dữ liệu của 2 khung, số 1 chỉ dữ liệu khung sau lớn hơn khung trước 1 đơn vị và số -1 chỉ ngược lại. Dĩ nhiên có thể sử dụng các số khác hơn là 1 và - 1. Thí dụ cho ta thấy sự xuất hiện một chuỗi dài các bit 0 và có thể được nén nhờ phương pháp Run length. 3.4 Mật mã Trong nhiều trường hợp, bản tin cần được giữ bí mật đối với đệ tam nhân thì việc mã hóa được thực hiện dưới dạng mật: bản tin được mã bởi một khóa mà chỉ hai người liên hệ trong trao đổi thông tin biết để sử dụng khi mã hóa và giải mã. _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 17 Gọi bản tin ban đầu là P (Plaintext), bản tin đã cài mật mã là C (Ciphertext) thì C = Ek(P), E và k là giải thuật và khóa tạo mã ( Algorithm & Encryption key). Nơi nhận, nhận bản tin C và phục hồi lại P với giải thuật và khóa là D và k’ : P =Dk’(C) = Dk’ Ek(P). Trong đa số trường hợp (nhưng không phải luôn luôn) k=k’. Giải thuật và khóa càng phức tạp thì độ an toàn của bản tin càng cao. Chúng ta sẽ xét một số cách tạo mật mã từ đơn giản đến phức tạp. 3.4.1. Mã Caesar (Caesar cipher) Còn gọi là mã mẫu tự đơn (mono-alphabetic cipher) Đây là loại mật mã có sớm nhất và đơn giản nhất. Người ta sẽ thay các ký tự của bản tin bằng các ký tự khác theo một qui luật nào đó, thí dụ bằng cách cộng một số nguyên vào mã ASCII của các ký tự ta sẽ có một bản tin mật. Thí dụ cộng 1 vào mã ASCII ta sẽ có ký tự B thay cho A, C thay cho B . . . . Và nơi nhận sẽ giải mã bằng cách trừ 1 cho các mã nhận được trước khi tra bảng mã ASCII. Vì giải thuật tạo mã quá đơn giản nên bản tin có thể được giải mã một cách dễ dàng mà không cần biết trước khóa. Thí dụ, trong tiếng Anh, các ký tự E, T, O và N là các ký tự thường xuất hiện nhiều lần trong các văn bản nên khi gặp bản mã người ta có thể thay các ký tự lặp lại nhiều lần bằng các ký tự này. Sau vài thử nghiệm có thể thấy được qui luật và suy ra bản tin. Để minh họa, giả sử một người nhận được bản tin sau: {;RSDR\SFF\,PMRU\YP\,U\NSML\SVVPIMY\$234567890 Trước nhất người ta liệt kê các ký tự thường xảy ra : \ (7 lần), S (4 lần), R, P và M (3 lần), như vậy người ta có thể thay thử các ký tự S, R, P, M bởi E, T, O, A và N (in đậm): {;EADE\AFF\,ONEU\YO\,U\NANL\AVVOINY\$234567890 Tiếp tục, người ta có thể nghĩ là trong một văn bản luôn có các khoảng trống, như vậy thử thay các dấu \ bằng các khoảng trống, bản tin thành {;EADE AFF ,ONEU YO ,U NANL AVVOINY $234567890 Nhận xét tiếp các từ chứa ít ký tự như AFF và YO, trong tiếng Anh, từ 3 ký tự mà hai ký tự sau giống nhau khiến ta nghĩ đến từ ADD và từ 2 ký tự kết thúc bằng O khiến ta nghĩ tới từ TO. Thay vào ta lại được bản tin: {;EADE ADD ,ONEU TO ,U NANL AVVOINY $234567890 Cho tới đây, dường như ta đã đi được một đoạn đường khá dài để sắp tới đích, thêm vài lần thử người ta có thể tìm ra bản tin. PLEASE ADD MONEY TO MY BANK ACCOUNT #123456789 Một phương pháp khác để tạo mã mẫu tự đơn có tên là Polybius square. Mẫu tự I và J được kết hợp lại và được xử lý như một từ đơn, để tổng số mẫu tự là 25. 25 mẫu tự lại được chia thành dãy 5x5. Mỗi mẫu tự sẽ được mã bởi một cặp số tương ứng với hàng và cột trong bảng mã 1 2 3 4 5 1 2 3 4 5 A F L Q V B G M R W C H N S X D IJ O T Y E K P U Z Thí dụ bản văn N O W I S T H E T I M E 33 43 25 42 34 44 32 51 44 42 23 51 _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 18 3.4.2. Mã đa mẫu tự (Poly-alphabetic cipher) Để tránh việc lặp lại các ký tự trong bản mật mã, người ta dùng loại mã đa mẫu tự, tương tự mã Caesar, mỗi ký tự cũng được thay bởi một ký tự khác, nhưng các ký tự giống nhau không phải được thay bằng một ký tự duy nhất, mà sẽ được thay bằng các ký tự khác nhau tùy theo vị trí của nó. Một thí dụ của mã đa mẫu tự là mã Vigenère Dùng một mãng 2 chiều của các ký tự, trong đó mỗi hàng chứa các mẫu tự theo Alphabet nhưng thứ tự trong từng hàng khác nhau: Thí dụ Cột 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Hàng 0 A B CD E FGH I J K L M N O P Q R S T U V W X Y Z Hàng 1 B C DE FGH I J K L M N O P Q R S T U V W X Y Z A Hàng 2 C DE F GH I J K L M N O P Q R S T U V W X Y Z A B Hàng 3 D E FG H I J K L M N O P Q R S T U V W X Y Z A B C . . . . . . . . . . . . . . Hàng 24 Y Z AB C D E FGH I J K L M N O P Q R S T U V W X Hàng 25 Z AB C D E FGH I J K L M N O P Q R S T U V W X Y Cột 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1920 21 22 23 24 25 Để thay thế một ký tự, gọi i là vị trí tương đối của nó trong bản tin (bắt đầu là vị trí 0) và j là vị trí tương đối của nó trong thứ tự Alphabet. Gọi V là mãng, ký tự sẽ được thay bằng một ký tự trong V[ i mod 26,j ]. Thí dụ dùng mãng ở trên để thay các chữ THE trong bản tin ở các vị trí 25, 54 và 104. Ta lập bảng thay thế như sau: Ký tự cần thay Vị trí i i mod 26 Vị trí j Ký tự phải thay T H E T H E T H E 25 26 27 54 55 56 104 105 106 25 0 1 2 3 4 0 1 2 19 7 4 19 7 4 19 7 4 S (h25, kt19) H (h0, kt7) F V K I T I G Như vậy các ký tự THE ở các vị trí khác nhau trong bản tin đã lần lượt được thay bởi SHF, VKI và TIG. Mặc dù đã giải quyết được sự lặp lại, nhưng xét kỹ chúng ta vẫn thấy rằng có một qui luật mà người ta vẫn có thể nhận ra đó là khoảng cách của các ký tự của cùng một mã là như nhau do tính tuần hoàn của mãng mẫu tự mà chúng ta sử dụng và do bài toán mod 26 (khoảng cách trong mã ASCII của S & H, V & K và T & I đều là 11). Để khắc phục điều này người ta có thể tăng số hàng của mãng ký tự lên, nhưng như vậy đưa đến kết quả là khóa có thể quá dài (thậm chí dài hơn bản tin), khó khăn cho việc phát và lưu trữ một cách an toàn. 3.4.3. Mã chuyển vị (Transposition cipher) Người ta sẽ sắp xếp lại thứ tự các ký tự của bản văn bằng cách lưu chúng trong một mãng 2 chiều m cột, m ký tự đầu tiên sẽ cho vào hàng thứ nhất, m ký tự kế tiếp cho vào hàng _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 19 thứ hai, và cứ thế tiếp tục cho hết bản tin, sau đó hoán đổi vị trí các cột theo thứ tự mới, giả sử p1, p2 . . . pm. Sự hoán đổi có thể thực hiện một cách ngẫu nhiên hoặc theo một qui luật định trước. Bản tin sẽ được truyền đi theo thứ tự từ p1, p2 . . . đến pm Thí dụ bản tin cần phát: MISS PIGGY KERMIT ANIMAL AND FOZZIE BEAR Giả sử dùng mãng 5 cột 1 2 3 4 5, Bản tin được đưa vào mãng như sau: Số cột 1 2 3 4 5 M P I I A O I I K T M N Z B S G E A D Z E S G R A L I A Y M N F E R Sắp xếp lại các cột theo thứ tự 2, 4, 3, 1, 5, ta được bản tin: IIKTMNZBSGRAL IASGE ADZEMP IIAO (2 khoảng trống) YMN FER Rõ ràng là bản tin đã mã hóa không còn một dáng dấp nào của bản tin ban đầu. Nhưng phương pháp vẫn còn khuyết điểm là sự lặp lại của các ký tự. Nếu kẻ gian xác định được mật mã đã dùng là loại chuyển vị thì khả năng giải được mã không khó lắm (nhất là có phương tiện tin học trong tay). 3.4.4. Mã DES (Data Encryption Standard) Mã DES được phát triển bởi IBM vào những năm đầu thập niên 70, đã được chính phủ cho phép xem như chuẩn trong việc tạo mật mã dùng trong thương mại và những tin tức không coi là bí mật và người ta đã chế tạo các chip VLSI để thực hiện viêc tạo mã nhanh hơn. DES chia bản tin ra thành từng khối 64 bit và dùng khóa 56 bit để thực hiện quá trình tạo mã rất phức tạp bao gồm các kỹ thuật như chuyển vị, thay thế, toán tử EX-OR và vài xử lý khác để tạo nên một bản mã 64 bit. Tiến trình thực hiên gồm: - Bước 1: Chuyển vị 64 bit dữ liệu và 56 bit khóa - Bước 2 gồm 16 lần thực hiện sự mã hóa tương tự nhau nhưng với các khóa khác nhau, dữ liệu ra của lần thực hiện trước sẽ là dữ liệu vào của lần thực hiện sau. - Bước 3: Trộn 32 bit đầu và 32 bit cuối - Bước 4: Thực hiện lần chuyển vị cuối cùng. (H 3. 6) mô tả các bước tạo mã của DES _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 20 (H 3.6) (H 3.7) minh họa một trong 16 lần thực hiện mã hóa Trong (H 3.7) , các ký hiệu C64 chỉ 64 bit đã được mã hóa, L32 chỉ 32 bit đầu của C64, R32 là 32 bit cuối, K56 là khóa 56 bit. Ngoài ra các ký hiệu như X48 chỉ chuỗi dữ liệu 48 bit có được từ một tác vụ trung gian trước đó. Lưu ý là để đơn giản, chúng ta chỉ dùng cùng 1 ký hiệu cho các chuỗi dữ liệu ra của cùng 1 tác vụ, nhưng các chuỗi này là khác nhau (Thí dụ, cùng dùng ký hiệu X6 cho các chuỗi dữ liệu ra từ mạch chia nhóm, nhưng các chuỗi ra từ các mạch khác nhau thì khác nhau). Như (H 3.7) mô tả, đầu tiên, người ta chia 64 bit ra làm đôi, 32 bit đầu ký hiệu L32 và 32 bit còn lại là R32. Tiếp theo chuỗi R32 được mở rộng thành 48 bit (R48) bằng cách chuyển vị và nhân đôi một số bit (Ta ký hiệu R48 để nhấn mạnh rằng chuỗi này được dẫn xuất từ R32). Đồng thời khóa 56 bit cũng được phân làm đôi và thực hiện việc quay vòng cho mỗi nhóm (số lần quay tùy theo giải thuật ở từng bước mã hóa khác nhau), sau đó thực hiện chuyển vị, chuỗi bit ra ký hiệu là K56. Bước tiếp theo là thực hiện hàm EX-OR cho R48 và K56, kết quả là chuỗi X48, chuỗi này lại được phân thành 8 nhóm 6 bit (X6) rồi thực hiện việc thay thế để giảm xuống thành các nhóm 4 bít (X4) sau đó tổ hợp 8 nhóm này để thành chuỗi X32. X32 lại được EX-OR với L32, kết quả là X32. Cuối cùng chuỗi X32 tổ hợp với chuỗi bit R32 để cho mã 64 bit (C64). _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu ___________________________________________ Chương 3 Các loại mã trong truyền dữ liệu III - 21 (H 3.7) Tóm lại, giải thuật để có được một bản tin mật rất là phức tạp, nhưng như thế vẫn chưa chắc đã bảo mật tuyệt đối được bản tin. Ngoài ra, việc qui ước với nhau cách tạo các khóa hoặc cách thông tin cho nhau về các khóa cũng phải được thực hiện sao cho bí mật phải được bảo đảm. Vấn đề bảo mật còn rất nhiều điều phải nghiên cứu. _____________________________________________________________________________________________________ Nguyễn Trung Lập Truyền dữ liệu