Bài giảng Truyền số liệu và mạng - Chương 2: Kỹ thuật truyền số liệu

=
=
43421
0
)(
2-64Khoa Điện – Điện tử - ĐHBK TP.HCM
Cyclic Redundant Check 
ƒ Ví dụ:
2-65Khoa Điện – Điện tử - ĐHBK TP.HCM
Cyclic Redundant Check
„ Ví dụ: Cho thông tin cần truyền M(x) = 110101. Sử dụng đa 
thức sinh G(x) = x3 + 1. 
„ Tìm CRC và thông tin cần truyền đi.
„ Bài giải:
„ Bước 1 : Chuyển thông báo nhị phân thành đa thức :M(x) 
= 1.x5 + 1.x4 + 0.x3 + 1.x2 + 0.x1 + 1.x0= x5 + x4 + x2 + 1
„ Chọn G(x) = x3 + 1.
„ Bước 2 : Nhân M(x).xc = (x5 + x4 + x2 + 1).x3 = x8 + x7 + x5
+ x3.
2-66Khoa Điện – Điện tử - ĐHBK TP.HCM
Cyclic Redundant Check
„ Bước 3 : Thực hiện phép tính với modulo 2 :
„ Bước 4 : Lập T(x) : T(x) = xc.M(x) + R(x)
⇒ T(x) = x8 + x7 + x5 + x3 + x +1 ⇒
Thông tin cần truyền : T = 1 1 0 1 0 1 0 1 1
)x(G
x).x(M C
x8 + x7 + x5 + + x3
x8 + x5 + x3
0 + x7 + 0 + x3
 x7 + x4
0 + x4 + x3
x4 + x
0 + x3 + x
 x3 + 1
0 + x +1 = R(x) ⇒ CRC = 011
 x3 + 1
x5 + x4 + x + 1
2-67Khoa Điện – Điện tử - ĐHBK TP.HCM
„ Mục đích : Giảm kích thước và thời gian truyền.
„ Các kỹ thuật nén cơ bản :
„ Packed Decimal : Khi truyền ký tự số dùng mã BCD 4 bit 
thay cho mã ASCII 7bits hay EDBIC
„ Relative Coding : Khi truyền các ký tự số, chỉ truyền sai 
số giữa các số liên tiếp nhau.
„ Character Suppression : Khi truyền các ký tự in được mà
các ký tự giống nhau được truyền liên tiếp, thay vì truyền 
hết các ký tự thì chỉ truyền 1 ký tự đại diên và kèm theo là
số các ký tự giống nhau.
„ Huffman Coding
„ Run Length Coding (Facsimile compression)
Các kỹ thuật nén dư liệu
(Data Compression)
2-68Khoa Điện – Điện tử - ĐHBK TP.HCM
„ Là một mã thống kê tối ưu
„ Các tin xuất hiện nhiều, xác suất xuất hiện lớn thì được mã 
hóa bằng từ mã ngắn và ngược lại. Do đó độ dài trung bình 
của các từ mã sẽ nhỏ nhất, làm giảm thiểu rất nhiều lượng 
thông tin truyền trên đường dây nên giảm sai số.
Huffman Coding
2-69Khoa Điện – Điện tử - ĐHBK TP.HCM
„ Ví dụ : Để tạo mã cho việc đo nhiệt độ từ 200 đến 300 C người ta lấy xác
suất của nó và được sắp xếp thứ tự xuất hiện như bảng.
„ Sắp xếp các khả năng xuất hiện theo thứ
tự giảm dần.
„ Hai giá trị 0,1 gán cho 2 khả năng xuất 
hiện nhỏ nhất, 2 khả năng này gộp lại 
thành 1 và sắp xếp theo thứ tự giảm dần. 
Tương tự như vậy cho đến 2 khả năng 
cuối cùng (tổng sẽ = 1).
„ Mã tương ứng của mỗi nhiệt độ được 
hình thành bằng cách chọn các bit 0,1 
trên đường đi xuất phát từ mức nhiệt độ
đến ngọn.
„ Bit LSM sẽ nằm bên trái cây.
30
20
29
21
28
22
27
23
26
24
25
0,02
0,03
0,04
0,05
0,05
0,06
0,10
0,12
0,15
0,17
0,21
0
1
0
1
0
1
0,05
1
0
0,10
0,32
0
1
0,09
0
1 0,15
0,20
0
1
0
0,27
0,41
0
1 0,59
0
1 1
Từ mã0C P
10
000
001
011
010001
010000
01001
1111
1110
0101
110
Huffman Coding
2-70Khoa Điện – Điện tử - ĐHBK TP.HCM
„ Entropy: .
H(x)=∑pi log2 (1/pi) (bits/symbol)
„ Chiều dài trung bình của từ mã.
N = ∑ piNi (bits/symbol)
„ Hiệu suất của mã hóa
h = H(x)/N
„ Tốc độ bit nhị phân
R= rN
Huffman Coding
2-71Khoa Điện – Điện tử - ĐHBK TP.HCM
„ Sử dụng trong máy Facsimile trắng đen.
„ Một trang Fax được chia 
„ Theo chiều dọc khoảng khoảng 3.85 hoặc 7.7 lines/mm, 
tương đương 100 hoặc 200 lines / inche
„ Mỗi line được số hoá với tốc độ 8.05 phần tử ảnh 
(pels)/mm.
„ Mỗi điểm ảnh trắng mã hoá ‘0’, điểm đen mã hoá ‘1’
„ Một trang Fax khi chưa nén được mã hóa khoảng 2 triệu bits.
Run Length Coding 
2-72Khoa Điện – Điện tử - ĐHBK TP.HCM
Run Length Coding 
2-73Khoa Điện – Điện tử - ĐHBK TP.HCM
„ Thực tế khi truyền bức Fax thì sẽ có những line mà có khoảng 
điểm ảnh trắng hay đen liên tục, để giảm bớt số bit trước khi 
truyền ta dùng phương pháp nén Facsimile:
„ Các từ mã cố định và chia thành 2 nhóm the termination-
codes and the make-up codes.
„ Để bên nhận đồng bộ thì ký mã EOL(End Of Line) được 
thêm vào ở cuối mỗi line.
„ Kết thúc trang là chuỗi 6 EOL liện tiếp.
„ Trong trường hợp bên thu không giải mã được EOL thì sẽ 
ngưng quá trình nhận và thông báo cho bên phát biết.
„ Nén MMR (Modified- modified read coding) : Nén kết hợp 
với sửa sai.
Run Length Coding
2-74Khoa Điện – Điện tử - ĐHBK TP.HCM
Run Length Coding
2-75Khoa Điện – Điện tử - ĐHBK TP.HCM
Thảo luận
Khoa Điện – Điện tử - ĐHBK TP.HCM 2-76
Chương 2_Bài tập :
Kỹ Thuật Truyền Số Liệu
2-77Khoa Điện – Điện tử - ĐHBK TP.HCM
Bài 1
Một tập tin nhị phân sau đây được phát như khối tin lên 
đường truyền nối tiếp:
LSB
10010011100001100000100001001111111
„ Hãy trình bày cấu trúc khung hoàn chỉnh khi truyền khối tin 
với các kiểu truyền sau:
„ Bất đồng bộ, mã ASCII, kiểm tra lẻ, 1 stop, 7 data.
„ Đồng bộ định hướng bit, mã ASCII, kiểm tra lẻ
2-78Khoa Điện – Điện tử - ĐHBK TP.HCM
Bài 2
„ Hãy trình bày ngắn gọn về kỹ thuật truyền số liệu bất đồng bộ về các 
nội dung sau:
„ Phương thức truyền và phạm vi ứng dụng. 
„ Đồng bộ bit
„ Đồng bộ byte
„ Đồng bộ khung
„ Cho hai ký tự có mã ASCII nhý sau: ký tự 1 : (MSB) X0101011 
(LSB) , ký tự 2 : (MSB) X1110011 (LSB), X là bit kiểm tra chẳn 
lẽ. Hai ký tự đýợc truyền sử dụng kỹ thuật truyền bất đồng bộ, kiểm 
tra chẳn (Parity chẳn), 1 stop bít. Viết đầy đủ chuỗi bít đýợc truyền 
trên môi trýờng truyền, ghi rõ tên gọi chức năng của từng bít nếu có
2-79Khoa Điện – Điện tử - ĐHBK TP.HCM
Bài 3
ƒ Một máy phát theo cơ chế truyền bất đồng bộ với tốc độ
9600bps, có kiểm tra parity chẵn, 2 bit stop và 7 bit dữ liệu.
ƒ Xác định hiệu suất truyền.
ƒ Để truyền một file bitmap kích thước 1024x800 pixel, 
mỗi pixel mã hóa bằng 14 bit theo cơ chế trên thì hết 
một khoảng thời gian là bao nhiêu.
ƒ Xác định chuỗi bit truyền đi nếu dữ liệu truyền là chuỗi 
ký tự ASCII 7 bit VMS. 
ƒ Máy thu làm cách nào để có thể đồng bộ bit.
2-80Khoa Điện – Điện tử - ĐHBK TP.HCM
Bài 4
„ Một máy phát muốn truyền chuỗi ký tự ASCII 7 bit 
MOBIFONE cho máy thu theo cơ chế thiên hướng ký tự và sử
dụng phương pháp kiểm tra tổng khối chẵn theo hàng và lẻ
theo cột.
„ Hãy xác định ký tự kiểm tra tổng khối BCC và chuỗi bit 
truyền đi nếu bit MSB được truyền đi trước.
„ Giả sử trong quá trình truyền bit thứ 12 và thứ 30 bị lỗi. 
Hỏi phía thu có phát hiện và sửa lỗi được không. Tại sao? 
„ Giả sử trong quá trình truyền bit thứ m1,n1,k1,l1 bị lỗi. 
Hỏi phía thu có phát hiện và sử lỗi được không.
2-81Khoa Điện – Điện tử - ĐHBK TP.HCM
Bài 5
„ Một file text gồm các ký tự ASCII 8 bit A,B,C,D,E,F,G với số
lượng mỗi ký tự được cho trong bảng sau:
„ Truyền file text trên qua kênh truyền có băng thông 
100Mhz với S/N=30dB. Tính thời gian nhỏ nhất để truyền 
hết file text trên nếu mỗi frame có định dạng như sau
2-82Khoa Điện – Điện tử - ĐHBK TP.HCM
Bài 6
„ Các ký tự ở Bài tập 5 trước khi turyền dùng mã Huffman để
nén. 
„ Xác định các từ mã Huffman.
„ Xác định chiều dài trung bình của từ mã, hiệu suất bộ
mã
„ Xác định tỉ số nén và thời gian ngắn nhất để truyền hết 
file (sau khi mã hóa) theo dạng bit-oriented qua kênh 
truyền ở câu 1) nếu bỏ qua thời gian truyền các bit FCS, cờ
đầu và cuối mỗi frame
2-83Khoa Điện – Điện tử - ĐHBK TP.HCM
Bài 7
„ Một nguồn phát 8 ký hiệu A, B, C, D, E, F, G, H với các xác 
xuất PA = 1/2, PB = 1/4, PC = 1/8, PD = 1/32, PE = 1/32, PF 
= 1/32, PG = 1/64, PH = 1/64. Sau 5 khoảng 10s đếm được 
lần lượt 7000, 5000, 4000, 6000, 8000 symbol.
„ Tính Entropy và tốc độ tin của nguồn này.
„ Xây dựng từ mã Huffman cho nguồn này. Tính hiệu suất 
sử dụng từ mã.
2-84Khoa Điện – Điện tử - ĐHBK TP.HCM
Bài 8
Cho 1 trang giấy A4 sau khi quét (scan) để truyền FAX có cấu trúc là ½ đầu là màu 
trắng, ½ sau là màu đen 
„ Biết kích thước trang A4 là 297 x 210mm 
„ Việc quét để truyền FAX được thực hiện với độ phân giải xấp xỉ như sau: 
„ Chiều ngang: 8,0476 cột/mm
„ Chiều dọc: 3,8485 dòng/mm
„ Việc mã hóa đựơc tiến hành theo kiểu: pixel trắng mã hóa thành bit 0, pixel đen mã 
hóa thành bit 1. Hãy tính tổng số bit cần thiết để mã hóa trang A4 trên
„ Giả sử việc truyền FAX đựơc thực hiện qua mạng PSTN với tốc độ là R=9600bps, 
hãy tính thời gian cần thiết để truyền hết bản FAX trên
„ Trang A4 trên sau khi quét với các thông số như trên được mã hóa theo chuẩn 
Facsimile G3 (bảng mã G3 được cho ở trang sau)
„ Hãy viết chuỗi bit tương ứng để truyền bản FAX trên
„ Tính tổng số bit cần thiết để truyền bản FAX trên
„ Tính thời gian cần thiết để truyền hết bản FAX trên
„ Suy ra tỷ số nén của việc mã hóa theo chuẩn FAX G3
2-85Khoa Điện – Điện tử - ĐHBK TP.HCM
Bài 9
„ Sử dụng mã CRC (7,4) để truyền bản tin M(x)=1+x2 (0101) 
với đa thức sinh G(x)=1+x2+x3
„ Xác định đa thức truyền đi T(x).
„ Nếu đa thức lỗi đường truyền là E(x)=x+x3 (0001010) thì
phía thu có phát hiện được lỗi không?
„ Nếu đa thức lỗi đường truyền là E(x)=x+x3+x4 (0011010) 
thì phía thu có phát hiện được lỗi không?
„ Hãy rút ra kết luận về khả năng phát hiện lỗi của mã 
CRC.
2-86Khoa Điện – Điện tử - ĐHBK TP.HCM
Bài 10
„ Sử dụng mã CRC (14,10) để truyền bản tin M(x)= x8 + x6 + 
x4+x3+x+1 với đa thức sinh G(x)=x+x4
„ Số dư được truyền như FCS. Tính FCS.
„ Nếu frame bị lỗi theo mẫu 00010010110000 (LSB).Tính 
FCS nơi thu, nhận xét
FCS