Wikipedia

Khác biệt giữa bản sửa đổi của “Định lý mã hóa trên kênh nhiễu”

Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
n clean up, General fixes using AWB
n chính tả, replaced: sác xuất → xác suất (14)
Dòng 12:
:<math> R < C \,</math> (''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 sácxác xuấtsuấ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
Dòng 18:
:<math> R > C \,</math> (''tỷ lệ truyền thông > dung lượng cho phép'')
 
thì sácxác xuấtsuấ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 2 cái tốt nhất trong 3 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ư [[Kỹ thuật sửa lỗi Reed-Solomon|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 <math>\begin{matrix} \frac{1}{10} \end{matrix}</math> đơn vị [[decibel]] của giới hạn Shannon.
Dòng 30:
::<math>C = \max_{P_X} \,I(X;Y)</math>
 
:có tính chất sau. Đối với mỗi &epsilon; &gt; 0 và ''R &lt; 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ệ &ge; R, cùng một thuật toán giải mã (''decoding algorithm''), mà trong đó sácxác xuấtsuất tối đa của sai số khối &le; &epsilon;. (''block error'')
 
:2. Nếu giá trị sácxác xuấtsuất của sai số bit (''a probability of bit error'') ''p<sub>b</sub>'' là một giá trị có thể chấp nhận được, thì những tỷ lệ bao gồm cho đến ''R(p<sub>b</sub>)'' là những tỷ lệ có thể đạt được, trong đó:
 
::<math>R(p_b) = \frac{C}{1-H_2(p_b)}.</math>
Dòng 55:
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 sácxác xuấtsuấ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'') <math>X_1^{n}</math>, và chiều dài n chuỗi ký tự của xuất liệu mà kênh truyền cho ra <math>Y_1^{n}</math>, 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:
Dòng 70:
 
'''Những bước tiến hành'''
#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 <math> 2^{nR} </math> các mã tự (''codewords'') với chiều dài n sử dụng một phân bố sácxác xuấtsuất Q (''probability distribution Q'').
#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'') <math>p(y|x)</math> mà kênh truyền thông sử dụng.
#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à: <math>Pr(W = w) = 2^{-nR}, w = 1, 2,..., 2^{nR}</math>.
Dòng 77:
#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 <math>Y_1^n</math> 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'').
 
Sácxác xuấtsuất sai số (''probability of error'') của kế hoạch này được chia ra làm hai phần:
 
#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'').
#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 sácxác xuấtsuấ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, sácxác xuấtsuấ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 sácxác xuấtsuất sai số (''error probability'') này bằng <math>\epsilon</math>.
 
*Đồng thời, từ AEP chung (''joint AEP''), chúng ta biết sácxác xuấtsuất của một <math>X_1^{n(i)}</math> nào đấy và <math>Y_1^n</math>, kết quả từ việc W = 1 là tiêu biểu chung, có giá trị <math>\le 2^{-n(I(X;Y) - 3\epsilon)}</math>.
 
Định nghĩa: <math>E_i = \{(X_1^n(i), Y_1^n) \in A_\epsilon^{(n)}\}, i = 1, 2,..., 2^{nR}</math>
Dòng 96:
:::<math>\le \epsilon + 2^{-n(I(X;Y)-R-3\epsilon)}</math>
 
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ó <math>R < I(X;Y)</math> thì sácxác xuấtsuấ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 sácxác xuấtsuấ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====
Dòng 114:
(''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 sácxác xuấtsuấ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
Lấy từ “https://vi.wikipedia.org/wiki/Định_lý_mã_hóa_trên_kênh_nhiễu”