Tujuan dari pekerjaan ini adalah untuk mengenalkan pembaca dengan algoritma Berlekamp-Massey (atau Berlekamp-Messi), termasuk inferensi dan beberapa aplikasinya.
Tujuan utama dari algoritma Berlekamp-Massey adalah untuk mengevaluasi kode BCH biner (kode Bose-Chowdhury-Hawkingham, kode BCH). Kode biner adalah cara merepresentasikan data dalam bentuk kode yang di dalamnya ada setiap digit mengambil salah satu dari dua nilai yang mungkin, biasanya dilambangkan dengan angka 0 dan 1. Berlekamp menerbitkan algoritmanya pada tahun 1968, dan segera setelah itu Massey menerbitkan versinya tentang algoritme pada tahun 1969. Algoritme ini paling banyak digunakan sebagai cara cepat untuk membalikkan matriks dengan diagonal konstan. Ini berfungsi di bidang apa pun, tetapi bidang terbatas, yang paling sering ditemukan dalam teori pengkodean, adalah yang paling umum digunakan. Algoritme ini sangat berguna untuk mendekode berbagai kode aljabar. Dalam publikasinya, Berlekamp menunjukkan bahwa algoritme menggunakan "persamaan kunci" untuk memasukkan sejumlah koefisien yang diketahui dari fungsi pembangkitan dan kemudian menentukan koefisien polinomial yang tersisa. Yang berguna tentang algoritme ini adalah hanya sebagian kecil dari pesan yang disandikan yang diperlukan,untuk dapat memecahkan kode itu. Langkah krusial adalah merumuskan kembali masalah sedemikian rupa untuk menghindari pemikiran tentang matriks n kali n secara eksplisit, karena jumlah pekerjaan dengan operasi semacam itu terlalu besar. Berlekamp berhasil melakukan ini menggunakan persamaan kuncinya dan kemudian mengulangi Massey menggunakan varian algoritmanya.
Aplikasi dan implementasi algoritma ini disempurnakan dan dikembangkan oleh Massey, yang menggunakan interpretasi fisik dari register geser umpan balik linier (LFSR) sebagai alat untuk lebih memahami algoritma. Varian ini mensintesis LFSR dengan urutan keluaran tertentu. LFSR menunjukkan panjang pesan yang disandikan untuk didekripsi oleh algoritma. Panjang pesan yang dibutuhkan hanya dua kali panjang LFSR ( 2n ). Sekarang kita memiliki ide tentang apa yang ingin dilakukan algoritma, kita dapat melihat aplikasinya yang berguna.
Penerapan algoritma
, BCH, - . . NASA CD . , .
. () — , .
, N, N , . m ( m = 2). c = (c0, c1, …, cN-1), s = (s0, s1, …, sN-1). sN+1 n + 1 > N :
, , . N = 5 m = 2. , c = (c0, c1, c2, c3, c4), C :
, c = ( c0, c1, c2, c3, c4 ) s = ( s0, s1, s2, s3, s4 ) , .
- c, c = ( c0, c1, …,cN-1 ), 2n , n = , . , , « ». , .
xn - 1. w , , n, θ, :
, wn = 1 wk ¹ 1 1 < k < n. , 1, w, w2, …, wn-1 - sn = 1, , , , , n n , . w n- . , , . . w . n . < w > , , < w > – wk, 1 £ k < n gcd( n, k ) = 1, gcd . () n- .
:
G = < a > - n. G = < ak > , gcd(n, k) = 1
, , , , . f(n) n n. , n f(n) n- . , f(n) n- .
:
n, w1, w2, …,wf(n) n- . N- Q :
*: Fn(x) (. 1) f(n), f(n) - .*
, Fn(x) , , .
n :
- , . , , , .
BCH (), t , Fn Q . 2 n, m . , - m, 2m mod n = 1 GF(2m) a GF(2m) - . , BCH.
BCH
, BCH :
, . R(x) = C(x) + E(x)
A
j = 1, 2, …, 2t aj. M(j)(x) – aj (1 < j < 2t). ,
B
t - , , e - . X1, X2, …, Xe , Ei = 1 ( ). , R(x) A M(j)(x) Sj = R(aj) r(j)(aj ). .
--------------
: R(x) , , S1 , S2 , S1 = R(a) S2 = R(a2)
--------------
, S - 1, R(x) M(1)(x) r(1)(x) , , S1 = r(1)(a). , S2, R(x) M(2)(x) r(2)(x). S2 = r(2)(a2).
S1, S2, …, S2t, , X1, X2, …, Xe
C
, . . :
D
[ , , , 1984 ., 1.]
, s(z), ( ) , Chien search ( , ). , .
— s(z) S. s(x) S, :
E
, . s(z) w(z):
F
[1 + S(z)]s(x) = w(z). , z S(z). ( , 2t ). S2t+1, S2t+2, S2t+3,…, S(z) , - S(z) mod z2t+1. .
G
S(z) - , – . s(z) w(z)- < e ( e - , ). .
, - . , .
:
1. [ ] https://ru.wikipedia.org/wiki/
2. - .., .. . , 2001. 672 .
3. Erin Casey, “Berlekamp-Massey Algorithm”, 2000
4. David C. Arney, Joseph Gallian, and Paul Campbell, “Principles and Practice of Mathematics: COMAP”
5. Berlekamp's Algebraic Coding Theory, Revised edition, 1984
6. Chien [ ] https://en.wikipedia.org/wiki/Chiensearch
7. Gallian, Joseph A. Contemporary Abstract Algebra, Houghton Miin Company, Boston, 1998.
8. Garrett, Paul. Error Correcting Codes. Notes 1999-2000.
9. Garrett, Paul. Introduction to Cryptography. Notes. 2000.
10. , . « » . 6. 2000, .93-118
11. [ ] https://ru.wikipedia.org/wiki/