Được thúc đẩy bởi Giải thưởng Proximity của cộng đồng Ethereum và cái được gọi không chính thức là "Proxember" , một loạt bài báo nổi bật đã đào sâu vào giả thuyết giải mã danh sách "lên đến dung lượng" từ công trình nổi tiếng Proximity Gaps for Reed-Solomon Codes . Loạt bài đầu tiên đến từ Diamond-Angus , ngay sau đó là công trình của Crites-Stewart , tất cả đều hội tụ về cùng một thông điệp: có điều gì đó rất sai trái với niềm tin dân gian rằng mã Reed-Solomon có thể được giải mã danh sách lên đến (1-\rho) ( 1 − ρ ) .
Bài viết này không nhằm mục đích chứng minh điều gì mới. Mục tiêu duy nhất của nó là đưa ra một ví dụ số nhỏ, có thể tái tạo hoàn toàn, giúp lý thuyết hiện tại trở nên cụ thể. Theo tinh thần của phương pháp Crites–Stewart, tôi sử dụng một đoạn mã Reed–Solomon đồ chơi, chọn các tham số nằm hoàn toàn giữa ngưỡng nội suy tầm thường và khả năng giải mã danh sách Elias, xuất phát từ giới hạn Elias kinh điển , và chứng minh rằng kích thước danh sách đã tăng lên đến hàng chục từ mã. Công trình của họ đưa ra một cách tiếp cận mang tính xây dựng và tổng quát hơn về sự bùng nổ kích thước danh sách vượt quá giới hạn này; ở đây tôi chỉ đơn giản là tạo ra cùng một hiện tượng trong một ví dụ nhỏ, kích thước màn hình mà bạn có thể tái tạo bằng vài dòng Python.
Giả thuyết giải mã danh sách “Up to Capacity”
Trước khi đi sâu vào các con số, chúng ta nên nêu ra phỏng đoán mà mọi người đang bàn tán.
Chúng tôi làm việc với mã Reed–Solomon (RS) có độ dài n n , kích thước k k , trên một trường hữu hạn \mathbb{F}_q F q . Tốc độ là \rho = \frac{k}{n} ρ = k n ,
và mỗi từ mã là phép đánh giá của một đa thức bậc < k k trên một tập đánh giá có kích thước n n .
Mã C \subseteq \mathbb{F}_q^n C ⊆ F n q được gọi là danh sách giải mã (\delta, L) ( δ , L ) nếu với mọi từ nhận được y \in \mathbb{F}_q^n y ∈ F n q , quả cầu Hamming có bán kính \delta n δ n xung quanh y y chứa nhiều nhất L L từ mã:
Ở đây \delta δ là tỷ lệ lỗi được chấp nhận và L L là kích thước danh sách . Giải mã duy nhất cổ điển tương ứng với trường hợp (L = 1).
Giả thuyết giải mã danh sách "lên đến công suất" (như xuất hiện trong Proximity Gaps for Reed–Solomon Codes ) có thể được diễn đạt một cách không chính thức như sau:
Với mọi tỷ lệ 0 < \rho < 1 0 < ρ < 1 và mọi \eta > 0 η > 0 , mọi mã Reed–Solomon của tỷ lệ \rho ρ là (\delta, \mathrm{poly}(1/\eta)) ( δ , p o l y ( 1 / η ) ) -list có thể giải mã được đối với mọi
\delta \le 1 - \rho - \eta.δ ≤ 1 − ρ − η .
Bằng lời:
- Mã có tỷ lệ \rho ρ có “chỗ trống” cho một phần 1-\rho 1 − ρ lỗi.
- Giả thuyết khẳng định rằng mã RS có thể được giải mã danh sách hiệu quả từ gần như nhiều lỗi như vậy (lên đến một khoảng trống nhỏ \eta η ), chỉ với kích thước danh sách bị giới hạn bởi đa thức .
- Đây là lý do tại sao mọi người tóm tắt nó là "Mã RS có thể giải mã danh sách lên đến dung lượng ", ngầm hiểu là "dung lượng" là đường 1-\rho 1 − ρ .
Điều khiến cho giả thuyết này trở nên hấp dẫn là nó khớp với một phương pháp tìm kiếm rất đơn giản: nếu bạn nén dữ liệu theo hệ số \rho ρ , thì về mặt đạo đức, bạn cảm thấy "đúng đắn" khi có thể chịu được nhiễu lên đến 1-\rho 1 − ρ . Điểm thú vị của Proxember là khi so sánh bức tranh dân gian này với khả năng giải mã danh sách Elias (đường cong \rho = 1 - H_q(\delta) ρ = 1 − H q ( δ ) ), bạn sẽ phát hiện ra rằng giả thuyết "đạt đến giới hạn" này thực sự đòi hỏi quá nhiều, và kích thước danh sách buộc phải bùng nổ.
Crites-Stewart làm gì trong Phần 3.1
Điểm khởi đầu trong Crites–Stewart là định lý năng lực giải mã danh sách cổ điển của Elias (như được trình bày ví dụ trong Guruswami–Rudra–Sudan):
Cho q \ge 2 q ≥ 2 , 0 \le \delta < 1 - 1/q 0 ≤ δ < 1 − 1 / q , và cho \eta > 0 η > 0 . Đối với mọi độ dài khối đủ lớn n n :
- Nếu \rho \le 1 - H_q(\delta) - \eta ρ ≤ 1 − H q ( δ ) − η , thì tồn tại một (\delta, O(1/\eta)) ( δ , O ( 1 / η ) ) - danh sách mã giải mã được.
- Nếu \rho \ge 1 - H_q(\delta) + \eta ρ ≥ 1 − H q ( δ ) + η , thì mọi mã giải mã được trong danh sách (\delta, L) ( δ , L ) đều có
L \ge q^{\Omega(\eta n)}.L ≥ q Ω ( η n ) .Đặc biệt, khả năng giải mã danh sách là đường cong \rho = 1 - H_q(\delta) ρ = 1 − H q ( δ ) , trong đó H_q(\delta) H q ( δ ) là hàm entropy q q -ary.
Phần 3.1 sau đó thực hiện ba điều chính:
Định lượng khoảng cách giữa \delta δ và H_q(\delta) H q ( δ ) .
Họ chứng minh một bất đẳng thức đơn giản nhưng quan trọng\delta < H_q(\delta) \le \delta + \frac{1}{\log_2 q}δ < H q ( δ ) δ + 1 log 2 qvới mọi 0 < \delta \le 1 - 1/q 0 < δ ≤ 1 − 1 / q , và chứng minh rằng giới hạn trên về cơ bản là chặt chẽ. Theo trực giác, điều này có nghĩa là: chi phí entropy của việc chấp nhận một phần \delta δ lỗi lớn hơn một chút so với \delta δ , với chi phí bổ sung tối đa là 1/\log_2 q 1 / log 2 hỏi .
Sử dụng điều này để loại trừ hình ảnh giải mã danh sách “lên đến $1-\rho$”.
Một phương pháp tìm kiếm rất phổ biến là mã có tỷ lệ \rho ρ phải có thể giải mã danh sách lên đến xấp xỉ\delta \khoảng 1 - \rhoδ ≈ 1 − ρlỗi phân số với danh sách nhỏ — tức là, dung lượng được xử lý không chính thức như đường thẳng \delta = 1 - \rho δ = 1 − ρ . Crites–Stewart chỉ ra rằng điều này không tương thích với định lý dung lượng Elias khi bạn nhớ rằng H_q(\delta) > \delta H q ( δ ) > δ :
- Giới hạn lý thuyết thông tin thực sự cho các danh sách nhỏ là\rho \le 1 - H_q(\delta).ρ ≤ 1 − H q ( δ ) .
- Nếu bạn cố gắng nhấn mạnh vào khả năng giải mã danh sách cho đến \delta \le 1 - \rho - \eta δ ≤ 1 − ρ − η đối với một số \eta > 0 η > 0 cố định, thì trong phạm vi tham số thú vị, bạn chắc chắn sẽ kết thúc ở vùng\rho \ge 1 - H_q(\delta) + \eta',ρ ≥ 1 − H q ( δ ) + η ′ ,nơi Elias đảm bảo danh sách lớn theo cấp số nhân.
Nói cách khác, câu chuyện dân gian “Reed–Solomon đạt đến khả năng” (giải thích “khả năng” là 1-\rho 1 − ρ ) chỉ đơn giản là yêu cầu các tham số nằm trên đường cong khả năng giải mã danh sách thực tế.
- Giới hạn lý thuyết thông tin thực sự cho các danh sách nhỏ là
Tóm lại, Mục 3.1 không giới thiệu một định lý về năng lực mới; thay vào đó, nó:
- gợi nhớ đến giới hạn khả năng giải mã danh sách Elias cổ điển,
- làm rõ ràng ràng buộc này mâu thuẫn với quan điểm “lên đến $1-\rho$”,
Ví dụ về đồ chơi số ở phần sau của bài đăng chỉ là một ví dụ cụ thể về hiện tượng tương tự này trong các thông số vi mô, theo đúng tinh thần của cuộc thảo luận ở Phần 3.1 này (tất nhiên, cách xử lý của Crites–Stewart mang tính tổng quát hơn và mang tính xây dựng hơn).
Ví dụ số: Vụ nổ tầm thường so với Vụ nổ Elias
Bây giờ, hãy xem điều gì xảy ra khi chúng ta đưa các tham số cụ thể vào một đoạn mã Reed-Solomon nhỏ và chạy giải mã danh sách kiểu brute-force. Mục đích chính của phần này là phân biệt hai lý do khác nhau dẫn đến sự bùng nổ kích thước danh sách:
- một lý do tầm thường dựa trên kích thước (khi chúng ta cho phép quá nhiều lỗi đến mức chúng ta có quá ít ràng buộc) và
- lý do Elias/sức chứa (trong đó phép tính entropy buộc phải có danh sách lớn mặc dù chúng ta vẫn có đủ ràng buộc).
Thí nghiệm của chúng tôi sẽ nằm hoàn toàn giữa hai ngưỡng này:
Cài đặt
Chúng tôi làm việc với:
- kích thước trường q = 13 q = 13 (do đó chúng ta đang ở trên \mathbb{F}_{13} F 13 ),
- chiều dài khối n = 12 n = 12 ,
- chiều k = 5 k = 5 , do đó tỷ lệ là\rho = \frac{k}{n} = \frac{5}{12} \approx 0,4167,ρ = kn = 5 12 ≈ 0,4167 ,
- phân số lỗi\delta = 0,5,δ = 0,5 ,tức là bán kính giải mã t = \delta n = 6 t = δ n = 6 lỗi.
Đối với mỗi lần thử nghiệm, chúng tôi:
- Lấy mẫu ngẫu nhiên một đa thức bậc < k < k trên \mathbb{F}_{13} F 13 .
- Đánh giá nó theo thứ tự nhân- 12 12 miền để có được độ dài- 12 12 từ mã RS c c .
- Làm hỏng chính xác 6 tọa độ của c c (được chọn ngẫu nhiên đồng đều và thay đổi thành các lỗi ngẫu nhiên khác không), thu được từ y y đã nhận.
- Chạy bộ giải mã danh sách vũ phu trả về tất cả các từ mã RS c' c ′ trong khoảng cách Hamming tối đa là 6 6 của y y .
Bộ giải mã danh sách tính toán ngưỡng thỏa thuận nội bộ
và giữ tất cả các từ mã đồng ý với y y ở ít nhất 6 vị trí , tức là ở khoảng cách \le 6 ≤ 6 .
Một lối đi vòng: ngưỡng bùng nổ tầm thường
Có một lý do rất đơn giản về "đếm chiều" tại sao kích thước danh sách có thể bùng nổ đối với mã Reed-Solomon. Nếu chúng ta cho phép quá nhiều lỗi đến mức số thỏa thuận (1-\delta)n ( 1 − δ ) n tối đa là k k , thì chúng ta có tối đa k k ràng buộc trên đa thức bậc <k < k .
Về mặt hình thức, chế độ nổ tầm thường là
Trong chế độ này:
- bạn có thể chọn (1-\delta)n ( 1 − δ ) n tọa độ và giá trị,
- luôn có một số bậc <k < k đa thức nội suy chúng,
- vì vậy bạn mong đợi một số lượng lớn các từ mã trong quả bóng giải mã gần như miễn phí, chỉ từ đại số tuyến tính.
Đối với đoạn mã nhỏ của chúng ta:
- n = 12 n = 12 ,
- k = 5 k = 5 ,
- vì vậy ngưỡng nổ tầm thường làt_{\text{triv}} = n - k = 12 - 5 = 7 \quad\text{lỗi},t triv = n − k = 12 − 5 = 7 lỗi ,tương đương\delta_{\text{triv}} = \frac{7}{12} \approx 0,5833.δ triv = 7 12 ≈ 0,5833.
Nếu chúng ta giải mã từ 7 lỗi trở lên, bất kỳ sự bùng nổ danh sách nào mà chúng ta quan sát được đều có thể đổ lỗi cho cơ chế tầm thường này.
Nơi thí nghiệm của chúng tôi diễn ra
Trong thí nghiệm của chúng tôi, chúng tôi giải mã từ
Chúng ta có:
- các thỏa thuận:(1-\delta)n = 0,5 \cdot 12 = 6,( 1 − δ ) n = 0,5 ⋅ 12 = 6 ,
- mà thỏa mãn6 > k = 5.6 > k = 5.
Vì vậy, chúng ta đang ở dưới ngưỡng tầm thường:
- (1-\delta)n > k ( 1 − δ ) n > k ,
- tương đương t = 6 < t_{\text{triv}} = 7 t = 6 < t triv = 7 .
Điều này có nghĩa là:
Bất kỳ sự gia tăng kích thước danh sách nào mà chúng ta thấy tại t = 6 t = 6 đều không thể được giải thích bằng lập luận đơn giản "chúng ta có nhiều nhất là k k ràng buộc, do đó nội suy cung cấp nhiều từ mã".
Nếu danh sách bùng nổ ở đây thì phải có lý do tinh tế hơn, lý thuyết thông tin.
“Lý do tinh tế hơn” đó chính xác là giới hạn khả năng giải mã danh sách Elias.
Trên ngưỡng công suất Elias
Đối với kích thước bảng chữ cái q = 13 q = 13 và phân số lỗi \delta = 0,5 δ = 0,5 , chúng tôi tính toán entropy q q -ary
vì vậy khả năng giải mã danh sách tại \delta δ này là
Tỷ lệ của chúng tôi là
vì vậy chúng tôi vượt quá khả năng:
Một sự tinh chỉnh chuẩn của đối số đếm theo phong cách Elias đưa ra giới hạn dưới rõ ràng về kích thước danh sách trung bình trên tất cả các trung tâm y \in \mathbb{F}_{13}^{12} y ∈ F 12 13 :
Đối với các tham số của chúng tôi:
- n(\rho + H_q(\delta) - 1) \khoảng 12 \cdot 0,171302 \khoảng 2,0556 n ( ρ + H q ( δ ) − 1 ) ≈ 12 ⋅ 0,171302 ≈ 2,0556 , do đóq^{n(\rho + H_q(\delta) - 1)} = 13^{2.0556} \approx 195,q n ( ρ + H q ( δ ) − 1 ) = 13 2.0556 ≈ 195 ,
- Và\sqrt{8 n \delta (1-\delta)}= \sqrt{8 \cdot 12 \cdot 0,5 \cdot 0,5}= \sqrt{24} \approx 4,90.√ 8 n δ ( 1 − δ ) = √ 8 ⋅ 12 ⋅ 0,5 ⋅ 0,5 = √ 24 ≈ 4,90.
Kết hợp những điều này lại với nhau,
Vì vậy, trung bình, một quả bóng Hamming có bán kính 6 6 xung quanh một từ ngẫu nhiên y y chứa ít nhất khoảng 40 40 từ mã Reed–Solomon ở các tham số này — và điều này xảy ra trước khi chúng ta đạt đến ngưỡng tầm thường t_{\text{triv}} = 7 t triv = 7 lỗi.
Trong thử nghiệm thực tế của chúng tôi, trong đó chúng tôi chỉ lấy mẫu y y có dạng "từ mã RS + + 6 lỗi ngẫu nhiên", chúng tôi quan sát thấy kích thước danh sách nằm trong khoảng từ 40 40 đến 55 55 , với giá trị trung bình khoảng 48 48 . Giá trị này nằm ngay trên giới hạn dưới lý thuyết của \approx 40 ≈ 40 , chính xác như bạn mong đợi: chúng tôi đang thấy một biểu hiện cụ thể, có kích thước hữu hạn của sự bùng nổ kích thước danh sách trong một chế độ mà đối số đơn giản (1-\delta)n \le k ( 1 − δ ) n ≤ k không áp dụng .
Những gì thí nghiệm đưa ra
Qua hơn 20 lần thử nghiệm độc lập (từ mã ngẫu nhiên, lỗi ngẫu nhiên 6-sparse, giải mã danh sách bằng phương pháp thử nghiệm với bán kính 6), chúng ta thu được:
Field size q = 13n = 12, k = 5, rate rho = 0.416667delta = 0.500000(1 - delta)*n = 6.000 vs k = 5-> (1 - delta)*n > k (OUT of the trivial interpolation regime)H_q(delta) ≈ 0.7546351 - H_q(delta) ≈ 0.245365 (capacity rate at this delta)rho - (1 - H_q(delta)) ≈ 0.171302 (above capacity)eta = rho + H_q(delta) - 1 ≈ 0.171302Refined Elias-style counting bound:E_y[|B(y, δn) ∩ C|] ≥ q^{n(ρ + H_q(δ) - 1)} / sqrt(8 n δ (1-δ))For these parameters that is ≥ 194.91 / 4.90 ≈ 39.79Random corrupted codewords and their list sizes:trial 0: s = 6, distance ≤ 6, list size = 47trial 1: s = 6, distance ≤ 6, list size = 48trial 2: s = 6, distance ≤ 6, list size = 45trial 3: s = 6, distance ≤ 6, list size = 49trial 4: s = 6, distance ≤ 6, list size = 53trial 5: s = 6, distance ≤ 6, list size = 46trial 6: s = 6, distance ≤ 6, list size = 42trial 7: s = 6, distance ≤ 6, list size = 47trial 8: s = 6, distance ≤ 6, list size = 50trial 9: s = 6, distance ≤ 6, list size = 53trial 10: s = 6, distance ≤ 6, list size = 50trial 11: s = 6, distance ≤ 6, list size = 47trial 12: s = 6, distance ≤ 6, list size = 52trial 13: s = 6, distance ≤ 6, list size = 43trial 14: s = 6, distance ≤ 6, list size = 46trial 15: s = 6, distance ≤ 6, list size = 49trial 16: s = 6, distance ≤ 6, list size = 48trial 17: s = 6, distance ≤ 6, list size = 49trial 18: s = 6, distance ≤ 6, list size = 55trial 19: s = 6, distance ≤ 6, list size = 48Observed list sizes: [47, 48, 45, 49, 53, 46, 42, 47, 50, 53, 50, 47, 52, 43, 46, 49, 48, 49, 55, 48]max list size = 55avg list size = 48.35Phần kết luận
Ví dụ về đồ chơi RS nhỏ này chỉ là một phép kiểm tra tính hợp lý: tại các tham số nằm giữa ngưỡng nội suy tầm thường và giới hạn Elias, một quả bóng Hamming đơn lẻ đã chứa hàng chục từ mã, chính xác như phân tích Elias dự đoán và phù hợp với bất kỳ truyền thuyết "lên đến $1-\rho$".
Mã tôi sử dụng ở đây:
https://github.com/asanso/ca/blob/50b6cfb4c3986a7695aa91401963b0ccf60eb986/elias-bound-toy.py
Nếu bạn muốn tham gia vào đội quân số, hãy điều chỉnh các thông số, chạy thử nghiệm lớn hơn và xem liệu các điểm dữ liệu của bạn có ủng hộ hình ảnh "không có vụ nổ nào dưới Elias" hay phản bác lại nó hay không.
Lời cảm ơn
Tôi biết ơn Giacomo Fenzi vì nhiều cuộc thảo luận hữu ích, sự kiên nhẫn gỡ lỗi các thí nghiệm đồ chơi của tôi và vì đã thúc đẩy tôi biến câu hỏi "khoan đã, danh sách này có thực sự bùng nổ không?" thành thứ gì đó có thể tái tạo được và (hy vọng là) có thể đọc được, và biết ơn Alistair Stewart , George Kadianakis và Benedikt Wagner vì đã đọc kỹ và đưa ra những gợi ý hữu ích.
