___________________________________________
Chương 3
Các loại mã trong truyền dữ liệu
III - 1
 CHƯƠNG 3

CÁC LOẠI MÃ TRONG TRUYỀN DỮ LIỆU

 MÃ NHỊ PHÂN
 Mã Baudot
 Mã ASCII
 Mã EBCDIC
 CÁC MÃ PHÁT HIỆN LỖI
 Kiểm tra chẵn lẻ
 Kiểm tra khối
 Kiểm tra dư thừa theo chu kỳ
 Mã Hamming
 MÃ NÉN DỮ LIỆU
 Mã Huffman
 Mã Run-length
 Mã vi phân
 MẬT MÃ
 Mã Caesar
 Mã đa mẫu tự
 Mã chuyển vị
 Mã DES
__________________________________________________________________________________________
____Tin tức bao gồm các văn bản, số liệu, hình ảnh . . . . cần được mã hóa bằng tập hợp các


___________________________________________
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
-

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

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

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

?
@
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
[
\

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ị))

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 ? “


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 P
1
và P
2
là các bit kiểm tra:
P
1
=0+1+1+0 = 0
và P
2
=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) để

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

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à b

= b
i1
+ b
i2
+ ...........+ b
im
+
Tập hợp các bit R
i
(j = 1,.......,m) dùng kiểm tra chiều dọc và tập hợp các bit C
i
(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 B
11
B
21
. . . . . . . B
n1
R
1
10110111 ↓VRC
Character 2 B
12
B

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
+

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 = 2
n
M + F
Chia số 2
n
M cho P ta được :
2
n

P
R
Q
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 = 2
n
M + 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
RR
Q
P
R

⏐⏐⏐⏐

0111011
⏐⏐⏐⏐

110101↓↓
⏐⏐

00111010
⏐⏐110101
↓↓

00111110
⏐⏐110101
↓↓

00101100
⏐110101
↓

0110010

1.x
5
+ 1.x
4

+ 0.x
3
+ 1. x
2
+ 0.x
1
+ 1.x
0

= x
5
+ x
4

+ x
2
+ 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
x
n



Lấy lại thí dụ trên, bản tin 1010001101 tương ứng với đa thức

M(x) = x
9
+ x
7

+ x
3
+ x
2
+1
Số chia P = 110101 (6 bít) tương ứng với đa thức
P(x) = x
5

+ x
4
+ x
2
+1
x
5
M(x) =

x
14
+ x
12


x
14
+ x
12

+ x
8
+ x
7
+ x
5

x
14
+ x
13

+ x
11
+ x
9

x
13
+ x
12

+ x
11

10

+ x
8
+ x
6
x
9
+ x
8
+ x
7
+ x
6
+ x
5
x
9
+ x
8
+ x
6
+x
4
x
7
+ x
5
+ x
4

+ x = R(x)
_____________________________________________________________________________________________________
Nguyễn Trung Lập

Truyền dữ liệu