Kode Reed-Solomon

Tugas penting kodologi dalam pemrosesan aliran informasi dari pesan yang dikodekan dalam saluran sistem komunikasi dan komputer adalah pemisahan aliran dan pemilihannya sesuai dengan fitur yang diberikan. Aliran khusus dibagi menjadi beberapa pesan terpisah dan untuk masing-masing pesan tersebut dilakukan analisis mendalam untuk menetapkan kode dan karakteristiknya, diikuti dengan decoding dan akses ke semantik pesan.



Jadi, misalnya, untuk kode Reed-Solomon tertentu (kode PC), Anda harus menyetel:

• panjang n dari codeword (blok);
• jumlah informasi k dan simbol cek Nk;
• polinomial p (x) yang tidak dapat direduksi mendefinisikan GF medan hingga (2 ^r );
• elemen primitif α dari medan hingga;
• menghasilkan polinomial g (x);
• parameter j kode;
• digunakan interleaving;
• urutan transmisi kata kode atau simbol ke saluran dan beberapa lainnya.

Di sini, masalah khusus yang sedikit berbeda dipertimbangkan dalam pekerjaan - pemodelan kode PC itu sendiri, yang merupakan bagian utama utama dari masalah analisis kode di atas.

Deskripsi kode PC dan karakteristiknya

Untuk kenyamanan dan pemahaman yang lebih baik tentang esensi perangkat kode PC dan proses pengkodean, pertama-tama kami menyajikan konsep dasar dan istilah (elemen) kode.



Buluh - Kode Solomon (RS-code) dapat diartikan sebagai kode BCH non-biner (Bose - Chowdhury - Hawkingham), nilai simbol kode yang diambil dari bidang GF (2 ^r ), yaitu simbol informasi r ditampilkan sebagai elemen terpisah dari bidang. Kode Reed-Solomon adalah kode siklik sistematis non-biner linier yang simbolnya adalah urutan r-bit, di mana r adalah bilangan bulat positif yang lebih besar dari 1.



Kode Reed-Solomon (n, k) didefinisikan pada simbol r-bit untuk semua n dan k, dimana:

0 <k <n <2 ^r + 2, dimana

k adalah jumlah simbol informasi yang akan dikodekan,

n adalah jumlah simbol kode dalam blok kode.



Untuk sebagian besar (n, k) kode Reed-Solomon; (n, k) = (2 ^r –1, 2 ^r –1–2 ∙ t), di mana

t adalah jumlah simbol kesalahan yang dapat dikoreksi kode, dan

n - k = 2t adalah jumlah simbol centang.



Kode Reed-Solomon memiliki jarak minimum terbesar (jumlah karakter yang membedakan urutan) yang mungkin untuk kode linier. Untuk kode Reed - Solomon, jarak minimum ditentukan sebagai berikut: dmin = n - k +1.



Definisi . Kode PC di atas bidang GF (q = ^m ), dengan panjang balok n = q ^m-1, mengoreksi kesalahan t, adalah himpunan semua codeword u _{(n) di} atas GF (q) yang 2t komponen spektrumnya berurutan dengan angka$$$m_0,m_0 +1,...,m_0+2t-1$sama dengan 0.



Fakta bahwa 2t pangkat berurutan dari α adalah akar dari polinomial g (x) pembangkitan atau bahwa spektrum mengandung 2t komponen nol berurutan adalah properti penting dari kode yang memungkinkan t kesalahan dikoreksi.



Informasi polinomial Q. Menentukan teks pesan, yang dibagi menjadi blok (kata) dengan panjang konstan dan digital. Inilah yang akan ditransmisikan dalam sistem komunikasi.

Polinomial yang menghasilkan g (x) dari kode PC adalah polinomial yang mengubah polinomial informasi (pesan) menjadi codeword dengan mengalikan Q · g (x) = = u _(n) melalui GF (q).



Pemeriksaan polinomial h (x) memungkinkan Anda untuk menetapkan keberadaan karakter yang terdistorsi dalam sebuah kata.

Sindrom polinomialS (z). Polinomial yang mengandung komponen sesuai dengan posisi yang salah. Dihitung untuk setiap kata yang diterima oleh decoder.

Error polynomial E. Polinomial dengan panjang yang sama dengan codeword, dengan nilai nol di semua posisi, kecuali yang mengandung distorsi simbol codeword.



Polinomial pelacak kesalahan Λ (z) memberikan akar yang menunjukkan posisi kesalahan dalam kata-kata yang diterima oleh sisi penerima saluran komunikasi (decoder). Akarnya dapat ditemukan dengan coba-coba, mis. dengan mengganti secara bergiliran semua elemen bidang sampai Λ (z) menjadi sama dengan nol.

Polinomial nilai kesalahan Ω (z) ≡Λ (z) S (z) (modz ^2t ) sebanding dengan modulo z ^2tdengan produk dari pencari kesalahan polinomial oleh polinomial sindrom.



Polinomial tereduksi dari bidang p (x). Bidang hingga tidak ada untuk sejumlah elemen, tetapi hanya jika jumlah elemen adalah bilangan prima p atau pangkat q = p ^{m dari} bilangan prima. Dalam kasus pertama, bidang ini disebut sederhana (unsur-unsurnya adalah residu dari angka modulo p prima), di kedua, itu adalah perpanjangan dari bidang utama yang sesuai (elemen q nya polinomial derajat m-1 atau kurang residu dari polinomial modulo yang p polinomial (x) derajat m)



Polinomial primitif . Jika akar dari polinomial medan yang tidak dapat direduksi adalah elemen primitif α, maka p (x) disebut sebagai polinomial primitif yang tidak dapat direduksi .



Dalam proses mendeskripsikan tindakan dengan kode PC, kita perlu berulang kali merujuk ke bidang Galois, oleh karena itu, segera di sini kita akan menempatkan lembar kerja dengan elemen bidang ini dengan representasi elemen yang berbeda (bilangan desimal, vektor biner, polinomial, derajat elemen primitif ).



Tabel II - Karakteristik elemen medan hingga ekstensi GF (2 ⁴ ), polinomial tak tereduksi p (x) = x ⁴ + x + 1, elemen primitif α = 0010 = 2 ₁₀





Contoh 1 . Di atas medan berhingga GF (2 ⁴ ), polinomial medan tak tereduksi p (x) = x ⁴ + x + 1 diberikan, elemen primitif α = 2, dan (n, k) - kode Reed-Solomon (kode PC) diberikan. Jarak kode kode ini adalah d = n - k + 1 = 7. Kode ini dapat mengoreksi hingga tiga kesalahan dalam blok (kata kode) pesan.



Polinom yang menghasilkan g (z) dari kode tersebut memiliki derajat m = nk = 15-9 = 6 (akarnya adalah 6 elemen bidang GF (2 ⁴ ) dalam notasi desimal, yaitu elemen 2, 3, 4, 5, 6, 7) dan ditentukan oleh rasio, yaitu polinomial dalam z dengan koefisien (elemen) dari GF (2 ⁴ ) dalam representasi desimal untuk i = 1 (1) 6. Dalam kode PC yang dianggap 2 ⁹ = 512 codeword.

Pengkodean pesan PC

Pada tabel II, akar ini juga memiliki representasi kekuatan $$$α^1=2, α^2=3,...,α^6=7$...





Di sini z adalah variabel abstrak, dan α adalah elemen primitif bidang, melalui kekuatannya semua (16) elemen bidang diekspresikan. Representasi polinomial dari elemen bidang menggunakan variabel x.

Perhitungan polinomial g (x) = A B dari kode PC dilakukan dalam beberapa bagian (masing-masing tiga tanda kurung):





Representasi vektor (dalam hal koefisien g (z) oleh elemen bidang dalam representasi desimal) dari polinomial pembangkit adalah



g (z) = G _<7> = (1, 11, 15, 5, 7, 10, 7).



Setelah pembuatan polinomial pembuatan kode PC yang berorientasi pada deteksi dan koreksi kesalahan, pesan ditetapkan. Pesan disajikan dalam bentuk digital (misalnya, kode ASCII), dari mana transisi ke representasi polinomial atau vektor.



Vektor informasi (kata pesan) memiliki k - komponen dari (n, k). Pada contoh k = 9, vektornya adalah 9 komponen, semua komponen adalah elemen dari bidang GF (2 ⁴ ) dalam representasi desimal Q _<9> = (11, 13, 9, 6, 7, 15, 14, 12, 10) ...



Dari vektor inilah terbentuk kata kode u_<15> adalah vektor dengan 15 komponen. Kata kode, seperti kode itu sendiri, bersifat sistematis dan non-sistematis. Kata sandi non-sistematis diperoleh dengan mengalikan vektor informasi Q dengan vektor yang sesuai dengan polinomial pembangkitan



