Bài giảng Truyền thông dữ liệu - Chương 4: Xử lý số liệu

Chương 4

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

Mục đích

(cid:1) Nhằm cải thiện chất lượng truyền/nhận

(cid:1) Truyền nhanh (cid:1) Truyền chính xác (cid:1) Truyền an toàn

Các chủ đề chính

(cid:1) Nén số liệu (cid:1) Kiểm soát lỗi (cid:1) Bảo mật

NÉN SỐ LIỆU

Có 3 hướng:

(cid:1) Đơn giản mã biểu diễn thông tin (cid:1) Bỏ bớt mẫu giống nhau (cid:1) Bỏ bớt mẫu dựa vào quan hệ giữa các mẫu

Phương pháp nén Huffman

(cid:1) Là phương pháp đổi mã (cid:1) 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

(cid:1) Ký tự xuất hiện nhiều có mã ngắn hơn ký tự

xuất hiện ít

(cid:1) Mã lấy ra từ cây Huffman (cid:1) Xây dựng cây Huffman

Cây Huffman

(cid:1) Là cây nhị phân (cid:1) 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.

(cid:1) 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.

(cid:1) Mã hóa cây: nhánh trái là bit 0 và nhánh phải là bit 1 (cid: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.

(cid:1) Mã của ký tự : tập hợp các bit nhánh từ gốc đến lá chứa

nó.

Ví dụ 1 AAAABBCD

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

0,5

A-0,5

0,25

B-0,25

C-0,125

D-0,125

A B C D

1 01 001 000

Ví dụ 2

(cid:1) Pa = 0.3 (cid:1) Pb = 0.25 (cid:1) Pc = 0.2 (cid:1) Pd = 0.15 (cid:1) Pe = 0.1

Hạn chế của Huffman tĩnh

(cid:1) 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.

(cid:1) Mỗi văn bản ứng với một bảng mã và phải

xây dựng riêng.

Huffman động

(cid:1) Khắc phục các hạn chế của Huffman tĩnh (cid:1) 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.

(cid:1) 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.

Thủ tục Huffman động

(cid:1) Bắt đầu với cây rỗng (cid:1) 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.

(cid:1) 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

Ví dụ

(cid:1) Truyền chuỗi ký tự: abadbccab (cid:1) Lưu ý thủ tục cập nhật cây và tạo mã mới: (cid:1) Lấy số lần xuất hiện ký tự thay cho xác suất (cid:1) Giá trị tăng dần theo chiều từ trái qua phải và từ dưới

lên

KIỂM SOÁT LỖI (Error Control)

(cid:1) Gồm có hai quá trình phần

(cid:1) Phát hiện lỗi (error detection) (cid:1) Sửa lỗi (error correction)

(cid:1) 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

Hai phương thức chính

(cid:1) Forward Error Control (cid:1) Máy thu tự sửa lỗi

(cid:1) Backward Error Control (cid:1) Máy thu không tự sửa lỗi

Các phương pháp phát hiện lỗi phổ biến

(cid:1) Parity bit (cid:1) Block Sum Check (cid:1) Cyclic Redundancy Check

Parity bit

(cid:1) 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).

(cid:1) Tính chẵn hay lẻ của bit 1 làm cơ sở để phát

hiện lỗi.

(cid:1) 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.

Ví dụ parity bit

Even parity bit

Odd parity bit

Data (số bit 1)

0000000 (0)

0000000 0

0000000 1

1010001 (3)

1101001 (4)

1010001 1 1101001 0

1010001 0 1101001 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.

Block Sum Check

(cid:1) 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. (cid:1) 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.

(cid:1) Ví dụ

CRC

(cid:1) Nhằm phát hiện một khối lỗi, dựa vào mã đa

