ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ КОДЕРІВ І ДЕКОДЕРІВ ЦИКЛІЧНИХ КОДІВ. Методичні вказівки до лабораторної роботи з Інформаційна безпека. Робота № 518489

Перехід до торгівельного партнера Binance

ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ КОДЕРІВ І ДЕКОДЕРІВ ЦИКЛІЧНИХ КОДІВ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2007

Тип роботи:

Методичні вказівки до лабораторної роботи

Предмет:

Інформаційна безпека

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ КОДЕРІВ І ДЕКОДЕРІВ ЦИКЛІЧНИХ КОДІВ МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 2 з курсу “Основи збору, передачі та обробки інформації” для студентів базового напряму 6.1601 “Інформаційна безпека” Затверджено на засiданнi кафедри "Захист інформації" Протокол № 21 вiд 14. 06. 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.exe). 2. Відкрити файл LR2_CRC.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 НАВЧАЛЬНЕ ВИДАННЯ ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ КОДЕРІВ І ДЕКОДЕРІВ ЦИКЛІЧНИХ КОДІВ МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи з курсу «Основи збору, передачі та обробки інформації» для студентів стаціонарної та заочної форм навчання за базовим напрямком 6.1601 «Інформаційна безпека» Укладачі Кіріанакі Микола Володимирович Хома Володимир Васильович Совин Ярослав Романович Комп’ютерне верстання Совин Ярослав Романович Видано кафедрою захисту інформації Національного університету «Львівська політехніка» згідно з розпорядженням № 39 від 12.10.1999 р., протокол засідання кафедри № 21 від 14.06.2007 р. Наклад 15 примірників.

Методичні вказівки до лабораторної роботи Інформаційна безпека

proffboss

16.01.2013 12:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись