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

Реферат: UA 93798 U UA 93798 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до обчислювальної техніки і може бути використана в системах обробки, збереження та передачі дискретних даних. Відомий пристрій для виправлення двократних помилок в блоках передачі та збереження інформації, який містить вхідний регістр, перший і другий формувачі синдрому помилки, схему порівняння, регістр помилок, блок пам'яті помилок, блок корекції, групу інверторів з керуючим виходом, елемент АБО і тригер помилки корекції [А.С. СССР № 1173417, кл. G06F 11/08, бюл. № 30, 1985 р.]. Недоліком цього пристрою є низька коректуюча здатність та великі апаратурні затрати. Найбільш близьким по технічній суті до запропонованого є пристрій для локалізації пакетів помилок в (n,k)-кодах Боуза-Чоудхурі-Хоквінгема [патент України на винахід № 46078 М. кл., G06F 11/08, Н03М 13/15, Н03М 13/17, 15.05.2002, бюл. № 5 15.05.2002], який містить перетворювач кодів, блок формування вхідного вектора помилки, блок визначення параметрів пакетів помилок і блок синхронізації, вихід якого з'єднаний з входом синхронізації перетворювача кодів, перший інформаційний вхід, вхід керування і вхід початкового установлення якого під'єднані відповідно до інформаційного входу пристрою, до входу вибору режиму роботи і до входу початкового установлення пристрою, перша і друга m-розрядні або 2m-розрядні групи інформаційних виходів блока визначення параметрів пакетів помилок, m  log2 n , де [] означає округлення до цілого в більший бік, під'єднані відповідно до першої і до другої групи інформаційних виходів пристрою, вхід керування пристрою з'єднаний з першим входом керування блока синхронізації, вихід якого з'єднаний також з входом синхронізації блока формування вхідного вектора помилки, перший інформаційний вихід якого з'єднаний з інформаційним входом блока визначення параметрів пакетів помилок, інформаційний вихід якого під'єднаний до першого інформаційного виходу пристрою і до другого входу керування блока синхронізації, третій вхід керування якого під'єднаний до інформаційного виходу перетворювача кодів і до другого інформаційного виходу пристрою, вхід початкового установлення якого з'єднаний також з входом початкового установлення блока визначення параметрів пакетів помилок, з входом початкового установлення блока синхронізації та з першим входом початкового установлення блока формування вхідного вектора помилки, другий вхід початкового установлення і другий інформаційний вихід якого з'єднані відповідно з виходом керування блока визначення параметрів пакетів помилок і з другим інформаційним входом перетворювача кодів. Недоліком цього пристрою є можливість виявлення обмеженого типу помилок: тільки суцільних пакетів помилок. В основу корисної моделі поставлена задача створення пристрою для виправлення помилок в циклічних (n,k)-кодах, в якому за рахунок введення нових блоків та зв'язків досягається можливість виправлення чотирьох типів помилок: випадкових регулярних помилок, випадкових нерегулярних помилок, розріджених пакетів помилок і суцільних пакетів помилок, що призводить до розширення функціональних можливостей. Поставлена задача вирішується тим, що в пристрої для виправлення помилок в циклічних (n,k)-кодах, який складається з перетворювача кодів і блока синхронізації, вихід синхронізації якого з'єднаний з входом синхронізації перетворювача кодів, інформаційний вхід і інформаційний вихід якого під'єднані відповідно до інформаційного входу та першого інформаційного виходу пристрою, вхід початкового установлення якого з'єднаний з входами початкового установлення перетворювача кодів і блока синхронізації, введені блок виявлення регулярних випадкових помилок, блок виявлення нерегулярних випадкових помилок, блок виявлення розріджених пакетів помилок, блок виявлення суцільних пакетів помилок, блок формування вектора помилки і блок виправлення помилок, n-розрядна група входів якого з'єднана з n-розрядною групою виходів блока формування вектора помилки, а виходи під'єднані до n-розрядної групи інформаційних виходів пристрою, вхід керування якого з'єднаний з входом керування перетворювача кодів і входом керування блока синхронізації, вихід синхронізації якого з'єднаний також з входом синхронізації блока 5 виявлення нерегулярних випадкових помилок і блока формування вектора помилки, керуючий вхід якого з'єднаний з інформаційним виходом перетворювача кодів, r-розрядна група інформаційних виходів якого з'єднана з rрозрядною групою інформаційних входів блока виявлення регулярних випадкових помилок, блока виявлення розріджених пакетів помилок, блока виявлення суцільних пакетів помилок і блока виявлення нерегулярних випадкових помилок, виходи яких з'єднані відповідно з першим, другим, третім і четвертим інформаційними входами блока формування вектора помилки, перша r-розрядна та друга n-розрядна групи інформаційних входів якого з'єднані відповідно з rрозрядною групою інформаційних виходів перетворювача кодів та з n-розрядною групою інформаційних виходів блока виявлення нерегулярних випадкових помилок, причому виходи 1 UA 93798 U 5 10 15 20 25 30 35 40 45 50 55 60 блока виявлення регулярних випадкових помилок, блока виявлення розріджених пакетів помилок, блока виявлення суцільних пакетів помилок, блока виявлення нерегулярних випадкових помилок і блока формування вектора помилки під'єднані відповідно до другого, третього, четвертого, п'ятого і шостого інформаційних виходів пристрою. На фіг. 1 представлена функціональна схема пристрою; на фіг. 2 - функціональна схема перетворювача кодів; на фіг. 3 - функціональна схема блока виявлення регулярних випадкових помилок; на фіг. 4 - функціональна схема блока виявлення нерегулярних випадкових помилок; на фіг. 5 - функціональна схема блока виявлення розріджених пакетів помилок; на фіг. 6 функціональна схема блока виявлення суцільних пакетів помилок; на фіг. 7 - функціональна схема блока формування вектора помилки; на фіг. 8 - функціональна схема блока виправлення помилок, на фіг. 9 - функціональна схема можливої реалізації лінійної послідовної схеми перетворювача кодів. Пристрій для виправлення в циклічних (n,k)-кодах помилок (фіг. 1) містить перетворювач кодів 1, блок 2 виявлення регулярних випадкових помилок, блок 3 виявлення розріджених пакетів помилок, блок 4 виявлення суцільних пакетів помилок, блок 5 виявлення нерегулярних випадкових помилок, блок 6 формування вектора помилки, блок 7 виправлення помилок і блок 8 синхронізації. Вихід синхронізації блока 8 синхронізації з'єднаний з входами синхронізації блока 5 виявлення нерегулярних випадкових помилок, блока 6 формування вектора помилки і перетворювача кодів 1, інформаційний вхід і інформаційний вихід якого під'єднані відповідно до інформаційного входу 9 та першого інформаційного виходу 13 пристрою, вхід 10 початкового установлення якого з'єднаний з входами початкового установлення перетворювача кодів 1 і блока синхронізації 8. n-розрядна група входів блока 7 виправлення помилок з'єднані з nрозрядною групою виходів блока 6 формування вектора помилки, а виходи під'єднані до nрозрядної групи 12 інформаційних виходів пристрою, вхід 11 керування якого з'єднаний з входом керування перетворювача кодів 1 і з входом керування блока синхронізації 8, вихід синхронізації якого з'єднаний також з входом синхронізації блока формування вектора помилки. Вхід керування блока 6 формування вектора помилки з'єднаний з інформаційним виходом перетворювача кодів 1, r-розрядна група інформаційних виходів якого з'єднана з r-розрядною групою інформаційних входів блока 2 виявлення регулярних випадкових помилок, блока 3 виявлення розріджених пакетів помилок, блока 4 виявлення суцільних пакетів помилок і блока 5 виявлення нерегулярних випадкових помилок, виходи яких з'єднані відповідно з першим, другим, третім і четвертим інформаційними входами блока 6 формування вектора помилки, перша r-розрядна та друга n-розрядна групи інформаційних входів якого з'єднані відповідно з rрозрядною групою інформаційних виходів перетворювача кодів 1 та з n-розрядною групою інформаційних виходів блока 5 виявлення нерегулярних випадкових помилок. Виходи блока 2 виявлення регулярних випадкових помилок, блока 3 виявлення розріджених пакетів помилок, блока 4 виявлення суцільних пакетів помилок, блока 5 виявлення нерегулярних випадкових помилок і блока 6 формування вектора помилки під'єднані відповідно до другого 14, третього 15, четвертого 16, п'ятого 17 і шостого 18 інформаційних виходів пристрою. Перетворювач кодів 1 (фіг. 2) містить лінійну послідовну схему (ЛПС) 19, лічильний тригер 20, елемент 1-АБО 21 і елемент АБО 22, вихід якого з'єднаний з інформаційним виходом перетворювача кодів і під'єднаний до першого інформаційного виходу 13 пристрою, вхід 11 керування якого з'єднаний з лічильним входом тригера 20, прямий та інверсний виходи якого з'єднані відповідно з першим та другим входами елемента І-АБО 21, третій вхід якого з'єднаний з інформаційним входом перетворювача кодів і під'єднаний до інформаційного входу 9 пристрою, вхід 10 початкового установлення якого з'єднаний з R-входом тригера 20 і з входом початкового установлення ЛПС 19, r-розрядна (r = n-k) група інформаційних виходів якої під'єднана до групи інформаційних виходів 24 перетворювача кодів і з'єднана з входами елемента АБО 22, а вхід синхронізації та інформаційний вхід з'єднані відповідно з входом 23 синхронізації перетворювача кодів і з виходом елемента І-АБО 21, на четвертий вхід якого подається константа логічного 0. Блок 2 виявлення регулярних випадкових помилок (фіг. 3) містить пороговий елемент 25 і елемент І 26. r-розрядна група інформаційних входів 27 блока 2 з'єднана з входами порогового елемента 25, вихід якого з'єднаний з першим входом елемента 126, вихід якого з'єднаний з інформаційним виходом блока 2 і під'єднаний до другого інформаційного виходу 14 пристрою. Другий вхід елемента І 26 з'єднаний з першим входом г-розрядної групи інформаційних входів 27 блока 2. Блок 3 виявлення розріджених пакетів помилок (фіг. 4) містить елемент АБО-НІ 28 і елемент І 29, вихід якого під'єднаний до третього інформаційного виходу 15 пристрою і з'єднаний з r виходом блока, група останніх /2-розрядних входів із r-розрядної групи інформаційних входів 30 2 UA 93798 U 5 10 15 20 25 30 35 40 45 50 55 якого з'єднана з входами АБО-НІ 28, вихід якого з'єднаний з першим входом елемента І 29, другий вхід якого з'єднаний з першим входом r-розрядної групи інформаційних входів 30 блока. Блок 4 виявлення суцільних пакетів помилок (фіг. 5) містить дешифратор 31 і елемент АБО 32, вихід якого під'єднаний до четвертого інформаційного виходу 16 пристрою і з'єднаний з виходом блока, r-розрядна група інформаційних входів 33 якого з'єднана з входами r дешифратора 31, /2-розрядна група виходів якого з'єднана з входами елемента АБО 32. Блок 5 виявлення нерегулярних випадкових помилок (фіг. 6) містить вузол пам’яті 34, генератор адрес 35 і схему порівняння 36, перша r-розрядна група входів якої з'єднана з rрозрядною групою інформаційних входів 37 блока, вхід синхронізації 38 якого з'єднаний з входом генератора адрес 35, m-розрядна група виходів якого з'єднана з адресними входами вузла пам'яті 34, перша r-розрядна група і друга n-розрядна група виходів якого з'єднані відповідно з r-розрядною групою інформаційних виходів 39 блока і з другою r-розрядною групою інформаційних входів схеми порівняння 36, вихід якої з'єднаний з виходом блока і під'єднаний до п'ятого інформаційного виходу 17 пристрою. Блок 6 формування вектора помилки (фіг. 7) містить n-розрядний регістр зсуву 40, реверсивний лічильник 41, перший RS-тригер 42, другий RS-тригер 43, мультиплексор 44, перший елемент АБО 45, другий елемент АБО 46, третій елемент АБО 47, перший елемент І 48, другий елемент І 49, третій елемент І 50, перший вхід якого з'єднаний з входом 53 синхронізації блока, перший, другий, третій інформаційні входи якого під'єднані відповідно до другого 14, третього 15, четвертого 16 виходів пристрою і з'єднані зі входами першого елемента АБО 45, вихід якого з'єднаний з першим входом другого елемента АБО 46 та з першим керуючим входом мультиплексора 44, n-розрядна група виходів якого з'єднана з інформаційними входами регістра зсуву 40, n-розрядна група виходів якого з'єднана з n-розрядною групою виходів 55 блока 6, четвертий інформаційний вхід якого з'єднаний з другим керуючим входом мультиплексора 44 та з другим входом другого елемента АБО 46, вихід якого з'єднаний з входом запису регістра зсуву 40 та з S-входом першого RS-тригера 42, прямий та інверсний виходи якого з'єднані з першими входами першого елемента І 48 та другого елемента І 49, виходи яких з'єднані відповідно з входом віднімання і входом додавання реверсивного лічильника 41, вихід переносу якого з'єднаний з виходом блока, під'єднаний до шостого інформаційного виходу 18 пристрою та з'єднаний з першим входом третього елемента АБО 47, вихід якого з'єднаний з R-входом другого RS-тригера 43, прямий вихід якого з'єднаний з другим входом третього елемента І 50, вихід якого з'єднаний з другими входами першого елемента І 48 та другого елемента 1 49. Вхід 10 початкового установлення пристрою з'єднаний з входом початкового установлення блока та з другим входом третього елемента АБО 47, з R-входом першого RS-тригера 42, з входами початкового установлення регістра зсуву 40 і реверсивного лічильника 41, вхід віднімання якого з'єднаний також з входом зсуву регістра зсуву 40. Перша rрозрядна група інформаційних входів 51 та друга n-розрядна група інформаційних входів 52 блока 6 з'єднані відповідно з першою та другою групами входів мультиплексора 44. Вхід 53 керування блока 6 з'єднаний з S-входом другого RS-тригера 43. Блок 7 виправлення помилок (фіг. 8) містить регістр зсуву 56 і суматор по модулю два 57, перша n-розрядна групу входів якого з'єднана з n-розрядною групою 58 входів блока 7, вхід якого під'єднаний до інформаційного входу 9 пристрою і з'єднаний з інформаційним входом регістра зсуву 56, n-розрядна групи виходів якого з'єднана з другою n-розрядною групою входів суматора по модулю два 57, n-розрядна група виходів якого під'єднана до n-розрядної групи інформаційних виходів 12 пристрою. ЛПС 19 (варіант реалізації при r =8) перетворювача кодів 1 (фіг. 9) містить суматор 59 по модулю два, D-тригери 60-67, входи синхронізації яких з'єднані з входом 24 синхронізації перетворювача кодів 1, а установочні входи з'єднані з входом початкового установлення перетворювача кодів 1 і під'єднані до входу 10 пристрою. D-вхід D-тригера 60 з'єднаний з виходом суматора 59 по модулю два, перший вхід якого з'єднаний з інформаційним входом 68 ЛПС 19. Виходи всіх D-тригерів 60-67 утворюють 8-розрядну групу інформаційних виходів ЛПС 19, причому прямий вихід (i-1)-го D-тригера з'єднаний з D-входом і-го D-тригера (i = 28). Виходи D-тригера 60, D-тригера 61, D-тригера 63, D-тригера 67 з'єднані також з іншими чотирма входами суматора 59 по модулю два. Пристрій працює наступним чином. Є два режими роботи пристрою: - режим декодування; - режим виправлення помилок. Теоретичною основою декодування циклічних кодів є математичний апарат ЛПС. 3 UA 93798 U В перетворювачі кодів 1 апаратно реалізована двійкова ЛПС, яка в дискретні моменти часу t описується лінійною функцією переходів (стану): St  1  A  St   B  Ut  , (1) 5 та лінійною функцією виходів: Yt   St  , де A  aij rr , B  bi r - характеристичні матриці ЛПС, S  s j , U  ui l, Y  y j r 10 m - відповідно вектори станів, вхідний та вихідний. У формулі (1) символи '+' та '' позначають відповідно операції додавання та множення по модулю два. Можливі два варіанта матриць A та B , які можуть бути реалізовані апаратно в перетворювачі кодів 1: 0 1 0  0 0 0 0 1  A     0 0 0  , B   (2)  1 0  gr 1 1 0 0 g0 g1 g2 0 0  0 g0 1 1 0  0 g1 0 A 0 1  0     0 15 0  1 g2 , B  0 . (3)   gr 1 0 Елементи останнього рядка матриці A в (2) або останнього стовпчика в (3) представляють собою коефіцієнти погоджувального багаточлена gx циклічного коду: gx   g0  g1x  g2x2    gr 2xr 2  gr 1xr 1 . Під дією t-розрядного вхідного вектора U  u1, u2,, ut  20 25 30 35 40 45 який надходить на вхід ЛПС, відбувається послідовна зміна її внутрішніх станів S  s1, s2,, sn , для обчислення яких, замість формул (1), зручно користуватись наступними співвідношеннями: St  1  A  St   B , якщо ut   1, St  1  A  St  , якщо ut   0 , На стороні передавача на основі k-розрядного інформаційного вектора Ix  обчислюється nрозрядний кодовий вектор Zx  , який далі передається по каналу зв'язку. Для обчислення кодового вектора Zx  використовується k-розрядна ЛПС з характеристичними матрицями (2) або (3). На стороні приймача в режимі декодування перевіряється вірність отриманого з каналу зв'язку кодового вектора Zx  за допомогою ЛПС такої ж структури, що і на стороні передавача. Перед початком роботи на вхід 10 пристрою надходить сигнал, по якому всі блоки установлюються в початковий стан. Робота пристрою в режимі декодування починається після приходу керуючого сигналу на вхід 11. Тривалість роботи пристрою в режимі декодування дорівнює n тактів, які складають один цикл. В кожному такті роботи блок 8 формує один синхроімпульс, який надходить на входи перетворювача кодів 1 і блока 6. Протягом всього режиму декодування на вхід 9 пристрою надходить n-розрядний кодовий вектор Zx  . Режим декодування завершується з отриманням одного із трьох результатів, які свідчать, про те, що: 1) в переданому кодовому векторі відсутні помилки в межах коректуючої здатності коду, 2) в переданому кодовому векторі присутні помилки і їх види та параметри можуть бути відразу визначені, 3) в переданому кодовому векторі присутні помилки, але і їх види та параметри не можуть бути відразу визначені. З використанням математичного апарату ЛПС вказані результати декодування визначаються наступним чином. 4 UA 93798 U 5 10 15 На початку режиму декодування ЛПС в пристрої встановлюється в нульовий початковий стан S0  і на її входи подається кодовий вектор Zx  . Якщо тоді через n тактів часу ЛПС знову повернеться в стан S0  , то це буде свідчити про відсутність помилок в кодовому векторі Zx  . В цьому випадку на другому інформаційному виході 13 пристрої буде сигнал логічного нуля. При наявності помилок в кодовому векторі, який позначимо як Serr x  , ЛПС через n тактів часу перейде в ненульовий стан, який позначимо як синдром помилки Serr n . Тоді на другому інформаційному виході 13 пристрою з'явиться сигнал логічної одиниці. В пристрої виявляються помилки чотирьох видів: - випадкові регулярні, - випадкові нерегулярні, - розріджені пакети помилок, - суцільні пакети помилок. Параметри вказаних помилок, які можна виявити і виправити, залежать від мінімальної кодової відстані dmin вибраного циклічного коду. Випадковими регулярними помилками кратності  в кодовому векторі Serr x  вважається сукупність  помилок, яка міститься в циклічному інтервалі довжини r і перша з яких розташована в першій позиції цього інтервалу (   min , min  20 dmin  1 ). 2 Випадковими нерегулярними помилками кратності  в кодовому векторі Serr x  вважається сукупність  помилок в межах всього вектора. Циклічним розрідженим пакетом помилок довжини b в кодовому векторі Serr x  вважається r 2 сукупність помилок довжини b , яка міститься в циклічному інтервалі довжини ( ) і перша і остання з яких розташовані в межах цього інтервалу, а між ними з можуть бути правильні 25 r 2 символи ( b  ) . Циклічним суцільним пакетом помилок довжини f в кодовому векторі Serr x  вважається сукупність помилок довжини ту, яка міститься в циклічному інтервалі довжини f , в якому всі 30 35 символи є неправильними ( f  r ) . Факт наявності вказаних видів помилок визначаються на основі аналізу синдрому помилки Serr n за допомогою блоків 2, 3, 4 і 5. За допомогою блока 6 формується n-розрядний вектор помилки, який містить ненульові (одиничні) значення в тих розрядах, які відповідають помилковим позиціям в кодовому векторі Serr x  . Якщо відразу після закінчення режиму декодування за допомогою блоків 2, 3 і 4 виявляється факт наявності помилки відповідного типу, тоді з'явиться сигнал логічної одиниці на відповідних інформаційних виходах 14, 15, 16 або 17 і в блоці 6 формується n-розрядний фактичний вектор Ex  цієї помилки, який дорівнює сумі по модулю два n-розрядного нульового вектора Ox  і зсунутого на k розрядів (в сторону старших розрядів) вектора Srs n : err Ex   Ox   Srs n . (4) err Вектор Srs n відрізняється від синдрома помилки Serr n реверсним розташуванням err 40 45 розрядів: і-й розряд i  1 r  вектора Srs n дорівнює (r-i+1)-му розряду синдрома помилки err Serr n . За допомогою блока 5 виявляється факт наявності випадкової нерегулярної помилки і формується n-розрядний фактичний вектор En x  цієї помилки. На наступному такті роботи пристрою знайдені помилки в векторі Zerr x  в блоці 7 виправляються: Zx   Zerr x   Ex  (5) або Zx   Zerr x   Enx  . (6) Далі кодовий вектор Zx  без помилок видається з першого інформаційного виходу 12. 5 UA 93798 U Якщо після завершення режиму декодування отримано ненульовий синдром помилки Serr n , а вид і параметри помилки не можуть бути відразу визначені, тоді пристрій переходить в 5 10 режим виправлення помилок. На першому етапі режиму виправлення помилок, який складається з двох етапів і може тривати від одного до (n-1) тактів, за допомогою блоків 2, 3, 4 і 5 перевіряється можлива наявність відповідної помилки. Якщо на і -му такті першого етапу режиму виправлення помилок ЛПС 19 перейде в стан Si і в блоках 2, 3 або 4 виявлена відповідна помилка, тоді на першому етапі в блоці 6 буде сформовано базовий вектор помилки Eb x   Ox   Srs i . (7) Вектор Srs i відрізняється від стану Si реверсним розташуванням розрядів: і-й розряд вектора Srs i дорівнює (r-i+1)-му розряду синдрома помилки Serr n За допомогою блока 5 на першому етапі виявляється факт наявності випадкової  нерегулярної помилки і формується n-розрядний базовий вектор Ebn  x  цієї помилки. i  1 r  15 На другому етапі режиму виправлення помилок в блоці 6 на основі базових векторів Eb x   або Ebn  x  помилок сформований фактичний вектор відповідної помилки: Ex  або En x  . Тривалість другого етапу така ж, як першого етапу. Далі в блоці 7 виявлена помилка в векторі Zerr x  виправляється, згідно з (5) або (6), і з 20 25 першого інформаційного виходу 12 видається кодовий вектор Zx  без помилок. Перетворювач кодів 1 працює таким чином. Перед початком режиму декодування на вхід початкового установлення перетворювача кодів 1 з входу 10 пристрою надходить сигнал логічної 1, який установлює ЛПС 19 в нульовий стан S(0) і лічильний тригер 20 в нульовий стан. Далі на вхід керування 11 надходить сигнал логічної одиниці, який встановлює тригер 20 в одиничний стан. В режимі декодування протягом перших п циклів з входу 9 пристрою черезелемент І-АБО 21 на вхід ЛПС 19 надходить кодовий вектор Zx  , під дією якого ЛПС з початкового нульового стану S0  буде періодично переходити в інші стани, згідно з функцією переходів: A  St   B, якщо z t  1 . (8) St  1    A  St , якщо zt  0 де zt - значення t-го розряду кодового вектора Zx  в момент часу t ; 30 t  0,12,, n  1 ; , A і B - матриці ЛПС, які визначають її структуру. Після закінчення режиму декодування за допомогою ЛПС 19 буде сформовано синдром помилки Serr n . При відсутності помилок в кодовому векторі буде отримано нульовий синдром 35 40 45 помилки: Serr n  S0 . За допомогою елемента АБО 22 буде встановлено значення логічного нуля на інформаційному виході перетворювача кодів 1 і, відповідно, на першому інформаційному виході 13 пристрою. В режимі виправлення помилок на вхід керування 11 надходить сигнал логічної 1, який по лічильному входу знову встановлює тригер 20 в нульовий стан. В результаті через елемент ІАБО 21 на вхід ЛПС 19 надходять нульові сигнали, під дією якого ЛПС 19 з початкового ненульового стану Serr n буде періодично переходити в інші стани, згідно з функцією переходів St  1  A  St  . (9) Значення станів ЛПС 19 на кожному такті будуть передаватись на r-розрядну групу інформаційних виходів 24 перетворювача кодів 1. Блок 2 працює таким чином. На r-розрядну групу інформаційних входів 27 блока 2 надходить синдром помилки Serr n . Ознакою наявності в кодовому векторі Zerr x  випадкової регулярної помилки кратності  є наявність в синдромі помилки Serr n  одиниць, одна з яких розташована в першому розряді Serr n . На виході порогового елемента 25 з'являється логічна одиниця, якщо на його вхід 50 надходить синдром помилки Serr n з кількістю одиниць, що не перевищує min . Для виділення  одиниць необхідно мати r-входовий пороговий елемент, який реалізує булеву функцію f xl, , xr  : 6 UA 93798 U , 1 якщо   min . f xl, , xr    0, якщо   min  5 Якщо при цьому одна одиниця буде розташована в першому розряді Serr n , тоді з'являється логічна одиниця на інформаційному виході блока 2 і, відповідно, на другому інформаційному виході 14 пристрою. Блок 3 працює таким чином. На r-розрядну групу інформаційних входів 30 блока 3 надходить синдром помилки Serr n . Ознакою наявності в кодовому векторі Zerr x  циклічного розрідженого пакета помилок довжини r b є наявність в синдромі помилки Serr n в перших /2-розрядах b одиниць, одна з яких розташована в першому розряді Serr n . На виході елемента АБО-НІ 28 з'являється логічна 10 15 r одиниця, якщо на його вхід надходить синдром помилки Serr n з r 2 нулями в останніх /2розрядах. Якщо при цьому одна одиниця буде розташована в першому розряді Serr n , тоді з'являється логічна одиниця на інформаційному виході блока 3 і, відповідно, на третьому інформаційному виході 15 пристрою. Блок 4 працює таким чином. На r-розрядну групу інформаційних входів 33 блока 4 надходить синдром помилки Serr n . Ознакою наявності в кодовому векторі Zerr x  циклічного суцільного пакета помилок довжини  c , є наявність в синдромі помилки Serr n  c одиниць, які розташовані суцільно c  r  , починаючи з першого розряду: r 1 0 0  0 0 1 1 0  0 0  1 1 1  1 1. 20 c  r , 2 Якщо суцільний пакет помилок має довжину тоді він може бути також ідентифікований як розріджений пакет помилок і виявлений за допомогою блока 3. З метою економії апаратних засобів в блоці 4 виявляються лише суцільні пакети помилок довжини c , синдроми помилки Serr n яких містять c r 2   c r  r одиниць і розпочинаються з ( /2+1)-го розряду: r 25 2 1 1 1  r 2 (10) 1 1 0 0  0 1 1 1  1 1 1  30 1 1 1 0  0  1 1 1 1  1. При наявності синдроми помилки Serr n виду (10) на одному із виходів дешифратора 31 з'являється логічна одиниця, яка далі передається на інформаційний вихід блока 4 і, відповідно, на четвертий інформаційний вихід 16 пристрою. Блок 5 працює таким чином.  Перед початком декодування у вузол пам'яті 34 записуються w базових векторів Ebn  x  випадкових нерегулярних помилок кратності  та відповідні їм базові синдроми помилки Sb n  . err В режимі декодування на r-розрядну групу інформаційних входів 37 блока 5 надходить фактичний синдром помилки Serr n . Ознакою наявності в кодовому векторі Zerr x  випадкової 35 нерегулярної помилки кратності  є збіг між Serr n та Sb n  , що виявляється за допомогою err схеми порівняння 36. Протягом одного такту роботи пристрою в режимі виправлення помилок генератор адрес 35  формує w адрес комірок вузла пам'яті 34, з яких зчитується w базових векторів Ebn  x  та відповідні їм синдроми помилки Sb n  . Якщо буде виявленозбіг між Serr n та одним із Sb n  , err err тоді на n-розрядну групу інформаційних виходів 39 блока 5 подається з вузла пам'яті 34 7 UA 93798 U  відповідний базовий вектор Ebn  x  і на п'ятий інформаційний вихід 17 пристрою подається 5 10 15 20 25 30 35 40 45 50 55 сигнал логічної одиниці. Блок 6 працює таким чином. Після закінчення режиму декодування на вхід початкового установлення блока надходить сигнал, який встановлює в нульовий стан регістр зсуву 40, реверсивний лічильник 41, перший RS-тригер 42 і другий RS-тригер 43. Якщо після закінчення режиму декодування відразу буде виявлено помилку, тоді на один із інформаційних входів блока 6 прийде відповідний сигнал помилки, який через перший елемент АБО 45 і другий елемент АБО 46 дозволить здійснити запис в регістр зсуву 40 вектора помилки, який надходить з виходів мультиплексора 44. Якщо сигнал помилки прийде на перший, другий або третій інформаційний вхід блока 6, тоді відповідний синдром помилки Serr n (випадкової регулярної помилки, розрідженого або суцільного пакета помилок) з першої r-розрядної групи інформаційних входів 51 через мультиплексор 44 записується в n-розрядний регістр зсуву 41, починаючи з n-го розряду. В результаті в регістр зсуву 41 буде сформовано n-розрядний фактичний вектор відповідної помилки Ex  , згідно з (4). Якщо сигнал помилки прийде на четвертий інформаційний вхід блока 6, тоді n-розрядний вектор En x  випадкової нерегулярної помилки з другої n-розрядної групи інформаційних входів 52 через мультиплексор 44 записується в регістр зсуву 41. Далі вектор помилок Ex  або En x  передається на n-розрядну групу інформаційних виходів 55 блока 6. Якщо після закінчення режиму декодування не буде відразу виявлено помилку, тоді розпочинається перший етап режиму виправлення помилок приходом одиничного сигналу на вхід 53 керування, який встановлює другий RS-тригер 43 в одиничний стан. В результаті з входу 54 синхронізації блока 6 кожного такту надходять синхросигнали, які через третій елемент І 50 та через другий елемент І 49 надходять на вхід додавання реверсивного лічильника 41, збільшуючи його вміст на одиницю. Якщо на і-му такті режиму виправлення помилок буде виявлено помилку одного із чотирьох видів, тоді надходить відповідний сигнал на один із інформаційний входів блока 6, який встановить RS-тригер 42 в одиничний стан, що буде означати перехід до другого етапу режиму виправлення помилок. Одночасно здійснюється запис в регістр зсуву 40 даних, що надходять з виходів мультиплексора 44. В результаті в регістрі зсуву 40 буде сформовано базовий вектор  помилки Eb x  , згідно з (7), або буде записано базовий вектор помилки Ebn  x  . Зміна стану RS-тригера 42 призводить до того, що синхросигнали з входу 54 надходять через третій елемент І 50 та через перший елемент І 48 на вхід віднімання реверсивного лічильника 41 та на вхід зсуву регістра зсуву 40. В результаті на кожному наступному такті роботи пристрою вміст реверсивного лічильника 41 зменшується на одиницю, а вміст регістра зсуву 40 циклічно зсовується на один розряд в сторону старших розрядів. При досягнення в реверсивному лічильнику 41 через і тактів нульового стану в регістрі зсуву 40 буде сформовано фактичний вектор відповідної помилки: Ex  або En x  . Далі цей вектор помилки передається на n-розрядну групу інформаційних виходів 55 блока 6. Одночасно з виходу переносу реверсивного лічильника 41 на шостий інформаційний вихід 18 пристрою передається сигнал про закінчення режиму виправлення помилок. Блок 7 працює таким чином. В режимі декодування в регістр 55 з інформаційний входу 9 пристрою послідовно записується кодовий вектор Zx  . При відсутності помилок далі він послідовно передається на перший інформаційний вихід 12 пристрою. При наявності помилок в кодовому векторі Zerr x  на другий інформаційний вхід 57 блока 7 надходить фактичний вектор відповідної помилки. За допомогою сумматора 56 виконується порозрядна операція додавання по модулю два кодового вектора Zerr x  з помилкою та фактичного вектора відповідної помилки, згідно з (5) або (6). В результаті на перший інформаційний вихід 12 пристрою передається виправлений кодовий вектор Zx  . Робота перетворювача кодів 1 та блока 6 виправлення помилок синхронізується синхроімпульсами, які кожного такту формуються в блоці 8 синхронізації. Розглянемо роботу ЛПС 19, апаратна реалізація якої задається матрицями A і B типу (2) та (3). При апаратній реалізації ЛПС 19 матриця А задає структуру зв'язків між елементами пам'яті (тригерами), а матриця B - структуру вхідних зв'язків. Якщо матриці A і B мають вигляд (2), 8 UA 93798 U 5 тоді ЛПС 19 має вигляд n-розрядного регістра зсуву з одним багатовходовим суматором по модулю 2 на його вході. Якщо матриці A і B мають вигляд (3), тоді ЛПС 19 має вигляд nрозрядного регістра зсуву з кількома суматорами по модулю 2, які розташовані між окремими тригерами. Елементи ar j останнього рядка матриці A типу (2), які рівні 1, показують наявність зв'язку між виходом j-го D-тригера і входом суматора по модулю 2, вихід якого з'єднаний з входом n-го D -тригера. Елементи a j r останнього стовпчика матриці A типу (3), які рівні 1, показують 10 наявність зв'язку між виходом n-го D-тригера і першим входом суматора по модулю 2, другий вхід якого з'єднаний з виходом (j-1)-го D-тригера, а вихід - з входом j-го D-тригера. Для обох типів матриці A значення інших елементів ai j  1 ( ai j  0 ) показують наявність (відсутність) зв'язку між виходом j-го D-тригера і входом i-го D-тригера. Для одновходової ЛПС 19 значення елемента bi  1 ( bi  0) матриці B показує наявність (відсутність) зв'язку інформаційного входу 15 ЛПС 19 з входом i-го тригера через суматор по модулю 2. На фіг. 9 показана 8-розрядна ЛПС 19, яка характеристичніих матриць A і B : 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 ,B  0 0 1 1 0 0 0 1 0 1 1 25 реалізацією таких 0 0 A 0 0 0 20 апаратною 0 0 0 0 0 1 0 0 0 0 є 0 . (11) 0 0 0 1 Матриці (11) відповідають (15,7)-коду БЧХ з погоджувальним багаточленом gx   1 x 4  x6  x7  x8 . Ця ЛПС 19 працює наступним чином. Перед початком роботи пристрою сигналом, який надходить на вхід 10 пристрою, D-тригери 60-67 установлюються в нульовий стан. В режимах декодування та виправлення помилок під дією сигналів, які приходять кожного такту на вхід 24 синхронізації та на інформаційний вхід 68 ЛПС 19, D-тригери 60-67 будуть почергово змінювати свій стан. Значення виходів D-тригерів 6067 в будь-якому такті роботи представляють собою 8-розрядний код внутрішнього стану ЛПС 19, який відображається на групі інформаційних виходів 25. Розглянемо на прикладі виявлення помилок в (15,7)-коді БЧХ з характеристичними матрицями (9). Нехай було отримано такий кодовий вектор: Zerr x   1111110111 01000 . (12) Згідно з (8), синдром помилки Serr n є значенням стану S(15) ЛПС при подачі на її входи 30 кодового вектора (10): z1  1 z2  1 , z15  0 , , S0   00000000 , S1  A  S0   B  z1  00000000 10000000  10000000 , S2  A  S1  B  z2  01000000 10000000  11000000 , S3   A  S2  B  z3  01100000 10000000  11100000 , S4   A  S3   B  z 4  01110000 10000000  11110000 , S5   A  S4   B  z5  01111000 10000000  11111000 , S6   A  S5   B  z6  01111100 10000000  11111100 , S7   A  S6   01111110 , S8   A  S7   B  z8  00111111 10000000  10111111 , S9   A  S8   B  z9  11010100 10000000  01010100 , S10  A  S9   B  z10  00101010 10000000  10101010 , S11  A  S10  01010101 , S12  A  S11  B  z12  10100001 10000000  00100001 , 9 UA 93798 U S13  A  S12  10011011 , S14  A  S13  11000110 , S15  A  S14  01100011. 5 В результаті декодування отриманого кодового вектора (12) отримано синдром помилок Serr 15  S15  011001011. (13) Синдром помилок (13) є ненульовим, що свідчить про наявність помилок в отриманому в кодовому векторі (12). Однак синдром помилок (13) не містить ознак жодної із можливих помилок. Оскільки вид і параметри помилки не можуть бути відразу визначені, тоді пристрій переходить в режим виправлення помилок. Згідно з (9), обчислюються нові значення станів ЛПС 19 при подачі на її входи нульових вхідних сигналів: S1  A  Serr 15  10111010 , 10 S2  A  S1  01011101 , S3   A  S2  10100101 , S4   A  S3   11011001 , S5   A  S4   11100111 , S6   A  S5   11111000. 15 Стан S6  містить ознаку наявності в кодовому векторі (12) суцільного пакета помилок довжини 5. Ця ознака буде сформована в блоці 4 і відповідний сигнал з'явиться на шостому такті роботи пристрою на першому етапі режиму виправлення помилок на виході 16. В реверсивний лічильник 41 буде записано число 6, а в регістр зсуву 40 блока 6 буде записано базовий вектор помилки, згідно з (7): Eb x  0000000000 11111. 20 Далі пристрій переходить до другого етапу режиму виправлення помилок. Протягом шести наступних тактів вміст реверсивного лічильника 41 зменшується на одиницю, а вміст регістра зсуву 40 циклічно зсовується на один розряд в сторону старших розрядів: 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1, 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1, 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1, 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1, 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0, 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0. 25 30 35 40 45 В результаті буде сформовано фактичний вектор відповідної помилки: Ex  0111110000 00000 . Далі в блоці 7 відбувається виправлення кодового вектора (12), згідно з (5). В результаті буде отримано кодовий вектор без помилок: Zx  Zerr x  Ex   1000000111 01000 . Перевагою запропонованого пристрою в порівнянні з відомим пристроєм є здатність одночасного виявлення та виправлення більш широкого типу помилок: випадкових регулярних помилок, випадкових нерегулярних помилок, розріджених пакетів помилок та суцільних пакетів помилок. Це дає можливість практичного використання запропонованого пристрою в різноманітних каналах зв'язку, в яких швидко змінюються характеристики каналу. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 1. Пристрій для виправлення помилок в циклічних (n, k)-кодах, який складається з перетворювача кодів і блока синхронізації, вихід синхронізації якого з'єднаний з входом синхронізації перетворювача кодів, інформаційний вхід і інформаційний вихід якого під'єднані відповідно до інформаційного входу та першого інформаційного виходу пристрою, вхід початкового установлення якого з'єднаний з входами початкового установлення перетворювача кодів і блока синхронізації, який відрізняється тим, що в нього введені блок виявлення регулярних випадкових помилок, блок виявлення нерегулярних випадкових помилок, блок виявлення розріджених пакетів помилок, блок виявлення суцільних пакетів помилок, блок формування вектора помилки і блок виправлення помилок, n-розрядна група входів якого 10 UA 93798 U 5 10 15 20 25 30 35 40 45 50 55 60 з'єднана з n-розрядною групою виходів блока формування вектора помилки, а виходи під'єднані до n-розрядної групи інформаційних виходів пристрою, вхід керування якого з'єднаний з входом керування перетворювача кодів і входом керування блока синхронізації, вихід синхронізації якого з'єднаний також з входом синхронізації блока виявлення нерегулярних випадкових помилок і блока формування вектора помилки, керуючий вхід якого з'єднаний з інформаційним виходом перетворювача кодів, r-розрядна група інформаційних виходів якого з'єднана з rрозрядною групою інформаційних входів блока виявлення регулярних випадкових помилок, блока виявлення розріджених пакетів помилок, блока виявлення суцільних пакетів помилок і блока виявлення нерегулярних випадкових помилок, виходи яких з'єднані відповідно з першим, другим, третім і четвертим інформаційними входами блока формування вектора помилки, перша r-розрядна та друга r-розрядна групи інформаційних входів якого з'єднані відповідно з rрозрядною групою інформаційних виходів перетворювача кодів та з n-розрядною групою інформаційних виходів блока виявлення нерегулярних випадкових помилок, причому виходи блока виявлення регулярних випадкових помилок, блока виявлення розріджених пакетів помилок, блока виявлення суцільних пакетів помилок, блока виявлення нерегулярних випадкових помилок і блока формування вектора помилки під'єднані відповідно до другого, третього, четвертого, п'ятого і шостого інформаційних виходів пристрою. 2. Пристрій за п. 1, який відрізняється тим, що перетворювач кодів містить лінійну послідовну схему (ЛПС), лічильний тригер, елемент І-АБО і елемент АБО, вихід якого з'єднаний з інформаційним виходом перетворювача кодів і під'єднаний до першого інформаційного виходу пристрою, вхід керування якого з'єднаний з лічильним входом тригера, прямий та інверсний виходи якого з'єднані відповідно з першим та другим входами елемента І-АБО, третій вхід якого з'єднаний з інформаційним входом перетворювача кодів і під'єднаний до інформаційного входу пристрою, вхід початкового установлення якого з'єднаний з R-входом тригера і з входом початкового установлення ЛПС, r-розрядна (r = n-k) група інформаційних виходів якої під'єднана до групи інформаційних виходів перетворювача кодів і з'єднана з входами елемента АБО, а вхід синхронізації та інформаційний вхід з'єднані відповідно з входом синхронізації перетворювача кодів і з виходом елемента І-АБО, на четвертий вхід якого подається константа логічного 0. 3. Пристрій за п. 1, який відрізняється тим, що блок виявлення регулярних випадкових помилок містить пороговий елемент і елемент І, вихід якого під'єднаний до другого інформаційного виходу пристрою і з'єднаний з виходом блока, r-розрядна група інформаційних входів якого з'єднана з входами порогового елемента, вихід якого з'єднаний з першим входом елемента І, другий вхід якого з'єднаний з першим входом r-розрядної групи інформаційних входів блока. 4. Пристрій за п. 1, який відрізняється тим, що блок виявлення розріджених пакетів помилок містить елемент АБО-НІ і елемент І, вихід якого під'єднаний до третього інформаційного виходу r пристрою і з'єднаний з виходом блока, група останніх /2-розрядних входів із r-розрядної групи інформаційних входів якого з'єднана з входами АБО-НІ, вихід якого з'єднаний з першим входом елемента І, другий вхід якого з'єднаний з першим входом r-розрядної групи інформаційних входів блока. 5. Пристрій за п. 1, який відрізняється тим, що блок виявлення суцільних пакетів помилок містить дешифратор і елемент АБО, вихід якого під'єднаний до четвертого інформаційного виходу пристрою і з'єднаний з виходом блока, r-розрядна група інформаційних входів якого r з'єднана з входами дешифратора, /2-розрядна група виходів якого з'єднана з входами елемента АБО. 6. Пристрій за п. 1, який відрізняється тим, що блок виявлення нерегулярних випадкових помилок містить вузол пам’яті, генератор адрес і схему порівняння, перша r-розрядна група входів якої з'єднана з r-розрядною групою інформаційних входів блока, вхід синхронізації якого з'єднаний з входом генератора адрес, m-розрядна група виходів якого з'єднана з адресними входами вузла пам'яті, перша r-розрядна група і друга n-розрядна група виходів якого з'єднані відповідно з r-розрядною групою інформаційних виходів блока і з другою r-розрядною групою інформаційних входів схеми порівняння, вихід якої з'єднаний з виходом блока і під'єднаний до п'ятого інформаційного виходу пристрою. 7. Пристрій за п. 1, який відрізняється тим, що блок формування вектора помилки містить nрозрядний регістр зсуву, реверсивний лічильник, перший RS-тригер, другий RS-тригер, мультиплексор, перший елемент АБО, другий елемент АБО, третій елемент АБО, перший елемент І, другий елемент І, третій елемент І, перший вхід якого з'єднаний з входом синхронізації блока, перший, другий, третій інформаційні входи якого під'єднані відповідно до другого, третього, четвертого виходів пристрою і з'єднані зі входами першого елемента АБО, вихід якого з'єднаний з першим входом другого елемента АБО та з першим керуючим входом 11 UA 93798 U 5 10 15 20 мультиплексора, n-розрядна група виходів якого з'єднана з інформаційними входами регістра зсуву, n-розрядна група виходів якого з'єднана з n-розрядною групою виходів блока, четвертий інформаційний вхід якого з'єднаний з другим керуючим входом мультиплексора та з другим входом другого елемента АБО, вихід якого з'єднаний з входом запису регістра зсуву та з Sвходом першого RS-тригера, прямий та інверсний виходи якого з'єднані з першими входами першого елемента І та другого елемента І, виходи яких з'єднані відповідно з входом віднімання і входом додавання реверсивного лічильника, вихід переносу якого з'єднаний з виходом блока і під'єднаний до шостого інформаційного виходу пристрою, та з'єднаний з першим входом третього елемента АБО, вихід якого з'єднаний з R-входом другого RS-тригера, прямий вихід якого з'єднаний з другим входом третього елемента І, вихід якого з'єднаний з другими входами другого елемента І та першого елемента І, вихід якого також з'єднаний з входом зсуву регістра зсуву, вхід початкового установлення якого з'єднаний з входами початкового установлення реверсивного лічильника, з R-входом першого RS-тригера, з другим входом третього елемента АБО, з входом початкового установлення блока і під'єднаний до входу початкового установлення пристрою, причому вхід керування блока з'єднаний з S-входом другого RSтригера, перша r-розрядна група інформаційних входів та друга n-розрядна група інформаційних входів блока з'єднані відповідно з першою та другою групами входів мультиплексора. 8. Пристрій за п. 1, який відрізняється тим, що блок виправлення помилок містить регістр зсуву і суматор по модулю два, перша n-розрядна групу входів якого з'єднана з n-розрядною групою входів блока, вхід якого під'єднаний до інформаційного входу пристрою і з'єднаний з інформаційним входом регістра зсуву, n-розрядна групи виходів якого з'єднана з другою nрозрядною групою входів суматора по модулю два, n-розрядна групою виходів якого під'єднана до n-розрядної групи інформаційних виходів пристрою. 12 UA 93798 U 13 UA 93798 U 14 UA 93798 U Комп’ютерна верстка Д. Шеверун Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 15