___________________________________________ 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
số nhị phân trước 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ệ

010101100110
101111001001
0011100110
00011
01101
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
-
?
:
$
3
!
&
#
8

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ó 2
5
= 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.

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

DLED
C1
DC2
DC3
DC4
NAK
SYN
ETB
CAN
EM
SUB
ESC
FS
GS
RS
US
SP
!
"
#
$
%
&
`
(
)
*
+
,
-

L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
[
\
]
^(↑)
_(←)
'
a
b
c
d
e
f
g
h
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.

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:

(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

→
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

Redundancy Check
, VRC) và ngang (Longitudinal Redundancy Check, LRC)
Gọi các bit của mỗi ký tự là b
ij
(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
R
j
là bit parity của ký tự thứ j, giả sử chọn parity chẵn, ta có :
R
j

= b
1j
+ b
2j
+ + b
nj

C
i
là bít parity của tất cả bít thứ i
C
i
= b
i1

n2
R
2
11010111
00111010
11110000
10001011
Character m B
1m
B
2m
. . . . . . . b
nm
R
m
01011111
Parity check char. C
1
C
2
. . . . . . . C
n
C
n+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

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

Vì R + R = 0 nên T/P = Q
Như vậy dùng số dư R của phép chia 2
n
M 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 2
5
cho : 101000110100000
- Thực hiện phép chia cho P 1101010110
110101 ⏐
101000110100000110101↓⏐⏐⏐⏐
0111011
⏐⏐⏐⏐
110101↓↓⏐⏐
00111010
⏐⏐

110101↓↓
00111110

Ví dụ số nhị phân 110101 có thể biểu diển bởi
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

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

+1 ⏐

x
14
+ x
12

+ x
8
+ x
7
+ x
5

x
14
+ x
13

+ x
11
+ x
9

x
13
+ x
12

+ x

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


+ 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) = x
3
+ x
2

+ 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) = x
10
+ x
9
+ x
7
+ x
5
+ x

=(1+1)x
7
= 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 x
i
, i là một số nguyên, E(x)
chia đúng cho P(x) chỉ khi P(x) cũng có dạng x
n
. 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

−

P(x) không là thừa số của x
i
nên E(x) chỉ chia đúng cho P(x) khi x
m-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 x
m-1
+ . . . +1 có thể chia đúng cho P(x). Vậy vấn đề là có

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ố 2
n
M 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ố 2
n
M 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ố 2
n
M (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(x
5
), B(x
4
), C(x
3
),
D(x
2
), 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ể )

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

) để 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). 2
n

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 = x
12

+x
11
+ x
3
+ x
2

+ x + 1
CRC_16 = x
16
+x
15

8
+ x
7
+ x
5

+ x
4

+ x
2
+ 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í.

và H
4
(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à X
3
, X
5
, X
6
, X
7
.
Tổ hợp các bit dữ liệu và bit mã, ta đươc

1 2 3 4 5 6 7
H
1
H
2
X
3
H
4
X
5
X
6
X
7
Giả sử ta chọn Parity chẵn, các bit mã sẽ được xác định như sau:

= X
3
⊕

X
6
⊕X
7

=1 ⊕ (1 ⊕ 0 ) = 1 ⊕ 1 = 0
H
4
= X
5
⊕

X
6
⊕X
7

=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:
C
1
= H
1
⊕ X
3

⊕

X
6
⊕X
7

Nếu C
1
=

C
2
= C
4
= 0, không có lỗi xảy ra
Nếu C
1
= 1, C
2
= C
4
= 0, một trong các bit ở vị trí 1, 3, 5, 7 bị lỗi. Nhưng C
2
= C
4
= 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 C
1


C
2
=

H
2
⊕ X
3
⊕

X
6
⊕X
7
= 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0C
4
=

H
4
⊕ X
5
⊕

X
6

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



(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

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.

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

E
k
(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 =D
k’
(C) = D
k’
E
k
(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

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)

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

___________________________________________ 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ử
p
1
, p
2
. . . p
m
. 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ừ p
1
, p
2
. . . đến p
m
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

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

_____________________________________________________________________________________________________

và
32 bit còn lại là R
32
. Tiếp theo chuỗi R
32
được mở rộng thành 48 bit (R
48
) bằng cách chuyển vị
và nhân đôi một số bit (Ta ký hiệu R
48
để nhấn mạnh rằng chuỗi này được dẫn xuất từ R
32
).
Đồ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à K
56
. Bước tiếp theo là thực hiện hàm EX-OR cho R
48
và K
56
, kết quả là
chuỗi X
48
, chuỗi này lại được phân thành 8 nhóm 6 bit (X
6
) rồi thực hiện việc thay thế để
giảm xuống thành các nhóm 4 bít (X
4
) sau đó tổ hợp 8 nhóm này để thành chuỗi X

_____________________________________________________________________________________________________
Nguyễn Trung Lập Truyền dữ liệu