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

Реферат: UA 115973 U UA 115973 U 5 10 15 20 25 30 35 40 45 50 55 Корисна модель належить до техніки електрозв'язку і може застосовуватись в системах передачі даних та в комп'ютерних системах, що піддаються впливу завад. Відомим аналогом є пристрій для кодування циклічних кодів [Авторське свідоцтво СРСР № 1083385, М. кл. Н 04 L 1/10; Н 03 К 13/02, опубл. 30.03.1984р., Бюл. № 12], який містить блок пам'яті, інформаційний регістр введення-виведення інформації, блоки суматорів по модулю два, елемент АБО, блок елементів І, блок вибору старшого розряду коду полінома і регістр коду полінома. Недоліком аналога є великий час кодування: 7k тактів часу для k-бігового інформаційного повідомлення з одним постійним породжувальним поліномом циклічного коду. Час кодування може бути зменшений лише в режимі передавання інформації групі абонентів і регулярної зміни породжувальних поліномів. Найближчим аналогом до корисної моделі є пристрій для кодування циклічних кодів [Авторське свідоцтво СРСР № 1448413. М. кл. Н 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+х+х . В основу корисної моделі поставлена задача створення пристрою для кодування циклічних кодів, в якому за рахунок введення нових блоків та зв'язків, досягається можливість прискорення операції кодування та розширення функціональних можливостей пристрою. Поставлена задача вирішується тим, що пристрій для кодування циклічних кодів, складається із r елементів пам'яті, де r - степінь породжувального полінома циклічного коду, тригера і ключового елемента, вихід, перший вхід і керуючий вхід якого з'єднані відповідно з послідовним виходом пристрою, інформаційним входом пристрою та з прямим виходом тригера, вхід якого з'єднаний з керуючим входом пристрою, згідно з корисною моделлю, введені багатовходовий суматор по модулю два, перший блок суматорів по модулю два, другий блок суматорів по модулю два, схема перемикання і регістр зсуву, послідовний вихід якого з'єднаний з другим входом ключового елемента, виходи m (mr) елементів пам'яті з'єднані згідно з видом породжувального полінома циклічного коду з першими m входами багатовходового суматора по модулю два, (m+1)-й вхід якого з'єднаний з інформаційним входом пристрою, а вихід - зі входом r-го елемента пам'яті, виходи всіх r елементів пам'яті також з'єднані з відповідними r входами першого блока суматорів по модулю два та другого блока суматорів по модулю два, паралельний r- розрядний вихід яких з'єднані відповідно з першим та другим паралельними rрозрядними входами схеми перемикання, паралельний г-розрядний вихід якої з'єднаний з паралельним r- розрядним входом регістра зсуву, паралельний r- розрядний вихід якого з'єднаний з паралельним r- розрядним інформаційним виходом пристрою, послідовний вихід якого з'єднаний з виходом ключового елемента. Корисна модель пояснюється кресленням, де на фіг. 1 представлена функціональна схема 3 4 пристрою; на фіг. 2 приклад пристрою для породжувального полінома g(x)=1+х +х . 1 UA 115973 U 5 10 15 20 25 30 35 Пристрій для кодування циклічних кодів даних (фіг. 1) містить r елементів пам'яті 1, де r степінь породжувального полінома циклічного коду, багатовходовий суматор 2 по модулю два, перший блок суматорів 3 по модулю два, другий блок суматорів 4 по модулю два, схему перемикання 5, регістр зсуву 6, ключовий елемент 7 і тригер 8, вхід якого з'єднаний з керуючим входом 9 пристрою, а вихід з керуючим входом ключового елемента 7, перший вхід якого з'єднаний з інформаційним входом 10 пристрою, виходи m (mr) елементів пам'яті 1 з'єднані згідно з видом породжувального полінома циклічного коду з першими т входами багатовходового суматора 2 по модулю два, (m+1) -й вхід якого з'єднаний з інформаційним входом 10 пристрою, а вихід - зі входом r-то елемента пам'яті 1, виходи всіх r елементів пам'яті 1 також з'єднані з відповідними r входами першого блока суматорів 3 по модулю два та другого блока суматорів 4 по модулю два, паралельний r- розрядний вихід яких з'єднаний відповідно з першим та другим паралельними r- розрядними входами схеми перемикання 5, паралельний rрозрядний вихід якого з'єднаний з паралельним r- розрядним входом регістра зсуву 6, паралельний г-розрядний вихід якого з'єднаний з паралельним r- розрядним інформаційним виходом 12 пристрою, послідовний вихід 11 якого з'єднаний з виходом ключового елемента 8, другий вхід якого з'єднаний з послідовним виходом регістра зсуву 6. 3 4 Приклад пристрою для породжу вального полінома g(x) = 1 + х + х (фіг. 2) містить чотири елементи пам'яті 1.11.4, багатовходовий суматор 2 по модулю два, суматор 3.1 першого блока суматорів 3 по модулю два, суматори 4.24.4 другого блока суматорів 4 по модулю два, елементи перемикання 5.15.4 схеми перемикання 5, тригери 6.1-6.4 регістра зсуву 6, ключовий елемент 7, тригер 8, керуючий вхід 9 пристрою, інформаційний вхід 10 пристрою, послідовний вихід 11 пристрою, паралельний r- розрядний вихід 12 пристрою. Пристрій працює наступним чином. В початковому стані всі елементи пам'яті 1 і тригер 8 знаходяться в нульовому стані. В підготовчому такті роботи на керуючий вхід 9 пристрою надходить сигнал, який встановлює тригер 8 в стан логічної одиниці. В результаті протягом перших k тактів роботи дозволяється передача k - розрядного інформаційного слова I від інформаційного входу 10 пристрою через ключовий елемент 7 на послідовний вихід 11 пристрою. Одночасно відбувається процес кодування циклічного коду, результатом якого є контрольне слово Ψ. Елементи пам'яті 1 і багатовходовий суматор 2 утворюють r- розрядну лінійну послідовну схему (ЛПС), за допомогою якої здійснюється систематичне кодування циклічного (n, k) - коду довжиною n і розмірністю k (n-k+r). Нульовий стан елементів пам'яті 1 означає нульовий стан S(0) ЛПС. Протягом наступних k тактів роботи ЛПС почергово переходить в наступні стани S(t) згідно формули: St 1  S t    Ut , (1) де t - дискретний час;   aij  r r ,   bij  r   - характеристичні матриці; 40 S t   si  r - слово стану U t   ui   - вхідне слово; "х" операція множення по модулю 2, "+ " - операція додавання по модулю 2. Характеристичні матриці ЛПС мають вигляд: 0 0  0 ... g0 45 1 0 0 1 0 0 ... ... g1 g2 ... 0 0 ... 0 0 ... 0 ,  0 , ... 1 ... ... gr 1 1 (2) Останній рядок матриці А в (2) містить коефіцієнти породжувального полінома g(x) циклічного коду степені г: g( x )  g0  g1x  g2 x 2  ...  gr 1x r 1 gr x r , 50 (3) Матриця А визначає внутрішню структуру ЛПС, тобто спосіб з'єднання виходів елементів пам'яті 1 і входів багатовходового суматора 2. Якщо в матриці А елемент аi, j,=1 (аі, j=0), тоді існує зв'язок (відсутній зв'язок) між виходом j-го елемента пам'яті 1 і входом і-го елемента 2 UA 115973 U 5 пам'яті 1. Вхід r-го елемента пам'яті 1 завжди з'єднаний з виходом багатовходового суматора 2. Вихід першого елемента пам'яті 1 завжди з'єднаний з першим входом багатовходового суматора 2 по модулю 2, а інші (m-1) входів якого з'єднані з виходами елементів пам'яті 1 згідно з видом породжувального полінома циклічного коду (3). Протягом перших k тактів роботи з послідовного входу 10 пристрою на його послідовний вихід 11 буде передано інформаційне слово I=ι1ι2 … ιk починаючи з першого розряду ι1, і буде k сформовано проміжний стан S(k) ЛПС: i-й елемент пам'яті 1 буде зберігати i-й розряд si стану S(k).  sk   1  k  s2  S k    ...  ,   s k1  r  k   sr  (3) 10 На (k+1)-му такті роботи пристрою за допомогою першого блока cуматорів 3 формується rрозрядне контрольне слово   1 2 ...r , розряди якого обчислюються за такої системи рівнянь: Lr    r  Sk , (4) 15 де (rr) - матриця L має вигляд:   L r   r 1   ,  r  2   ,...,    ,  . Для характеристичних матриць А і В виду (2) матриця L матиме вигляд: 0  1  1  2,1  3,1  3,2 Lr   ...  ...   r,1  r,2 ... ... ... ... ... 0  0 0 0 0  ,  i, j  0,1, i  j.  ... ...  r ,r  1 1   0 (5) 20 Систему рівнянь (4) можна записати у вигляді: k  1  ar,1s1  ar,2 sk  ...  ar,r sk , GF (2), GF (2); 2 r  k  1  2,1   2  ar 1,1s1  ar 1,2 sk  ...  ar 1,r sk , GF (2) : 2 r  .......... .......... .......... .......... .......... .......... .......... .  k k k    ...    r 1 r,r 1   r  a1,1s1  a1,2 s 2  ...  a1,r sr , GF (2),  1 r,1  (6)  де ai, j - (i, j) -та компонента матриці r ai, j r ; i 1... r ; j  1...r ; 25 30   s k - i-й розряд слова стану Sk  sk1  Sk . i i Сформовані розряди контрольного слова   1 2 ...r  через схему перемикання 5 записуються у регістр зсуву 6. Далі контрольне слово У передається з регістра зсуву 6 на паралельний r- розрядний вихід 12 пристрою на (k+2)-му такті роботи, або, починаючи з розряду 1 , передається протягом r тактів через ключовий елемент 7 на послідовний вихід 11 пристрою. Можливий також другий спосіб кодування циклічних кодів. В цьому випадку після передачі інформаційного слова I=ι1ι2 … ιk далі протягом наступних r тактів роботи на послідовний вхід 10 пристрою надходять нульові сигнали і на (k+r)-му такті роботи буде сформовано проміжний стан S(n) ЛПС: i-й елемент пам'яті 1 буде зберігати розряд s n стану S(n). i 3 UA 115973 U  sn   1  n  s2  Sn    ...    s n1  r  n   sr  На (n+1)-му такті роботи пристрою за допомогою другого блока суматорів 4 формується rрозрядне контрольне слово   1 2 ...r , розряди якого обчислюються за такої системи рівнянь: 5 Lr    Sn, (7) Систему рівнянь (7) можна записати у вигляді: n   r  s1   r  2,1   r 1  sn  2 ,  .......... .......... .......... .......... .......... . n     ...    2 r,r 1  1  sr  r 2,1 10 15 20 (8)  де s n - і-розряд слова стану Sn sn  Sn; i  1  r i i  i, j  i, j  - та компонента матриці (5).  S(n), Сформовані розряди контрольного слова   1 2 ...r  із системи рівнянь (8) через схему перемикання 5 також записуються у регістр зсуву 6. Далі контрольне слово Ψ може бути передано на паралельний г- розрядний вихід 12 пристрою на (n+2)-му такті роботи або передано протягом r тактів через ключовий елемент 7 на послідовний вихід 11 пристрою. В обох випадках за допомогою пристрою буде сформоване однакове кодове слово 1  2 ... k 1 2 ...r 1,12 …lAV|/,V(/2 …\|/,. Розглянемо приклад кодування першим способом для циклічного (15,11)-коду, що задається 3 4 породжувальним поліномом g(x)=1+x +x . Характеристичні матриці ЛПС цього коду згідно з (2) мають вигляд: 0 1 0 0 0     0 0 1 0 0  ,   . 0 0 0 1 0     1 0 0 1 1 Нехай на інформаційний вхід 8 надходить таке інформаційне слово:   1 2  3  4  5  6 7 8 9 10 11  1 1 0 1 0 0 1 1 0 1 0 ; Для обчислення за формулою (1) сформуємо розряди вхідного слова ЛПС: U0  1 1; U1   2  1; U2  3  0 ; U3   4  1; 25 U4   5  0 ; U5   6  0 ; U6   7  1; U8   9  0 ; U9  10  1; U10   11  0 ; U7   8 1; . Стани елементів пам'яті 1.1-1.4 формують 4-розрядний стан ЛПС (фіг.2). Для знаходження стану S(k) для k=11 виконуються обчислення згідно з формулою(1): 0 1 0 0 0 0 0 0 0            0 0 1 0 0 0 1  0  0  0 ; S1    S 0     U 0     0 0 0 1 0 0 0 0 0            1 0 0 1 0 1 0 1 1 4 UA 115973 U 0  0 S2    S 1    U 1   0  1 5 0 0 0       0  0  0 ; 1 0 1       1 1 0 . 0 1 0 0 1 0 1 0 1           0 0 1 0 1 0 0  1  0  1 ; S11    S 10     U 10     0 0 0 1 1 0 1 0 1           1 0 0 1 1 1 0 0 0 Визначимо контрольне слово Ψ за допомогою системи рівнянь (6). Оскільки структура цієї системи рівнянь буде незмінною для одного й того ж циклічного коду, тому можна наперед визначити r-у степінь матриці А: 1 0 0 1   1 1 0 1 4           . 1 1 0 1   1 1 1 0 Далі визначимо матрицю (4): 1 0 0 0   1 1 0 0 . L 4  3    2         1 1 1 0   1 1 1 1 В результаті отримаємо таку систему рівнянь:  10 1 0 0 0 0     0 1 0 0 0 1   0 0 1 0 0     0 0 1 1 1 ...  L 4     4  S 11 , або, згідно з системою (6): 1  s1  s 4   1   2  s1  s 2  s 4  ,   1   2   3  s1  s 2  s 3  s 4 1   2   3   4  s1  s 2  s 3  (9) В результаті розв'язання системи рівнянь (9) отримаємо такі значення розрядів контрольного слова   1  2 3  4  ; 1  s1  s 4  1  1  0 ,  2  s 2  1,  3  s3  0 , 15 20 25  4  s 4  1. Ці розряди контрольного слова   0 1 0 1 формуються після 11-го такту роботи на виходах першого блока суматорів 3.1-3.4 і записуються у відповідні тригери 6.1-6.4 регістра зсуву 6. Далі контрольне слово   0 1 0 1 , починаючи з розряду 1 , передається протягом r тактів через ключовий елемент 7 на послідовний вихід 11 пристрою. В результаті буде сформовано кодове слово: 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1. Аналогічним чином знаходиться розв'язання системи рівнянь (8) і будуть отримані такі ж значення компонент контрольного слова Ψ. Таким чином, в пристрої можливі чотири варіанти формування і видачі контрольного слова Ψ: паралельний варіант з видачею результату на (k+2)-му такті роботи пристрою, послідовний варіант з видачею результату після (k+r+1)-му такті роботи пристрою, паралельний з видачею результату на (k+r+2) -му такті, послідовний з видачею на (k+2r+1)-му такті роботи пристрою. У відомому пристрою результат кодування видається завжди після n-го такту роботи пристрою. У запропонованому пристрої реалізовано універсальний спосіб систематичного кодування циклічного коду, який не залежить від виду породжувального полінома g(x) коду. 5 UA 115973 U ФОРМУЛА КОРИСНОЇ МОДЕЛІ 5 10 15 20 Пристрій для кодування циклічних кодів, що містить r елементи пам'яті, де r - степінь породжувального полінома циклічного коду, тригер і ключовий елемент, вихід, перший вхід і керуючий вхід якого з'єднані відповідно з послідовним виходом пристрою, інформаційним входом пристрою та з прямим виходом тригера, вхід якого з'єднаний з керуючим входом пристрою, який відрізняється тим, що додатково містить багатовходовий суматор по модулю два, перший блок суматорів по модулю два, другий блок суматорів по модулю два, схема перемикання і регістр зсуву, послідовний вихід якого з'єднаний з другим входом ключового елемента, виходи m (mr) елементів пам'яті з'єднані згідно з видом породжувального полінома циклічного коду з першими m входами багатовходового суматора по модулю два, (m+1)-й вхід якого з'єднаний з інформаційним входом пристрою, а вихід - зі входом r-го елемента пам'яті, виходи всіх r елементів пам'яті також з'єднані з відповідними r входами першого блока суматорів по модулю два та другого блока суматорів по модулю два, паралельний r-розрядний вихід яких з'єднані відповідно з першим та другим паралельними r-розрядними входами схеми перемикання, паралельний r-розрядний вихід якої з'єднаний з паралельним r-розрядним входом регістра зсуву, паралельний r-розрядний вихід якого з'єднаний з паралельним r-розрядним інформаційним виходом пристрою, послідовний вихід якого з'єднаний з виходом ключового елемента. 6 UA 115973 U 7 UA 115973 U Комп’ютерна верстка Л. Ціхановська Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 8