thức (cid:1) Cơ sở:

)x(Q

x)x(M )x(G

)x(r )x(G

x)x(M

)x(r

⇒

)x(Q

)x(G

Áp dụng

(cid:1) Máy phát

(cid:1) M(x) biểu diễn data (cid:1) Xây dựng từ mã: Chọn G(x) tính r(x) (cid:1) Từ mã được biểu diễn qua: T(x)=M(x).xn + r(x)

(cid:1) Máy thu nhận từ mã T(x)

(cid:1) Máy thu cũng được cung cấp G(x) (cid:1) Thực hiện phép chia T(x)/G(x)

(cid:1) Nếu phép chia không dư --> không có lỗi (cid:1) Nếu phép chia có dư --> có lỗi

Ví dụ về CRC

(cid:1) Data : 11100110 (cid:1) G(x) = x4+x3+1 (cid:1) Tính mã phát hiện lỗi CRC

Thực hiện CRC

(cid:1) Bằng phần mềm: hàm CRC (cid:1) Bằng phần cứng

tín hiệu điều khiển chuyển từ 1->0 sau mỗi N xung TxC

gn-1

xn-1

TxC

lsb

msb

Thanh ghi N bit

TxD

Áp dụng vào ví dụ

(cid:1) Vẽ mạch và trình bày hoạt động

G(x) = x4+x3+1

tín hiệu điều khiển chuyển từ 1->0 sau mỗi 8 xung TxC

TxC

lsb

msb

Thanh ghi 8 bit

Bảng mô tả hoạt động cho ví dụ

Thanh ghi truyền

Xung TxC

msb

lsb

FCS x2

1 0

1 1 0

0 1 1 0

0 0 1 1 0

1 0 0 1 1 0

1 1 0 0 1 1 0

1 1 1 0 0 1 1 0

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: ⊕⊕⊕⊕ b2 c0=b0 ⊕⊕⊕⊕ b3 c1=b0 ⊕⊕⊕⊕ b3 c2=b1

⊕⊕⊕⊕ b1 ⊕⊕⊕⊕ b2 ⊕⊕⊕⊕ b2

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

Phát hiện và sửa sai 1 bit theo Hamming

M bit data

Nhận M bit data

K bit tính lại

so sánh

Vector hội chứng K bit

K bit kiểm tra

Nhận K bit kiểm tra

Sơ đồ nguyên lý

Phát hiện và sửa sai 1 bit theo Hamming (tt)

(cid:1) Kiểm tra:

(cid:1) Nếu K bit vector là 0 thì từ mã nhận được không có lỗi. (cid:1) 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ã.

(cid:1) Để có được điều này Hamming qui định: (cid:1) Số bit kiểm tra K= Kmin thỏa 2K-1 ≥ M+K (cid:1) 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)

Số tt Từ mã

Vòng tròn 1 Vòng tròn 2 Vòng tròn 3 Vòng tròn 4

1 1 0 0 12 M8

1 0 1 1 11 M7

Với M=8

(cid:1) Data 8 bit => K= 4 bit kiểm tra

1 0 1 0 10 M6

C0, C1,C2,C3

1 0 0 1 9 M5

1 0 0 0 8 C3

0 1 1 1 7 M4

0 1 1 0 6 M3

(cid:1) Vậy từ mã có 12 bit (cid:1) Xác định f (để tính các Ci) (cid:1) 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

0 1 0 1 5 M2

0 1 0 0 4 C2

0 0 1 1 3 M1

(cid:1) 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 đó

0 0 1 0 2 C1

=> Ci = xor tất cả các bit có mặt

trong vòng tròn tương ứng

0 0 0 1 1 C0

0 0 0 0 0 Không sai

Ví dụ

⊕⊕⊕⊕ M7 =1 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 1 ⊕⊕⊕⊕ 1 = 1 ⊕⊕⊕⊕ M7 =1 ⊕⊕⊕⊕ 1 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 1 = 1

(cid:1) Data: 11010101 (M8=1, M7=1, M6=0, M5=1,M4=0, M3=1, M2=0, M1=1) ⊕⊕⊕⊕ M4 (cid:1) Tính ⊕⊕⊕⊕ M4 ⊕⊕⊕⊕ M4 ⊕⊕⊕⊕ M7

