Tương tác người máy

Mã hóa Entropy (Lossless coding)Là các dạng mã hóa nhằm loại bỏ các dư thừa thông tin. Thông tin sau khi giải mã bằng chính xác thông tin trước khi mã.Mã hóa dự đoán (Lossy coding)Là các dạng mã hóa nhằm loại bỏ các dư thừa thông tin. Thông tin sau khi giải có thể (ít nhiều) khác thông tin trước khi mã.
Nội dung trích xuất từ tài liệu:
Tương tác người máy Lê Thanh Hà, TS.Phòng thí nghiệm Tương tác người máy Số lượng dữ liệu âm thành, phim ảnh trở nên khổng lồ. Nhưng hệ thống lưu trữ và truyền tải hạn chế. Cần những phương pháp giảm kích thước âm thanh và hình ảnh để lưu trữ và truyền tải hiệu quả.11/4/2013 Lê Thanh Hà 2 Sự dư thừa về mặt không gian chính là ở giữa các điểm của một ảnh. Nói rõ hơn, các điểm ảnh thường có quan hệ mật thiết với nhau.11/4/2013 Lê Thanh Hà 3 Mã hóa Entropy (Lossless coding) Là các dạng mã hóa nhằm loại bỏ các dư thừa thông tin. Thông tin sau khi giải mã bằng chính xác thông tin trước khi mã. Mã hóa dự đoán (Lossy coding) Là các dạng mã hóa nhằm loại bỏ các dư thừa thông tin. Thông tin sau khi giải có thể (ít nhiều) khác thông tin trước khi mã.11/4/2013 Lê Thanh Hà 4 Đo thông tin Giả thiết một biểu tượng x với xác suất xuất hiện p, thì nội dung thông tin của nó (thông tin chứa trong biểu tượng) là: I ( x)   log( p ( x)) Độ đo thông tin không phụ thuộc vào giá trị biểu tượng Độ đo thông tin chỉ phụ thuộc vào xác suất của biểu tượng Khi cơ sở của hàm log là 2 thì đơn vị tính của độ đo thông tin gọi là bit.11/4/2013 Lê Thanh Hà 5 Entropy thông tin Entropy được định nghĩa là trung bình thông tin đối với mỗi biểu tượng trong một nguồn. Entropy, H, được thể hiện như sau: H ( X )   p ( x) I ( x)    p ( x) log( p ( x)) x x Từ định nghĩa này, entropy của một nguồn thông tin là một hàm của xác suất xảy ra. Entropy đạt giá trị cực đại khi mọi biểu tượng đều xảy ra với xác suất như nhau11/4/2013 Lê Thanh Hà 6 Ví dụ nguồn thông tin digital ={0,1}, p(0)=1/3, p(1)=1-p(0)=2/3 p(1)=1- H ( X )   p (0) log( p (0)  p (1) log( p (1)) 1 1 2 2   log( )  log( ) 3 3 3 3  0.64611/4/2013 Lê Thanh Hà 7 Đồ thị Entropy là 1 hàm lồi với p Khi p tiến gần tới 0 hoặc 1 thì nguồn  mang càng ít thông tin. Cực đại tại p=0.511/4/2013 Lê Thanh Hà 8 Tính Entropy H(X) của: a p (a)  1/ 2 b p (b)  1/ 4  X  c p (c)  1/ 8 d  p (d )  1/ 811/4/2013 Lê Thanh Hà 911/4/2013 Lê Thanh Hà 10 1 2 1 2 1 1 1 3 3 2 3 1   1 5 6 5 5 1 I   2 5 7 7 4 2 1 3 3 2 3 1   1 2 1 1 1 211/4/2013 Lê Thanh Hà 11 Tổng số lượng bit dùng để thể hiện dữ liệu có thể tính được trên nội dung thông tin. Những biểu tượng với khả năng xảy ra cao được thể hiện bằng các đoạn mã ngắn trong khi đó những biểu tượng với khả năng xảy ra thấp được thể hiện bằng những đoạn mã dài hơn Kết quả là giảm được số lượng bit trung bình cần cho một biểu tượng11/4/2013 Lê Thanh Hà 12 Mã C cho một nguồn X là 1 ánh xạ từ tập  (miền của X), tới D*. D* là tập các chuỗi ký tự mã. Ví dụ: Nguồn X là màu sắc,  = {Red, Blue} C(Red)=00, C(Blue)=11 là mã cho tập ={Red,Blue) với D={0,1} Độ dài trung bình của mã C: L(C )   p ( x)l ( x) x11/4/2013 Lê Thanh Hà 13 Mã C được gọi là mà tiền tố (prefix code) nếu không có mã nào là tiền tố của mã nào. 00 là tiền tố của 001 Mã C(1)=0, C(2)=10, C(3)=110, C(4)=111 là mà tiền tố Mã tiền tố cho phép giải mã mà không phải duyệt đến cuối chuỗi mã.11/4/2013 Lê Thanh Hà 14Ví dụ - mã hóa độ dài cố định Biểu tượng x Xác suất Đoạn mã C(x) Độ dài đoạn mã L(c) A 0.75 00 2 B 0.125 01 2 C 0.0625 10 2 D 0.0625 11 2 Số bit trung bình/ biểu tượng = 0.75*2 + 0.125*2 + 0.0625*2 + 0.0625*2 = 2.0 bits/biểu tượng11/4/2013 Lê Thanh Hà 15Ví dụ - mã hóa có độ dài không cố định Biểu tượng Xác suất Đoạn mã Độ dài đoạn mã A 0.75 0 1 B 0.125 10 2 C 0.0625 110 3 D 0.0625 111 3 Số bit trung bình/ biểu tượng = 0.75*1 + 0.125*2 + 0.0625*3 + 0.0625*3 = 1.375 bits/biểu tượng (tiết kiệm 30% mà không mất dữ liệu)11/4/2013 Lê Thanh Hà 16 Exp- Exp-Golomb codes Thường được sử dụng trong n ...