Kode koreksi kesalahan Boolean lebih dari

Apakah ada konstruksi yang diketahui dari kode koreksi kesalahan linier (dengan parameter wajar), sehingga ketika diberi vektor Boolean , ia juga mengembalikan vektor Boolean whp? (meskipun sudah selesai ) $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ $v\in \{0,1\}^n$ $\mathbb{F}_q$

(yaitu, , di mana probabilitas diambil alih secara seragam memilih , dan kecil secara sewenang-wenang) $\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon$ $v\in \{0,1\}^n$ $\epsilon$

Jika tidak, bagaimana jika kita mengendurkan kondisi ke

Pr [{E C C}_{i} (v) \in {0, 1}] > 1 - ϵ

$\Pr[\mathsf{ECC}_i(v) \in \{0,1\}]> 1-\epsilon$ Where

{E C C}_{i}

$\mathsf{ECC}_i$ mengembalikan koordinat ke -

i

$i$ dari

E C C

$\mathsf{ECC}$ ,

ϵ

$\epsilon$ adalah sewenang-wenang kecil, dan probabilitas diambil baik secara seragam memilih

v \in {0, 1}^{n}

$v\in \{0,1\}^n$ dan secara seragam memilih koordinat

i \in [m]

$i\in[m]$ .

Karena penasaran, apakah Anda memiliki aplikasi dalam pikiran?

Tsuyoshi Ito

Ya, saya sebenarnya memiliki beberapa aplikasi untuk kode koreksi kesalahan dengan properti tersebut. Namun, saya pikir tidak mungkin menjelaskan dalam lingkup komentar. Anda dapat menghubungi saya melalui surat jika Anda tertarik.

Terima kasih balasannya. Jika tidak cocok dalam komentar, saya mungkin tidak punya waktu untuk memahami semuanya, jadi saya akan membiarkannya apa adanya. Terima kasih!

Tsuyoshi Ito

Jawaban:

Iya. Misalnya, kode Reed-Solomon berisi kode BCH, yang merupakan kode linear biner, sebagai sub-kode. Ini disebut sub-sub-sub kode.

Mahdi Cheraghchi
sumber

Apakah ini berarti bahwa diberi kode Reed-Solomon (linear dalam F_q), probabilitas bahwa kode akan mengembalikan codeword biner, diberi input biner, adalah 1? Bisakah Anda mengarahkan saya ke beberapa makalah / survei di mana saya bisa membaca tentang properti ini secara lebih rinci? Saya agak baru dalam teori pengkodean. Terima kasih!

Referensi terbaik untuk membaca tentang kode BCH biner adalah buku teks klasik "Theory of Error Correcting Codes" oleh MacWilliams dan Sloane dan juga "Pengantar Teori Pengkodean" dari van Lint.

Mahdi Cheraghchi

@ TomGur: Saya tidak yakin kode BCH memenuhi kebutuhan Anda. Sampai taraf tertentu jawabannya tergantung pada seberapa banyak upaya komputasi yang Anda inginkan dekoder untuk tugas itu. Decoder "off the shelf" dibatasi decoder jarak, dan hanya dikoreksi hingga batas dekodabilitas unik (<setengah jarak minimum). Untuk kode BCH, fraksi ruang biner yang tidak dapat diabaikan berada di luar jangkauan, dan kesalahan dekoder akan terjadi. Memiliki kode saja tidak cukup kecuali jika Anda merinci algoritma decoding (tidak semua ECC memiliki yang dikenal efisien).

Jyrki Lahtonen