Định lý mã hóa trên kênh nhiễu

Trong Lý thuyết thông tin, Định lý mã hóa trên kênh nhiễu (tiếng Anh: noisy-channel coding theorem) đề xuất rằng, cho dù một kênh truyền thông có bị ô nhiễm bởi nhiễu âm bao nhiêu đi chăng nữa, chúng ta cũng vẫn có thể truyền thông (thông tin) dữ liệu số (digital data) không lỗi (error-free) tới một tỷ lệ tối đa nhất định qua một kênh truyền. Kết quả đáng ngạc nhiên này, đôi khi được gọi là định lý nền tảng của lý thuyết thông tin (fundamental theorem of information theory), hay chỉ đơn giản là Định lý Shannon, được giới thiệu lần đầu tiên bởi Claude Shannon vào năm 1948.

Giới hạn Shannon hoặc Dung lượng Shannon của một kênh truyền thông là tỷ lệ tối đa trên lý thuyết về lượng thông tin một kênh truyền thông có thể truyền tải, đối với một độ nhiễu nhất định.

Đại cương

Định lý được Claude Shannon chứng minh vào năm 1948, diễn tả hiệu quả tối đa mà các phương pháp sửa lỗi (error-correcting methods) có thể đạt được, ngược lại mức độ nhiễu ô nhiễm và mức độ thoái hóa của dữ liệu (data corruption). Lý thuyết không diễn tả cách "làm thế nào để kiến tạo" một phương pháp sửa lỗi, song nó chỉ nói cho chúng ta biết mức độ hiệu quả có thể đạt được đối với một phương pháp "khả dĩ tốt nhất" nào đó mà thôi. Định lý Shannon có nhiều ứng dụng trên phạm vi rộng lớn, cả trong các ứng dụng truyền thông lẫn các ứng dụng về lưu trữ dữ liệu (data storage applications). Định lý này là nền tảng quan trọng đối với ngành Lý thuyết thông tin hiện đại.

Định lý Shannon chỉ ra rằng đối với một kênh nhiễu có một dung lượng thông tin C và một tỷ lệ truyền thông tin R nào đấy, thì nếu

$R<C\,$ (tỷ lệ truyền thông < dung lượng cho phép)

sẽ có tồn tại một kỹ thuật mã hóa cho phép xác suất lỗi bên máy thu được tùy tiện giảm nhỏ đi. Điều này có nghĩa là trên lý thuyết, người ta có thể truyền tải thông tin không bị lỗi tới một tỷ lệ giới hạn cao nhất bằng dung lượng cho phép C.

Ngược lại, điều đối lập với quan điểm trên cũng quan trọng. Nếu

$R>C\,$ (tỷ lệ truyền thông > dung lượng cho phép)

thì xác suất lỗi nhỏ tùy tiện trên không thể đạt được. Như vậy, thông tin không thể truyền tải một cách đảm bảo trên một kênh với tỷ lệ lớn hơn dung lượng của kênh truyền. Định lý không nói đến một trường hợp hiếm thấy, là trường hợp khi tỷ lệ và dung lượng bằng nhau.

Những phương thức đơn giản như "kế hoạch gửi thông điệp 3 lần và dùng hai cái tốt nhất trong ba cái được bầu, nếu các bản sao khác nhau" là những phương pháp sửa lỗi vô hiệu quả (inefficient), không thể nào đảm bảo chắc chắn rằng một khối dữ liệu được truyền thông là không có lỗi. Những kỹ thuật tân tiến như Mã Reed-Solomon, và gần đây, mã Turbo (Turbo code) đã đạt được gần đến giới hạn giả thuyết của Shannon, với cái giá phải trả là sự phức tạp lớn trong tính toán (at a cost of high computational complexity). Với mã Turbo và với công suất tính toán của các bộ xử lý tín hiệu số (digital signal processors) hiện nay, người ta có thể đạt được ${\begin{matrix}{\frac {1}{10}}\end{matrix}}$ đơn vị decibel của giới hạn Shannon.

Mệnh đề toán học

Định lý (Shannon, 1948):

1. Với mỗi kênh truyền thông không nhớ rời rạc (discrete memoryless channel), dung lượng của kênh truyền (channel capacity):

$C=\max _{P_{X}}\,I(X;Y)$

