tanyaprinc3ss
New Member
Download miễn phí Giáo trình Truyền dữ liệu - Các loại mã trong truyền dữ liệu
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 ralớ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ượngcủ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
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
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 hay 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...