Saya mencari kode koreksi kesalahan dari jenis berikut:
kode biner dengan laju konstan,
didekodekan dari beberapa fraksi konstan kesalahan, oleh decoder diimplementasikan sebagai sirkuit Boolean ukuran , di mana N adalah panjang pengkodean.
Beberapa latar belakang:
Spielman, dalam Linear-Time Encodable dan Decodable Error-Correcting Codes , memberikan kode yang dapat didekodekan dalam waktu dalam model RAM berbiaya logaritmik , dan juga didekodekan oleh sirkuit berukuran-ukuran .
Guruswami dan Indyk memberikan peningkatan konstruksi dalam Kode Linear Waktu Encodable / Decodable dengan Tingkat Hampir-Optimal . Mereka tidak menganalisis kompleksitas rangkaian yang dihasilkan, meskipun saya percaya itu juga .
Terima kasih sebelumnya!
co.combinatorics
it.information-theory
coding-theory
Andy Drucker
sumber
sumber
Jawaban:
Anda harus melihat kode Tornado {1}, yang, untuk setiap dan dan cukup besar dapat dirancang untuk pulih (dengan probabilitas tinggi) dari kehilangan a fraksi bit dalam waktu sebanding dengan (lihat Teorema 1 dalam {1}).R ϵ>0 n (1−R)(1−ϵ) nln1ϵ
{1} Luby, Michael G., et al. "Kode praktis tahan-rugi." Prosiding simposium ACM tahunan ke dua puluh sembilan tentang Teori komputasi. ACM, 1997: http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf
sumber