🥝 👟 🍪 Koreksi beberapa kesalahan saat mengenkode pesan ↘️ 👩🏿‍🎓 🕺🏾

Dalam sistem informasi, pertukaran pesan dalam jaringan komunikasi atau komputasi disertai dengan pengaruh lingkungan yang mengganggu atau penyusup, yang menyebabkan munculnya distorsi sinyal dan kesalahan dalam simbol selama transmisi digital. Perang melawan fenomena ini dilakukan dengan menggunakan kode koreksi. Sebelumnya saya menjelaskan kode Hamming, dan menunjukkan cara memperbaiki satu kesalahan dalam kata kode. Tentu, muncul pertanyaan tentang situasi dengan sejumlah besar kesalahan. Hari ini kita akan mempertimbangkan kasus dua kesalahan dalam codeword (kesalahan ganda). Di satu sisi, segala sesuatu dalam teori lebih atau kurang sederhana dan dapat dimengerti, tetapi di sisi lain, itu sama sekali tidak jelas. Penyajian materi berdasarkan karya E. Berlekamp.

Ketentuan teoretis

Ide untuk menggunakan redundansi terorganisir dalam pesan membawa R. Hamming ke konstruksi kode koreksi yang dijelaskan di sini . Kode koreksi linier (n, k) dicirikan oleh matriks cek (m × n) H. Persyaratan untuk matriks tersebut sederhana: jumlah baris sesuai dengan jumlah simbol centang, kolomnya harus berbeda dari nol, dan semuanya berbeda. Selain itu, nilai kolom menggambarkan nomor posisi yang ditempati dalam kata sandi dengan karakter kata yang merupakan elemen dari bidang akhir.

Seringkali, decoder menggunakan penghitungan sindrom yang dihitung untuk kata itu untuk menentukan apakah kata yang dikirimkan salah. Sindromnya sama dengan jumlah kolom matriks ini dikalikan dengan komponen vektor kesalahan. Jika H berisi m baris dan kode memungkinkan Anda untuk memperbaiki kesalahan tunggal, maka panjang blok (codeword) tidak melebihi

n \leq 2^{m} - 1

$n≤2^m-1$ . Juga penting adalah kelayakan jarak yang dibutuhkan dari kata kode satu sama lain.

Kode Hamming mencapai batas ini. Setiap posisi kata kode Hamming dapat diberi nomor dengan vektor biner yang bertepatan dengan kolom yang sesuai dari matriks H. Dalam hal ini, sindrom akan bertepatan langsung dengan nomor posisi di mana kesalahan terjadi (jika hanya ada satu kesalahan) atau dengan jumlah biner angka (jika ada beberapa kesalahan).

Penomoran vektor adalah ide yang sangat bermanfaat. Selanjutnya, kami akan berasumsi

n \leq 2^{m} - 1

$n≤2^m-1$ dan posisi ke-i kata tersebut diberi nomor i.

Penomoran biner, (yaitu representasi seperti itu) disebutpencari posisi.Misalkan Anda ingin memperbaiki semua kesalahan ganda dan tunggal. Tampaknya, ini akan membutuhkan redundansi kode yang besar, mis. matriks H harus memiliki lebih banyak baris (dua kali jumlahnya). Oleh karena itu, kita akan membentuk matriks H dengan baris 2m dan dengan

n \leq 2^{m} - 1

$n≤2^m-1$ kolom, dan masuk akal untuk memilih kolom yang berbeda. Untuk m baris pertama kita akan mengambil matriks sebelumnya dari kode Hamming. Ini adalah vektor kata dasar dari ruang kata.

Contoh 1

Misalkan m = 5 dan n = 31. Akan diinginkan untuk mendapatkan kode (n, k) yang mengoreksi kesalahan ganda, dengan matriks cek paritas H dalam bentuk:

Untuk fungsi fj (ξ) yang ditunjukkan dalam matriks, diinginkan untuk memiliki fungsi yang memetakan kumpulan vektor 5 dimensi menjadi dirinya sendiri. 5 baris terakhir dari matriks akan menentukan kode Hamming jika dan hanya jika fungsi f adalah bijection (permutasi).

Jika 5 baris pertama dan 5 baris terakhir secara terpisah memungkinkan Anda untuk memperbaiki kesalahan tunggal, maka mungkin bersama-sama keduanya akan memungkinkan Anda untuk memperbaiki dua kesalahan.

Kita harus belajar menambah, mengurangi, mengalikan, dan membagi vektor biner 5 dimensi, merepresentasikannya dengan polinomial berderajat paling banyak 4, untuk menemukan fungsi yang diperlukan fj (ξ).

Contoh 2

00000 ← → 0

00010 ← → 1

00011 ← → x

...

Jumlah dan perbedaan polinomial tersebut sesuai dengan jumlah dan perbedaan vektor: 0 ± 0 = 0, 0 ± 1 = 1, 1 ± 0 = 1, 1 ± 1 = 0, ± tanda memiliki dalam kasus biner, artinya sama. Tidak demikian halnya dengan perkalian, eksponen hasil perkalian bisa melebihi 4.Contoh 3

11011 \leftarrow\to х^{4} + х^{3} + х + 1

$11011 ←→ ^4 +^3++1$

(х^{3} + х + 1) х^{4} + х^{3} + х + 1) = х^{7} + х^{6} + х^{5} + 3 х^{4} + 2 х^{3} + х^{2} + 2 х + 1 =

$(^3++1)^4+^3++1)=^7+^6+^5+3^4+2^3+^2+2+1=$

= х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1

$=^7+^6+^5+^4+^2+1$ .

Diperlukan suatu metode untuk menurunkan derajat lebih besar dari 4.

Ini disebut (reduksi) konstruksi modulo residu suatu polinomial tak tereduksi M (x) derajat 5; metode terdiri dari transisi dari polinomial produk ke sisa setelah pembagian oleh

M (x) = x^{5} + x^{2} + 1

$M(x)=x^5+x^2 + 1$

Jadi

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 = (х^{2} + х + 1) (х^{5} + х^{2} + 1) + х^{3} + х^{2} + х

$^7+^6+^5+^4+^2+1 =(^2+ + 1)(^5 +^2 +1) +^3 +^2 +$ atau

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 \equiv (х^{3} + х^{2} + x) m o d (х^{5} + х^{2} + 1) .

$^7+^6+^5+^4+^2+1 ≡(^3+^2 + x)mod(^5 +^2 +1).$

Simbol ≡ berbunyi "sebanding dengan".

Secara umum, A (x) ≡a (x) mod M (x)

Jika dan hanya jika terdapat polinomial C (x) sedemikian rupa sehingga

A (x) = M (x) C (x) + a (x) koefisien polinomial direduksi modulo dua:

A (x) ≡ a (x) mod (2, M (x)).

Sifat penting dari perbandingan

Jika a (x) ≡A (x) mod M (x) dan b (x) ≡ B (x) mod M (x), maka

a (x) ± b (x) ≡ A (x) ± B (x ) mod M (x) dan

(x) b (x) ≡ (x) B (x) mod M (x).

Selain itu, jika derajat polinomial a (x) dan A (x) lebih kecil dari derajat M (x), maka dari rumus

a (x) ≡ A (x) mod (2, M (x)) a (x) = A (x).

Ada 2 kelas residu yang berbeda dalam derajat degM (x) - yaitu, sebanyak ada polinomial berbeda dengan derajat kurang dari m, yaitu berapa banyak residu divisi yang berbeda. Perpecahan bahkan lebih sulit.

Algoritme pembagian

Untuk angka.

Untuk a dan M yang diberikan, ada bilangan yang ditentukan secara unik q dan A, sehingga a = qM + A, 0 ≤ A ≤ M,

Untuk polinomial dengan koefisien dari bidang tertentu.

Untuk diberikan a (x) dan M (x), ada polinomial yang didefinisikan secara unik q (x) dan A (x) sedemikian sehingga a (x) = q (x) M (x) + A (x), degA (x ) <derajat M (x).

Kemungkinan membagi polinomial disediakan oleh algoritma Euclidean.

Untuk angka, contoh GCD yang diperpanjang dijelaskan di sini .

Untuk a dan b tertentu, ada bilangan A dan B sehingga aA + bB = (a, b), di mana (a, b) adalah PBT dari bilangan a dan b.

Untuk polinomial dengan koefisien dari bidang tertentu.

Untuk diberikan a (x) dan b (x), terdapat polinomial A (x) dan B (x) sehingga

a (x) A (x) + b (x) B (x) = (a (x), b (x)),

di mana (a (x), b (x)) adalah pembagi persekutuan ternormalisasi dari a (x) dan b (x) derajat terbesar.

Jika a (x) dan M (x) memiliki pembagi yang sama d (x) ≠ 1, maka pembagian dengan a (x) mod M (x) tidak selalu memungkinkan.

Jelas bahwa pembagian dengan a (x) sama dengan perkalian dengan A (x).

Karena jika (a (x), b (x)) = 1 = PBT, maka menurut algoritma Euclid terdapat A (x) dan B (x) sehingga a (x) A (x) + b (x) B (x) = 1, sehingga a (x) A (x) ≡ 1mod b (x). Memeriksa bahwa polinomial biner tidak dapat direduksi pada bidang GF (

), dilakukan dengan pembagian langsung oleh semua pembagi yang mungkin dengan derajat kurang dari derajat M (x). Contoh 4.

2^{5}

$2^5$

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ dibagi x dan (x + 1)

dengan pembagi linier. Hasil pembagian bukan nol. Bagilah dengan pembagi persegi

х^{2}, х^{2} + х = х (х + 1), х^{2} + 1, х^{2} + 2 х + 1 = (х + 1)^{2}, х^{2} + х + 1.

$^2 , ^2 +=( +1),^2 +1, ^2 +2 +1= ( +1)^2, ^2 + + 1.$ .. Mereka memberikan saldo bukan nol. Pembagi derajat ≥ 3 tidak ada, karena hasil kali mereka memberikan derajat ≥ 6.

