Bài giảng Lý thuyết thông tin: Chương 2.2 - ThS. Huỳnh Văn Kha

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

89
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết thông tin - Chương 2 cung cấp cho người học những kiến thức về bài toán mã trường hợp kênh không bị nhiễu. Trong phần 2.2 này chúng ta sẽ tìm hiểu về sự tồn tại của bộ mã tiền tố và giải được. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết thông tin: Chương 2.2 - ThS. Huỳnh Văn Kha

Chương 2: Bài toán mã trường hợp kênh không bị nhiễu 2.2 Sự tồn tại của bộ mã tiền tố và giải được
2 Huỳnh Văn Kha 9/30/2010 Mở ñầu • Cho biến ngẫu nhiên X có các giá trị x1, x2, …, xM. Tập các ký tự mã a1, a2, …, aD • Cho trước các số nguyên dương n1, n2, …, nM • Bài toán đặt ra là: có thể xây dựng bộ mã giải được sao cho từ mã ứng với xk có chiều dài là nk? • Mã tiền tố có thể giải mã từng bước • Trong bài toán kênh không bị nhiễu, mã giải được có thể quy về mã tiền tố • Đầu tiên ta sẽ xét sự tồn tại của bộ mã tiền tố, sau đó mở rộng cho bộ mã giải được
3 Huỳnh Văn Kha 9/30/2010 Ví dụ • Ví dụ 1: M = 3, D = 2, n1 = 1, n2 = 2, n3 = 3 Có thể chọn bộ mã {0, 10, 110} • Ví dụ 2: M = 3, D = 2, n1 = n2 = 1, n3 = 2 Không có bộ mã giải được nào thỏa yêu cầu bài toán (sẽ chứng minh sau) • Khi nào có thể xây dựng được bộ mã thỏa yêu cầu, khi nào không?
4 Huỳnh Văn Kha 9/30/2010 ðịnh lý 2.2 Một bộ mã tiền tố với chiều dài các từ mã n1, n2, …, nM là tồn tại khi và chỉ khi Trong đó D là số các ký tự mã
5 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 2.2 • Cây bậc D kích thước k là một hệ thống các điểm và đoạn thẳng • Mỗi dãy s được tạo thành từ các ký tự trong {0, 1, …, D – 1} có chiều dài không lớn hơn k được biểu diễn bởi một điểm Vs khác nhau • Nếu dãy t có được do thêm duy nhất một ký tự vào sau s thì nối Vs và Vt bằng một đoạn thẳng • Các điểm ứng với dãy có chiều dài k gọi là các điểm ngọn của cây kích thước k
6 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 2.2 00 000 00 0 01 001 0 02 010 10 Cây bậc 01 011 Cây bậc 2 1 11 3 kích kích thước 3 thước 2 100 12 10 101 20 1 110 2 21 11 22 111
7 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 2.2 • Giả sử n1 ≤ n2 ≤ … ≤ nM • Mỗi từ mã được đồng nhất với một điểm trên cây bậc D kích thước nM 0 Cây ứng với bộ 10 mã {0, 10, 111} 1 11 111
8 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 2.2 • Do bộ mã là tiền tố nên khi điểm P đại diện cho một từ mã, thì không điểm nào trên nhánh bắt đầu từ P đại diện cho một từ mã khác • Điểm ứng với từ mã chiều dài nk sẽ che điểm ngọn của cây • Số điểm ngọn bị toàn bộ bộ mã che ≤ Tổng số các điểm ngọn của cây
9 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 2.2 • Ngược lại, giả sử và n1 ≤ n2 ≤ … ≤ nM • Chọn điểm bất kỳ trên cây ứng với dãy có chiều dài n1. Điểm này che điểm ngọn • Còn lại ít nhất 1 điểm ngọn, chọn được điểm ứng với n2. Lúc đó, do ta chọn được điểm ứng với n3. Và cứ thế cho đến hết
10 Huỳnh Văn Kha 9/30/2010 Mở rộng cho bộ mã giải ñược • Điều kiện ở định lý 2.2 cũng là điều kiện cần và đủ cho sự tồn tại của bộ mã giải được • Do bộ mã tiền tố là giải được nên chỉ cần chứng minh định lý sau là đủ. Định lý 2.3: Nếu bộ mã giải được có chiều dài từ mã lần lượt là n1, n2, …, nM thì:
11 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 2.3 • Gọi ωj là số từ mã chiều dài j và r là chiều dài lớn nhất của các từ mã, ta có: • Với mỗi số tự nhiên n cho trước, nhân phân phối và rút gọn, ta được:
12 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 2.3 • Trong đó: • Nk chính là tổng số mẫu tin được tạo thành từ n trạng thái xi sao cho đoạn mã của các mẫu tin này đều có chiều dài k • Bộ mã là giải được nên mỗi dãy ký tự mã tương ứng với nhiều nhất một mẫu tin • Nk không vượt quá tổng số các dãy ký tự mã có chiều dài k
13 Huỳnh Văn Kha 9/30/2010 Chứng minh ñịnh lý 2.3 • Như vậy Nk ≤ Dk và ta có: • Lấy căn bậc n: • Cho n tiến ra vô cực ta được điều cần chứng minh