Неалгебраїчний декодер коригувальних кодів

Реферат: UA 84354 U UA 84354 U 5 10 15 20 25 30 35 40 45 50 55 Корисна модель належить до області завадостійкого кодування і може бути використана в цифрових каналах передачі інформації, у телекомунікаційних комп'ютерних мережах, супутникових мережах передачі даних, стільникових мережах мобільного зв'язку цифрових стандартів, пристроях запису/зчитування інформації на магнітні або оптичні носії й у ряді інших областей передачі й обробки інформації. Відомий декодер Меггіта, що містить (n-k)-розрядний синдромний регістр зі зворотними зв'язками, буферний зсувний n-розрядний регістр, логічний блок перевірки на збіг табличних синдромів, коректор помилок і модифікатор синдрому [1]. Недоліком цього пристрою є відсутність можливості повної обробки (декодування з виділенням інформаційної групи з кодового слова) несистематичних кодових слів без додаткового пристрою - дільника поліномів (цифрового фільтра). Відомий декодер з виловлюванням помилок, що містить (n-k)-розрядний синдромний регістр зі зворотними зв'язками, буферний зсувний n-розрядний регістр, логічний блок перевірки за критеріями ковзних синдромів, модифікатор синдрому й два керованих ключі [2]. Недоліком цього пристрою є відсутність можливості повної обробки (декодування з виділенням інформаційної групи з кодового слова) несистематичних кодових слів без додаткового пристрою - дільника поліномів (цифрового фільтра). Відомий неалгебраїчний декодер (Меггіта) для декодування кодових слів досконалого коду Голея, що включає додатково коригувальну схему, керовану керуючою схемою й з'єднану з k розрядами (тригерами) зсувного буферного регістра, що дозволяє в 1,5 рази підвищити швидкість декодування [3]. Недоліком даного пристрою є неможливість повної обробки несистематичних кодових слів без додаткового пристрою-виділювача з них інформаційних груп. Найбільш близьким по технічній суті є синдромний декодер для несистематичного (15, 11) коду Хеммінга [4]. Декодер, узятий як прототип, містить (n-k=15-11=4)-х-розрядний синдромний регістр зі зворотними зв'язками, виходи кожного тригера якого з'єднані із чотирма входами пристрою зберігання всіх синдромів - ПЗП з організацією 16 кодових слів по 15 бітів кожне. Крім того, він містить два 15-бітових зсувних регістри, причому вхід одного з них з'єднаний з виходом ПЗП, а вхід другого - із входом декодера, виходи обох регістрів з'єднані із входом суматора за модулем 2 (коректора помилок), вихід якого з'єднаний із входом пристрою виділення інформаційної групи ~ і(х) з оцінки кодового слова Cx  на виході декодера й регістр, що являє собою зсувний регістр зі зворотними зв'язками (цифровий фільтр). Робота прототипу полягає в наступному. Прийнята з каналу зв'язку 15-бітова кодова послідовність v(x) надходить через пристрій розв'язки сигналів (суматор за модулем 2) на 4розрядний синдромний регістр зі зворотними зв'язками, у якому виконується ділення v(x) на g(x), причому g(x) задає структуру синдромного регістра. На виходах його тригерів утвориться синдром s(x), який дорівнює залишку від ділення v(x) на g(x): Re g(x)[v(x)]. Синдромний поліном s(x) ≠ 0, якщо в прийнятому v(x) є помилка. Для коду (15, 11) синдром представляє 4-бітовий 4 (15, 11) багаточлен. У ПЗП записані всі 2 =16 синдромів, що є адресами для вибору з таблиці ПЗП оцінки для багаточлена с(х). У випадку рівності синдрому на виході синдромного регістра із 1 записаним у ПЗП, на виході останнього формується сигнал логічної одиниці U , що надходить на один з 15-розрядних регістрів зрушення й просувається до його виходу. Одночасно на вхід другого буферного 15-розрядного регістра зрушення надходить і послідовно просувається по ньому вхідна послідовність v(x) разом з помилкою в ній. У той момент, коли помилка досягає останнього розряду буферного регістра й готова надійти на вхід пристрою виділення інформаційної групи ~ x  , сигнал логічної одиниці з виходу першого зсувного регістра i надходить на вхід коректора помилок (суматора за модулем 2) і виправляє помилку: 1 0 трансформує U в U і навпаки. ПЗП разом з першим 15-розрядним регістром зрушення є одним з варіантів рішення логічного блока перевірки синдромів за критеріями (ЛБПСК), властивих синдромному декодеру. ~ Продекодоване, виправлене від помилок кодове слово Cx  , сформоване кодером у несистематичному вигляді, надходить потім на вхід пристрою виділення 11-бітової ~ інформаційної групи ~ x  з Cx  . Цей пристрій являє собою 4-розрядний зсувний регістр зі i зворотними зв'язками, за структурою й параметрами повністю співпадаючий із синдромним регістром. Такий збіг не випадковий і визначається тим, що синдромний регістр реалізує ~ функцію s(x) = Reg(x)[v(x)], а пристрій виділення помилок функцію ~ x   Cx  / gx  . Як видно, i виконувані дії практично ідентичні. 1 UA 84354 U 5 10 15 20 25 30 35 40 45 50 55 60 Недоліками пристрою, узятого як прототип, є: - складність схеми декодера для несистематичного коду за рахунок приєднання до нього пристрою виділення інформаційної групи (цифрового фільтра-дільника); - вузька межа використання декодера, оскільки він в даному випадку є синдромним декодером, що обробляє лише кодові слова (15, 11) коду Хеммінга; - великий час обробки кодових слів. Це пояснюється тим, що кодове слово при несистематичному кодуванні утвориться шляхом множення інформаційної групи і(х) на утворюючий поліном g(x) використовуваного коду: с(х) = і(х) g(x). Крім того, у прототипі робота відбувається таким чином, що протягом першого тимчасового циклу з n тактів формується синдром s(x) = Reg(x)[v(x)], протягом 2-го й 3-го (іноді тільки 2-го) циклів відбувається корекція помилок. Але для послідовної роботи пристрою виділення інформаційної групи символів (біт) необхідний ще один додатковий цикл роботи - 4ий (або 3-ий). Таким чином, у першому випадку час обробки збільшується в 4/3 разу, а в другому - в 3/2 разу, а, виходить, у стільки ж раз зменшується припустима швидкість обробки даних, які надходять з каналу зв'язку. В основу корисної моделі поставлена задача вдосконалити неалгебраїчний декодер коригувальних кодів шляхом виділення інформаційної групи і(х) за допомогою синдромного (nk)-розрядного регістра зсуву зі зворотними зв'язками, що дозволяє спростити схему декодера, розширити границю його використання, зменшити час обробки кодових слів. Поставлена задача вирішується тим, що в неалгебраїчний декодер коригувальних кодів, що містить синдромний (n-k)-розрядний регістр зсуву зі зворотними зв'язками, виходи кожного тригера якого з'єднані із входами логічного блока перевірки синдромів за заданими критеріями, буферний n-розрядний регістр зсуву, вихід якого з'єднаний з коректором помилок, пристрій розв'язки вхідних сигналів, вихід якого з'єднаний із входом синдромного (n-k)-розрядного регістра зсуву зі зворотними зв'язками, його перший вхід з'єднаний із входом декодера, вихідний ключ, з'єднаний з виходом коректора помилок і з першим виходом декодера (Вихід 1), пристрій виділення інформаційної групи, додатково уведені два ланцюги із ключами, причому один з них встановлено між виходом (n-k)-ого осередку буферного n-розрядного регістра зсуву й другим входом пристрою розв'язки вхідних сигналів, другий одним кінцем з'єднаний з виходом першого тригера синдромного (n-k)-розрядного регістра зсуву зі зворотними зв'язками, а другий його кінець - з другим виходом декодера, при цьому знову уведений модифікатор синдрому, перший вхід якого з'єднаний з виходом синдромного (n-k)-розрядного регістра зсуву зі зворотними зв'язками, другий - з виходом логічного блока перевірки синдромів за заданими критеріями, а вихід модифікатора синдрому з'єднаний із третім входом пристрою розв'язки, причому як пристрій виділення інформаційної групи використовується синдромний (n-k)розрядний регістр зсуву зі зворотними зв'язками. Таким чином, введення в декодер двох ланцюгів із ключами, модифікатора синдрому й використання як пристрою виділення інформаційної групи синдромного (n-k)-розрядного регістра зсуву зі зворотними зв'язками, дозволяє спростити схему декодера, розширити границю його використання, зменшити час обробки кодових слів. Суть корисної моделі пояснюється ілюстраціями (фіг. 1, 2, 3), де представлені структурна схема неалгебраїчного декодера (фіг. 1), структурна схема синдромного (n-k)-розрядного регістра зсуву зі зворотними зв'язками 2 декодера для коду Голея (фіг. 2) і просторово-часова діаграма (ПЧД) роботи декодера (фіг. 3). Неалгебраїчний декодер коригувальних кодів містить пристрій розв'язки вхідних сигналів 1, вихід якого з'єднаний із синдромним (n-k)-розрядним регістром зсуву зі зворотними зв'язками 2, буферний n-розрядний регістр зсуву 3, логічний блок перевірки синдромів за заданими критеріями 4. Вихідний ключ 5 з'єднаний з першим виходом декодера. Ланцюг із ключем 6 з'єднує (n-k)-тригер буферного n-розрядного регістра зсуву 3 із третім входом пристрою розв'язки 1, а ланцюг із ключем 7 з'єднує перший тригер синдромного (n-k)-розрядного регістра зсуву зі зворотними зв'язками 2 із другим виходом декодера. Буферний n-розрядний регістр зсуву 3 з'єднаний з коректором помилок 8, а модифікатор синдрому 9 своїми входами з'єднаний з синдромним (n-k)-розрядним регістром зсуву зі зворотними зв'язками 2 і логічним блоком перевірки синдромів за заданими критеріями 4, а своїм виходом - із пристроєм розв'язки вхідних сигналів 1. Робота пропонованого пристрою відбувається в такий спосіб (фіг. 1). Попередньо всі блоки декодера обнулені. Вхідне кодове слово  або v(x), можливо, уражене перешкодами в каналі зв'язку (тобто з помилками) через пристрій розв'язки вхідних сигналів 1 послідовно подається на вхід синдромного (n-k)-розрядного регістра зсуву зі зворотними зв'язками 2. Неалгебраїчний декодер обробляє вступні кодові слова за три цикли роботи з n тимчасових тактів кожний. 2 UA 84354 U 5 10 15 20 25 30 35 40 45 Протягом 1-го циклу роботи в синдромному регістрі зсуву 2 формується синдром S або s(x), а буферний n-розрядний регістр зсуву 3 послідовно заповнюється символами кодового слова v(x), що надходить на вхід декодера. Оскільки синдром по визначенню є залишком від ділення v(x) на утворюючий поліном g(x), то синдромний регістр зсуву 2, структура якого задається структурою g(x), є таким дільником (цифровим фільтром). Логічний блок перевірки синдромів за заданими критеріями 4 протягом 1-го циклу функціонування декодера не працює. Якщо продекодоване кодове слово с(х) не має помилок, то v(x) = c(x), е(х) = 0, і до кінця 1-го циклу роботи синдромний регістр зсуву 2 обнуляється. У випадку наявності помилок у кодовому слові, що надходить на декодер, е(х) ≠ 0, v(x) ≠ с(х), і до кінця 1-го циклу роботи на виході синдромного регістра зсуву 2 формується деяка кодова комбінація. Протягом 1-го циклу роботи ключі 5, 6 і 7 розімкнуті. Протягом 2-го циклу роботи у випадку обнуління синдромного регістра зсуву 2 на 1-ому циклі роботи синдромний регістр зсуву 2 простоює, перебуваючи в обнуленому стані. У випадку, якщо синдромний регістр зсуву 2 не обнулився на 1-ому циклі роботи, логічний блок перевірки синдромів за заданими критеріями 4 на кожному такті аналізує кодові комбінації на виходах осередків синдромного регістра зсуву 2, у випадках виявлення синдромів способом, різним для 1 кожного типу декодера, видає з виходу сигнал логічної одиниці U , що надходить на коректор помилок 8, виправляючи помилку й на модифікатор синдромів 9, спрощуючи структуру синдромів. За час 2-го циклу роботи ключі 5, 6, 7 розімкнуті. У результаті вхідна послідовність v(x) примусово повторно проходить осередку буферного n-розрядного регістра зсуву 3, що забезпечує скорочення відстані між широко (  n  k біт) розташованими помилками і дозволяє обробляти й виправляти їх. Протягом 3-го циклу роботи синдромний регістр зсуву 2 продовжує працювати разом з логічним блоком перевірки синдромів за заданими критеріями 4, виправляючи помилки, що залишилися, і модернізує синдроми. З виправленням останньої помилки синдромний регістр зсуву 2 обнуляється. На цьому останньому циклі роботи функціонування декодера залежить від способу формування кодових слів. А. У випадку формування кодового слова систематичним методом ключі 6 і 7 розімкнуті, вихідний ключ замкнуто протягом перших k тактів, пропускаючи на Вихід 1 інформаційну групу і(х), після чого розмикається. Б. У випадку формування кодового слова несистематичним методом ключ 5 розімкнуто. Ключі 6 і 7 також розімкнуті на перших n-k=r тактів 3-го циклу роботи. Потім вони замикаються на тактах, що залишилися, 3-го циклу роботи. У цей час із (n-k)-го тригера буферного nрозрядного регістра зсуву 3 знімається й подається на вхід синдромного регістра зсуву 2 ~ декодована оцінка кодового слова Cx  , а з першого тригера цього регістра в послідовному коді ~ знімається оцінка інформаційної групи i x  (Вихід 2), Наприкінці 3-го цикли роботи регістри обнуляються, і декодер готовий до обробки чергового кодового слова, можливо, перекрученого перешкодами в каналі зв'язку. Розглянемо роботу синдромного регістра зсуву 2 і всього декодера на конкретному прикладі з використанням просторово-часової діаграми (ПЧД). Нехай декодер є декодером з виловлюванням помилок, розробленим під обробку кодового слова блокового коду Голея (23, 12, 7). Структура синдромного регістра зсуву 2 для цього випадку наведена на фіг. 2, де 1 пристрій розв'язки вхідних сигналів; 2 - синдромний регістр зсуву 2; 9 - модифікатор синдромів. Зі схеми видно, що розташування зворотних зв'язків синдромного регістра зсуву повністю визначається структурою одного із двох утворюючих поліномів g(x) цього коду, що має вигляд gx   x11  x10  x 6  x 5  x 4  x 2  1, 50 (1) Нехай кодові слова коду Голея формуються кодером несистематичним способом, тобто c(x) = i(x)g(x). 10 3 Розглянемо для приклада значення і(х) = х +х або у векторному вигляді І = 010000001000. Значення кодового слова для взятого і(х) буде дорівнювати    c x   i x gx   x10  x 3 x11  x10  x 6  x 5  x 4  x 2  1  x 55 21 x 20 x 16 x 15 x 13 x 12 x 10 9 8 , 7  x  x  x  x5  x3 Відомо, що код Голея здатний виправляти всі помилки кратністю t не більше трьох 3 (2) UA 84354 U t шир  dм и н  1  7  1 / 2  3 помилки. 2 (3) Розглянемо випадок з максимальним числом помилок - 3 у сформованому кодовому слові (2). Нехай поліном помилок дорівнює 5 ex   x19  x16  x , (4) що відповідає вектору Е = 00010010000000000000010. Тоді кодове слово (2), уражене перешкодами (помилками (4)), буде мати вигляд x16 v x   c x   ex   x 21  x 20  x19  0  x15  x13  x12  x10  x 9  x 8  x 7  x 5  x 3  x , (5) 10 або у векторному вигляді V  C E  0111000101 1011110101 010 , 15 20 25 30 35 40 45 (6) Тут виділені чорним шрифтом біти помилок. Далі роботу синдромного регістра зсуву й декодера зручно й наочно розглянути за допомогою ПЧД (фіг. 2), розробленої для взятих як приклад і(х), с(х), е(х), v(x). ПЧД являє собою поле розміром 3n х (n-k), у цьому випадку (69 × 11) для ілюстрації роботи синдромного регістра зсуву, поле розміром 3n х n (69 × 23) для ілюстрації роботи буферного регістра й стовпець розміром 3n х 1 (69 × 1) для ілюстрації роботи логічного блока перевірки синдромів за заданими критеріями. На фіг. 3 для спрощення представлені лише поля синдромного регістра зсуву й логічного блока. У кожному полі по горизонталі відкладені осередки регістрів (координати простору), по вертикалі - такти й цикли роботи (координати часу). Розглянутий декодер обробляє кодові слова коду Голея за три цикли роботи з 23 (n) тактів кожний. На фіг. 3 показане послідовне надходження в синдромний регістр зсуву протягом 1-го циклу вхідного кодового слова v(x), що має 3 помилки (їхні позиції відзначені) і процес формування в цьому синдромному регістрі зсуву. ПЧД показує, що до кінця 1-го циклу синдромний регістр зсуву не обнулився, що свідчить про наявність в v(x) помилок і виявленні їх декодером. Перший синдром sx   v x  / gx   x 7  x 5  x 4  x 3  x 2  x сформований, як видно, на 35ому такті 2-го циклу. До 44-му такту цей синдром перетвориться в кодову комбінацію з трьома одиницями, що збігається за структурою з конфігурацією помилок в v(x) після повторного проходження їм буферного регістра. У цьому випадку на 44-ому такті роботи логічний блок на 1 основі логіки своєї роботи із заданих критеріїв видає сигнал логічної одиниці U зі свого виходу, що надходить на коректор помилок 8 і виправляє помилковий біт, що виходить із останнього осередку буферного регістра. Подібним же чином декодер протягом першої половини 3-го циклу виправляє дві помилки, що залишилися. У другій половині 3-го циклу роботи (з 58-го такту), завдяки замиканню ключів 6 і 7 з (n-k)-го ~ тригера буферного регістра 3 знімається кодове слово Cx  і через пристрій розв'язки 1 надходять на входи синдромного регістра зсуву 2. Одночасно з виходу його 1-ого осередку послідовно знімається інформаційна група і(х) на Вихід 2. ~ Як видно із ПЧД, виділення ~ x  з Cx  у синдромному регістрі 2 не заважає його основній i роботі й не вимагає додаткового часу. Таким чином, з розглянутого вище видно, що: 1. Запропонований декодер значно спрощений за рахунок відсутності пристрою виділення ~ ~ i x  з Cx  (який є присутнім у прототипі). Він універсальний, тому що дозволяє обробляти кодові слова, сформовані як систематичним, так і несистематичним методами. 2. Запропонований декодер має широку область застосування, оскільки може бути реалізований замість будь-якого неалгебраїчного декодера, що має у своєму складі синдромний регістр зсуву зі зворотними зв'язками й призначеного, насамперед, для обробки кодових слів, сформованих несистематичним методом. 4 UA 84354 U 5 10 3. Запропонований декодер не сповільнює процес обробки кодових слів і швидкість передачі їх по каналу зв'язку, тому що виділення інформаційної групи ~ x  відбувається в межах 3-го i циклу роботи, який і так необхідний для виконання основної функції - декодування. Джерела інформації: 1. Блейхут Р. Теория и практика кодов, контролирующих ошибки/ Пер. с англ. - М: Мир, 1986. - С. 169.-576 с. 2. Блейхут Р. Теория и практика кодов, контролирующих ошибки/ Пер. с англ. - М: Мир, 1986. - С. 174. - 576 с. 3. Патент RU № 85778 Неалгебраический декодер, авторы Жиляков Е.Г., Белов С.П., Макаров Л.Б. и др., по заявке 2009112662/22, 06.04.2009. 4. Блейхут Р. Теория и практика кодов, контролирующих ошибки/ Пер, с англ. - М.: Мир, 1986. - С. 164. - Рис. 6.17. - 576 с. - прототип. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 15 20 25 30 Неалгебраїчний декодер коригувальних кодів, що містить синдромний (n-k)-розрядний регістр зсуву зі зворотними зв'язками, виходи кожного тригера якого з'єднані із входами логічного блока перевірки синдромів за заданими критеріями, буферний n-розрядний регістр зсуву, вихід якого з'єднаний з коректором помилок, пристрій розв'язки вхідних сигналів, вихід якого з'єднаний із входом синдромного (n-k)-розрядного регістра зсуву зі зворотними зв'язками, його перший вхід з'єднаний із входом декодера, вихідний ключ, з'єднаний з виходом коректора помилок і з першим виходом декодера (Вихід 1), пристрій виділення інформаційної групи, який відрізняється тим, що в ньому додатково уведені два ланцюги із ключами, причому один з них установлений між виходом (n-k)-ого осередку буферного n-розрядного регістра зсуву й другим входом пристрою розв'язки вхідних сигналів, другий одним кінцем з'єднаний з виходом першого тригера синдромного (n-k)-розрядного регістра зсуву зі зворотними зв'язками, а другий його кінець з'єднаний з другим виходом декодера (Вихід 2), при цьому знову уведений модифікатор синдрому, перший вхід якого з'єднаний з виходом синдромного (n-k)-розрядного регістра зсуву зі зворотними зв'язками, другий - з виходом логічного блока перевірки синдромів за заданими критеріями, а вихід модифікатора синдрому з'єднаний із третім входом пристрою розв'язки, причому як пристрій виділення інформаційної групи використовується синдромний (n-k)розрядний регістр зсуву зі зворотними зв'язками. 5 UA 84354 U 6 UA 84354 U Комп’ютерна верстка Л. Ціхановська Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 7