Setelah transformasi, diperoleh codeword (vektor) non-sistematis dalam bentuk

Q · g = <11, 15, 3, 9, 6, 14, 7, 5, 12, 15, 14, 3, 3, 7, 1>.



Dalam pengkodean sistematis, sebuah pesan (vektor informasi) direpresentasikan dengan polinomial Q (z) berupa Q (z) = q (z) g (z) + R (z), dimana derajat degR (z) <m = 6. Setelah itu, untuk vektor Q di sebelah kanan diberi sisa R (semua dalam bentuk desimal). Ini dilakukan seperti ini.



Polinomial Q digeser ke arah digit yang lebih tinggi dengan nilai m = n - k, yang dicapai dengan mengalikan Q (z) dengan Z ^{n - k} (dalam contoh Z ^{n - k} = Z ⁶ ) dan setelah pergeseran tersebut, pembagian Q (z) Z ^{n - k kali} g (z). Hasilnya, temukan sisa dari pembagian R (z). Semua operasi dilakukan di lapangan GF (2 ⁴ )



(11, 13, 9, 6, 7, 15, 14, 12, 10, 0, 0, 0, 0, 0, 0) =

= (1, 11, 15, 5, 7, 10, 7) ( 11, 15, 9, 10,12,10,10,10,10,3) + (1, 2, 3, 7, 13, 9) = G · S + R.



Sisa pembagian polinomial dihitung dengan cara biasa ( lihat sudut di sini Contoh 6 ). Pembagian dilakukan menurut pola: Misalkan Q = 26, g (z) = 7 lalu 26 = 7 3 + R (z), R (z) = 26 -7 3 = 26-21 = 5. Perhitungan sisa R (z ) pada pembagian polinomial. Kami menetapkan sisa R ke vektor Q di sebelah kanan



Kami mendapatkan u _<15> - kata kode dalam bentuk sistematis. Tampilan ini jelas berisi pesan informasi dalam k bit orde tinggi dari codeword



u _<15> = (11,13,9,6,7,15,14,12,10; 1, 2, 3, 7, 13, 9)



Digit dari vektor diberi nomor dari kanan ke kiri dari 0 (1) 14. Enam bit paling tidak signifikan di sebelah kanan adalah bit cek.

Menguraikan kode Reed-Solomon

Setelah menerima satu blok, decoder memproses setiap blok (codeword) dan memperbaiki kesalahan yang terjadi selama transmisi atau penyimpanan. Dekoder membagi polinom yang dihasilkan dengan menghasilkan polinomial dari kode RS. Jika sisanya nol, maka tidak ada kesalahan yang ditemukan; jika tidak, kesalahan terjadi.



Dekoder PC biasa melakukan lima langkah dalam loop decoding, yaitu:

1. Perhitungan sindrom polinomial (koefisiennya), kesalahan ditemukan.
2. Persamaan Pade kunci diselesaikan - menghitung nilai kesalahan dan posisinya di lokasi yang sesuai.
3. Prosedur Chen diterapkan - menemukan akar polinomial pelacak kesalahan.
4. Algoritma Forney digunakan untuk menghitung nilai kesalahan.
5. Koreksi dibuat untuk codeword yang terdistorsi;

Siklus diakhiri dengan mengekstrak pesan dari kata-kata kode (menghapus kode).



Perhitungan sindrom.



Pembuatan sindrom dari codeword yang diterima adalah langkah pertama dalam proses

decoding. Di sini sindrom dihitung dan ditentukan apakah ada kesalahan dalam codeword yang diterima atau tidak



Dekoding kata-kata kode PC dapat diatur dengan cara yang berbeda. Metode klasik termasuk decoding menggunakan algoritme yang beroperasi dalam domain waktu atau frekuensi, yang menggunakan komputasi sindrom atau tidak. Tanpa mempelajari teori masalah ini, kami akan memilih decoding dengan komputasi sindrom kata sandi dalam domain waktu.

Deteksi distorsi

Sindromik $$$S = (S_v,S_{v+1},...,S_{m+v-1})$dimana $$$v∊{0, 1}$vektor ditentukan secara berurutan untuk masing-masing codeword yang diterima oleh decoder pada inputnya. Dengan nilai nol dari komponen vektor sindrom$$$Sj = 0, j=v,v+1,...,m + v - 1$, decoder menganggap bahwa tidak ada kesalahan dalam kata yang diterima. Jika setidaknya satu$$$j≥1,Sj≠0$, kemudian decoder menyimpulkan bahwa ada kesalahan dalam vektor kode dan mulai mengidentifikasinya, yang merupakan langkah pertama dalam operasi decoder.



