CHƯƠNG 1: GIỚI THIỆU

– Đầu vào: nhận tính hiệu là các ký hiệu theo tập hợp và phân phối. Có  thể bị nhiễu thông qua kênh truyền

– Đầu ra: Tính hiệu từ đầu vào có thể bị nhiễu

– Định nghĩ kênh truyền: (bit) – xác định tốc độ truyền tối đa của mỗi kênh

  • Vật lý: một hệ thống truyền tín hiệu (dây dẫn, mạch, sóng, …) và gây nhiễu tùy thao chất lượng của hệ thống.
  • Toán học: các phân phối xác suất xác định trên lớp các tín hiệu đang xét ở đầu nhận tín hiệu (output).

– Mô hình lý thuyết thông tin:

  • Nguồn: Input
  • Mã hóa: bộ sinh mã
    •  Số nghị phân (01010101)
    • Sóng liên tục (radio)
  • Kênh: phương tiện truyền mã của thông tin.
  • Nhiễu: sinh ra do kênh truyền tin. Tùy vào chất lượng của kênh truyền mà nhiễu nhiều hay ít.
  • Giải mã : output đưa dãy mã trở về dạng thông báo ban đầu với xác suất cao nhất. Sau đó thông báo sẽ được chuyển cho nới nhận.

– Định lý cơ sở của kỹ thuật truyền tin 

Feinstein – 1954: “Trên một kênh truyền có nhiễu, người ta luôn có thể thực hiện một phương pháp truyền sao cho đạt được sai số nhỏ hơn sai số cho phép (nhỏ bất kỳ) cho trước đối với kênh truyền.”

CHƯƠNG 2: LƯỢNG TIN

1. Entropy

Entropy của X là lượng tin không chắc chắn của X

Lượng tin:

  • Xác xuất nhỏ: ít xảy ra, không chắc chắn lớn, lượng tin ko biết lơn, entropy lớn
  • Phân phối đều: không chắc chắn lớn, ko chắc chắn lớn, entropy lớn
  • Lệch nhiều: ko chắc chắn ít, tin chưa biết nhỏ, entropy nhỏ.

Khái niệm: 

– Entropy là một đại lượng toán học dùng để đo lượng tin không chắc (hay lượng ngẫu nhiên) của một sự kiện hay của phân phối ngẫu nhiên cho trước.

– Entropy sự kiện:

  • p ⊆ [0,1]. Hàm h(p) được gọi là Entropy nếu nó thoả 2 tiêu đề toán học sau:
  • Tiên đề 01: h(p) là hàm liên tục không âm và đơn điệu giảm.
  • Tiên đề 02: nếu A và B độc lập –> p(A,B) = pA.pB nhưng h(A,B) = h(pA) + h(pB).

– Entropy phân phối:

  • Entropy của X chính là kỳ vọng toán học của Y=h(X) có dạng:
  • H(X)=H(p1, p2, p3, …,pn) = p1h(p1)+ p2h(p2)+…+pnh(pn).
  • Tổng quát:

– Công thức:  – Ví dụ: 2. Tính chất Entropy

1. Ngẫu nhiên phân phối đều, xác suất nhỏ, entropy lớn:

2. 2 biến ngẫu nhiên độc lập phân phối đều

3. Gom các sự kiện để tạo xác suất mới

4. Hàm liên tục

– Định lý cực đại:

3. Entropy của nhiều biến

– Định nghĩa

– Entropy có điều kiện:

CHƯƠNG 3: SINH MÃ TÁCH ĐƯỢC

1. Khái niệm

– Bài toán sinh mã

  • Bộ mã được gọi là tách được nếu như ta luôn giải mã được với kết quả duy nhất từ một dãy liên tục các ký tự mã nhận được.
  • Bài toán sinh mã tối ưu: độ dài trung bình các từ mã là nhỏ nhất

– Bảng mã không tách được: 

Bảng mã không tách được là bảng mã mà khi mã hóa thông báo Msg ta sẽ nhận được một dãy các từ mã ws, và khi giải mã dãy các từ mã ws thì ta có thể nhận được nhiều thông báo Msg khác nhau.

– Bảng mã tách được: 

  • Bảng mã tách được là bảng mã mà khi mã hóa thông báo Msg ta sẽ nhận được dãy các từ mã ws, và khi giải mã dãy các từ mã ws thì ta chỉ nhận được một thông báo duy nhấtMsg ban đầu.
  • Có thể là tiền tố hoặc hậu tố của mã khác
  • Định lý: Điều kiện cần và đủ để W là bảng mã tách đuoc: Sk ∩S0 ≠ ∅ (k≥1)

– Bảng mã tức thời:

  • Bảng mã tách được + Bảng mã tức thời là bảng mã không tồn tại từ mã này là tiền tố của từ mã khác.
  • Điều kiện cần và đủ để tồn tại bảng mã tức thời:

  • Ví dụ 1: Bảng mã W={w1=10; w2=101; w3=100} không phải bảng mã tức thời vì w1 là tiền tố của w2 và w3. 
  • Ví dụ 2: Bảng mã W={w1=0, w2=100, w3=101, w4=11} là bảng mã tức thời vì không tồn tại từ mã này là tiền tố của từ mã khác.

2. Định lý Kraft 1949- Quan hệ mã tách được và độ dài mã

– Điều kiện cần và đủ để tồn tại bảng mã tức thời:

Cây bậc D cỡ k:

    • D nút con tối đa
    • k cành từ lá đến gốc

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

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ó.

3. Tính tối ưu của độ dài mã – Định lý Shannon

– Bảng mã tối ưu tương đối và tuyệt đối

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

– Phương pháp sinh mã Huffman: Bài tập

CHƯƠNG 4: KÊNH TRUYỀN

1. Kênh truyền rời rạc không nhớ

Rời rạc: Truyền rời rạc từng ký tự và nhận rời rạc từng ký tự.

Không nhớ: Ký tự nhận sau không phụ thuộc vào ký tự nhận trước.

– Mô hình vật lý

– Dung lượng kênh truyền

2. Các dạng kênh truyền

– Kênh truyền không mất thông tin: 1 x –> nhiều y

– Kênh truyền xác định: nhiều x –> 1 y

– Kênh truyền không nhiễu: kết hợp giữa xác định + ko mất thông tin

– Kênh truyền không sử dụng được:

– Kênh truyền đối xứng: Dòng là hoán vị của P, cột là hoán vị của Q.

3. Lược đồ giải mã

– Sơ đồ truyền tin:

– Các khai niệm cơ bản:

– Các dạng sai số cơ bản:

CHƯƠNG 5: SỬA LỖI

BÀI TẬP

1. Tính entropy của nhiều biến

2. Tính entropy có điều kiện

3.  Phương pháp sinh mã Huffman