Apakah ada kode seperti Reed-Solomon di atas simbol desimal?

8

Kode koreksi kesalahan Reed-Solomon yang terdiri dari simbol N dijamin untuk mendeteksi hingga penggantian N simbol tunggal dalam input panjang yang sewenang-wenang ditambah ECC itu sendiri, dan juga dijamin untuk memperbaiki simbol tunggal hingga lantai (N / 2) simbol tunggal penggantian yang sama.

Saya tidak dapat mengklaim untuk memahami matematika di balik Reed-Solomon ECC, tapi saya perhatikan bahwa semua implementasi yang saya temukan beroperasi pada simbol di basis 16, 64 atau 256. Ini tampaknya menunjukkan bahwa 1024 dll juga merupakan basis di mana ini Skema dapat beroperasi dengan polinomial yang tepat.

Apakah mungkin untuk memiliki skema ECC dengan tepat properti di atas yang beroperasi pada simbol desimal? Bisakah Reed-Solomon diadaptasi sepele untuk tujuan ini?

(pertanyaan ini diminta oleh jawaban saya untuk pertanyaan yang membingungkan. SE )

Roman Starkov
sumber

Jawaban:

5

Properti kode Reed – Solomon yang Anda sebutkan dikenal sebagai Pemisahan Jarak Maksimum, dan kode dengan properti ini dikenal sebagai kode MDS . Dalam teori pengkodean, jenis kode yang paling populer adalah kode linier, dan ini hanya didefinisikan di atas huruf yang merupakan kekuatan utama. Namun, dalam literatur Anda dapat menemukan beberapa makalah tentang kode MDS pada huruf sewenang-wenang; Saya akan membiarkan Anda meneliti sendiri.

Untuk kasus khusus N=1, ada kode MDS yang sangat sederhana, yaitu checksum: Anda menambahkan ke data asli digit baru yang nilainya adalah jumlah negated dari digit lainnya (sehingga semua digit baru dijumlahkan ke nol). Kode ini dapat mendeteksi kesalahan tunggal apa pun.

Yuval Filmus
sumber
Bandingkan dengan kasus nomor kartu kredit: en.wikipedia.org/wiki/Luhn_algorithm
Aaron Brick
Itu juga menghubungkan ke algoritma Verhoeff dan algoritma Damm yang meningkatkan pada Luhn dengan mendeteksi setiap transposisi dalam digit yang berdekatan menggunakan hanya satu digit cek desimal tunggal. Impresif! Luhn hanya mendeteksi beberapa, sementara mod 10 checksum yang sederhana tidak mendeteksi siapa pun (tetapi untuk bilangan pendek mod 10 checksum dapat diperiksa secara mental, yang dapat berguna)
Roman Starkov