Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2007
Тип роботи:
Інші
Предмет:
Основи збору, передачі та обробки інформації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ
КОДЕРІВ І ДЕКОДЕРІВ ЦИКЛІЧНИХ КОДІВ
ІНСТРУКЦІЯ
до лабораторної роботи № 2
з курсу “ Основи збору, передачі та обробки інформації”
для студентів базового напряму 6.1601
“Захист інформації”
Затверджено
на засiданнi кафедри
"Захист інформації"
Протокол N вiд . .2007 p.
Львів 2007
Дослідження кодоутворення та принципів побудови кодерів і декодерів циклічних кодів: інструкція до лабораторної роботи № 2 з курсів «Основи збору, передачі та обробки інформації» для студентів базового напрямку «Захист інформації» усіх форм навчання / Укл. М. В. Кіріанакі, В. В. Хома, В. І. Отенко, Я. Р. Совин. - Львів: НУЛП, 2007. - 9 с.
Укладачі: М. В. Кіріанакі, канд. техн. наук, доц., В. В. Хома, док. техн. наук, проф., В. І. Отенко, канд. техн. наук, доц., Я. Р. Совин, асист.
Відповідальний за випуск М. В.Кіріанакі, канд. техн. наук., доц.
Рецензенти: З. Р. Мичуда, канд. техн. наук., доц. О. В. Івахів, канд. техн. наук.. доп.
Складання і відлагодження схеми здійснено асист. каф. захисту інформації Совином Я. Р.
Мета роботи – ознайомлення з основами кодування і декодування цифрової інформації циклічними кодами і набуттю практичних навиків розробки функціональних схем кодерів і декодерів.
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Циклічні коди (ЦК) є одними з найпростіших в реалізації та ефективних у забезпеченні високої завадостійкості і завдяки цьому широко використовуються не лише в телемеханіці, але і в обчислювальній техніці та зв’язку.
Для утворення циклічних кодів використовуються так звані неприведені поліноми Р(х), тобто многочлени, які не можна представити добутком поліномів нижчих степенів. Існує декілька різних способів кодування [1, 2].
Найпростіший спосіб утворення ЦК полягає у множенні многочлена G(х)1, який відповідає інформаційним ni розрядам первинного (безнадлишкового) коду, на утворюючий поліном Р(х). Такий спосіб легко реалізувати, але йому притаманний суттєвий недолік: одержані в результаті множення комбінації ЦК не містять в явному вигляд інформаційні розряди. Після виправлення помилок такі комбінації для виділення інформаційних символів доводиться ділити на утворюючий поліном.
Інший спосіб передбачає відведення під інформаційні ni , символи старших розрядів коду, а під контрольні nk = n - ni, символів молодших розрядів. Для утворення ЦК використовується така процедура. Многочлен G(х) який відповідає ni - розрядній кодовій комбінації (КК) первинного коду, множиться на . Ця операція еквівалентна приписуванню із боку молодших розрядів G(х) - nk нулів. Добуток G(х)* ділиться на утворюючий поліном Р(х). При цьому одержують частку Q(x) того ж степеня, що і G(х), та залишок R(x), який додається до G(х)* . Отже, КК циклічного коду буде визначатися як поліном
F(x) = G(х)* ( R(х) (1)
Оскільки степінь Р(х) вибирають nk, степінь залишку R(х), не перевищує nk - 1. В комбінації, що відповідає многочленові G(х)* , nk молодших розрядів нульові, і відповідно, операція додавання (1) рівносильна приписуванню R(x) до G(x) з боку молодших розряд. Очевидно, що R(х) має зміст контрольних розрядів ЦК. Таким чином, циклічний код можна будувати, приписуючи до кожної комбінації безнадлишкового коду G(х) залишок від ділення G(х)* на утво рюючий поліном Р(х) коду.
Захисні можливості ЦК визначаються утворюючим поліномом Р(х), вибір якого має бути підпорядкований кільком правилам:
1. кількість ненульових членів Р(х) має бути не меншою від кодо вої віддалі d;
2.степінь полінома Р(х) не може бути меншим за nk (бажано, щоб він дорівнював nk);
3. довжина Р(х) має бути мінімальною.
ЦК, утворений поліномом P(x)=x + 1, забезпечує кодову від даль d = 2 і збігається з кодом з захистом за паритетом, забезпечую чи виявлення не лише поодиноких помилок, але і довільної непарної кількості помилок.
ЦК з d = 3 можуть виявляти поодинокі та подвійні помилки або виправляти поодинокі помилки. Утворюючий поліном для такого коду можна вибрати із таблиці, наведеної в додатку. Необхідний степінь полінома визначається довжиною кодової комбінації n або кіль кістю інформаційних розрядів ni
2
При d=4 ЦК може виявляти поодинокі, подвійні і потрійні помилки або виявляти та виправляти поодинокі помилки. В цьому випадку утворюючий поліном знаходять множенням одного з неприведених многочленів додатку, вибраного відповідно до вказаних рекомендацій на двочлен х + 1. Очевидно, що степінь Р(х) зросте на одиницю і на стільки ж збільшиться кількість контрольних розрядів.
Циклічні коди з d ( 5, розроблені Боузом, Чоудхурі і Хоквінхемом (коди БЧХ), дають змогу виявляти і виправляти довільну кількість помилок, при цьому кількість контрольних розрядів може переважати кількість інформаційних. Процедура вибору утворюючого полінома Р(х) кодів БЧХ складніша [1, 2].
Оскільки ЦК - лінійний код, то для кодування можна викорис товувати утворюючу матрицю, що складається із одиничної транспонованої матриці рангу ni, до якої дописана додаткова матриця [nk, ni], що складається із залишків від ділення одиниці з ni - 1 нулями на P(x), вага яких не менша за d - 1. Так, наприклад, у випадку ЦК (7, 4) з Р(х) = x3 + х + 1 утворююча матриця має вигляд
Члени одиничної матриці є комбінаціями чотирирозрядного безнадлишкового коду G(x), тому чотири рядки утворюючої матриці - це комбінація ЦК. Всіх дозволених комбінацій має бути = 16 (включаючи нульову). Решту 11 ненульових можна одержати, дода ючи за модулем два наявні 4 комбінації матриці у найрізноманітні ших сполученнях рядків.
Існує інший спосіб побудови утворюючої матриці, який прості ший від описаного, але утворююча матриця менш зручна. Перший рядок утворюючої матриці формується виписуванням зліва до утво рюючого полінома P(x) ni - 1 нулів. Кожен наступний рядок матриці отримується циклічним зсувом цього рядка на один розряд вліво. Цей спосіб побудови утворюючої матриці використовує основну вла стивість циклічного коду - належність до ЦК кодових комбінацій при циклічному зсуві (звідси і назва коду). Для розглянутого раніше ЦК (7, 4) така матриця має вигляд
(3)
Декодування ЦК засновано на такій властивості: якщо помилок немає, то кодова комбінація F(х) ділиться на P(x) без залишку, а як що є - то із залишком. У першому випадку перші ni розрядів КК ви користовуються без корекції за своїм призначенням. У другому ви падку формується або заборона на використання, якщо ЦК виявляє помилки, або коректуючий цифровий сигнал, якщо ЦК виправляє помилки. Методи корекції детально описані в [1, 3].
Основу технічних засобів кодування і декодування ЦК склада ють регістри зсуву зі зворотними зв’язками, які дають змогу здійс нювати як множення, так і ділення многочленів в полі двійкових чи сел. Такі регістри називаються лінійними кодовими фільтрами Хофмена. Вони складаються із комірок пам’яті і суматорів за модулем 2. Зсув інформації в регістрі здійснюється імпульсами тактового генератора, який, як правило, на схемі не наводиться.
На рис. 1 і 2 наведені схеми помножувача і подільника полінома на P(x)=x4+х3+1. Для побудови таких схем необхідно керувати ся правилами:
1) кількість комірок регістра зсуву дорівнює старшому степеню утворюючого полінома P(x), причому комірка старшого розря ду відсутня, але завжди є комірка x0;
2) кількість суматорів за модулем два на одиницю менша від чис ла ненульових членів Р(х);
3) суматори завжди встановлюються перед комірками регістра, яким відповідають ненульові члени полінома Р(х), причому в подільнику зсувається суматор старшого розряду Р(х), а в по множувачі - молодшого;
4) в помножувачах на входи суматорів подається множене, а в подільниках - частка від ділення;
5) двійкові коди, над якими виконують операції множення і ді лення, подаються на вхід відповідних пристроїв зі старшими розрядами попереду.
На рис. 3 наведені два варіанти схем кодера ЦК, які побудовані відповідно на основі схеми помножувача і подільника. Робота кодерів проходить в два етапи. На першому, який триває ni тактів, переми кач П знаходиться в положенні 1, а ключ К - замкнений. При цьому кодовані інформаційні розряди полінома G(х), починаючи із старшо го, надходять безпосередньо на вихід та в схему кодера. Проходить множення G(х) на і виділення залишку R(x) від ділення G(х)* на Р(х). Після проходження останнього розрядку G(х) ключ К розмикається, а перемикач П переводиться в положення 2. Настає другий етап кодоутворення, на якому проходить порозрядне виштовхування залишку R(х) після кожного зсуву праворуч інформації, що міститься в регістрі. Таких зсувів буде nk і сформовані на виході кодера контрольні розряди R(х) будуть розташовані відразу після інформаційної КК G(х).
Наприклад, якщо на вхід кодера надходить послідовність G(x) = х7 + х5 + х4 + x3 + х + 1 ( 10111011, то на його виході, з’являються зі старшими розрядами попереду всі 8 двійкових розрядів первинного коду G(х), а після 8 такту - чотири контрольних розряди R(x) = x1 + 1( 0011 зафіксовані у комірках регістра у кінці першого такту. Отже, комбінація в ЦК має вигляд G(х) = x11 + x9 +x8 + х7 + х5 + х4 + х1 + 1( 101110110011
На рис. 4 наведена схема декодера ЦК в режимі виявлення помилок, до складу якого входять регістр пам’яті РП, дешифратор ДШ помилок і подільник, виконаний за схемою рис. 2.
Робота декодера проходить в два етапи. На першому етапі тривалістю ni тактів ключ К замкнений, тому на вхід регістра пам’яті і на вхід подільника надходить прийнята із лінії зв’язку КК F*(х) яка може відрізнятися від переданої F(х) внаслідок дії завад.
Ємність регістра пам’яті відповідає кількості інформаційних розрядів, тому в його комірках в кінці першого етапу буде міститися комбінація G*(х). На другому етапі ключ К розмикається, а ділення комбінації F*(х) на P(x) продовжується і триває ще пk тактів.
В результаті ni + пk тактів в комірка регістрів подільника буде зафіксований синдром помилки S(х), тобто залишок від ділення F*(х) на Р(х). Якщо вага синдрому S(х) не дорівнює нулеві, значить, відбулося спотворення інформації під час передачі і дешифратор стирає записану в регістрі пам’яті кодову комбінацію.
2. МЕТОДИЧНІ ВКАЗІВКИ
Лабораторна робота полягає у дослідженні схеми кодера та декодера ЦК (для твірного поліному Р(х) = x5 + x3 + x + 1) шляхом моделювання їх роботи у середовищі LogicWorks. Для чого необхідно:
1. Запустити програму LogicWorks (файл LogicWorks 4.0.exe).
2. Відкрити файл LR2_1.cct. Це можна зробити через пункт меню File/Open. При цьому в редакторі появиться схема представлена на рис. 5, що здійснює кодуваня 7-розрядної інформаційної комбінації ЦК із d = 4 з індикацією інформаційних та контрольних розрядів, подальшу передачу утвореної КК з можливістю внесення спотворень під час передачі, декодування одержаної комбінації та індикацію прийнятих розрядів і синдромів помилок.
До складу схеми входять:
а. 7 перемикачів (І7(І1) та індикаторів для задання значень і відображення інформаційних розрядів;
б. Перетворювач парале льного коду в 12-розрядний послідовний побудований на регістрах зсуву REG 1(REG 2;
в. Кодер ЦК побудований на 5 D-тригерах Х4(Х0, суматорах за модулем два та ключах К1 та К2;
г. Регістри REG5(REG6 та індикатори F12(F1 сформованої кодової комбінації
д. Пристрій внесення спотворень (ПВС) в розряди передаваної кодової комбінації реалізований на регістрах зсуву REG 3(REG 4 та суматорі за модулем два SUM. ПВС за допомогою перемикачів для внесення спотворень (F 12(F 1) формує сиг нали помилок, які, надходячи на суматор за модулем два, інвертують розряди КК, що передається;
е. Декодер ЦК разом з регістрами для зберігання одержаної кодової комбінації REG 7(REG 8, її відображення FD12(FD1, а також індикатори синдрому помилки S4(S0 та індикатор прапорця наявності помилки Error_Flag.
є. Генератор тактових імпульсів ГТІ та лічильник імпульсів (ЛІ) (на схемі 5 не показаний);
ж. Схема управління (СУ) у складі перемикачів SAVE і RES. Схема управління кодуванням забезпечує проходження 7 інформаційних імпульсів на вхід кодера, а після цього від’єднує коло зворотного зв’язку кодера і підключає його вихід на вхід регістрів пам’яті REG5(REG6. Схема управління декодуванням забезпечує проходження КК, що декодується з виходу регістрів REG5(REG6 на вхід декодера і на вхід регістрів REG7(REG8. Після n = ni + пk = 7 + 5 = 12 тактів процес декодування закінчиться.
3. В початковому стані перемикачі SAVE (ЗАПИС, здійснює запис кодової комбінації в регістри для передачі в послідовному коді), RES (СКИД) знаходяться в положенні 1, всі перемикачі внесення спотворень знаходяться в нульовому стані (спотворення відсутні).
4. Запустити моделювання схеми для чого необхідно вибрати пункт меню Simulation/Run або натиснути лівою клавішею мишки по піктограмі на панелі інструментів.
5. З допомогою перемикачів І7(І1 задати передбачені завданням кодові комбі нації в (щоб змінити положення перемикача потрібно навести на нього мишку і натиснути ліву клавішу). Якщо потрібно внести спотворення в певні розряди необхідно перевести відповідні перемикачі F 12(F 1 в одиничне положення.
6. Перевести перемикач SAVE в положення 0.
7. Перевести перемикач RES в положення 0.
8. Натиснути лівою клавішею мишки по піктограмі на панелі інструментів. З’явиться меню представлене на рис. 6.
Рис. 6. Меню Simulation Trigger Setup (заданння умови закінчення моделювання)
У ньому потрібно вести дані представлені на рис. 6 та натиснути кнопку OK.
10. Перевести спочатку перемикач SAVE, а потім RES в положення 1. Після цього починається моделювання роботи схеми, яке триває 12 тактів сигналу NCLK1. Після 12 такту моделювання автоматично зупиняється, а в регістрах REG 5–REG 6 (рис. 5) буде записана сформованна кодова комбінація у двійковому коді. З допомогою індикаторів сформованої КК F12(F1 порівняти одержані контрольні розряди з обчисленими при домашній підготовці. Одночасно відбувається декодування сформованої КК. З допомогою індикаторів прийнятої КК FD12(FD1 порівняти одержану і передану КК.
11. Порівняти одержані синдроми S4(S0, тобто залишок від ді лення комбінації F(х) на P(x) з розрахованими при домашній підготовці. Відсутність залишку свідчить про без помилкову передачу КК F(х) циклічного коду на що вказує нульовий стан прапорця наявності помилки Error_Flag.
12. Одночасно можна спостерігати часові діаграми роботи схеми (рис. 7), які виводяться у вікні Timing Window, що розташоване у нижній частині редактора схем. У разі якщо вікно Timing Window відсутнє, його можна вивести вибравши пункт меню Window/Timing Window.
Рис. 7. Часова діаграма роботи схеми
13. Повторити пункти 1-12 з внесенням відповідних спотворень у КК (див. пункт 5 ЗАВДАННЯ). Для того, щоб спотворити певний розряд необхідно на кроці 5 перевести відповідні перемикачі внесення спотворення (F 12(F 1) у одиничний стан.
Рис. 5. Схема моделювання роботи кодера-декодера ЦК
3. ЗАВДАННЯ
1. Вивчити теорію побудови ЦК, принципи синтезу кодерів і декодерів.
2.3 Визначити основні параметри ЦК з d = 4 (пk, п, N, N(, N3, R, В) якщо кількість інформаційних розрядів дорівнює двом останнім цифрам номера залікової книжки (НЗК).
3.3 Побудувати утворюючу матрицю ЦК з утворюючим поліномом Р(х) = x4 + х3 + 1 і на її, основі закодувати КК G(х), що дорівнює двом останнім цифрам НЗК.
4.3 Розробити структурні схеми кодера і декодера для ni = 7 і кодової віддалі d = 4 (на базі твірного поліному з d = 3: Р(х) = x4 + х3 + 1).
5.3 Провести кодування і декодування двійкової кодової комбінації, що дорівнює двом останнім цифрам НЗК. Декодувати цю КК при відсутності та наявності 1-, 2-, 3- і 4-кратних помилок.
6. Дослідити в лабораторії схему кодуючого пристрою, виконати операцію кодування і порівняти її з результатом, одержаним в п. 5.
7. Дослідити схему де кодера і провести операцію декодування.
8. Здійснити декодування спотворених КК і порівняти результати з даними п. 5.
4. ЗМІСТ ЗВІТУ
1. Мета роботи.
2. Результати виконання пунктів 2-5 при домашній підготовці.
3. Результати досліджень в лабораторії.
4. Схеми кодерів і декодерів.
5. Висновки по роботі.
5. КОНТРОЛЬНІ ЗАПИТАННЯ
1. Чому ЦК належать до блочних, систематичних рівномірних кодів.
2. Методика визначення кількості контрольних розрядів.
3. Правила вибору утворюючого полінома.
4. Алгоритми утворення нероздільного і роздільного ЦК.
5. Методика побудови утворюючої матриці, одержання із неї кодових комбінацій ЦК.
6. Принцип побудови помножувачів і подільників двійкових поліномів.
7. Алгоритм декодування ЦК і визначення синдромів помилок.
8. Схемотехнічне забезпечення операцій кодування і декодування ЦК.
6. СПИСОК ЛІТЕРАТУРИ
1. Кодирование информации. Двоичные коды. Справочник под ред. Н. Т. Березюка. – Харьков: Вища шк., 1978.
2. Темников Ф. Е. и др. Теоретические основы информационной техники / Уч. пос. для вузов. – 2-е изд., перераб. и доп. – М.: Энергия, 1979.
3. Тутевич В. Н. Телемеханика. – М.: Вища шк., 1985.
Фрагменти таблиці утворюючих поліномів
Код
Поліном Р(x)
Код
Поліном Р(х)
11
x + 1
100001
х5 + 1
101
х2 + 1
100011
x5 + х + 1
111
х2 + х + 1
100101
x5 + х2 + 1
1001
х3 + 1
100111
х5 + х2 + х + 1
1011
х3 + х + 1
101001
x5 + x3 + 1
1101
x3 + x2 + 1
101011
x5 + x3 + x + 1
1111
x3 + x2 + х + 1
101101
x5 + х3 + х2 + 1
10001
x4 + 1
101111
x5 + х3 + х2 + х + 1
10011
x4 + x+ 1
110001
x5 + x4 + 1
11001
x4+ x3 + 1
110101
x5 + x4 +x2 + 1
11011
x4+ x3 + х + 1
110111
х5 + х4 + х2 + х + 1
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора