Đị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
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
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 formula_3 đơn vị decibel của giới hạn Shannon.
Mệnh đề toán học.
Định lý (Shannon, 1948):
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") formula_8, và chiều dài n chuỗi ký tự của xuất liệu mà kênh truyền cho ra formula_9, 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:
formula_10
Chúng ta có thể nói rằng hai chuỗi tuần tự ("sequences") formula_14 và formula_15 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
xác suất sai số ("probability of error") của kế hoạch này được chia ra làm hai phần:
Định nghĩa: formula_25
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.
formula_26
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ó formula_28 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 formula_29 từ mã ("codewords"). Tạm cho W là chỉ số ("index") đồng dạng được rút ra từ nhóm này. Cho formula_30 là từ mã và formula_31 là từ mã thu nhận được.
Kết quả của những bước này là formula_36. Trong khi chiều dài n của khối tiến về vô cực, chúng ta tìm được formula_37 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.
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
formula_38
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à:
formula_39
trong đó formula_40 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 formula_41 không đồng quy ("converge").