Perhitungan

perkalian polinomial sindromik pada sisi penerima kata sandi C dengan matriks pemeriksaan paritas H dapat menghasilkan dua hasil:

• vektor sindrom S = 0, yang sesuai dengan tidak adanya kesalahan pada vektor C;
• sindrom vektor S ≠ 0 yang berarti adanya kesalahan (satu atau lebih) pada komponen vektor C.

Kasus kedua menarik.



Vektor kode dengan kesalahan direpresentasikan sebagai C (E) = C + E, E adalah vektor kesalahan. Kemudian$$$(C +E)H^t = CH^t + EH^t = 0 + EH^t = S$



Komponen Sj dari sindrom ditentukan baik oleh hubungan penjumlahan

untuk n = q-1 dan j = 1 (1) m = nk, atau dengan skema Horner:



$$$S_j = C_0 +α^j(C_1 +α^j(C_2 +...+α^j(C_{n-2} +α^jC_{n-1})...))$



Contoh 2 . Misalkan vektor kesalahan berbentuk = <0 0 0 0 12 0 0 0 0 0 0 8 0 0 0>. Ini merusak karakter pada posisi ke-3 dan ke-10 dalam vektor kode. Nilai kesalahannya masing-masing adalah 8 dan 12 - nilai ini juga merupakan elemen dari bidang GF (2 ⁴ ) dan diberikan dalam notasi desimal (Tabel P). Dalam vektor E, posisi diberi nomor dari yang lebih rendah dari kanan ke kiri, dimulai dari 0 (1) 14.



Sekarang mari kita membentuk vektor kode dengan dua kesalahan di bit ke-3 dan ke-10 dengan nilai masing-masing 8 dan 12. Ini dilakukan dengan menjumlahkan GF (2 ⁴) menurut aturan aritmatika bidang ini. Menjumlahkan elemen bidang dengan nol tidak mengubah nilainya. Nilai bukan nol (elemen bidang) dijumlahkan setelah mengubahnya menjadi representasi polinomial, karena polinomial biasanya dijumlahkan, tetapi koefisien untuk yang tidak diketahui dikurangi mod 2.



Setelah hasil penjumlahan diperoleh, mereka kembali diubah menjadi representasi desimal, setelah sebelumnya melewati representasi pangkat





Berikut ini adalah perhitungan nilai-nilai yang rusak karena kesalahan pada posisi 10 dan 3 dari kata kode:



$$$(7+12) →α^6+α^11 =x^3 +x^2 +x^3 +x^2 +x^1 =α^1 = 2,$

$$$(3 + 8) →α^2+ α^7 =x^2 +x^3 +x^1 + 1 =α^{12}=13.$



Decoder melakukan perhitungan sesuai dengan rumus umum untuk komponen Sj, j = 1 (1) m. Di sini (dalam model) kami menggunakan relasi$$$S=EH^t$, karena kita menentukan (mensimulasikan) dalam program itu sendiri, suku-suku bukan nol hanya diperoleh untuk i = 3 dan i = 10.





Di bawah ini, kami secara khusus akan menampilkan perhitungan dengan rumus ini dalam bentuk yang diperluas.

Matriks cek dari PC - kode

Segera setelah pembuatan polinomial kode diformulasikan, menjadi mungkin untuk membuat matriks pemeriksa paritas untuk kata-kata kode, serta untuk menentukan jumlah kesalahan yang akan dikoreksi ( lihat di sini, decoder ). Mari kita buat matriks bantu [7 × 15], yang darinya dua matriks pemeriksa paritas berbeda dapat diperoleh: enam baris pertama adalah satu dan enam baris terakhir adalah yang lain.



Matriks itu sendiri dibentuk dengan cara khusus. Dua baris pertama sudah jelas, baris ketiga dan semua baris berikutnya diperoleh dengan mengurangi dari baris sebelumnya (kedua) segmen bilangan asli 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 mod 15. Ketika nilai nol terjadi, diganti dengan 15, residu negatif diubah menjadi positif.





Setiap matriks sesuai dengan polinomial generatornya sendiri untuk pengkodean sistematis dan non-sistematis.

Penentuan koefisien dari polinomial sindrom

Berikut ini, kita akan menentukan koefisien dari polinomial sindrom untuk j = 1 (1) 6.

Sehubungan dengan kata kode dengan panjang$$$n<q=p^r$tiba di input decoder, kami berasumsi bahwa itu terdistorsi oleh kesalahan.



Untuk mengidentifikasi vektor kesalahan, Anda perlu mengetahui hal berikut:

• jumlah posisi terdistorsi dalam kata kode
• $$$v≤v_{max}=0.5m$;
• angka (posisi) posisi terdistorsi dalam kata kode $$$ℓ_i: ℓ_i=0(1)n-1$;
• nilai distorsi $$$e_ℓ; e_ℓ∊GF(2^4)$...

Bagaimana vektor sindrom (polinomial) S dihitung dan digunakan lebih lanjut? Perannya dalam decoding codeword sangat signifikan. Mari kita tunjukkan ini dengan ilustrasi menggunakan contoh numerik.



Contoh 3 . (Perhitungan komponen vektor sindrom$$$S_{<6>}$ )





lalu pada akhirnya kita punya $$$S_{<6>}=(S_1,S_2,S_3,S_4,S_5,S_6)$= <8,13,7,13,15,15>



Untuk pertimbangan lebih lanjut, kami memperkenalkan konsep baru. Nilai$$$x_i = α^{ℓ_i}$akan disebut pelacak kesalahan, di sini simbol codeword terdistorsi pada posisi $$$ℓ_i$, α adalah elemen primitif dari bidang GF (2 ⁴ ).



Himpunan pencari kesalahan dari kata sandi tertentu dianggap di bawah sebagai koefisien polinomial pelacak kesalahan σ (z), akar$$$z_i$ yang mana nilainya $$$x_i ^{-1}$terbalik ke pencari lokasi.



Apalagi ekspresinya$$$(1-zx_i)=0$lenyap.



$$$σ(z) = (1-zx_1)(1-zx_2)...(1-zx_v) =σ_vz^v +σ_{v-1}z^{v-1} +...+σ_1z +σ_0$

suku bebas selalu dari persamaan selalu suku bebas dari persamaan $$$σ_0 =1$...

Derajat polinomial pencari kesalahan sama dengan v - jumlah kesalahan dan tidak melebihi nilainya$$$v≤v_{max}=0.5m$...



Semua karakter yang terdistorsi berada pada posisi kata yang berbeda, oleh karena itu, di antara para pencari lokasi$$$x_i = α^i$, tidak boleh ada elemen bidang yang berulang, dan polinomial σ (z) = 0 tidak memiliki banyak akar.



Untuk kenyamanan penulisan, nilai kesalahan akan didesain ulang oleh simbol$$$Y_i = e_i$... Untuk koefisien polinomial sindrom, persamaan nonlinier telah dipertimbangkan sebelumnya. Dalam kasus kami, v = 1 adalah asal mula komponen sindrom.





Dimana $$$y_i,x_i$ Apakah jumlahnya tidak diketahui, dan $$$S_j$- diketahui, dihitung pada tahap pertama decoding, parameter (komponen vektor sindrom).



Metode untuk menyelesaikan sistem persamaan nonlinier semacam itu tidak diketahui, tetapi solusi ditemukan menggunakan trik (penyelesaian). Transisi ke sistem persamaan linier Hankel (Toeplitz) sehubungan dengan koefisien$$$σ_i$polinomial locator.



Konversi ke sistem persamaan linier



ke persamaan$$$σ_i$ dari polinomial pelacak kesalahan, nilai akarnya diganti $$$z =x_i^{-1}$... Dalam kasus ini, polinomial menghilang. Sebuah identitas terbentuk, yang kedua sisinya dikalikan$$$y_ix_i^{j+v}$, kita mendapatkan:



$$$y_i(σ_vx_i^{j}+σ_{v-1}x_i^{j+1}+...+σ_1x_i^{j+v-1}+x_i^{j+v})=0,1≤i≤v, 1≤j≤v$...



Kami mendapatkan persamaan seperti itu$$$v×v =v^2$



Kami menjumlahkan semua persamaan ini $$$i, 1≤i≤v$untuk itu kesetaraan ini terpenuhi. Karena polinomial σ (z) memiliki akar v$$$x_i^{-1}$, buka tanda kurung dan pindahkan koefisien $$$σ_i$ per tanda jumlah:





Dalam persamaan ini, menurut sistem persamaan nonlinier yang diberikan

