Di mana saya dapat menemukan contoh kode koreksi kesalahan dari jenis berikut?

Pertama, minta maaf jika pertanyaan ini sesuai atau sepele untuk situs ini. Saya seorang fisikawan yang mencari bantuan di luar zona nyamannya.

Dalam PRL 87 167902 (2001) diklaim bahwa

" ... untuk sewenang-wenang kecil terdapat kode error-correcting E : { 0 , 1 } n → { 0 , 1 } m dengan m ≤ n / δ c (untuk beberapa konstan c ) sehingga Hamming jarak antara dua kata kode yang berbeda E ( x ) dan E ( y ) adalah antara ( 1 - δ ) m /$\delta>0$$E: \{0,1\}^n \rightarrow \{0,1\}^m$$m\leq n / \delta^c$$c$$E(x)$$E(y)$$(1 - \delta)m/2$dan "$(1 + \delta)m/2$

Di koran, ini dikenal karena bukti keberadaan non-konstruktif. Saya ingin tahu apakah ada contoh eksplisit dari kode tersebut (atau yang serupa, atau yang lebih baik) ada, mengingat makalah itu 16 tahun yang lalu.

Secara khusus, saya tertarik pada kode mana m = O ( n ) dan jarak Hamming antara dua kata kode yang berbeda memiliki batas yang lebih rendah setidaknya linier dalam m ( aku cukup fleksibel tentang perilaku dengan δ , karena saya hanya perlu δ = 1 / 2 kasus).$E: \{0,1\}^n \rightarrow \{0,1\}^m$$m = O(n)$$m$$\delta$$\delta = 1/2$

Saya bertanya di sini karena saya yakin ini akan menjadi pertanyaan yang sangat mudah bagi orang yang tepat, tetapi saya bukan orang itu dan saya tidak yakin di mana sebaiknya mulai mencari. Petunjuk tentang ke mana harus mencari akan sangat dihargai.

Jika Anda hanya memerlukan kode mana m = O ( n ) dan di mana jaraknya linier dalam m , maka apa yang Anda cari disebut "kode asimtotik yang baik ". Ada banyak konstruksi eksplisit dari kode-kode semacam itu, dan Anda dapat menemukan kode dasar dalam catatan kuliah tentang teori koding. Misalnya, Anda dapat menemukan deskripsi konstruksi klasik di Kuliah 7 di sini . Contoh lain dari konstruksi adalah kode expander, yang dijelaskan dalam Kuliah 14 di sana.$E : \{0,1\}^n \to \{0,1\}^m$$m=O(n)$$m$

Jika Anda mencari kode khusus di mana jarak antara dua codeword dekat dengan , dan secara khususatasdibatasi oleh(1+δ)⋅$\frac{m}{2}$ , maka hal-hal sedikit lebih rumit. Kode tersebut erat terkait dengan benda-benda yang disebut "εset -biased", yang telah dipelajari selama beberapa waktu di TCS. Anda dapat menemukan konstruksi kode yang sangat baru disini. Konstruksi paling awal dapat ditemukan disinidan disini(meskipun mereka hanya memberi Andam=poly(n)).$(1+\delta)\cdot \frac{m}{2}$$\epsilon$$m = \rm{poly}(n)$