Спосіб алгебраїчного декодування перешкодостійких кодів

Спосіб алгебраїчного декодування перешкодостійких кодів, який полягає у тому, що по прийнятій кодовій послідовності за допомогою відповідних пристроїв обчислюють багатовимірну синдромну послідовність, відповідно до якої, вико 3 54545 задають значення та знаходження ненульових елементів вектору помилок, після чого за допомогою пристроїв додавання елементів над кінцевим полем GF(q) виправляють помилки в прийнятій послідовності. Недоліком способу-прототипу декодування алгеброгеометричних кодів на просторових кривих є обмежені можливості по декодуванню інших класів кодів та неспроможність алгебраїчного декодування алгеброгеометричних кодів заданих на кривих у просторі розмірністю u > 3. В основу корисної моделі поставлена задача створити спосіб алгебраїчного декодування перешкодостійких кодів який, дозволить реалізувати алгебраїчне декодування алгеброгеометричних кодів заданих на кривих у просторі розмірністю u > 3. Поставлена задача вирішується за рахунок використання багатовимірної матриці синдромів та багатоваріантного многочлену локаторів помилок, що дозволяє реалізувати алгебраїчне декодування алгеброгеометричних кодів заданих на кривих у просторі розмірністю u > 3. Технічний результат, який може бути отриманий при здійсненні корисної моделі полягає в розширенні можливостей по алгебраїчному декодування алгеброгеометричних кодів заданих на кри кривих у просторі розмірністю u > 3. Сутність запропонованого способу алгебраїчного декодування перешко-достійких кодів полягає в тому, що за рахунок обчислення за допомогою відповідних пристроїв багатовимірної синдромної послідовності s (s0,0,..., 0 , s1,0,..., 0,..., s0,0,..., deg F ), за правилом: 1 Fi0 ,i1,..., iu 1 де Fi ,i ,..., i 0 1 u j 0 e j Fi0 ,i1,..., iu 1 (p j ( x 0 , x1,..., xu 1)), i1 0 u 1 xi0 x1 ... xiu 1 , 1 - багаточлен степеня і0 + іх +...+ іu degF. Перевірочна матриця алгеброгеометричного коду на кривих у просторі розмірністю u > 3 задається через значення генераторних функцій у точках кривої Fi0 ,i1,..., iu 1 1 p j ( x0, x1,..., xu 1) ( X0 j , X1j ,..., Xu 1j ) , тобто значен ня генераторних функцій мають вигляд Fi0 ,i1,...,u i i1 Xi0 X1 ... Xiu 0 u 1 1 1, j 0 .. n 1 , перевірочна матриця H має вигляд 1 1 ... 1 X00 X01 ... X0n 1 X10 F1,0,..., 0 (p j ( x0 , x1,..., xu 1)) X11 X1n 1 ... F0,0,..., deg F (p j ( x0 , x1,..., xu 1)) ... deg Xu 1 F ... . ... deg deg Xu 1 F ... Xu 1 F 0 1 n 1 s = c* HT =(с + е) НT =с.НT + е НT =е НT, тобто Таким чином, на першому етапі запропонованого способу обчислюють синдромну послідовність s (s0,0,..., 0, s1,0,..., 0,..., s0,0,..., deg F ) за правилом (s0,0,..., 0 , s1,0,..., 0,..., s0,0,..., deg F ) n 1 si0 ,i1,..., iu F0,0,..., 0 (p j ( x0 , x1,..., xu 1)) H 4 1 X0 0 X10 ... deg Xu 1 F (e0 , e1, e2,..., en 1) 1 X01 X11 ... deg Xu 1 F 0 ... ... 1 T X 0n 1 X1n 1 ... ... deg ... Xu 1 F 1 , n 1 що еквівалентно системі рівнянь: s0,0,..., 0 s1,0,..., 0 s0,1,..., 0 e0 e1 e2 ... en n 1 1 j 0 e0 X0 0 e1X01 e 2 X0 2 ... e0 X10 e1X11 e2 X12 ... s0,0,..., deg F deg en 1Xu 1 F deg e0 Xu 1 F n 1 0 n 1 j 0 deg Xu 1 F ei X0 0 1 j ei X0 0 0 0 X1 ... Xu j j en 1X0n en 1X1n ... deg e2 Xu 1 F 2 n 1 1 1 j 0 n 1 j 0 1j , ei X0 ei X0 0 j j 0 0 X1 ... Xu j 0 X1j ... Xu 1 1j , 1j , ... deg 0 X1 ... Xu 1 F . j Декодування алгеброгеометричного коду, побудованого через відображення точок кривої у просp j ( x0, x1,..., xu 1) ( X0 j , X1j ,..., Xu 1j ) торі розмірністю u > 3 однорідними одночленами степеня degF полягає в знаходженні всіх ei, і = 0,..., n - 1 за відомими елементами багатовимірної j синдромної послідовності s (s0,0,..., 0, s1,0,..., 0,..., s0,0,..., deg F ) . На другому етапі алгебраїчного декодування обчислюють кількість помилок, що відбулися. Для цього використовують многочлен локаторів помилок ступеня u 1 від u змінних: 5 54545 ( x 0 , x1,..., x u 1 ) u 1 x0 a u,1,..., 0 6 x0 u x1 ... (2) a0,1,..., 0 x1 ... a 0,0,...,1 x u 1 a 0,0,..., 0 , Помноживши обидві частини многочлена (2) де - кількість помилок, які виникли у кодовона ei і просумувавши за всіма j=0..n-1 значеннями му слові, в точці p ( x , x ,..., x ) ( X , X ,..., X , отри( d 1) j 0 1 u 1 0j 1j u 1j ) t , 2 маємо де t - кількість помилок, що може виправити (n, k, d) код. a1,0,..., 0 x 0 n 1 j 0 ej F a1,0,..., 0 u 1,0,..., 0 ( X0 j , X1j ,..., n 1 Xu 1j ) e j F1,0,..., 0 ( X0 j , X1j ,..., Xu j 0 n 1 a0,0,..., 1 j 0 si0 ,i ,..., iu 1 1 j 0 Відповідно до введених вище позначень отримаємо рекурентний вираз s u 1,0,..., 0 a u,1,..., 0 s u,1,..., 0 ... a0,0,..., 1 s0,0,..., 1 a0,0,..., 0 s0,0,..., 0 0, який задає систему лінійних рівнянь щодо невідомих коефіцієнтів многочлена локаторів помилок: s u 1,0,..., 0 a u,1,..., 0 s u,1,..., 0 ... a0,1,..., 0 s0,1,..., 0 ... a0,0,..., 1 s0,0,..., 1 a0,0,..., 0 s0,0,..., 0 s a u 2,0,..., 0 u,1,..., 0 a1,0,..., 0 s2,0,..., 0 s 0; u 1,1,..., 0 ... a0,1,..., 0 s1,1,..., 0 ... a0,0,..., 1 s1,0,..., 1 a0,0,..., 0 s1,0,..., 0 0; ... s2 2u 2,0,..., 0 a1,0,..., 0 s a0,0,..., 1 s a u,1,..., 0 u 2,0,..., 0 u 1,0,..., 1 a0,1,..., 0 n 1 j 0 Xu 1j ) ... e j F0,1,..., 0 ( X0 j , X1j ,..., Xu 1j ) ... 1j ) u,1,..., 0 ( X0 j , X1j ,..., a1,0,..., 0 s2 2u 1,1,..., 0 a0,1,..., 0 s a0,0,..., 0 s ... u 1,1,..., 0 u 1,0,..., 0 ... 0; Обчислення системи дає значення коефіцієнтів многочлена локаторів помилок (2), що однозначно вказує на місце розташування помилок. На наступному етапі обчислюються локатори, що однозначно вказують на положення помилок. Суть алгоритму полягає в підстановці всіх можливих локаторів p j ( x0, x1,..., xu 1) ( X0 , X1 ,..., Xu 1 ) і j j j вибір тих з них, які перетворюють у нуль многочлен локаторів помилок (2). На останньому етапі алгебраїчного декодування обчислюються значення ei і формується вектор помилок e = (е0, e1,..., еn-1). Для цього підставимо значення знайдених локаторів n 1 j 0 ej 0. ( X0 j , X1j ,..., Xu 1j ) і невідомі зна чення ei у систему рівнянь (1). Інші ei при і ≠ j дорівнюють нулю. Отже, система рівнянь (1) має вигляд: s0,0,..., 0 s1,0,..., 0 a0,1,..., 0 s0,1,..., 0 ... a1,0,..., 0 s1,0,..., 0 ej F j 0 p j ( x0, x1,..., xu 1) e j Fi0 ,i1,..., iu 1(p j ( x0, x1,..., xu 1)). a1,0,..., 0 s1,0,..., 0 1j ) n 1 u,1,..., 0 e j F0,0,..., 1( X0 j , X1j ,..., Xu Після внесення заміни n 1 a s0,1,..., 0 j J j J j J 0 0 ei X0 X1 ... Xu 0 1j , 0 0 ei X0 X1 ... Xu 1j , 0 ei X0 X1j ... Xu 1 0 1j , j j j j j ... s0,0,..., deg F j J deg ei X0 X1j ... Xu 1 F , 1 0 j j де J - множина індексів ненульових елементів вектора помилок, тобто набір номерів локаторів помилок, причому / J / t. Обчислення системи лінійних рівнянь дає невідомі ненульові значення вектора помилок (е0, e1, e2,..., еn-1). Виправлення помилок здійснюється за допомогою пристроїв додавання елементів над кінцевим полем GF(q) за правилом * * * c c * e ( c 0 e0, c1 e1,..., cn 1 en 1). Таким чином, за рахунок використання багатовимірної матриці синдромів та багатоваріантного багаточлену локаторів помилок реалізується алгебраїчне декодування алгеброгеометричних кодів заданих на кривих у просторі розмірністю u > 3. Джерела інформації: 1. Бэрлекэмп Э.Р. Алгебраическая теория кодирования. Пер. с англ. - М.: Мир, 1971. - 478 с. 2. Feng G.L., Rao T.R.N. Decoding algebraic geometric codes up to the designed minimum distance // ІЕЕЕ Trans. Inform. Theory. - 1993. - Vol. 39, N 1 - P. 37-46. 3. Пат. UA 38387 U, MKI (2006) G09C 1/00. Спосіб алгебраїчного декодування перешкодостійких кодів. / О.О. Кузнецов, С.П. Євсеєв, О.В. Дорохов, І.В. Пасько, Р.В. Корольов - №u200810955; Заявл. 08.09.2008; Опубл. 12.01.2009, Бюл. №1, 2009р. - 4с. 7 Комп’ютерна верстка А. Крулевський 54545 8 Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601