Truyền thông dữ liệu - Chương 4: Xử lý số liệu - Nguyễn Hồng Sơn

XỬ LÝ SỐ LIỆU TS. Nguyễn Hồng Sơn Bộ môn Mạng máy tính & Truyền số liệu Học viện CN BC VT Chương 4 2Mục đích
Nhằm cải thiện chất lượng truyền/nhận
Truyền nhanh
Truyền chính xác
Truyền an toàn 3Các chủ đề chính
Nén số liệu
Kiểm soát lỗi
Bảo mật 4NÉN SỐ LIỆU Có 3 hướng:
Đơn giản mã biểu diễn thông tin
Bỏ bớt mẫu giống nhau
Bỏ bớt mẫu dựa vào quan hệ giữa các mẫu 5Phương pháp nén Huffman
Là phương pháp đổi mã
Tạo mã mới dựa vào xác suất xuất hiện các ký tự trong văn bản
Ký tự xuất hiện nhiều có mã ngắn hơn ký tự xuất hiện ít
Mã lấy ra từ cây Huffman
Xây dựng cây Huffman 6Cây Huffman
Là cây nhị phân
Mỗi nút có giá trị xác suất là tổng xác suất của 2 nhánh thành phần.
Phân bố giá trị xác suất phải tăng dần từ lá đến gốc theo chiều từ trái sang phải và từ dưới lên.
Mã hóa cây: nhánh trái là bit 0 và nhánh phải là bit 1
Các lá chứa một ký tự ứng với xác suất xuất hiện ký tự đó trong văn bản.
Mã của ký tự : tập hợp các bit nhánh từ gốc đến lá chứa nó. 7Ví dụ 1 AAAABBCD RN A-0,50,5 B-0,250,25 D-0,125 C-0,125 0 0 0 1 1 1 Văn bản chứa AAAABBCD -Xác suất A: 0,5 -Xác suất B: 0,25 -Xác suất C: 0,125 -Xác suất D: 0,125 A 1 B 01 C 001 D 000 8Ví dụ 2
Pa = 0.3
Pb = 0.25
Pc = 0.2
Pd = 0.15
Pe = 0.1 9Hạn chế của Huffman tĩnh
Máy phát phải xây dựng từ mã trước, truyền bảng mã mới cho máy thu, sau đó mới truyền văn bản.
Mỗi văn bản ứng với một bảng mã và phải xây dựng riêng. 10 Huffman động
Khắc phục các hạn chế của Huffman tĩnh
Không cần xây dựng bảng mã trước, truyền đến đâu nén đến đó, lấy thống kê ngay trước đó để xây dựng mã và dùng để truyền ký tự hiện hành.
Cả máy phát và máy thu đều tiến hành đồng thời cùng giải thuật xây dựng cây và mã hiện hành. 11 Thủ tục Huffman động
Bắt đầu với cây rỗng
Khi truyền ký tự thứ nhất, dùng mã gốc để truyền, cập nhật cây với văn bản có 1 ký tự, tạo bảng mã theo Huffman.
Khi truyền ký tự kế tiếp, nếu ký tự trùng với ký tự đã mã hóa trong cây thì truyền mã tương ứng. Nếu ký tự là mới thì truyền mã gốc. Trong cả hai trường hợp đều phải cập nhật cây với sự xuất hiện của ký tự mới này và tạo bảng mã mới 12 Ví dụ
Truyền chuỗi ký tự: abadbccab
Lưu ý thủ tục cập nhật cây và tạo mã mới:
Lấy số lần xuất hiện ký tự thay cho xác suất
Giá trị tăng dần theo chiều từ trái qua phải và từ dưới lên 13 KIỂM SOÁT LỖI (Error Control)
Gồm có hai quá trình phần
Phát hiện lỗi (error detection)
Sửa lỗi (error correction)
Các phương pháp kiểm soát lỗi sẽ khác nhau về thủ tục phát hiện và cơ chế sửa lỗi 14 Hai phương thức chính
Forward Error Control
Máy thu tự sửa lỗi
Backward Error Control
Máy thu không tự sửa lỗi 15 Các phương pháp phát hiện lỗi phổ biến
Parity bit
Block Sum Check
Cyclic Redundancy Check 16 Parity bit
Parity bit là bit được bổ sung vào data sao cho tổng số bit 1 trong tập hợp bit là số chẵn (even) hay lẻ (odd).
Tính chẵn hay lẻ của bit 1 làm cơ sở để phát hiện lỗi.
Parity bit trong hệ chẵn bit 1 được tạo ra thông qua phép xor tất cả các bit trong phần data. 17 Ví dụ parity bit 1101001 11101001 01101001 (4) 1010001 01010001 11010001 (3) 0000000 10000000 00000000 (0) Odd parity bitEven parity bitData (số bit 1) Khi máy thu nhận tập bit (từ mã), tính lại tổng số bit 1, nếu có vi phạm tính chẵn (hay lẻ) thì tập bit bị lỗi. 18 Block Sum Check
Hạn chế của phương pháp parity bit: nếu số bit bị lỗi là số chẵn thì sai lại thành đúng.
Phương pháp BSC tiến hành kiểm tra theo phương pháp parity bit theo cả chiều ngang và chiều dọc.
Ví dụ 19 CRC
Nhằm phát hiện một khối lỗi, dựa vào mã đa thức
Cơ sở: )x(Q)x(G )x(rx)x(M )x(G )x(r)x(Q)x(G x)x(M n n = +× ⇒ += × 20 Áp dụng
Máy phát
M(x) biểu diễn data
Xây dựng từ mã: Chọn G(x) tính r(x)
Từ mã được biểu diễn qua: T(x)=M(x).xn + r(x)
Máy thu nhận từ mã T(x)
Máy thu cũng được cung cấp G(x)
Thực hiện phép chia T(x)/G(x)
Nếu phép chia không dư --> không có lỗi
Nếu phép chia có dư --> có lỗi 21 Ví dụ về CRC
Data : 11100110
G(x) = x4+x3+1
Tính mã phát hiện lỗi CRC 22 Thực hiện CRC
Bằng phần mềm: hàm CRC
Bằng phần cứng x0 x1 xn-1 lsb msb g1 g2 gn-1 TxC Thanh ghi N bit tín hiệu điều khiển chuyển từ 1->0 sau mỗi N xung TxC TxD 23 Áp dụng vào ví dụ
Vẽ mạch và trình bày hoạt động x0 x1 x3 lsb msb TxC Thanh ghi 8 bit tín hiệu điều khiển chuyển từ 1->0 sau mỗi 8 xung TxC x2 G(x) = x4+x3+1 24 Bảng mô tả hoạt động cho ví dụ 011007 106 1105 01104 001103 1001102 11001101 0000111001100 x3x2x1x0msblsb FCSThanh ghi truyềnXungTxC 25 Phát hiện và sửa sai theo Hamming (Một phương pháp FEC) Ý tưởng: Tổng số bit 1 trong một vòng tròn là số chẵn --> tính parity bit như sau: c0=b0 ⊕ b1 ⊕ b2 c1=b0 ⊕ b2 ⊕ b3 c2=b1 ⊕ b2 ⊕ b3 Nếu có 1 bit bị sai --> vi phạm tính chẵn trong một vòng tròn. Vị trí bit sai được xác định : bit chung của các vòng tròn bị sai là bit sai. Sửa: đảo bit c0 c1 c2 b0 b1 b2 b3 26 Phát hiện và sửa sai 1 bit theo Hamming f M bit data K bit kiểm tra f so sánh K bit tính lại Vector hội chứng K bit Nhận M bit data Nhận K bit kiểm tra Sơ đồ nguyên lý 27 Phát hiện và sửa sai 1 bit theo Hamming (tt)
Kiểm tra:
Nếu K bit vector là 0 thì từ mã nhận được không có lỗi.
Nếu K bit vector khác 0 thì từ mã có lỗi và giá trị thập phân của K bit này chỉ ra số thứ tự của bit sai trong từ mã.
Để có được điều này Hamming qui định:
Số bit kiểm tra K= Kmin thỏa 2K-1 ≥M+K
Trong từ mã, các bit kiểm tra Ci nằm tại vị trí có thứ tự i = 2i với i = 0 ÷ (K-1) 28 Với M=8
Data 8 bit => K= 4 bit kiểm tra C0, C1,C2,C3
Vậy từ mã có 12 bit
Xác định f (để tính các Ci)
Bảng bên phải mô tả giá trị của vector hội chứng ứng với vị trí bit trong từ mã và sự hình thành vòng tròn kiểm tra
Trong mỗi cột vòng tròn số 1 chỉ ra bit tương ứng trong từ mã (ngoài cùng bên phải) có mặt trong vòng tròn đó => Ci = xor tất cả các bit có mặt trong vòng tròn tương ứng Không sai00000 C010001 C101002 M111003 C200104 M210105 M301106 M411107 C300018 1 0 1 0 Vòng tròn 4 M50019 M610110 M710111 M801112 Từ mãVòng tròn 3 Vòng tròn 2 Vòng tròn 1 Số tt 29 Ví dụ
Data: 11010101 (M8=1, M7=1, M6=0, M5=1,M4=0, M3=1, M2=0, M1=1)
Tính C0 = M1 ⊕M2 ⊕ M4 ⊕ M5⊕ M7 =1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 1 C1 = M1 ⊕M3⊕ M4 ⊕ M6⊕ M7 =1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 = 1 C2 = M2 ⊕M3 ⊕ M4 ⊕ M8 =0 ⊕ 1 ⊕ 0 ⊕ 1 = 0 C3 = M5 ⊕M6 ⊕ M7 ⊕ M8 =1 ⊕ 0 ⊕ 1 ⊕ 1 = 1
Từ mã truyền
Giả sử nhận được 123456789101112 111001011011 C0C1M1C2M2M3M4C3M5M6M7M8 123456789101112 111001010011 C0C1M1C2M2M3M4C3M5M6M7M8 Vị trí Vị trí 30 Ví dụ (tt)
Tính lại các Ci theo từ mã nhận được
C0 = M1 ⊕M2 ⊕ M4 ⊕ M5⊕ M7 =1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 = 0 C1 = M1 ⊕M3⊕ M4 ⊕ M6⊕ M7 =1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 = 1 C2 = M2 ⊕M3 ⊕ M4 ⊕ M8 =0 ⊕ 1 ⊕ 0 ⊕ 1 = 0 C3 = M5 ⊕M6 ⊕ M7 ⊕ M8 =0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
So sánh 1001 0100 1101 C0C1C2C3 Vector hội chứng = 9D Vậy bit có vị trí thứ 9 trong từ mã nhận được bị sai. Sửa bằng cách đảo bit này từ 0 --> 1 31 MẬT MÃ SỐ LIỆU
Mật mã cổ điển
Mật mã khóa công khai 32 Mật mã cổ điển
Hệ thống mật mã (P,C,K,E,D)
P là tập hữu hạn các bản gốc
C là tập hữu hạn các bản mã
K là tập khóa
E là tập luật mật mã eK: P-->C
D là tập luật giải mã dK: C-->P
dK(eK(x)) = x , Với mọi x∈P
Chỉ có khóa mật
Mã thay thế, mã affine, mã Vigenére... 33 Mật mã khóa công khai
Ứng dụng tính chất đặc biệt của các hàm một chiều, thường dùng logarit rời rạc gọi là hệ mật Elgamal
Máy A chọn
i) Một số rất lớn pA (giả sử từ 200 đến 300 chữ số),
ii) Một phần tử αA modulo pA,
iii) Một số nguyên (ngẫu nhiên) dA với 2 ≤ dA ≤ pA –2
Máy A tính
iv) αA dA ≡ βA (mod pA)
Public key của máy A là (pA, αA, βA). Private key là dA 34 Mật mã khóa công khai (tt)
Máy B mật mã bản tin M để gửi cho máy A:
i) Chọn một số nguyên ngẫu nhiên k (giữ bí mật)
ii) Tính r ≡ αAk (mod pA) và t ≡ βAk M (mod pA), sau đó bỏ k.
Máy B gửi bản mật (r, t) đến máy A.
Khi máy A nhận bản mật (r, t), nó sẽ dùng khóa riêng (private key) dA để giải mã bằng cách tính tr−dA ≡ βAk M (αAk )−dA (mod pA) ≡ (αA dA)k M (αAk )−dA (mod pA) ≡M (mod pA) Adtr −