Пристрій для декодування подвійних помилок

Реферат: UA 69627 U UA 69627 U 5 10 Корисна модель належить до галузі обчислювальної техніки і може бути використана в пристроях для кодування та декодування циклічних кодів, призначених для передачі повідомлень з високою достовірністю в системах доставки і обробки дискретної інформації. Відомий пристрій для декодування одиночних недвійкових помилок, що містить блок інформаційних вузлів, блок обчислення викривленого поліному, блок контрольних вузлів, блок виявлення помилок, блок корекції помилок [1]. Такі пристрої мають великі апаратурні витрати на реалізацію операцій кодування та декодування та в цілому на реалізацію схем контролю і схем видачі результату. Найбільш близьким до пропонованого по технічній суті є [2] пристрій для декодування одиночних недвійкових помилок, який містить блок інформаційних вузлів, вихід якого з'єднаний з входом блока контрольних вузлів, перший вихід якого з'єднаний з першим входом блока корекції помилок, а другий вихід якого з'єднаний з входом блока виявлення помилок, вихід якого з'єднаний з другим входом блока корекції помилок, а в блоці інформаційних вузлів визначаються величини неув'язок R1 та R2 та обчислюються величини синдромів Qo та Q1, який містить значення викривленого полінома f x  , причому значення викривленого полінома f x  обчислюються в блоці контрольних вузлів, а блок виявлення помилок визначає номер позиції ~ 15 ~ ~ x 20 25 30 35  або місце викривленого символу j та обчислюється величина помилки j , для якого в блоці корекції помилок відбувається корекція викривленого символу. Недоліком даного пристрою є обмеженість функціональних можливостей за рахунок важких апаратурних витрат при виконанні операції виявлення та декодування одиночних помилок та обмежене виявлення двійкових помилок, за рахунок чого зростають часові витрати при кодуванні та декодуванні інформації. Задачею корисної моделі є удосконалення пристрою для декодування одиночних недвійкових помилок шляхом введення блока неув'язок, блока синдромів та блока елементарних симетричних функцій. Це дозволяє забезпечити безпосередньо виконання операції корекції не тільки одиночних та подвійних помилок, а також виявлення деяких помилок в кількості більше ніж 2, тобто має широкі функціональні можливості застосування їх в процедурах кодування та декодування кодів. Поставлена задача вирішується тим, що в пристрої для декодування подвійних помилок, що містить блок контрольних символів прийнятого повідомлення, вихід якого з'єднаний з входом блока неув'язок, вихід якого з'єднаний з входом блока синдромів, вихід якого з'єднаний з входом блока елементарних симетричних функцій, а також, згідно з корисною моделлю, вихід якого з'єднаний з входом блока виявлення помилок та їх величин, вихід якого з'єднаний з входом блока корекції помилок. Для виправлення подвійної помилки, наприклад, необхідно виконати обчислення значення викривленого полінома в усіх контрольних вузлах, де для першого контрольного вузла маємо: f * 1   s  ~ i fiL S 1    i0 s 4   x   / i0 ~ fi i l 1  l  l2 . При обчисленні значення викривленого полінома f x  у другому, третьому та четвертому 40 ~ fi контрольних вузлах, окрім інформаційних ~ ~ ~ f 1  f  2  f  3  ~ символів, використовується відповідно значення , , контрольних символів прийнятої кодової послідовності. А величина неув'язок визначається як: ~ ~ R1  f 1   f * 1  R 2  f  2   f *  2  , , ~ ~ R3  f 3   f * 3  R 4  f  4   f *  4  45 , . А обчислення величини синдромів визначається як: Q0  R 4 , Q1  R44  R3 3  4    R  ,      R  2 Q2  R42  R3 3  2  R2 2  3 2  4  4 4 Q3  R43 4 50 3 3 3 4 ,  3 2  4 2  3  4   R11  2 1  3 1  4  3 2 2 . Визначення місця та величини помилки виконується обчисленням визначника матриці: 1 UA 69627 U M 5 10 15 20 Q0 Q1 2  Q0Q2  Q1 Q1 Q2 .     Q , ~   ~  Q x x 0 i1 i1 i2 i2 1 Після обчислення величини помилки i1 i2 виконується корекція помилки та викривлених символів. При виконанні алгоритму пристрій для декодування виправляє одиночні та подвійні помилки, а також виявляє деякі помилки в кількості більше двох. В результаті це дозволяє забезпечити безпосередньо виконувати операції декодування подвійних помилок, і як наслідок, розширення функціональних можливостей побудови комбінаційних схем. На фіг. 1 зображена структурна схема пристрою декодування подвійних помилок. На фіг. 2 приклад схеми пристрою для виправлення подвійної помилки алгоритму декодування одиночних недвійкових помилок. Пристрій для декодування подвійних помилок містить блок контрольних символів прийнятого повідомлення 1, блок неув'язок 2, блок синдромів 3, блок елементарних симетричних функцій 4, блок виявлення помилок та їх величин 5, блок корекції помилок 6. Блок контрольних символів прийнятого повідомлення 1 містить виходи 7 значень величин викривленого полінома, блок неув'язок 2 містить виходи 8 значень неув'язок, блок синдромів 3 містить виходи 9 величин синдромів, блок елементарних симетричних функцій 4 містить виходи 10 визначених нормалізованих елементарних функцій, блок виявлення помилок та їх величин 5 містить виходи 11 визначених місць та величин помилок. Пристрій для декодування подвійних помилок працює в такий спосіб. В блоці контрольних символів прийнятого повідомлення 1 виконується декодування подвійної помилки та обчислюються значення викривленого полінома в усіх контрольних вузлах, значення яких надходять до виходів 7. f * 1   s  ~ i fiL S 1    i0 s 4   x   / ~ fi i0 i l 1  l  l2 Також виконується обчислення значення викривленого полінома f x  у другому, третьому та ~ 25 четвертому контрольних вузлах, окрім інформаційних ~ ~ ~ f 1  f  2  f  3  відповідно значення f *  2   [ s  , 1 i0 f *  4   [ s , ~ ~ i fi  f 1 ]LS  2  f *  3   [  f  f    f  ~ ~ 1 2 3 ,  x    / i LS 2    ~ i i   f 3 ]LS  4  S2  S   1,2 S3  S   1,2,3    4 ~ ~ 1 i0 i0 30  f  f    f  2 i ]LS 3  2 ,  ~ i символів, для яких використовується контрольних символів прийнятої кодової послідовності. s , ~ fi   , де S1  S  1 , ,  l  i Li 3   xi  4  /3  4  LS 3   1 , S2 , 2 . У блоці неув'язок 2 обчислюються величини неув'язок 8: 1 i l 2 l3 ~ ~ R1  f 1   f * 1  R 2  f  2   f *  2  , , ~ ~ R3  f 3   f * 3  R 4  f  4   f *  4  35 ~ f 1  , ~ f  2  ~ f  3  , де , , , - значення контрольних символів прийнятого повідомлення. Якщо R1=R2=R3=R4=0, то помилок немає. А обчислення величин синдромів 9 визначається у блоці синдромів 3 як: Q0  R 4 , Q1  R44  R3 3  4  40 ~ f  4    R  ,      R  2 Q2  R42  R3 3  2  R2 2  3 2  4  4 4 Q3  R43 4 3 3 3 4 ,  3 2  4 2  3  4   R11  2 1  3 1  4  3 2 2 . Визначених нормалізованих елементарних функцій 10 виконується в блоці елементарних симетричних функцій 4, використовуючи співвідношення: 2 UA 69627 U Q02  Q11  Q2  0, Q12  Q21  Q3  0 . Ці рівняння будуть вирішенні, якщо матриця буде не вироджена, M  Q0 Q1 Q1 Q2 , M 0 т. ч. визначник матриці 5 При M 0 Q0 1  . обчислюються елементарні симетричні функції Q2 Q1 Q3 M  Q1Q 2  Q0Q3 2 Q0Q 2  Q1 . Визначення місця та величини помилки виконується в блоці виявлення помилок та їх величин 5 обчисленням визначника матриці: M 10 Q0 Q1 2  Q0Q2  Q1 Q1 Q2 M 0 Якщо . M 0 , то кількість помилок дорівнює 2. Якщо M 0 , то кількість помилок не більше 1, Q0  0 інакше та , то декодування вважається невдалим та реєструється виявлення невиправленої комбінації помилок. Визначення номера позиції викривлених символів ~2   ~    0 x x 1 2 виконується за допомогою алгоритму Ченя вирішенням рівняння . Якщо мала місце тільки одна помилка, то номер помилкового вузла визначається із співвідношень 15 Q0  i1 ~i0 x 1 , Q1  i1 ~i1  Q0~i1 x x вирішенням рівнянь   i1  Q0~i2  Q1 x i2  Q1  Q0~i2 x , звідки i1  i2  Q0 / ~i x / ~i x 2 2  ~i1 x  ~i1 x    .   , ~  Q /Q xi1 1 0 i1 ~i1  i2 ~i2  Q1 x x Якщо виникла одна помилка, то i1  Q0 Після обчислення величини помилки 20 25 . Обчислення величин помилок знаходимо , де отримаємо . i1  i2  Q0 , i1 ~i1  i2 ~i2  Q1 x x ~ fi1  fi1  i1 виконується корекція ~ fi 2  fi 2  i 2 помилки та викривлених символів у блоці 6 корекції помилок та . Таким чином, ефективність запропонованого пристрою визначається його багатофункціональними можливостями (деякі дані про місце та величину помилки можливо отримати навіть при аналізі величин неув'язок R та синдромів Q), регулярністю структури та можливістю реалізації у вигляді ВІС або ПЛІС. Джерела інформації: 1. Патент Російської Федерації № 2007042, кл. Н 03 М 13/02, 1994. 2. Деклараційний патент на корисну модель № 49052, кл. Н 03 М 13/00, 2009. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 35 Пристрій для декодування подвійних помилок, що містить блок контрольних символів прийнятого повідомлення, вихід якого з'єднаний з входом блока неув'язок, вихід якого з'єднаний з входом блока синдромів, вихід якого з'єднаний з входом блока елементарних симетричних функцій, який відрізняється тим, що вихід блока елементарних симетричних функцій з'єднаний з входом блока виявлення помилок та їх величин, вихід якого з'єднаний з входом блока корекції помилок. 3 UA 69627 U 4 UA 69627 U Комп’ютерна верстка І. Скворцова Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5