có tính chất sau. Đối với mỗi ε > 0 và R < C, và một số N có độ lớn vừa đủ, sẽ tồn tại một mã có chiều dài N và một tỷ lệ ≥ R, cùng một thuật toán giải mã (decoding algorithm), mà trong đó xác suất tối đa của sai số khối ≤ ε. (block error)

2. Nếu giá trị xác suất của sai số bit (a probability of bit error) p_b là một giá trị có thể chấp nhận được, thì những tỷ lệ bao gồm cho đến R(p_b) là những tỷ lệ có thể đạt được, trong đó:

$R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.$

và $H_{2}(p_{b})$ là Hàm entrôpi nhị phân

$H_{2}(p_{b})=-\left[p_{b}\log {p_{b}}+(1-p_{b})\log({1-p_{b}})\right]$

3. Đối với mỗi giá trị p_b, những tỷ lệ lớn hơn R(p_b) là những tỷ lệ không thể đạt được.

(MacKay (2003), p. 162; cf Gallager (1968), ch.5; Cover and Thomas (1991), p. 198; Shannon (1948) thm. 11)

Lược điểm phần chứng minh

Tương tự như một vài kết quả lớn trong lý thuyết thông tin, phần chứng minh của định lý mã hóa kênh nhiễu cho chúng ta một kết quả có thể đạt được, cũng như một kết quả đồng bộ ngược lại. Cả hai phần tử đều có nhiệm vụ để giới hạn, trong trường hợp này, một chuỗi các tỷ lệ khả dĩ, cho phép việc truyền thông qua một kênh nhiễu có thể thi hành được, và kết quả đồng bộ ngược lại ở đây dùng để thể hiện rằng những giới hạn này là những giới hạn rất sát (tight bounds).

Những lược điểm dưới đây chỉ là một phần của nhiều phong cách hiện dùng để nghiên cứu các văn bản về lý thuyết thông tin.

Kết quả có thể đạt được đối với các kênh truyền thông không nhớ rời rạc

Phần chứng minh cụ thể này về kết quả có thể đạt được (achievability) phỏng theo phong cách của các chứng minh sử dụng tính chất phân hoạch đều tiệm cận (Asymptotic equipartition property - viết tắt là AEP). Một phong cách khác nữa cũng tồn tại, được thấy trong các văn bản về lý thuyết thông tin (information theory), sử dụng Tích sai số (Error Exponents).

Cả hai phong cách chứng minh đều sử dụng một đối số mã hóa ngẫu nhiên (random coding argument), trong đó bảng mã (codebook) dùng trên toàn thể kênh truyền, được kiến tạo một cách tùy tiện (randomly constructed) - việc làm này hòng nhằm mục đích giảm ước tính phức tạp trong tính toán, trong khi vẫn chứng minh được sự tồn tại của một mã thỏa mãn yêu cầu về một xác suất sai số nhỏ đối với bất cứ một tỷ lệ dữ liệu nào đó có giá trị thấp, dưới dung lượng của kênh truyền.

Với một đối số có liên quan EAP, đối với một kênh truyền cho trước, chiều dài n của chuỗi ký tự các ký hiệu nguồn (strings of source symbols) $X_{1}^{n}$, và chiều dài n chuỗi ký tự của xuất liệu mà kênh truyền cho ra $Y_{1}^{n}$, chúng ta có thể định nghĩa một nhóm tiêu biểu chung (jointly typical set) bởi những bước sau đây:

$A_{\epsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}$

$2^{-n(H(X)+\epsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\epsilon )}$

$2^{-n(H(Y)+\epsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\epsilon )}$

${2^{-n(H(X,Y)+\epsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\epsilon )}\}$

Chúng ta có thể nói rằng hai chuỗi tuần tự (sequences) ${X_{1}^{n}}$ và $Y_{1}^{n}$ là tiêu biểu chung (jointly typical) nếu chúng nằm trong nhóm tiêu biểu chung đã định nghĩa ở trên.

Những bước tiến hành

1. Theo phong cách của đối số mã hóa ngẫu nhiên, chúng ta tùy tiện tạo nên $2^{nR}$ các mã tự (codewords) với chiều dài n sử dụng một phân bố xác suất Q (probability distribution Q).
2. Máy thu và máy nhận đều được cho biết mã số này là gì. Chúng ta cũng có thể cho rằng cả hai bên đều biết ma trận chuyển tiếp (transition matrix) $p(y|x)$ mà kênh truyền thông sử dụng.
3. Một thông điệp W được lựa chọn theo sự phân phối đồng dạng trên nhóm mã tự (uniform distribution on the set of codewords). Có nghĩa là: $Pr(W=w)=2^{-nR},w=1,2,...,2^{nR}$.
4. Thông điệp W được truyền gửi qua kênh truyền.
5. Máy nhận tiếp thu một chuỗi tín hiệu theo công thức $P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))$
6. Bằng cách truyền gửi những mã tự (codewords) qua kênh truyền thông, chúng ta nhận được $Y_{1}^{n}$ chuỗi xuất liệu, và giải mã thành một chuỗi dữ liệu nguồn (source sequence) nào đó nếu chỉ có tồn tại chính xác 1 mã tự là tiêu biểu chung với Y. Nếu không tồn tại các mã tự tiêu biểu chung (jointly typical codewords), hoặc nếu có hơn một cái thì một sai số (error) - hay lỗi - xảy ra và phải được thông báo (declared). Sai số còn có thể xảy ra nếu một mã tự đã giải không đồng bộ với mã tự gốc (a decoded codeword doesn't match the original codeword). Điều này được gọi là giải mã nhóm tiêu biểu (typical set decoding).

xác suất sai số (probability of error) của kế hoạch này được chia ra làm hai phần:

1. Thứ nhất, sai số có thể xảy ra nếu với một chuỗi Y nhận được, chúng ta không tìm thấy các chuỗi X tiêu biểu chung cho nó (jointly typical X sequences).
2. Thứ nhì, sai số có thể xảy ra nếu một chuỗi X không đúng (incorrect X sequence) là tiêu biểu chung với một chuỗi Y nhận được (is jointly typical with a received Y sequence).

• Do việc kiến tạo mã mang tính ngẫu nhiên (không định trước), chúng ta có thể cho rằng xác suất sai số trung bình (average probability of error), tính trung bình trên toàn bộ các mã, là một giá trị không phụ thuộc vào chỉ số được gửi (index sent). Vì thế, chúng ta có thể cho rằng W = 1, mà không sợ mất chính xác vì tính tổng quát của kết luận (without loss of generality).
• Từ AEP chung (joint AEP), chúng ta biết rằng, xác suất của việc giá trị X tiêu biểu chung không tồn tại sẽ giảm xuống về giá trị 0 trong khi n tăng lên. Chúng ta có thể giới hạn xác suất sai số (error probability) này bằng $\epsilon$.
• Đồng thời, từ AEP chung (joint AEP), chúng ta biết xác suất của một $X_{1}^{n(i)}$ nào đấy và $Y_{1}^{n}$, kết quả từ việc W = 1 là tiêu biểu chung, có giá trị $\leq 2^{-n(I(X;Y)-3\epsilon )}$.

Định nghĩa: $E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\epsilon }^{(n)}\},i=1,2,...,2^{nR}$

theo sự kiện một thông điệp i là tiêu biểu chung với chuỗi tín hiệu nhận được khi thông điệp 1 được truyền gửi.

${P(error)=P(error|W=1)}\leq P(E_{1}^{c})+\sum _{i=2}^{2^{nR}}P(E_{i})$

$\leq \epsilon +2^{-n(I(X;Y)-R-3\epsilon )}$

Chúng ta có thể quan xát và thấy rằng khi n đạt đến vô cực (infinity), và nếu kênh truyền thông có $R<I(X;Y)$ thì xác suất sai số sẽ tiến về giá trị 0.

Cuối cùng, nếu giả thiết có một bảng mã trung bình (average codebook) nào đấy biểu hiện nó là một bảng mã "tốt", thì chúng ta biết rằng sẽ có tồn tại một bảng mã mà công suất (performance) của nó sẽ khá hơn bảng mã trung bình kia, do đó thỏa mãn yêu cầu của chúng ta về một xác suất sai số nhỏ tùy tiện (arbitrarily low error probability), trong việc truyền thông qua kênh nhiễu (noisy channel).

Nghịch lý của các kênh truyền thông không nhớ rời rạc

Giả sử chúng ta có một mã bao gồm $2^{nR}$ từ mã (codewords). Tạm cho W là chỉ số (index) đồng dạng được rút ra từ nhóm này. Cho $X^{n}$ là từ mã và $Y^{n}$ là từ mã thu nhận được.

1. ${nR={H(W)=H(W|Y^{n})+I(W;Y^{n})\;}}$ sử dụng các đồng nhất thức (identities) với sự kết hợp của entrôpi và các thông tin chung
2. $\leq {H(W|Y^{n})}+{I(X^{n}(W);Y^{n})}$ vì X là một hàm của W
3. $\leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})$ bằng cách sử dụng Bất đẳng thức Fano
4. $\leq 1+{P_{e}^{(n)}nR+nC}$ do thực tế dung lượng là thông tin chung được tối đa hóa (maximized mutual information).

Kết quả của những bước này là $P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}$. Trong khi chiều dài n của khối tiến về vô cực, chúng ta tìm được $P_{e}^{(n)}$ và các giá trị này vượt ra ngoài hàng số 0 nếu R (tỷ lệ) lớn hơn C (dung lượng) - chúng ta chỉ có thể tìm được những tỷ lệ sai số thấp tùy tiện nếu R nhỏ hơn C mà thôi.

Định lý mã hóa kênh truyền đối với những kênh truyền không nhớ bất tĩnh tại

(Channel coding theorem for non-stationary memoryless channels)

Chúng ta tạm cho rằng kênh truyền là không nhớ, song các xác suất chuyển tiếp của nó thay đổi theo thời gian với một phong thái được biết trước tại máy phát và máy thu.

Dung lượng của kênh truyền tiếp đó được xác định bởi

$C=\lim \;\inf \;\;\max _{p^{(}X_{1}),p^{(}X_{2}),...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i})$

Giá trị tối đa (MAXimum) đạt được do những sự phân bổ về dung lượng đạt được đối với mỗi kênh truyền. Có nghĩa là: $C=\lim \;\inf \;\;{\frac {1}{n}}\sum _{i=1}^{n}C_{i}$

trong đó $C_{i}$ là dung lượng của kênh truyền thứ i.

Lược điểm phần chứng minh

Các bước chứng minh cũng tương tự như các bước trong định lý mã hóa kênh truyền. Khả năng đạt được kết quả phát sinh từ quá trình mã hóa tùy tiện (random coding) với mỗi ký hiệu được chọn lựa một cách tùy tiện từ sự phân bổ về dung lượng đạt được đối với một kênh truyền. Các đối số điển hình (Typicality arguments) dùng định nghĩa của các nhóm điển hình (definition of typical sets) đối với các nguồn bất tĩnh tại (non-stationary sources) được định nghĩa trong tính chất phân hoạch đều tiệm cận (Asymptotic Equipartition Property).

Tính chất kỹ thuật (technicality) của lim inf có tác động đến quá trình khi ${\frac {1}{n}}\sum _{i=1}^{n}C_{i}$ không đồng quy (converge).

Tham chiếu

• C. E. Shannon, The Mathematical Theory of Information. Urbana, IL:University of Illinois Press, 1949 (reprinted 1998).
• David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0521642981
• Thomas Cover, Joy Thomas, Elements of Information Theory. New York, NY:John Wiley & Sons, Inc., 1991. ISBN 0471062596

Xem thêm

• Tích sai số (Error exponent)
• Tính chất phân hoạch đều tiệm cận (Asymptotic equipartition property - viết tắt là AEP)
• Định lý Shannon-Hartley (Shannon-Hartley theorem)
• Mã Turbo (Turbo code)
• Bất đẳng thức Fano (Fano's Inequality)

Liên kết ngoài

• On Shannon and Shannon's law Lưu trữ 2016-03-15 tại Wayback Machine
• On-line textbook: Information Theory, Inference, and Learning Algorithms, của David MacKay - một bản giới thiệu thú vị và toàn diện về lý thuyết Shannon, bao gồm 2 chứng minh về định lý mã hóa kênh nhiễu. Bài viết này còn bàn luận về những phương pháp tân tiến (state-of-the-art), như mã kiểm tra chẵn lẻ mật độ thấp (low-density parity-check codes), và Mã Turbo.