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ệ 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êmvào các từ mã có khả năng phát hiện lỗi và thậm chí sửa được lỗi.
21 trang |
Chia sẻ: haohao89 | Lượt xem: 2341 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Bài giảng Các loại mã trong truyền dữ liệu, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
___________________________________________ 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ệ
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 = 110000