quan hệ giữa mã tách được và độ dài mã

QUAN HỆ GIỮA MÃ TÁCH ĐƯỢC VÀ ĐỘ DÀI MÃ

Mục tiêu

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

• Định lý Kraft (1949),
• Định nghĩa cây bậc D cỡ K,
• Vấn đề sinh mã cho cây bậc D cỡ K,
• Vận dụng định lý Kraff để kiểm tra sự tồn tại bảng mã tách được và sinh bảng mã tách được.

Định lý Kraftn(1949).

Gọi X={x₁, x₂,…, x_M} là biến ngẫu nhiên chứa các giá trị cần truyền có phân phối là P={p₁, p₂, …, p_M}.

A={a₁, a₂,…,a_D} là bộ ký tự sinh mã có D chữ cái (D được gọi là cơ số sinh mã).

Giá trị x_i được mã hóa thành từ mã w_i có độ dài là n_i.

Đặt N={n₁, n_2,…,n_M} là tập hợp độ dài các từ mã.

Định lý (Kraft- 1949):

Điều kiện cần và đủ để tồn tại bảng mã tức thời với độ dài N={n₁,n₂,…,n_M} là

Ví dụ 1: Bộ mã W={w₁, w₂, w₃} với M=3; n₁=1; n₂=2; n₃=3; D=2

=> Tồn tại bảng mã tức thời.

Ví dụ 2: Bộ mã W={w₁, w₂, w₃} với M=3; n₁=n₂=1; n₃=2; D=2

=> Không tồn tại bảng mã tức thời.

Đề nghị: sinh viên tìm hiểu nội dung tiếp theo và trở lại giải thích 2 ví dụ trên.

Định nghĩa cây bậc D cỡ k.

Định nghĩa: Cây bậc D cỡ k là cây có hệ thống nút, cạnh thỏa điều kiện:

• Từ 1 nút có số cạnh đi ra không vượt quá D hay một nút có không quá D nút con.
• Nút cuối cùng (Nút lá) cách nút gốc không vượt quá k cạnh.

Ví dụ: cây bậc D=2 và cỡ k=3

Vấn đề sinh mã cho cây bậc D cỡ k

Sinh mã cho các nút của cây bậc D cỡ K (trừ nút gốc):

Để đơn giản hóa: mỗi nút (trừ nút gốc) được ký hiệu bởi dãy ký hiệu của nút cha làm tiền tố + một ký tự bổ sung lấy từ tập hợp {0, 1, 2, …, D-1} thay cho bảng chữ cái A={a₁, a₂, …, a_D}.

Ví dụ 1: Cây bậc D=2 cỡ k=3 Ví dụ 2: Cây bậc D=3 cỡ k=2.

Tính chất:

+ Các nút (trừ nút gốc) của cây đều được mã hóa từ bảng chữ cái {0, 1, 2,…, D-1}

+ Mỗi nút (đã mã hóa) có mã của nút kề trước là tiền tố.

+ Tổng số các nút lá bằng D^k = tổng số các mã tức thời có thể có.

Chứng minh định lý Kraft (Điều kiện cần)

Giả sử, cho trước bảng mã tức thời W={w₁, w₂,…, w_M} với N={n₁<_ n₂ <_ …<_ n_M}. Ta cần c/m:

Xây dựng cây bậc D cỡ n_M và sinh mã cho các nút trừ nút gốc với các ký tự mã lấy từ bảng chữ cái A = {0, 1, 2,…, D-1}. Mã tại mỗi nút (trừ nùt gốc) đều có khả năng được chọn là từ mã.

Như vậy, ta tiến hành chọn các từ mã cho bảng mã tức thời với qui tắc là: một nút nào đó được chọn để gán một từ mã thì tất cả các nút kề sau nút gán từ mã phải được xóa. Cụ thể như sau:

Chọn một nút có mã với độ dài mã là n₁ gán cho nó một từ mã w₁.

Chứng minh định lý Kraft (Điều kiện đủ)

Giả sử:

,

để cần chứng minh tồn tại bảng mã tức thời với N={n₁, n₂, …, n_M}, ta chỉ cần chỉ ra thủ tục xây dựng bảng mã tức thời như sau:

Thủ tục tạo mã tức thời:

Xét N={n₁, n₂, …,n_M} và cơ số sinh mã là D:

Bước 1: Ta xếp thứ tự n₁<_ n₂ <_ … <_ n_M, xây dựng cây bậc D cỡ k=n_M và sinh mã cho các nút.

Bước 2: Chọn nút bất kỳ trên cây có độ dài n₁ gán cho từ mã w₁ và xóa tất cả các nút kề sau nó.

Bước 3: Lặp lại các bước 2 đối với việc chọn các từ mã còn lại w₂, …, w_M ứng với n₂, …, n_M.

=> Bảng mã W={w₁, w₂, …, w_M} là bảng mã tức thời.

Ví dụ minh họa định lý Kraft

Ví dụ 1: Xét bảng mã thỏa M=3, D=2, n₁=1, n₂=2, n₃=3. Vậy ta kiểm tra xem có tạo được bảng mã tức thời hay không?

Ta có

=> W= {w₁, w₂, w₃} là bảng mã tức thời

Ta Xây dựng bảng mã như sau:

Chú ý: ngoài bảng mã tức thời chọn được ở trên, ta còn có thể sinh được nhiều bảng mã tức thời khác. Đề nghị sinh viên đưa ra bảng mã tức thời khác.

Bài tập

Tìm 1 bảng mã tách được thỏa tính chất D = 2, k = 4?

Tìm tất cả các bảng mã tách được thỏa tính chất D=2, k=3?

Hãy chỉ ra bảng mã sau đây là bảng mã không tách được:

W={w1=00, w2=1, w3=100, w4=110, w5=111}

Hãy tìm một bảng mã nhị phân tách được có ít nhất 5 từ mã thỏa điều kiện