Sửa lỗi Reed-Solomon "đảo ngược", đã cho tiền tố đầu vào

tôi có một chuỗi $S$ có độ dài (giả sử) 34, mà tôi biết 24 byte đầu tiên (giả sử) nhưng không biết 10 byte cuối cùng. Tôi cũng có mã sửa lỗi 10 byte $RS_{44,34}(S)$ đầy đủ. Tôi có bất kỳ hy vọng phục hồi $S$?

Lượng thông tin của $S$ mà tôi thiếu vượt xa mức đảm bảo lý thuyết của Reed-Solomon (mà tôi nghĩ trong trường hợp này là 3 byte), nhưng đồng thời, có $2^{80}$ các giá trị có thể cho phần chưa biết của $S$, và cũng $2^{80}$ đầu ra có thể cho việc sửa lỗi. Nếu chúng ta lặp lại tất cả các giá trị có thể cho phần chưa biết của $S$, tôi ngây thơ mong đợi khoảng 1 trong số chúng khớp với sửa lỗi. Nhưng mà $2^{80}$ là quá nhiều để vũ phu.

Có bất kỳ kỹ thuật nào có thể phục hồi (hoặc ít nhất là giảm không gian trạng thái cho) một đầu vào, với Reed-Solomon EC của nó không? Có bất kỳ lý do nào để nghĩ theo cách này hay cách khác rằng RS được bảo mật bằng mật mã theo nghĩa này không?

Đối với nền tảng, ứng dụng "thế giới thực" ở đây là tôi có mã QR (phiên bản 2, EC cấp L), nơi tôi không có các bit dữ liệu chính, nhưng tôi có các bit EC. Tôi biết rằng dữ liệu là một URL trên một miền cụ thể, do đó, tiền tố.

Có bất kỳ kỹ thuật nào có thể phục hồi (hoặc ít nhất là giảm không gian trạng thái cho) một đầu vào, với Reed-Solomon EC của nó không?

Bạn thật may mắn - Reed-Solomon là một mã tuyến tính, nghĩa là phần sửa lỗi là một hàm tuyến tính của đầu vào và trên thực tế, bằng cách sửa tất cả trừ 10 byte của đầu vào, đó là một phép loại bỏ.

Điều này có nghĩa là bạn có thể xây dựng lại 10 byte đầu vào bị thiếu một cách hiệu quả; Loại bỏ Gaussian sẽ hoạt động và mặc dù có khả năng có sẵn các thuật toán hiệu quả hơn, nhưng việc loại bỏ Gaussian sẽ mất khoảng $10^3$ hoạt động, và do đó có thể đủ hiệu quả.

Không phải tất cả các mã đều có thuộc tính đẹp mà mã RS có, đó là mọi $k$ các ký hiệu là một bộ thông tin có thể được sử dụng để tái tạo lại từ mã ban đầu.

có hiệu quả tẩy xóa bộ giải mã ngoài đó. Xóa có nghĩa là một số biểu tượng không xác định, không chỉ bị lỗi.

Ví dụ, điều này giấy gần đây trình bày thuật toán giải mã hiệu quả mã RS trên trường hữu hạn với $q$ yếu tố, $\mathbb{F}_q$ với $q=2^m,$ Trong $O(q \log_q q^2)$ thời gian. Nó sử dụng phép biến đổi walsh để thực hiện phép nội suy Lagrange.