sebelumnya, setiap jumlah sama dengan salah satu komponen vektor sindrom. Oleh karena itu ia menyimpulkan bahwa berkenaan dengan koefisien$$$σ_v, σ_{v-1},...,σ_1$ Anda dapat menuliskan sistem persamaan linier.





Tanda "-" saat menghitung di atas bidang biner dihilangkan, karena sesuai dengan "+". Sistem persamaan linier yang dihasilkan adalah Hankel dan bersesuaian dengan matriks berdimensi$$$v×(v+1)$ sedikit.





Matriks ini tidak merosot jika jumlah kesalahan dalam codeword C (E) sama dengan $$$v , v ≤0.5(n-k)$, yaitu kemampuan kekebalan kebisingan kode ini tidak dilanggar.

Memecahkan sistem persamaan linier

Sistem persamaan linier yang dihasilkan mengandung koefisien sebagai tidak diketahui $$$σ_i =1(1)t$polinomial pelacak kesalahan untuk kata sandi C (E). Komponen vektor sindrom yang dihitung sebelumnya$$$S_j, j=1(1)m$... Di sini t adalah jumlah kesalahan pada kata, m adalah jumlah posisi cek pada kata tersebut.



Ada beberapa metode berbeda untuk menyelesaikan sistem yang terbentuk.



Perhatikan bahwa matriks (Hankel) tidak mengalami penurunan untuk dimensi yang dibatasi oleh jumlah kesalahan yang diperbolehkan dalam satu kata (kurang dari 0,5m). Dalam kasus ini, sistem persamaan diselesaikan secara unik, dan masalahnya dapat direduksi menjadi inversi matriks Hankel. Sebaiknya hapus batasan pada dimensi matriks, mis. di atas bidang yang tak berujung.



Metode untuk menyelesaikan sistem persamaan linier Hankel diketahui melalui bidang tak hingga:

• Parit berulang - Metode Berlekamp - Messi (metode TBM); (1)
• deterministik langsung Peterson - Gorenstein - Zierler; (PHC - metode); (2)
• Metode Sugiyama menggunakan algoritma Euclid untuk mencari GCD (C-method). (3)

Tanpa mempertimbangkan metode lain, kami akan memilih metode TBM. Motivasi untuk memilih adalah sebagai berikut.



Metode (PHC) sederhana dan bagus, tetapi untuk sejumlah kecil kesalahan yang dapat diperbaiki, metode-C sulit untuk diterapkan di komputer dan dipublikasikan secara terbatas (tercakup) di sumber, meskipun metode-C, seperti metode TBM menurut polinomial terkenal dari sindrom S (z), menyediakan solusi persamaan Pade di atas bidang Galois. Persamaan ini dibentuk untuk polinomial pelacak kesalahan σ (z) dan polinomial ω (z), dalam teori pengkodean disebut persamaan kunci Pade:



$$$S(z)σ(z) = ω(z)(mod z^m)$...



Solusi dari persamaan kunci adalah himpunan$$$x_i^{-1}$ akar polinomial σ (z), dan, karenanya, pelacaknya $$$x_i =α^{ℓ_i}$, yaitu posisi kesalahan. Nilai kesalahan (besaran)$$$e_i$ ditentukan dari rumus Forney di formulir





Dimana $$$σ_z^{'}(α^{-i})$ dan $$$ω(α^{-i})$ Apakah nilai polinomial σ (z) dan ω (z) pada titik tersebut $$$z =α^{-i}$terbalik ke akar polinomial σ (z);

saya adalah posisi kesalahan;$$$σ_z^{'}(z)$ - turunan formal dari polinomial σ (z) terhadap z;

Turunan formal polinom dalam medan berhingga

Ada perbedaan dan persamaan untuk turunan sehubungan dengan variabel di bidang bilangan real dan turunan formal di bidang berhingga. Pertimbangkan polinomial





$$$a_i$Apakah elemen bidang, i = 1 (1) n



elemen bidang. Kode di atas GF bidang nyata (2 ⁴ ) diberikan. Turunan terhadap z adalah:





Dalam medan nyata tak terbatas, operasi dikalikan dengan n dan jumlah n kali bertepatan. Untuk bidang berhingga, turunannya didefinisikan secara berbeda.



Turunannya juga ditentukan oleh rasio:





di mana ((i)) = 1 + 1 + ... + 1, (i) kali, dijumlahkan sesuai dengan aturan bidang berhingga: tanda + menunjukkan operasi "jumlahkan berkali-kali", yaitu elemen$$$a_2z$ ulangi 2 kali, elemen $$$a_3z^2$ ulangi 3 kali, elemen $$$a_nz^{n-1}$ulangi sebanyak n kali.



Jelas bahwa operasi ini tidak bertepatan dengan operasi perkalian dalam medan berhingga. Secara khusus, dalam bidang GF (2 ^r ), jumlah bilangan genap suku identik diambil mod2 dan nol, dan bilangan ganjil sama dengan suku itu sendiri tanpa perubahan. Oleh karena itu, dalam bidang GF (2 ^r ), turunannya mengambil bentuk





turunan genap kedua dan tertinggi di bidang ini sama dengan nol.



Dari aljabar diketahui bahwa jika suatu polinom memiliki akar rangkap (multiplisitas p), maka turunan polinomial tersebut akan memiliki akar yang sama, tetapi dengan kelipatan p-1. Jika p = 1, maka f (z) dan f '(z) tidak memiliki akar yang sama. Oleh karena itu, jika polinomial dan turunannya memiliki pembagi yang sama, maka ada akar ganda. Semua akar dari turunan f '(z) adalah kelipatan dalam f (z).

Metode solusi persamaan kunci

TMB (Trench-Berlekampa-Messi) adalah metode untuk menyelesaikan persamaan kunci. Algoritma iteratif memberikan definisi polinomial σ (z) dan ω (z), dan solusi dari persamaan Pade (kunci).



Data awal: koefisien polinomial$$$S_1,S_2,...,S_n$derajat n-1.

Tujuan. Definisi dalam bentuk eksplisit (analitik) dari polinomial σ (z) dan ω (z).



Algoritma menggunakan notasi berikut: j - nomor langkah,$$$v_j$ - derajat polinomial, $$$σ_j(z) =σ_{ji}z^i +σ_{ji-1}z^{i-1}+...+σ_{j1}z+σ_{j0}$ - perluasan polinom dalam pangkat $$$z, k_j, L_j, θ_j(z)$ dan $$$Ω_j(z)$- variabel dan fungsi perantara pada langkah ke-j dari algoritma;



Kondisi awal harus ditentukan, karena rekursi digunakan di sini.



Kondisi awal:





Contoh 4 . Eksekusi algoritma iteratif untuk vektor

S = (8,13,7,13,15,15). Polinomial ditentukan$$$σ(z) =σ_n(z)$ dan $$$ω(z) = ω_n(z)$...



Tabel 2 - Perhitungan polinomial pelacak kesalahan







begitu $$$σ_j^←(z)=14z^2+13z+1$, $$$ω_j^←(z)$= 7z + 8.



Polinomial pelacak kesalahan σ (z) di atas bidang GF (2 ⁴ ) dengan polinomial tak tersederhanakan p (x) = x ⁴ + x + 1 memiliki akar



$$$z_1 = α^{-i_1} = 13 = 4^{-1}$ dan $$$z_2 =α^{-i_2} = 6 = 11^{-1}$, mudah untuk memverifikasi ini dengan verifikasi langsung, mis. $$$i_1= 3, i_2 =10, 13 = α^{12}, 1 =α^{12}α^{3}$ dan $$$α^{12} =α^{-3}=>13=4^{-1}$... Substitusi root di

$$$σ(z=13)=14(13)^2+13·13+1=α^{13}(α^{12})^2+(α^{12})^2+α^0= α^{37}+α^{24} +α^{0}$=

=$$$α^{7}+α^{9}+α^0 =x^3+x+1=0(mod2)$;

$$$σ(z = 6)=14(6)^2+13·6+1 = α^{13}(α^{5})^2+(α^{5})^2+α^{0}$=

=$$$α^{8}+α^{2} +α^{0} = x^2 +1+x^2 +1 = 0(mod2)$...



Mengambil turunan formal dari σ (z), kita mendapatkan σ_2 (z) = 2 14 + 13 = 13, karena 14z diambil dalam jumlah 2 kali dan menghilangkan mod 2.



Menggunakan rumus Forney, kami akan menemukan ekspresi untuk menghitung nilai kesalahan$$$e_i$...



Mensubstitusikan nilai i = 3 dan i = 10 posisi pada ekspresi terakhir,

kami temukan



$$$_3 = 10α^{15-3}+11 =α^{6}+α^{10}$= =$$$x^3+x^2+x^2+x+1=x^3+x+1=α^{7}=>8$;

$$$_{10} = 10α^{15-10}+11 =α^{9}α^{5}+α^{10}=α^{14}+α^{10}$= =$$$x^3+x^2+x=α^{11}=>12$...

Arsitektur membangun paket perangkat lunak

Untuk membangun paket perangkat lunak, diusulkan untuk menggunakan solusi arsitektur berikut. Paket perangkat lunak diimplementasikan sebagai aplikasi dengan antarmuka pengguna grafis.



Data awal untuk paket perangkat lunak adalah aliran informasi digital yang dibongkar menggunakan dump dari file. Untuk kenyamanan analisis dan kejelasan operasi yang kompleks, sebaiknya gunakan file .txt.



Aliran digital yang dimuat disajikan dalam bentuk array data, selama pekerjaan kompleks di mana berbagai tindakan komputasi diterapkan.



Pada setiap tahap operasi yang kompleks, dimungkinkan untuk memvisualisasikan hasil antara dari pekerjaan tersebut.



Hasil operasi kompleks program disajikan dalam bentuk data numerik yang ditampilkan dalam tabel.



Hasil analisis menengah dan akhir disimpan ke file.



Skema fungsi kompleks perangkat lunak



Operasi dengan kompleks dimulai dengan memuat aliran digital menggunakan dump dari file. Setelah diunduh, pengguna disajikan dengan representasi visual dari konten biner file dan konten tekstualnya.



Dalam kerangka kerja antarmuka ini, tugas fungsional berikut harus dilaksanakan:

• Unduh pesan asli;
• Mengubah pesan menjadi dump;
• Pengodean pesan;
• Mensimulasikan pesan yang dicegat
• Konstruksi spektrum kata-kata kode yang diterima untuk menganalisis representasi visualnya;
• Menampilkan parameter kode.

Deskripsi operasi paket perangkat lunak



Ketika file yang dapat dijalankan dari program diluncurkan, jendela yang ditunjukkan pada Gambar 2 muncul di layar, di mana antarmuka utama program ditampilkan.



Input dari program adalah file yang perlu dikirim melalui saluran komunikasi. Untuk transmisi melalui saluran komunikasi nyata, pengkodean diperlukan - penambahan simbol centang padanya, diperlukan untuk penguraian kata yang tidak ambigu di penerima-sumber. Untuk memulai pekerjaan kompleks, pilih file teks yang diperlukan menggunakan tombol "Muat file". Isinya akan ditampilkan di kolom bawah jendela program utama.



Representasi biner dari pesan akan disajikan di kolom yang sesuai, representasi biner dari kata-kata informasi - di kolom "Representasi biner dari kata-kata informasi".



Jumlah bit dalam pesan asli dan jumlah total kata di dalamnya ditampilkan di kolom "Jumlah bit dalam pesan yang dikirim" dan "Jumlah kata dalam pesan yang dikirim".



Informasi yang terbentuk dan kata kode ditampilkan dalam tabel di sisi kanan jendela program utama.



Jendela program dengan hasil antara ditunjukkan pada Gambar 3.





Gambar 3 - Presentasi antara hasil paket perangkat lunak





Gambar 4. Hasil download file pesan





Gambar 5. File hasil encoding





Gambar 6. Output dari pesan dengan kesalahan masuk ke dalamnya.





Gambar 7. Output dari hasil decoding dan pesan dengan kesalahan yang diperkenalkan





Gambar 8. Output dari pesan yang didekode.

Kesimpulan

NSA AS adalah operator utama sistem intersepsi global Eselon. Eselon memiliki infrastruktur yang luas termasuk stasiun pelacakan darat yang terletak di seluruh dunia. Hampir semua arus informasi dunia dipantau.



Studi tentang kemungkinan mendapatkan akses ke semantik pesan informasi yang dikodekan pada saat peperangan informasi aktif saat ini baik di bidang teknologi dan politik telah menjadi tantangan berikutnya dan salah satu tugas mendesak dan dituntut di zaman kita.



Dalam sebagian besar kode, pengkodean dan penguraian pesan (informasi) diimplementasikan pada dasar matematika yang ketat dari bidang Galois yang diperluas hingga. Bekerja dengan elemen bidang semacam itu berbeda dari yang diterima secara umum dalam aritmatika dan memerlukan penulisan prosedur khusus untuk memanipulasi elemen bidang saat menggunakan alat komputasi.

Karya yang ditawarkan untuk menarik perhatian pembaca sedikit membuka tabir kerahasiaan atas aktivitas semacam itu di tingkat firma, perusahaan, dan negara bagian pada umumnya.