Lý thuyết thông tin là nghiên cứu về cách dữ liệu có thể được mã hóa và giải mã, nén và giải nén. Mục tiêu chính của lý thuyết thông tin, như Claude Shannon đã đặt ra, là truyền thông tin đáng tin cậy qua một kênh không đáng tin cậy. Trong các bài viết này, chúng ta sẽ thảo luận về độ dài tối thiểu mà dữ liệu có thể được nén xuống, cũng như lượng dư thừa tối thiểu cần thêm vào dữ liệu để mã hóa sao cho có thể giải mã không có lỗi.
Lưu ý: trong các bài viết này, $\log(x)$ đề cập đến $\log_2(x)$.
Giả sử chúng ta có một sự kiện \( x_i \) thuộc về phân phối xác suất \( P(X) \). Khi đó, lượng thông tin Shannon của sự kiện đó là:
$$h(x_i) = \log\left(\frac{1}{p(x_i)}\right)$$
Ví dụ, giả sử thời tiết có xác suất mưa là \( 0.5 \), và một ngày bạn bước ra ngoài và thấy trời đang mưa. Khi đó lượng thông tin thu được từ sự kiện này là: \( \log_2{2} = 1 \text{ bit}\). Chúng ta thu được một bit thông tin mỗi khi chúng ta giảm một nửa không gian mẫu của tất cả các chuỗi sự kiện có thể xảy ra. Nếu trời mưa với xác suất \( 0.25 \), thì lượng thông tin thu được sẽ là \( 2 \) bit, bởi vì chúng ta đã cắt không gian mẫu thành một nửa hai lần. Một cách trực quan, lượng thông tin thu được từ một sự kiện \( x_i \) đo lường mức độ ngạc nhiên của chúng ta khi sự kiện đó xảy ra. Nếu chúng ta biết chắc chắn rằng trời sẽ mưa, thì lượng thông tin thu được sẽ là \( \log_2{1} = 0 \text{ bit} \), bởi vì chúng ta hoàn toàn không ngạc nhiên - chúng ta không thu được thông tin mới nào từ việc nhìn thấy trời mưa vì chúng ta đã biết trời sẽ mưa!
Entropy của một phân phối xác suất, \( H(X) \), chỉ là kỳ vọng của lượng thông tin thu được:
$$H(X) = \sum_i{p(x_i) \log\left(\frac{1}{p(x_i)}\right)}$$
Bạn có thể nghĩ về entropy như “sự ngạc nhiên trung bình” của chúng ta khi lấy mẫu từ phân phối này, hoặc nói cách khác, bạn có thể nói rằng đó là lượng thông tin trung bình mà chúng ta thiếu (nếu lượng thông tin kỳ vọng thu được cao, có nghĩa là chúng ta không biết nhiều về phân phối trước đó). Nếu một sự kiện có xác suất \( 1 \), trong khi các sự kiện khác đều xảy ra với xác suất \( 0 \), thì chúng ta không có thông tin để thu được, bởi vì chúng ta biết chính xác điều gì sẽ xảy ra. Trong trường hợp này, entropy là \( 0 \).
Entropy đạt giá trị lớn nhất khi \( X \) được phân phối đều. Điều này tương ứng với việc chúng ta có sự thiếu hiểu biết tối đa / thiếu thông tin tối đa về phân phối, bởi vì chúng ta không có lý do để tin rằng một sự kiện sẽ xảy ra hơn một sự kiện khác. Entropy tối đa là:
$$H_{max}(X) = \log(N) $$
trong đó N là số lượng sự kiện trong phân phối.
Chúng ta cũng có thể định nghĩa entropy của một phân phối kết hợp \( p(X, Y) \):
$$ H(X, Y) = -\sum_{x \in X} \sum_{y \in Y} p(x, y) \log p(x, y) $$
Sử dụng quy tắc Bayes:
$$ \begin{align*} P(X, Y) &= P(X | Y) P(Y) \\ -\log P(X, Y) &= -\log(P(X|Y)) - \log P(Y) \\ \end{align*} $$
Lấy kỳ vọng ở cả hai vế,
$$ H(X, Y) = H(X | Y) + H(Y) $$
Chúng ta cũng có thể tìm được \( H(X, Y) = H(Y \vert X) + H(X) \) bằng lập luận tương tự.
Cho đến nay, chúng ta đã trình bày các công thức về lượng thông tin và entropy của một phân phối, mà không cho thấy tại sao chúng hữu ích hoặc thực sự là những đại lượng mà chúng ta nên quan tâm ngay từ đầu. Hãy xem xét một bài toán đơn giản: đồng xu lệch. Đây là một đồng xu với phân phối sau:
$$ \begin{aligned} &P(\text{Ngửa (1)}) = p \ &P(\text{Sấp (0)}) = 1 - p \end{aligned} $$
Để cụ thể, giả sử \( p = 0.1 \), vì vậy \( 1 - p = 0.9 \). Đồng xu lệch được tung \( N = 1000 \) lần, để tạo ra một số xổ số N chữ số. Chúng ta muốn biết câu trả lời cho câu hỏi sau: chúng ta phải mua bao nhiêu vé xổ số để có 99% chắc chắn trúng thưởng?
Chúng ta có thể bắt đầu bằng việc tự hỏi: vé xổ số nào có xác suất cao nhất? Và câu trả lời sẽ đơn giản - đó sẽ là vé với tất cả là 0 (tất cả là sấp), xảy ra với xác suất \( 0.9^N = 1.7 \times 10^{-46}\). Tuy nhiên, nếu tôi hỏi bạn, số lượng kỳ vọng các số 1 trong vé là bao nhiêu, thì bạn sẽ nói \( p N \) số 1, tức là kỳ vọng 100 số 1.
Một chiến lược hợp lý sẽ là mua trước tất cả các vé chứa tất cả số 1, sau đó là những vé chứa một số 1, sau đó là hai số 1, và cứ tiếp tục, cho đến khi chúng ta đạt đến các vé chứa 100 số 1. Chúng ta cũng có thể muốn mua các vé chứa 101 số 1, để an toàn. Bởi vì phân phối của đồng xu này là nhị thức, và chúng ta có \( N \) lớn, chúng ta có thể sử dụng xấp xỉ phân phối chuẩn cho phân phối này, sao cho:
$$ X \sim \mathcal{N}(Np, Np(1-p)) $$
Biết rằng độ lệch chuẩn của phân phối này là \( \sqrt{Np(1-p)} \), chúng ta có thể mua các vé với tối đa \( \mu + 2\sigma \) số 1, điều đó sẽ cho chúng ta xấp xỉ \( 99% \) của phân phối. Trong trường hợp của chúng ta, \( \mu = 100 \) và \( \sigma \approx 10 \), vì vậy chúng ta nên mua các vé với tối đa \( 120 \) số 1. Số lượng này có thể được biểu diễn là:
$$\sum_{k=0}^{120} \binom{1000}{k}$$
Số hạng chiếm ưu thế trong tổng này là \( \binom{1000}{120} \). Chúng ta có thể áp dụng xấp xỉ Stirling:
$$\binom{N}{r} \approx 2^{N H_2(\frac{N}{r})} $$
trong đó \( H_2(X) \) là entropy nhị phân của phân phối của X:
\( H_2(p) = p \log \left(\frac{1}{p} \right) + (1-p) \log \left(\frac{1}{1-p}\right) \)
Do đó số lượng vé chúng ta cần mua, \( \binom{1000}{120} \), xấp xỉ bằng:
$$ n = \binom{1000}{120} \approx 2^{N H(X)} \approx 2^{470} $$
Những \( n = 2^{470} \) vé này tạo thành cái gọi là tập điển hình của phân phối này - đây là những vé mà chúng ta “mong đợi” sẽ thấy khi lấy mẫu từ đồng xu lệch. \( 2^{470} \) vé ngụ ý rằng chúng ta có thể mã hóa mỗi vé chỉ sử dụng \( 470 \) bit thay vì \( N = 1000 \) như ban đầu. Điều này cung cấp một số bằng chứng rằng entropy của một phân phối có liên quan đến số bit tối thiểu mà một chuỗi có thể được nén xuống. Cụ thể, đối với một chuỗi N kết quả, được lấy mẫu từ một phân phối xác suất \( X \), Shannon đã chứng minh rằng giới hạn nén là:
$$ \text{giới hạn nén} = N H(X) \text{ bit} $$
Khi gửi dữ liệu qua một kênh, một số nhiễu \( \mathbf{n} \) được thêm vào dữ liệu đó, làm biến dạng nó. Chúng ta muốn xây dựng một sơ đồ mã hóa và giải mã, để giảm thiểu xác suất lỗi trong quá trình truyền. Trong quá trình mã hóa, chúng ta sẽ thêm dư thừa vào dữ liệu, và trong quá trình giải mã, chúng ta sẽ tận dụng sự dư thừa này để phát hiện nơi lỗi đã xảy ra trong quá trình truyền và sửa chúng.
Hãy bắt đầu bằng việc xem xét một kênh rất đơn giản: kênh đối xứng nhị phân. Đây là một kênh đảo bit với xác suất \( p \), và giữ nguyên bit với xác suất \( 1-p \).
Giả sử chúng ta tạo ra chuỗi sau \( \mathbf{s} = 011 \), và gửi nó cho bạn của chúng ta mà không có sơ đồ mã hóa nào. Giả sử do nhiễu \( \mathbf{n} \), thông điệp nhận được \( \mathbf{r} = 111 \), vì một trong các bit đã bị đảo. Bạn của chúng ta sẽ nhận được thông điệp sai! Một cách để khắc phục điều này là sử dụng mã lặp lại. Điều này lặp lại mỗi bit \( N \) lần, vì vậy nếu \( N = 3 \), thông điệp của chúng ta \( \mathbf{s} = 000111111 \). Giả sử nó được nhận là \( \mathbf{r} = 010110011 \). Bằng cách chia chuỗi thành các nhóm \( N \), chúng ta có \( 010 110 011 \), và bằng cách lấy đa số phiếu trong mỗi khối, chúng ta giải mã thông điệp là \( 011 \), đó là thông điệp ban đầu của chúng ta.
Mã lặp lại có thể giảm giá trị \( f \) của chúng ta (xác suất lỗi trong một chuỗi), nhưng chúng đi kèm với chi phí là sự dư thừa tăng lên. Chúng ta định nghĩa dung lượng của kênh là số bit thông tin hữu ích được gửi trên mỗi bit. Ví dụ, mã lặp lại của chúng ta gửi 1 bit thông tin cho mỗi 3 bit được gửi, vì vậy dung lượng \( C = \frac{1}{3} \).
Shannon đã chứng minh trong định lý mã hóa kênh nhiễu của mình rằng bạn có thể đạt được lỗi \( f \) thấp tùy ý ở một dung lượng hữu hạn \( C \). Đây là một kết quả đáng chú ý, bởi vì lẽ thường nói với chúng ta rằng bạn cần dung lượng của mình tiến về không để lỗi tiến về không, bởi vì bạn sẽ cần một mã lặp lại cực kỳ lớn để đảm bảo không có lỗi. Nhưng Shannon nói với chúng ta rằng bạn có thể có lỗi bằng không với một \( C \) không vô cùng! Chúng ta sẽ quay lại điều này sau và chứng minh kết quả này trong một bài viết sau.
Bài viết này giới thiệu các khái niệm về thông tin và entropy của một phân phối xác suất. Chúng ta đã khám phá các giới hạn của việc nén dữ liệu và dung lượng kênh, đưa chúng ta đến gần hơn mục tiêu truyền thông tin đáng tin cậy qua một kênh không đáng tin cậy. Dưới đây là tóm tắt các điểm chính: