Пристрій для паралельного декодування пакетів помилок в циклічних (n,к)-кодах

1. Пристрій для паралельного декодування пакетів помилок в циклічних (п, к)-кодах, який містить перший перетворювач кодів І блок синхронізації, вихід якого з'єднаний з входом синхронізації першого перетворювача кодів, інформаційний вхід і вхід початкового установлення якого під'єднані відповідно до інформаційного входу пристрою і до входу початкового установлення пристрою, який відрізняється тим, що в нього введені доп-1 . . датково перетворювачів кодів і блок визначення параметрів пакетів помилок, перша 2т-розрядна група інформаційних виходів якого І друга 2т-розрядна група Інформаційних виходів якого під'єднані відпоаідно до першої групи інформаційних виходів пристрою і до другої групи Інформаційних виходів пристрою, т=[Іодгп], вхід керування пристрою з'єднаний з першим входом керування блока синхронізації, вихід якого з'єднаний також з входами синхронізації інших перетворювачів кодів та блока визначення параметрів пакетів помилок, інформаційний вихід якого з'єднаний з другим входом керування блока синхронізації і під'єднаний до першого Інформаційного виходу пристрою, перший інформаційний вихід і-го перетворювача кодів з'єднаний з інформаційним входом (і+1)-го перетворювача кодів (і = 1-*- - ^ — ) , а другий інформаційний вихід і-го перетворювача кодів з'єднаний з І-м інформаційним входом блока визначення па,. п• 1 „ + раметрів пакетів помилок, (і = 1 + ——- ), а другий інформаційний вихід першого перетворювача кодів також під'єднаний до другого інформаційного виходу пристрою, вхід початкового установлення якого з'єднаний також з входами початкового установлення інших перетворювачів кодів, блока синхронізації та блока визначення параметрів пакетів помилок. 2. Пристрій по п.1, який відрізняється тим, що перетворювач кодів містить лінійну послідовнісну схему (ЛПС), елемент ( та D-тригер, прямий вихід якого з'єднаний з першим інформаційним виходом перетворювача кодів, інформаційний вхід якого під'єднаний до інформаційного входу пристрою і з'єднаний з інформаційним входом ЛПС і з D-входом D-тригера, синхровхід якого з'єднаний з входом синхронізації ЛПС і з входом синхронізації перетворювача кодів, вхід початкового установлення якого з'єднаний з входом початкового установлення перетворювача кодів і з входом початкового установлення ЛПС, другий інформаційний вихід і-го перетворювача кодів з'єднаний з виходом елемента І, ]-й вхід-якого з'єднаний з прямим значенням ]го виходу ЛПС, якщо j-й розряд і-го еталонного вектору дорівнює одиниці, а j-й вхід елемента І з'єднаний з інверсним значенням j-ro виходу ЛПС, якщо j-й розряд і-го еталонного вектору дорівнює нулю, де еталонний вектор визначається вибраним породним многочленом циклічного (п, к)-коду 3. Пристрій по п.1, який відрізняється тим, що блок формування параметрів пакетів помилок містить m-роэрядний регістр зсуву, m-розрядний лічильник, шифратор, перший паралельний двійковий m-розрядний суматор, другий паралельний двійковий m-розрядний суматор, третій паралельний двійковий m-розрядний суматор, елемент АБО, вихід якого з'єднаний з входом паралельного запису регістра зсуву та з інформаційним виходом п+1 . , . , блоку, ——- інформаційних входів якого з єднані з входами елемента АБО та з входами шифратора, група m-розрядних Інформаційних виходів якого з'єднана з групою інформаційних входів регістра зсуву та з першими групами інформаційних входів першого та другого суматорів, вхід синхронізації блока з'єднаний з входом зсуву регістра зсуву та з входом додавання лічильника, група ш-розрядних інформаційних виходів якого з'єднана з першою групою Інформаційних входів третього суматора, другу групу m-розрядних Інформаційних входів якого з'єднано з групою інформаційних виходів регістра зсуву, а вихід - з другою групою інформаційних входів другого суматора, на другу групу гл-розрядних інформаційних входів першого суматора подано число п, m-розрядна група інформаційних виходів шифратора і m-розрядна група ін CO ю со 34753 формаційних виходів першого суматора створюють першу 2т-розрядну групу Інформаційних виходів блока, т-розрядна група інформаційних виходів другого суматора І т-розрядна група інформаційних виходів третього сумато ра створюють другу 2т-розрядну групу інформаційних виходів блока, вхід початкового установлення якого з'єднаний з входами початкового установлення регістра зсуву та лічильника. Винахід відноситься до обчислювальної техніки і може бути використаний в системах обробки, збереження та передачі дискретних даних. Відомий пристрійдля виправлення двократних помилок в блоках передачі та збереження інформації, який містить вхідний регістр, перший і другий формувачі синдрому помилки, схему порівняння, регістр помилок, блок пам'яті помилок, блок корекції, групу інверторів з керуючим виходом, елемент АБО і тригер помилки корекції [див. А.С. СССР N 1173417, кл. G 06 F 11/08, бюп. N ЗО, 1985р.]. Недоліком цього пристрою є низька коректуюча здатність та великі апаратурні затрати. Найбільш близьким технічним розв'язком до запропонованого с пристрій для знаходження пакетних помилок, який містить перетворювач кодів, блок синхронізації, блок формування типу помилки, блок порівняння, лічильник, обчислювач адреси пакета помилки, регістр І дешифратор, причому перший вхід перетворювача кодів є першим Інформаційним входом пристрою, перші виходи перет.ворювача кодів з'єднані з першими входами блока порівняння, другі виходи перетворювача кодів з'єднані з першими входами обчислювача адреси пакета помилки, виходи якого є першими інформаційними виходами пристрою,перший вхід лічильника є входом початкового установлення пристрою, вихід лічильника - другим інформаційним ви- ходом пристрою, перший і другий виходи блока синхронізації з'єднані відповідно з другим входом лічильника і першим входом блока формування типу помилки, перший і другий виходи якого відповідно з'єднані з другим входом блока порівняння і з першими входами блока синхронізації та регістра і з другими входами блока синхронізації та обчислювача адреси пакета помилки і є першим та другим керуючими виходами пристрою відповідно, треті виходи перетворювача кодів з'єднані з другими входами блока формування типу помилки та регістра і з третіми входами блока порівняння, вихід якого з'єднаний з третіми входами блока формування типу помилки, четверті і п'яті входи якого під'єднані відповідно до перших і других виходів перетворювача кодів, четверті виходи якого з'єднані з шостими входами блока формування типу ' помилки, виходи регістра з'єднані з третіми входами обчислювача адреси пакета помилки, четверті входи якого і входи дешифратора під'єднані до виходів лічильника, третій І четвертий виходи блока синхронізації з'єднані відповідно з другим І третім входами перетворювача кодів, четвертий вхід якого є входом вибору режима роботи пристрою, п'ятий вхід перетворювача кодів, сьомий вхід блока формування типу помилки І треті входи блока синхронізації І регістра даних об'єднані та під'єднані до входу початкового установлення пристрою, четвертий вхід блока синхрон ізації є входом синхронізації пристрою, п'ятий і другий виходи пе ретворювача кодів І вихід дешифратора є відпо-, відно третім та четвертим інформаційними виходами і третім керуючим виходом пристрою [див. А С. СССР N 1541607 кл G 06 F 11/08. бюл. N 5 1990 р.]. Недоліком цього пристрою є невисока продуктивність роботи та низька коректуюча здатність, яка полягає в тому, що виявляються лише 4розрядні пакети помилок при великій довжині циклічного (п, к)-коду (наприклад, п=341, к=325, п=16). В основу винаходу поставлена задача створення пристрою для паралельного декодування пакетів помилок в циклічних (п, к)-кодах, в якому за рахунок введення нових блоків та зв'язків між ними досягається можливість швидкого знаходження довільних поодиноких пакетів помилок у відповідності із ймовірністю їх появи (спочатку пакети ПОМИЛОК ДОВЖИНИ 1, ПОТІМ ДОВЖИНИ 2, І Т. Д.). Найкращим відомим циклічним кодом для локалізації та виправлення одиночного пакета помилок є двійковий код Файра. Породний многочлен цього коду де д{х) - незвідний многочлен степені v, яка належить степені m (m=2 v -1}; с - просте число, яке не ділиться на m без остачі. Для виправлення одиночного пакету помилок довжиною z за допомогою коду Файра число перевірочних розрядів г повинно бути r=c+z або r>=3z-1, а довжина п коду дорівнює найменшому спільному кратному (НСК) чисел с та т.тобто п=НСК(с, гп); при цьому величина п буде не меншою, ніж (2M)(2z-1). За допомогою запропонованого методу можно буде виявляти та виправляти поодинокі пакети помилок максимальною довжиною z (z=n-1) розрядів, для будь-якого циклічного (п, к)-коду, для якого виконується умова: 2Г-1>= п(п ~1>. t ** Таким чином для виявлення пакетів помилок однакової довжини z в запропонованому пристрої знадобиться значно менша довжина коду п. Невелике збільшення апаратурних затрат в запропонованому пристрої дає можливість підвищити продуктивність роботи за рахунок одночасного пошуку можливих пакетів помилок, а також проводити послідовність пошуку пакетів помилок у відповідності із ймовірністю їх появи (спочатку пакети ПОМИЛОК ДОВЖИНИ 1 , ПОТІМ ДОВЖИНИ 2 , І Т. Д.) Поставлена задача розв'язується за рахунок 34753 того, що в пристрій для паралельного декодування пакетів помилок в циклічних (п, к)-кодах, де п довжина коду, a k - кількість інформаційних символів коду, який містить перший перетворювач кодів і блок синхронізації', вихід якого з'єднаний з входом синхронізації першого перетворювача кодів, інформаційний вхід і вхід початкового установлення якого під'єднані відповідно до інформаційного входу пристрою і до входу початкового установлення пристрою, введені додатково перетворювачів кодів І блок визначення параметрів пакетів помилок, перша 2т-розрядна група інформаційних виходів якого і друга 2т-розрядна група інформаційних виходів якого під'єднані відповідно до першої групи інформаційних виходів пристрою і до другої групи" Інформаційних виходів пристрою, m-ііодгп], де ( J означає округлення до цілого в більшу сторону, вхід керування пристрою з'єднаний з першим входом керування блока синхронізації, вихід якого з'єднаний також з входами синхронізації' Інших перетворювачів кодів та блока визначення параметрів пакетів помилок, інформаційний вихід якого з'єднаний з другим входом керування блока синхронізації і під'єднаний до першого інформаційного виходу пристрою, перший інформаційний вихід і-го перетворювача кодів з'єднаний з Інформаційним входом (і+1)-го перетворювача кодів (і=1 л - 1 ), а другий інформаційний вихід і-го перетворювача кодів з'єднаний з і-м інформаційним входом блока визначення параметрів пакетів ,. . п +1 , . . ^_ _ _ помилок, (і=1 + ——-), а другий інформаційний вихід першого перетворювача кодів також під'єднаний до другого інформаційного виходу пристрою, вхід початкового установлення якого з'єднаний також з входами початкового установлення інших перетворювачів кодів, блока синхронізації та блока визначення параметрів пакетів помилок. На ФІГ. 1 представлена функціональна схема пристрою; на ФІГ. 2 -функціональна схема перетворювача кодів, на ФІГ. З - функціональна схема блока визначення параметрів пакетів помилок; на ФІГ. 4 - функціональна схема можливої' реалізації лінійної послідовнісної схеми перетворювача кодів пристрою. Пристрій для паралельного декодування пакетів помилок в циклічних (п, к)-кодах, де п - довжина коду, а к - кількість інформаційних символів коду. (ФІГ. 1) містить f (f=(n+1)/2) перетворювачів кодів 1, блок 2 визначення параметрів пакетів помилок, блок 3 синхронізації. Вхід 4 Інформаційний пристрою з'єднаний з Інформаційним входом першого перетворювача кодів 1 Вхід 5 початкового установлення пристрою з'єднаний з входами початкового установлення всіх перетворювачів кодів 1, блоку 2 та блоку 3, перший вхід керування якого з'єднаний з входом керування б пристрою. Перша 2т-розрядна група Інформаційних виходів блока 2, і друга 2т-розрядна група інформаційних виходів блока 2 під'єднані відповідно до першої групи інформаційних виходів 7 пристрою І до другої групи інформаційних виходів 8 пристрою гл= [Іодгп], де ІJ означає округлення до цілого в більшу сторону. Інформаційний вихід блока 2 з'єднаний з другим входом керування блока 3 і під'єднаний до першого інформаційного виходу 9 пристрою. Перший інформаційний вихід і-го перетворювача кодів 1 з'єднаний з інформаційним входом (і+1)-го перетворювача кодів 1, (і=1 + М ) Другий інформаційний вихід і-го перетворювача кодів 1 з'єднаний з і-м інформаційним входом блока 2, (і=1 •- f ), а другий * інформаційний вихід першого перетворювача кодів 1 також під'єднаний до другого інформаційного виходу Ю пристрою Вихід блока 3 з'єднаний з входами синхронізації всіх перетворювачів кодів 1 та блока 2 Перетворювач кодів 1 (ФІГ 2) містить лінійну послідовнісну схему (ЛПС) 11, елемент І 12, D-тригер 13 Інформаційний вхід перетворювача кодів 1 під'єднаний до входу 4 пристрою і з'єднаний з інформаційним входом ЛПС 11 і з D-входом D-тригера 13, прямий вихід якого з'єднаний з першим інформаційним виходом перетворювача КОДІВ 1 Вхід початкового установлення перетворювача кодів 1 під'єднаний до входу 5 пристрою і з'єднаний з входом початкового установлення ЛПС 11. Вхід 14 синхронізації перетворювача кодів 1 з'єднаний з синхровходом D-тригера 13 і з входом синхронізації ЛПС 11, другий інформаційний вихід і-го перетворювача кодів 1 з'єднаний з виходом елемента І 12, і-й вхід якого з'єднаний з прямим значенням j го виходу ЛЛС 11, якщо j-й розряд і-го еталонного вектору дорівнює одиниці, а j-й вхід елемента І 12 з'єднаний з інверсним значенням j-ro виходу ЛПС • 11, якщо j-й розряд і-го еталонного вектору дорівнює нулю, де еталонний вектор визначається вибраним породним многочленом циклічного (п, к)-коду (j = 1 - г, І = 1 + f). Блок 2 формування параметрів пакетів помилок (ФІГ 3) містить m-розрядний репстр зсуву 17, m-розрядний ЛІЧИЛЬНИК 18, шифратор 19, перший паралельний двійковий m-розрядний суматор 20, другий паралельний двійковий m-розрядний суматор 21, третій паралельний двійковий m-розрядний суматор 22, елемент АБО 23, вихід якого з'єднаний з входом паралельного запису регістра 17 та з інформаційним виходом блоку, п + 1 ін формаційних входів 25 якого з'єднані з входами елемента АБО 23 та з входами шифратора 19, група m-розрядних інформаційних виходів якого з'єднана з групою інформаційних входів регістра 17 та з першими групами інформаційних входів суматорів 20 та 21. вхід 24 синхронізації блока з'єднаний з входом зсуву регістра 17 та з входом додавання лічильника 18, група m-розрядних інформаційних виходів якого з'єднана з першою групою інформаційних входів суматора 22, другу групу т розрядних Інформаційних входів якого з'єднано з групою інформаційних виходів регістра 17, а вихід - з другою rn-розрядною групою інформаційних входів суматора 21, на другу групу m-розрядних інформаційних входів суматора 20 подано число п, т-розрпдна група інформаційних виходів шифратора 19 і m-розрядна група Інформаційних виходів суматора 20 створюють першу 2т-розрядну групу Інформаційних виходів блока, т-розрядна група інформаційних виходів суматора 21 та т-розрядна група інформаційних виходів суматора 22 створюють другу 2п>розрядну групу інформаційних виходів блока, вхід початкового установлення якого 34753 з'єднаний з входами початкового установлення регістра 17 та лічильника 18. ЛПС 11 (варіант реалізації при г=8) перетворювача кодів 1 (ФІГ. 4) містить суматор 26 по модулю два, D-тригери 27-34, входи синхронізації яких з'єднані з входом 14 перетворювача кодів 1. Перший вхід суматора 26 з'єднаний з інформаційним входом перетворювача кодів 1, а його вихід з'єднаний з D-входом D-тригера 27. Виходи D-тригера 29, D-тригера ЗО, D-тригера З І , D-тригера 34 з'єднані з іншими чотирма входами суматора 26. Входи установки D-тригерів 27-34 з'єднані з входом початкового установлення перетворювача кодів 1 і під'єднані до входу 5 пристрою, прямі виходи D-тригерів 27-34 створюють 8-розрядну групу інформаційних виходів 35 перетворювача кодів 1, причому прямий вихід (Н)-го D-тригера з'єднаний з D-входом j-ro D-тригера 0=2 +8). Пристрій працює таким чином. Є два режима роботи пристрою: режим декодування і режим локалізації помилок. В режимі декодування в перетворювачі кодів 1 визначається вірність кодового вектора, який поступає послідовно на вхід 4 пристрою. В режимі локалізації помилок визначаються параметри пакета помилки в кодовому векторі. В цей режим роботи пристрій переходить після виявлення помилки в кодовому векторі. Теоретичною основою декодування циклічних кодів є математичний апарат ЛПС. В перетворювачі кодів 1 апаратно реалізована двійкова ЛПС, яка описується лінійною функцією переходів (стану) S та лінійною функцією виходів Y: S=AS+BU " . (1) ' .де S, U, Y - відповідно вектори станів, вхідний та вихідний; A- ia,,lrxr - основна характеристична матриця ЛПС; В= |b,lr - характеристична матриця ЛПС. В формулах (1) символи V т а ' ' позначають відповідно операції додавання та множення по модулю два. Можливі два варіанта матриць А та В, які можуть бути реалізовані апаратно в перетворювачі кодів 1: 0 І 0 ... 0 0 0 1 ... 0 0 в А (2) 0 0 0 ... 1 р 1 Р(х)=ро+ріХ+...+р.-іХм+ргхг. Ро 0 0 ... 0 ря 1 0 ... 0 р, "о р2 оі о о Рг-1 в (3) ' який поступає на вхід ЛПС, відбувається послідовна зміна и внутрішніх станів S=s(O),s(1),...;s(i-1),s(i) s(t). для обчислення яких замість формул (1) зручно користуватись наступними співвідношеннями: А • s(i -1) + В, якщо и(і -1) = 1, А • s(i -1), якщо и(і -1) = 0, Якщо на вхід ЛПС 11 поступає п-розрядний кодовий вектор без помилок, тоді г-розрядна ЛПС 11 з початкового нульового стану's(0) через п тактів роботи знову перейде в стан s(n)p. • . s(n)=s(O). тобто буде одержано попередній нульовий стан. При наявності помилки в кодовому векторі ЛПС 11 перейде в деякий ненульовий стан, який будемо називати синдромом помилки: s(n)=$*(n). Розглянемо кодовий вектор с^(х), який містить пакет помилок довжини z, який починається з w-ої позиції. Введемо вектор помилки F£ (х) Під дією кодового вектора czw (x) ЛПС 11 перейде в стан .?^.(и). для переходу із якого знову в стан s(0) необхідно подати на вхід ЛПС 11 вектор Особливістю двійкових циклічних кодів є те, що до одного і того ж синдрому помилки s^(n) призводить кодовий вектор з двома варіантами одиночних пакетів помилок довжиш відповідно zi та гг, які починаються в позиціях відповідно wi та w 2 . Якщо відомі параметри одного пакета помилки (zi і Wi), тоді можна визначити також параметри другого пакету помилок по формулах z2=n -zi, W або Під дією t-роэрядного вхідного вектора 0 р 2 ... Елементи останнього рядка матриці А в (2) або останнього стовпчика в (3) представляють собою коефіцієнти породного многочлена Р(х) коду : (5) , ЯКЩО W, +Z] П (6) Перед початком роботи пристрою на вхід 5 поступає сигнал, по якому всі блоки установлюються в початковий стан. Після приходу керуючого сигнала на вхід 6 починається робота пристрою в режимі декодування Протягом наступних п циклів на вхід 4 поступає n-роэрядний кодовий вектор с(х). На Інформаційний вхід і-го перетворювача кодів 1 j-й розряд кодового вектора с(х) поступає в (i+j-i)-" му циклі, тобто протягом f циклів j-й розряд век 34753 тора с(х) почергово проходить крізь f перетворювачів кодів 1 (i=1+f, j=1*n) Тривалість циклу роботи пристрою визначається проміжком між початками двох сусідніх синхроімпульсів, які поступають з виходу блоку 3 на всі інші блоки пристрою. Таким чином, в {і+1)-му перетворювачі кодів 1 відбувається декодування кодового вектора із затримкою на один цикл відносно і-го перетворювача кодів 1 (i=1+f). Через перші п циклів в першому перетворювачі кодів 2 закінчується етап декодування. При відсутності в кодовому векторі помилок на виході 10 пристрою в кінці n-циклу режиму декодування з'явиться сигнал логічної 1, а при наявності в кодовому векторі помилок - значення логічного 0 і робота пристрою далі продовжується в режимі локалізації помилок. При наявності в кодовому векторі помилок робота пристрою далі продовжується: перший перетворювач кодів 1 в (п+1)-му циклі переходить в режим локалізації помилок, а інші перетворювачі кодів 1 закінчують роботу в режимі декодування На вхід 4 пристрою в кожному циклі, починаючи з (п-И)-го циклу, поступають сигнали логічного 0. В режимі локалізації помилок і-й перетворювач кодів 1 призначений для виявлення першого можливого пакету помилок довжиною Zi= ('- 1 0 = 2-^f). З цією метою в і-му перетворювачі кодів 1 відбувається порівняння чергового стану своєї ЛПС 11 з відповідним і-м еталонним векторе ,., ром Л(