Giáo Trình Lý Thuyết Thông Tin: Tính Tối ưu Của độ Dài Mã - .vn

Donate to VNFoundation Project name

• Trang chủ
• Tra cứu tài liệu
• Đóng góp
• Giới thiệu

• • 
• Đăng ký
• Đăng nhập

Đăng nhập

• Ghi nhớ
• Quên mật khẩu?

Đăng nhập Bạn chưa có tài khoản? Hãy đăng ký. Tên đăng nhập hoặc mật khẩu chưa đúng GIÁO TRÌNH giáo trình lý thuyết thông tin Science and Technology

tính tối ưu của độ dài mã

Tác giả: duongvanhieu 0

Mục tiêu

Sau khi hoàn tất bài học này bạn có thể:

Hiểu định lý Shannon (1948),

Biết được các tiêu chuẩn đánh giá bảng mã tối ưu tuyệt đối và bảng mã tối ưu tương đối,

Điều kiện nhận biết một bảng mã tối ưu,

Hiểu Định lý Huffman,

Biết Phương pháp sinh mã Huffman,

Vận dụng phương pháp sinh mã Huffman để sinh mã Huffman cho một thông báo,

Vận dụng phương pháp sinh mã Huffman để viết chương trình nén.

Định lý Shannon (1948)

Phát biểu định lý:

Đặt

là độ dài trung bình của bảng mã.

Khi đó

Dấu đẳng thức xảy ra khi và chỉ khi

Diễn giải: Đối với mã tách được độ dài trung bình của mã sẽ có cận dưới làH(x)/Log2(d). Nếu mã không tách được độ dài trung bình của nó có thể nhỏ hơn cận dưới. Nếu mã tách được không tối ưu thì độ dài của nó sẽ lớn hơn nhiều so với cận dưới, còn nếu mã tách được tối ưu thì độ dài trung bình của nó gần với cận dưới.

Bài toán đặt ra sẽ là tìm phương pháp xây dựng bảng mã tách được tối ưu.

Chú ý:

là entropy của X với cơ số D.

Bảng mã tối ưu tuyệt đối

Định lý: Bảng mã được gọi là tối ưu tuyệt đối khi

Ví dụ: xét biến ngẫu nhiên X={x1, x2, x3, x4}

Có phân phối: P={1/2, 1/4, 1/8, 1/8}

Có bảng mã W={w1= 0, w2=10, w3=110, w4=111}

Ta tính được độ dài trung bình từ mã:

Tính Entropy của X: H(X)= H(0.5, 0.25, 0.125, 0.125) = 0.5 +0.5 + 0.375 + 0.375 =1.75

Log2D=1.

Bảng mã tối ưu tương đối

Định lý: Bảng mã được gọi là tối ưu tương đối khi:

Điều kiện nhận biết một bảng mã tối ưu

Định lý (với D=2):

• Xác suất pi càng lớn thì độ dài ni của từ mã wi càng nhỏ.
• Giả sử p1_> p2 _> …1_> pM. Nếu pi_> pi+1 _> pi+r thì ni <_ni+1 <_ni+r thì 2 từ mã tương ứng với 2 giá trị có xác suất nhỏ nhất có độ dài mã bằng nhau nM-1 =nM.
• Trong các từ mã có độ dài bằng nhau và cùng bằng nM (dài nhất) thì tồn tại ít nhất 2 từ mã wM-1 và wM có M-1 ký tự đầu giống nhau và ký tự thứ M khác nhau.

Ví dụ: xét bảng mã W={w1=0, w2=100, w3=101, w4=1101, w5=1110}

Bảng mã trên không phải là bảng mã tối ưu vì 2 từ mã w4, w5 có độ dài lớn nhất =4 ký tự nhưng 3 ký tự đầu khác nhau.

Ghi chú: D > 2 được xét tương tự.

Định lý Huffman

Định lý: Giả sử X có phân phối xác suất với thứ tự giảm dần sau:

Giả sử bảng mã của X là W={w1, w2, …, wM-1, wM}.

Đặt xM-1,M={xM-1, xM} có xác suất là pM-1,M=pM-1+pM.

và X* = { x1, x2,…, xM-1,M} có phân phối sau:

Giả sử W* ={w1, w2, …, wM-2, x*M-1,M} là bảng mã tối ưu của X*. Khi đó:

- wM-1=w*M-1,M + “0”.

- wM =w*M-1,M + “1”.

Phương pháp sinh mã Huffman

Giả sử X có phân phối xác suất với thứ tự giảm dần sau:

Thủ tục lùi (D=2):

Khởi tạo: Đặt M0=M

Bước 1:

- Đặt

có xác suất

- Sắp xếp lại theo tứ tự giảm dần của xác suất ta nhận được dãy phân phối mới có M0-1 phần tử như sau:

Bước 2: Lặp lại bước 1 với sự lưu vết

Giảm M0: M0=M0-1, vòng lặp kết thúc khi M0=2

(Chú ý: trong trường hợp tổng quát, vong lặp kết thúc khi M0 <_ D.)

Thủ tục tiến:

Đi ngược lại so với thủ tục lùi đồng thời xác định từ mã ở mỗi bước từ sự lưu vết ở thủ tục lùi.

Minh họa phương pháp sinh mã Huffman

Ví dụ 1: sinh bảng mã nhị phân Huffman cho X có phân phối sau:

Thủ tục lùi: Độ dài trung bình của từ mã:

Vecto n=(0.3 x 2)+ (0.25 x 2)+ (0.2 x 2) + (0.1 x 3) +(0.1 x 4) + (0.05 x 4) = 2.4

Entropy của X: H(X) = H(0.3, 0.25; 0.2, 0.1,0.1, 0.05)

= 2.4

Nhận xét: Do D = 2 và log2D=1, Ta có vecto n = H(X) nên bảng mã trên tối ưu tuyệt đối.

Bài tập

Cho biến ngẫu nhiên X có phân phối sau:

Cho biến ngẫu nhiên Y có phân phối sau:

Cho đoạn văn bản “thoi the thi thoi thi the thoi thi the”. Tìm bảng mã nhị phân Huffman dùng để mã hóa đoạn văn bản trên.

Thay từng ký tự trong đoạn văn bản trên thành một từ mã, cắt từng đoạn 8 bits đổi thành số thập phân. Cho biết dãy số thập phân kết quả.

0 TẢI VỀ TÁI SỬ DỤNG

• Tài liệu PDF
• Tài liệu EPUB

• duongvanhieu
• 2 GIÁO TRÌNH | 30 TÀI LIỆU

MỤC LỤC

• giáo trình lý thuyết thông tin
• giới thiệu tổng quan giáo trình lý thuyết thông tin
• yêu cầu
• nội dung cốt lõi
• kiến thức tiên quyết
• phương pháp học tập
• giới thiệu
• mô hình lý thuyết thông tin theo quan điểm Shannon
• định lý cơ sở của kĩ thuật truyền tin
• khái niệm về dung lượng kênh truyền
• độ đo lượng tin
• các tính chất của entropy
• entropy của nhiều biến
• minh họa các entropy
• ĐO LƯỢNG TIN (MESURE OF INFORMATION)
• SINH MÃ TÁCH ĐƯỢC (Decypherable Coding)
• quan hệ giữa mã tách được và độ dài mã
• tính tối ưu của độ dài mã
• kênh truyền rời rạc không nhớ
• các dạng kênh truyền
• lược đồ giải mã
• nguyên lý khoảng cách nhỏ nhất hamming
• Bổ đề về tự sửa lỗi và cận hamming
• mã kiểm tra chẵn lẻ
• nhóm cộng tính và bộ từ mã chẵn lẻ
• lược đồ sửa lỗi tối ưu
• mã hamming
• thanh ghi lùi tưng bước
• mã xoay vòng
• đa thức đặc trưng của thanh ghi
• phương pháp sinh mã xoay vòng
• bài tập tổng hợp

NỘI DUNG CÙNG TÁC GIẢ

• nội dung cốt lõi
• thanh ghi lùi tưng bước
• mã hamming
• Bổ đề về tự sửa lỗi và cận hamming
• ĐO LƯỢNG TIN (MESURE OF INFORMATION)
• định lý cơ sở của kĩ thuật truyền tin
• lược đồ giải mã
• khái niệm về dung lượng kênh truyền
• giới thiệu
• minh họa các entropy

×

VOER message

×

VOER message

Thư viện Học liệu Mở Việt Nam (VOER) được tài trợ bởi Vietnam Foundation và vận hành trên nền tảng Hanoi Spring. Các tài liệu đều tuân thủ giấy phép Creative Commons Attribution 3.0 trừ khi ghi chú rõ ngoại lệ.

•