Tại sao bộ hiệu chỉnh Von Neumann chỉ hoạt động khi các bit đầu vào độc lập với nhau và cùng độ lệch?
Bộ phân biệt Von Neumann cơ bản hoạt động như sau: bạn tạo hai bit X, Y, sau đó xuất ra một bit (hoặc không xuất ra một chút) với logic này:
X=0 Y=0 -> Không có đầu ra
X=0 Y=1 -> Xuất ra 0
X=1 Y=0 -> Xuất ra 1
X=1 Y=1 -> Không có đầu ra
Nếu X và Y không tương quan và có cùng độ lệch (nghĩa là xác suất để chúng bằng 0 là $p$ và xác suất của 1 là $(1-tr)$), thì ngay sau đó xác suất của quy trình trên xuất ra 0 là $p(1-p)$ và xác suất của 1 là $p(1-p)$, giống hệt nhau (và có xác suất $p^2 + (1-p)^2$ không xuất ra bất cứ thứ gì - chúng tôi sẽ chạy lại với hai bit đầu vào nữa). Ngoài ra, vì chúng ta giả định rằng các bit đầu vào là độc lập, nên việc chạy bộ khử thiên vị nhiều lần trên các bit đầu vào độc lập sẽ tạo ra các đầu ra độc lập.
Tuy nhiên, câu hỏi của bạn là "điều gì sẽ xảy ra nếu các bit không độc lập hoặc không có cùng xu hướng").
Trong trường hợp đó, logic trên không giữ được.
Nếu các bit chứa các độ lệch khác nhau, nghĩa là nếu bit đầu tiên bằng 0 với xác suất $p$, và bit thứ hai là 0 với xác suất $q \ne p$) thì xác suất của a 0 là $p(1-q) = p - pq$ và xác suất của 1 là $q(1-p) = q - pq$, như chúng tôi giả định rằng $p \ne q$, những thứ này rõ ràng là khác nhau và do đó, đầu ra của bộ định vị bị sai lệch.
Nếu các bit có cùng độ lệch trung bình, nhưng tương quan với nhau, thì điều có thể xảy ra là các bit trình tự từ bộ giải sai lệch có thể tương quan với nhau. Ví dụ, nếu một 01 trình tự được theo sau bởi một trình tự khác 01 trình tự 90% thời gian (và tương tự cho một 10 chuỗi), thì các đầu ra liền kề từ bộ giải sai lệch sẽ tự tương quan chặt chẽ với nhau, nghĩa là, bộ giải sai lệch đã thất bại trong việc biến chuỗi đầu vào thô thành thứ gì đó 'ngẫu nhiên'.
Câu trả lời trước (vừa đưa ra phản ví dụ):
Hãy xem xét trường hợp các bit đầu vào chẵn là 0 90% thời gian và các bit đầu vào lẻ là 1 90% thời gian.
Trong trường hợp đó, đầu ra của bộ hiệu chỉnh Von Neumann thậm chí còn bị sai lệch mạnh hơn đầu vào.
Bài tập cho bạn: đưa ra một phản ví dụ tương tự trong đó các bit không độc lập với nhau...
Paul phàn nàn rằng ví dụ của tôi "quá cực đoan" (bất kể điều đó có nghĩa là gì - tôi đã nghĩ rằng bất kỳ phản ví dụ nào cũng sẽ áp dụng được). Trong mọi trường hợp, tôi sẽ trả lời bằng một ví dụ khác, thậm chí còn cực đoan hơn.
Hãy xem xét một nguồn thô đã tạo ra các cặp bit với phân phối xác suất này:
- 00 với xác suất 1/3
- 01 với xác suất 1/3
- 11 với xác suất 1/3
(với mỗi cặp không tương quan với bất kỳ cặp nào khác).
Tính toán đơn giản cho thấy rằng mỗi cặp có entropy Shannon là $log_2(3) \khoảng 1,5850$ bit (hoặc khoảng $0.7925$ bit entropy trên mỗi bit).
Tuy nhiên, nếu chúng ta chạy nó thông qua bộ hiệu chỉnh Von Neumann, chúng ta sẽ nhận được một luồng có, à, 0 chút entropy...