⊕⊕⊕⊕ M5 ⊕⊕⊕⊕ M6 ⊕⊕⊕⊕ M8 =0 ⊕⊕⊕⊕ 1 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 1 = 0 ⊕⊕⊕⊕ M8 =1 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 1 ⊕⊕⊕⊕ 1 = 1

C0 = M1 C1 = M1 C2 = M2 C3 = M5

⊕⊕⊕⊕ M2 ⊕⊕⊕⊕ M3 ⊕⊕⊕⊕ M3 ⊕⊕⊕⊕ M6

(cid:1) Từ mã truyền

Vị trí

M8 1

M7 1

M6 0

M5 1

C3 1

M4 0

M3 1

M2 0

C2 0

M1 1

C1 1

C0 1

(cid:1) Giả sử nhận được

Vị trí

M8 1

M7 1

M6 0

M5 0

C3 1

M4 0

M3 1

M2 0

C2 0

M1 1

C1 1

C0 1

Ví dụ (tt)

⊕⊕⊕⊕ M7 =1 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 1 = 0 ⊕⊕⊕⊕ M7 =1 ⊕⊕⊕⊕ 1 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 1 = 1

⊕⊕⊕⊕ M5 ⊕⊕⊕⊕ M6 ⊕⊕⊕⊕ M8 =0 ⊕⊕⊕⊕ 1 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 1 = 0 ⊕⊕⊕⊕ M8 =0 ⊕⊕⊕⊕ 0 ⊕⊕⊕⊕ 1 ⊕⊕⊕⊕ 1 = 0

⊕⊕⊕⊕ M2 ⊕⊕⊕⊕ M3 ⊕⊕⊕⊕ M3 ⊕⊕⊕⊕ M6

(cid:1) Tính lại các Ci theo từ mã nhận được ⊕⊕⊕⊕ M4 (cid:1) C0 = M1 ⊕⊕⊕⊕ M4 C1 = M1 ⊕⊕⊕⊕ M4 C2 = M2 ⊕⊕⊕⊕ M7 C3 = M5 (cid:1) So sánh

Vector hội chứng

C3 1 0 1

C2 0 0 0

C1 1 1 0

C0 1 0 1

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

MẬT MÃ SỐ LIỆU

(cid:1) Mật mã cổ điển (cid:1) Mật mã khóa công khai

Mật mã cổ điển

(cid:1) Hệ thống mật mã (P,C,K,E,D) (cid:1) P là tập hữu hạn các bản gốc (cid:1) C là tập hữu hạn các bản mã (cid:1) K là tập khóa (cid:1) E là tập luật mật mã eK: P-->C (cid:1) D là tập luật giải mã dK: C-->P (cid:1) dK(eK(x)) = x , Với mọi x∈P

(cid:1) Chỉ có khóa mật (cid:1) Mã thay thế, mã affine, mã Vigenére...

Mật mã khóa công khai

(cid:1) Ứ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

(cid:1) Máy A chọn

(cid:1) i) Một số rất lớn pA (giả sử từ 200 đến 300 chữ số), (cid:1) ii) Một phần tử αA modulo pA, (cid:1) iii) Một số nguyên (ngẫu nhiên) dA với 2 ≤ dA ≤ pA –2

(cid:1) Máy A tính (cid:1) iv) αA

(cid:1) Public key của máy A là (pA, αA, βA). Private key là dA

dA ≡ βA (mod pA)

Mật mã khóa công khai (tt)

(cid:1) Máy B mật mã bản tin M để gửi cho máy A: (cid:1) i) Chọn một số nguyên ngẫu nhiên k (giữ bí mật) k (mod pA) và t ≡ βA (cid:1) ii) Tính r ≡ αA (cid:1) Máy B gửi bản mật (r, t) đến máy A.

(cid:1) Khi máy A nhận bản mật (r, t), nó sẽ dùng khóa riêng

tr −

k )−dA (mod pA)

k M (αA dA)k M (αA

k )−dA (mod pA)

(private key) dA để giải mã bằng cách tính tr−dA ≡ βA ≡ (αA ≡ M (mod pA)

k M (mod pA), sau đó bỏ k.