Dengan demikian, polinomial dapat ditambahkan, dikurangi, dikalikan, dan dibagi modulo

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ .

Kita beralih ke pencarian fungsi untuk matriks pemeriksaan paritas H yang mendefinisikan kode koreksi kesalahan ganda dengan panjang blok 31 dan laju 21/31; 31-21 = 10 = 2t - centang simbol = 10. Fungsi tersebut harus berakar dari jumlah posisi yang salah dalam kata kode, yaitu. Ketika nomor posisi diganti ke dalam fungsi ini, hasilnya menjadi nol.

Fungsi pencarian

Misalkan β1 dan β2 adalah jumlah karakter terdistorsi (posisi) dari kata tersebut. Menggunakan notasi biner dari bilangan β1 dan β2 , bilangan-bilangan ini dapat direpresentasikan sebagai kelas residu modulo M (x) yaitu menetapkan korespondensi βi → β ⁽ⁱ⁾ (x) - polinomial biner derajat <5.

5 kondisi pengujian pertama menentukan β1 + β2 ; Persamaan tes kedua harus menentukan f (β1) + f (β2) .

Decoder harus menentukan β1 dan β2 sesuai dengan sistem yang diberikan:

Apa yang seharusnya menjadi fungsi f (x) ?

Fungsi paling sederhana adalah perkalian dengan konstanta f (β) ≡ αβ () modM (x) .

Tapi kemudian ξ2 = αξ1 , yaitu persamaan sistem bergantung. Lima kondisi pengujian baru tidak akan memberikan decoder sesuatu yang baru.

Demikian pula, fungsi f (β) = β + α tidak mengubah keadaan, karena ξ2 = ξ1 .

Mencoba fungsi daya: pengambilan pertama

f (β) = β^{2}

$f(β) = β^2$ ... Selain itu,

persamaan ini juga bergantung, karena

ξ 1^{2} = (β 1 + β 2)^{2} = β 1^{2} + 2 β 1 β 2 + β 2^{2} = β 1^{2} + β 2^{2} = ξ 2

$ξ1^2 =(β1 + β2)^2=β1^2 + 2β1β2 + β2^2 = β1^2 + β2^2 =ξ2$

Jadi persamaan kedua adalah kuadrat dari persamaan pertama.

Mencoba

f (β) = β^{3}

$f(β) = β^3$ ... Ubah bentuk persamaan decoder:

Lokasi

ξ 2 = β 1^{3} + β 2^{3} = (β 1 + β 2) (β 1^{2} - β 1 β 2 + β 2^{2}) = ξ 1 (β 1 β 2 - ξ 1^{2}) .

$ξ2 =β1^3 + β2^3=(β1 + β2)(β1^2 -β1β2+ β2^2)=ξ1(β1β2-ξ1^2).$

Jadi untuk ξ1 ≠ 0 kita punya

Jadi, β1 dan β2 memenuhi persamaan

Jadi, jika tepat dua kesalahan terjadi, maka lokator mereka memenuhi persamaan ini.

Karena persamaan ini memiliki tepat 2 akar dalam bidang polinomial biner modulo M (x) , dekoder selalu dapat menemukan dua lokasi yang diperlukan.

Jika hanya satu kesalahan yang terjadi, maka β1 = ξ1 dan $β1^2 = ξ2$ ... Oleh karena itu, dalam kasus ini, satu-satunya kesalahan memenuhi persamaan β + ξ1 = 0 atau 1+ ξ1β ^-1 = 0 .

Terakhir, decoder selalu melakukan decoding, jika tidak terjadi error, dalam hal ini ξ1 + ξ2 = 0 .

Lebih mudah (dalam praktik) untuk beroperasi tidak secara langsung dengan polinomial yang akarnya adalah pelacak kesalahan, tetapi dengan polinomial yang akarnya saling berhubungan dengan pelacak; itu. adalah kebalikan perkalian mereka.

Jelas bahwa dengan tidak lebih dari dua kesalahan, decoder dapat menentukan nomor kesalahan. Jika tiga atau lebih simbol terdistorsi, maka kesalahan decoding atau kegagalan decoding akan terjadi.

Jadi fungsinya

f (x) = x^{3}

$f(x) = x^3$ cocok untuk membangun lima baris terbawah dari cek matriks H dari kode biner dengan panjang codeword 31 dan 10 simbol cek, mengoreksi semua kesalahan ganda.

Lima pemeriksaan pertama menentukan jumlah nomor kesalahan (S1); lima pemeriksaan kedua adalah jumlah kubus nomor kesalahan (S3).

Prosedur decoding terdiri dari tiga langkah utama:

setiap codeword yang diterima diperiksa dan S1 dan S3 dihitung;
temukan polinomial pelacak kesalahan dalam σ (z);
nilai timbal balik untuk akar σ (z) dihitung dan simbol di posisi terkait dari kata yang dihasilkan berubah.

Koreksi beberapa kesalahan saat mengenkode pesan

Ketentuan teoretis

Sifat penting dari perbandingan

Algoritme pembagian

Fungsi pencarian

More articles: