LTTT

GIÁO VIÊN HƯỚNG DẪN: BÙI THỊ MINH TÚ

SINH VIÊN THỰC HIỆN : 1. HỒ VŨ DUY BẢO(1)

2. PHẠM ĐỖ DUY NGUYÊN(9)

3. TRẦN MẠNH TIẾN(17)

BẢO

NGUYÊN

TIẾN

HỆ THỐNG TRUYỀN TIN SỐ

CÁC LOẠI MÃ

Bảng mã không tách được là bảng mã có tồn tại 2 hoặc nhiều từ mã giống nhau.

*Ví dụ: Biến ngẫu nhiên X và bộ từ mã W

Thông báo nguồn có nội dung: x4x2x3x4x3x2x1 ???

=> Khi đó dãy mã tương ứng viết từ W có dạng: 001010001101

Bảng mã giải mã không tách được là bảng mã mà trong đó tồn tại 2 từ mã trùng nhau trong bộ mã (ví dụ từ mã w1=01 trùng với W3=01).

TẤT CẢ CÁC MÃ

Bảng mã tách được là bảng mã KHÔNG có tồn tại 2 hoặc nhiều từ mã giống nhau

*Ví dụ: Biến ngẫu nhiên X và bộ từ mã W

Giả sử dãy mã nhận được ( cần giải mã) là: 0010000101001.

Bảng mã tách được là bảng mã gồm các từ mã khác nhau!

MÃ TÁCH ĐƯỢC

VÍ DỤ:

Lập bảng thử mã cho bộ mã sau:

A={00,01,011,1100,00010}

+Một bộ mã được gọi là tách được duy nhất (uniquely decodable) khi bộ mã mở rộng từ nó là tách được.

Bộ mã mở rộng C* của C là phép biến đổi chuỗi các giá trị của biến X thành chuỗi từ mã:

+ Ví du: ĐỎ -->00

VÀNG -->11

XANH -->10

(1) Đem các từ mã xếp thành một cột, theo thứ tự chiều dài của từ mã từ nhỏ đến lớn, đánh dấu là cột 1

(2) Trong cột này, đối chiếu các từ mã ngắn với các từ mã dài hơn, nếu từ mã ngắn là tiếp đầu ngữ của từ mã dài thì ghi tiếp vĩ ngữ vào cột tiếp theo và đánh dấu là cột 2.

(3) Tiếp tục, đối chiếu các chuỗi trong cột 1 và cột 2 với nhau. Nếu có chuỗi nào trong cột này là tiếp đầu ngữ của chuỗi trong cột kia thì tiếp vĩ ngữ sẽ được ghi vào cột tiếp theo là cột 3.

(4) Tiếp tục theo khuôn mẫu nãy nếu đang xét cột thư sJ thì đối chiếu các chuột trong cột này với cột 1. Nếu có chuỗi nào trong cột này là tiếp đầu ngữ của chuỗi trong cột kia thì tiếp vĩ ngữ sẽ được ghi vào cột j + 1. Thực hiện cho đến khi không thể điền thêm được nữa(mã tách được duy nhất) hoặc có một chuỗi trong cột mới trùng với một từ mã (mã tách được nhưng không duy nhất).

Mã là phân tách được không duy nhất, trên chuỗi 000101100 vì có hai cách phân tách khác nhau:

00|01|011|00

00010|1100

MÃ TÁCH ĐƯỢC

DUY NHẤT

MÃ TỨC THỜI

+Một bộ mã được gọi là tức thời (instantaneous code hay prefix code) nếu không tồn tại từ mã nầy là tiền tố của từ mã khác.

Ví dụ:

BỘ MÃ VỚI CHIỀU DÀI TỪ MÃ BIẾT TRƯỚC

+Mục đích của mã hóa dữ liệu: mã tách được duy nhất có chiều dài từ mã ngắn nhất.

+Không có bộ mã bao gồm tất cả từ mã có chiều dài ngắn.

+Để đảm bảo tính tách được duy nhất: một số từ mã có chiều dài dài trong khi các từ mã khác ngắn hơn.

KRAFT

EXAMPLE

+Cho bảng chữ cái có kích thước D = 2.

Ta có: Ví dụ 1:

+Tồn tại mã tức thời cho các từ mã có chiều dài 1, 3, 3, 3 vì:

Ví dụ 2:

+Không có mã tức thời có chiều dài

1, 2, 2, 2 vì:

Define

+ Cho mã tức thời có:

+Bảng chữ cái A có kích thước D.

+ Chiều dài từ mã: l1, l2,…,lm.

+Chiều dài từ mã phải thỏa mãn (bất đẳng thức Kraft):

+Ngược lại, nếu có tập hợp các từ mã thỏa mãn bất đẳng thức Kraft thì sẽ tồn tại bộ mã tức thời tạo bởi các từ mã có chiều dài như trên.

Practice

x