Пристрій для кодування циклічних кодів

Реферат: UA 111785 U UA 111785 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до техніки електрозв'язку і може застосовуватись в системах передачі даних та в комп'ютерних системах, що піддаються впливу завад. Відомий пристрій для кодування циклічних кодів [Авторське свідоцтво СРСР № 1083385, М. кл. Η 04 L 1/10; Η 03 К 13/02, опубл. 30.03.1984 р., Бюл. № 12], який містить блок пам’яті, інформаційний регістр введення-виведення інформації, блоки суматорів по модулю два, елемент АБО, блок елементів І, блок вибору старшого розряду коду полінома і регістр коду полінома. Недоліком цього пристрою є великий час кодування: 7k тактів часу для k-бітового інформаційного повідомлення з одним постійним породжувальним поліномом циклічного коду. Час кодування може бути зменшений лише в режимі передавання інформації групі абонентів і регулярної зміни породжувальних поліномів. Найбільш близьким по технічній суті до запропонованого є пристрій для кодування циклічних кодів [Авторське свідоцтво СРСР № 1448413, М. кл. H 03 Μ 13/00, опубл. 30.12.1988 р., Бюл. № 48], що містить r елементів пам'яті, де r - ступінь породжувального поліному, (r-1) перших логічних блоків, другий логічний блок, елемент НІ, два елементи АБО, ключовий елемент і тригер, перший і другий входи якого з'єднані з об'єднаними входами ключового елемента, вихід якого є виходом пристрою, третій вхід ключового елемента є інформаційним входом пристрою, перші і другі виходи перших і других логічних блоків з'єднані з першими і другими входами однойменних елементів пам'яті, перший і другий виходи i-го (i=3…r) елемента пам'яті з'єднані відповідно з першим і другим входами i-го логічного блока та з третім і четвертим входами (i-1)го логічного блока, перший і другий виходи першого елемента пам'яті з'єднані з першим і другим входами однойменного першого логічного блока та з третім і четвертим входами другого логічного блока, перший і другий виходи другого елемента пам'яті з'єднані з першим і другим входами однойменного першого логічного блока третім і четвертим входами попереднього першого логічного блока та з п'ятим і шостим входами другого логічного блока, третій і четвертий виходи першого логічного блока з'єднані з входами першого елемента АБО, вихід якого з'єднаний з входом ключового елемента, сьомий і восьмий входи другого логічного блока підключені до відповідних виходів тригера, вихід елемента НІ з'єднаний з дев'ятим входом другого логічного блока і з першим входом другого елемента АБО, другий вхід якого підключений до другого виходу тригера, вихід - до п'ятих входів перших логічних блоків, десятий вхід другого логічного блока і вхід елемента НІ об'єднані та підключені до третього входу пристрою. У відомому пристрої для кодування циклічних кодів процедура кодування закінчується після (k+r)-го такту роботи, де k - кількість інформаційних розрядів кодового слова, що передається по каналу зв'язку. Недоліками відомого пристрою є тривалий час процедури кодування та h використання породжувального поліному лише виду g(x)=1+x+x . В основу корисної моделі поставлена задача створення пристрою для кодування циклічних кодів, в якому за рахунок введення нових блоків та зв'язків, досягається можливість прискорення операції кодування та розширення функціональних можливостей пристрою. Поставлена задача вирішується за рахунок того, що у пристрій для кодування циклічних кодів, який складається із r елементів пам'яті, де r ступінь породжувального поліному циклічного коду, тригера і ключового елемента, вихід, перший вхід і керуючий вхід якого з'єднані відповідно з послідовним виходом пристрою, інформаційним входом пристрою та з прямим виходом тригера, вхід якого з'єднаний з керуючим входом пристрою, введені перший блок суматорів по модулю два, другий блок суматорів по модулю два і регістр зсуву, послідовний вихід, паралельний r-розрядний вихід і паралельний r-розрядний вхід якого з'єднані відповідно з другим входом ключового елемента, з паралельним r-розрядним виходом пристрою і з r виходами другого блока суматорів по модулю два, r входів якого з'єднані з виходами r елементів пам'яті, вихід r-го елемента пам'яті з'єднаний з першими входами першого блока суматорів по модулю два, інші входи яких з'єднані з інформаційним входом пристрою та з виходами інших елементів пам'яті згідно з видом породжувального поліному циклічного коду. На фіг. 1 представлена функціональна схема пристрою; на фіг. 2 приклад пристрою для 3 4 породжувального поліному g(x)=1+x +x . Пристрій для кодування циклічних кодів даних (фіг. 1) містить r елементів пам'яті 1, де r – ступінь породжувального поліному циклічного коду, перший блок суматорів 2 по модулю два, другий блок суматорів 3 по модулю два, регістр зсуву 4, ключовий елемент 5 і тригер 6, вхід якого з'єднаний з керуючим входом 7 пристрою, а вихід з керуючим входом ключового елемента 5, перший вхід якого з'єднаний з інформаційним входом 8 пристрою, вихід r-го елемента пам'яті 1 з'єднаний з першими входами першого блока суматорів 2 по модулю два, інші входи яких з'єднані з інформаційним входом 8 пристрою та з виходами інших елементів пам'яті 1 згідно з 1 UA 111785 U 5 10 15 20 видом породжувального поліному циклічного коду, виходи всіх r елементів пам'яті 1 з'єднані також з паралельним r-розрядним входом другого блока суматорів 3, паралельний r-розрядний вихід якого з'єднаний з паралельним r-розрядним входом регістра зсуву 4, паралельний rрозрядний вихід якого з'єднаний з паралельним r-розрядним інформаційним виходом 9 пристрою, послідовний вихід 10 якого з'єднаний з виходом ключового елемента 5, другий вхід якого з'єднаний з послідовним виходом регістра зсуву 4. 3 4 Приклад пристрою для породжувального поліному g(x)=1+х +х (фіг. 2) містить чотири елементи пам'яті 1.1 – 1.4, суматор 2.1 і суматор 2.2 першого блока суматорів 2 по модулю два, суматори 3.1-3.4 другого блока суматорів 3 по модулю два, тригери 4.1-4.4 регістра зсуву 4, ключовий елемент 5, тригер 6, керуючий вхід 7 пристрою, інформаційний вхід 8 пристрою, паралельний r-розрядний інформаційний вихід 9 пристрою і послідовний вихід 10 пристрою. Пристрій працює таким чином. В початковому стані всі елементи пам'яті 1 і тригер 6 знаходяться в нульовому стані. В підготовчому такті роботи на керуючий вхід 7 пристрою надходить сигнал, який встановлює тригер 6 в стан логічної одиниці. В результаті протягом перших к тактів роботи дозволяється передача k-розрядного інформаційного слова I від інформаційного входу 8 пристрою через ключовий елемент 5 на послідовний вихід 10 пристрою. Одночасно відбувається процес кодування циклічного коду, результатом якого є контрольне слово Ψ. Елементи пам'яті 1 і перший блок суматорів 2 утворюють r-розрядну лінійну послідовнісну схему (ЛПС), за допомогою якої здійснюється систематичне кодування циклічного (n, k)-коду довжиною n і розмірністю k(n=k+r). Нульовий стан елементів пам'яті 1 означає нульовий стан S(0) ЛПС. Протягом наступних k тактів роботи ЛПС почергово переходить в наступні стани S t згідно з формулою: S t  1  A  S t  B  U t , (1)  25    де t - дискретний час;    A  aij rr , B  bij rl - характеристичні матриці; St   si r - слово стану Ut   ui l - вхідне слово;  - операція множення по модулю 2,  - операція додавання по модулю 2. Характеристичні матриці ЛПС мають вигляд: 0 0 0 1 0 0 A 0 1 0    0 0 0 30  g0  g1  g2 , B    1 gr 1 1 0 0 . (2)  0 Останній стовпець матриці А в (2) містить коефіцієнти породжувального поліному циклічного коду ступеня r: gx  gx   g0  g1x  g2 x 2    gr 1x r 1  gr x r Матриця А визначає внутрішню структуру ЛПС, тобто спосіб з'єднання виходів елементів пам'яті 1 і входів першого блоку суматорів 2. Якщо в матриці А елемент a i, j  1 a i, j  0 , тоді  35 40 45  існує зв'язок (відсутній зв'язок) між виходом j-го елемента пам'яті 1 і входом і-го елемента пам'яті 1. Якщо одночасно a i, j  1  j  1..r  1 і ai,r  1 , тоді вхід і-го елемента пам'яті 1 з'єднаний з виходом першого блока суматорів 2, перший вхід якого з'єднаний з виходом (i-1)-гo елемента пам'яті 1, а другий вхід з'єднаний з виходом г-го елемента пам'яті 1. Вхід першого елемента пам'яті 1 завжди з'єднаний з виходом першого суматора першого блока суматорів 2, перший вхід якого з'єднаний з інформаційним входом 8 пристрою, а другий вхід - з виходом r-го елемента пам'яті 1. Кількість суматорів в першому блоці суматорів 2 дорівнює кількості одиниць в останньому стовпці матриці А. Протягом перших k тактів роботи на послідовний вихід 10 пристрою буде передано інформаційне слово I  1 2 ...k , починаючи з першого розряду 1 , і буде сформовано проміжний стан Sk  ЛПС: i-й елемент пам'яті 1 буде зберігати i-й розряд si стану Sk  . 2 UA 111785 U k s1 sk 2 Sk    (3) sk1 r sk r На (k+1)-му такті роботи пристрою за допомогою другого блока суматорів 3 формується rрозрядне контрольне слово   1 2   r , розряди якого обчислюються в результаті виконання такої системи рівнянь:  5  k   r  a1,1s1  a1,2 sk    a1,r sk 2 r  k k k   r 1  a 2,1s1  a 2,2 s 2    a 2,r sr , (4)  . . . . . . . . . . . . . . . . k  1  ar,1s1  ar,2 sk    ar,r sk 2 r  В результаті буде сформоване кодове слово 1 2 ...k 1 2   r , 10 Обчислене контрольне слово  може також передаватись паралельно на паралельний rрозрядний інформаційний вихід 9 пристрою після (k+1)-го такту роботи, . Розглянемо приклад кодування для циклічного (15,11)-коду, що задається породжувальним 3 4 поліномом g(x)=1+х +х . Характеристичні матриці ЛПС цього коду згідно з (2) мають вигляд: 0 1 A 0  0 0 0 1 1  0 0 0 0 , B   . 0 1 0 0    0 1 1 0 Нехай на інформаційний вхід 8 надходить таке інформаційне слово: I  1 2  3  4  5  6  7  8  9 10 11  1 1 0 0 0 1 1 0 1 0 1; 15 Для обчислення за формулою (1) сформуємо розряди вхідного слова ЛПС: U0  1  1; U1   2  1; U2   3  0 ; U3   4  0 ; U4   5  1; U5   6  1; U6   7  0 ; U7   8  0 ; U8   9  0 ; U9  10  0 ; U10  11  1. Стани елементів пам'яті 1.1-1.4 формують 4-розрядний стан ЛПС. Для знаходження стану Sk  для k=11 виконаємо обчислення згідно з формулою (1): 0 1 S1  A  S0   B  U0    0  0 20 0 0 1 0 0 0 0 1 0 1 S2  A  S1  B  U1   0  0 0 0 1 0 0 0 0 1 0 1 S11  A  S10  B  U10   0  0 0 0 1 0 1 0 1 0 1 1  0 0 0 0 0 0     1         ;  0 0 0 0 0 0           1 0 0 0 0 0 1 1 1 0 1 1  0 0 1 0 1 0     1         ;  0 0 0 0 0 0           1 0 0 0 0 0  0 0 0 1 1 0 1 1 1 0  0 0 0 0 0 0     1         .  0 0 0 0 0 0           1 1 0 1 0 1 3 UA 111785 U Визначимо контрольне слово  за допомогою системи рівнянь (4). Оскільки структура цієї системи рівнянь буде незмінною для одного й того ж циклічного коду, тому можна наперед визначити r-у ступінь матриці А: 1 0 A 4  A  A  A  A  1 0  1 5 1 1 1 1 1 1 .  0 1 1  1 1 0 Тепер обчислимо розряди контрольного слова  :  4  s11  s11  s11  s11  0  0  0  1  1;  3  s11  s11  s11  s11  0  0  1  1 ; 1 2 3 4 2 3 4 4  2  s11  s11  1  0  1;  1  s11  s11  s11  0  0  0  0 . 3 4 1 2 3  10 15 20  Ці розряди контрольного слова   0 1 1 1 формуються після 11-го такту роботи на виходах суматорів 3.1-3.4 і записуються у відповідні тригери 4.1-4.4 регістра зсуву 4. В результаті буде сформовано кодове слово: 1 1 0 0 0 1 1 0 1 0 1 0 1 1 1. Протягом перших 11 тактів роботи цього пристрою, одночасно з підготовкою контрольного слова  , на послідовний вихід 10 відбувається послідовна передача інформаційного слова I. Далі відбувається або паралельна передача контрольного слова  на 12-му такті на паралельний r-розрядний інформаційний вихід 9 пристрою або послідовна передача контрольного слова  протягом 12-15 тактів на послідовний вихід 10 пристрою. Таким чином, в пристрої можливі два варіанти видачі контрольного слова Ψ: паралельний варіант з видачею результату на (k+1)-му такті роботи пристрою, і послідовний варіант з видачею результату після k-го такту роботи пристрою. У відомому пристрої результат кодування видається завжди після k-го такту роботи пристрою. У запропонованому пристрої реалізовано універсальний спосіб систематичного кодування циклічного коду, який не залежить від виду породжувального поліному g(x) коду. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 25 30 35 Пристрій для кодування циклічних кодів, який складається із r елементів пам'яті, де r-ступінь породжувального поліному циклічного коду, тригера і ключового елемента, вихід, перший вхід і керуючий вхід якого з'єднані відповідно з послідовним виходом пристрою, інформаційним входом пристрою та з прямим виходом тригера, вхід якого з'єднаний з керуючим входом пристрою, який відрізняється тим, що в нього введені перший блок суматорів по модулю два, другий блок суматорів по модулю два і регістр зсуву, послідовний вихід, паралельний rрозрядний вихід і паралельний r-розрядний вхід якого з'єднані відповідно з другим входом ключового елемента, з паралельним r-розрядним виходом пристрою і з r виходами другого блока суматорів по модулю два, r входів якого з'єднані з виходами r елементів пам'яті, вихід r-го елемента пам'яті з'єднаний з першими входами першого блока суматорів по модулю два, інші входи яких з'єднані з інформаційним входом пристрою та з виходами інших елементів пам'яті згідно з видом породжувального поліному циклічного коду. 4 UA 111785 U 5 UA 111785 U Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 6