пропонується дипломна робота на тему «Розробка та дослідження програмного забезпечення для завадостійкого кодування на основі циклічних кодів»
Важливим способом боротьби з завадами в системах передачі та обробки інформації є застосування кодів, що виявляють і виправляють помилки. Відомі два взаємодоповнювальних методи боротьби з завадами:
- кодування з виправленням помилок (корегуючі коди) - приймач виявляє і виправляє помилки;
- кодування з виявленням помилок - приймач розпізнає помилки і, у разі потреби, проводить запит на повторну передачу помилкового блока.
Корегуючі коди формуються шляхом введення значної надлишковості в дані, що передаються, цифрові потоки можуть зростати в два і більше раз. Крім того, вони працюють з блоками обмеженої довжини і при певних конфігураціях помилок або не виявляють їх зовсім, або невірно інтерпретують характер помилок.
Другий метод припускає наявність каналу зворотного зв'язку і знаходить своє застосування в каналах з достатньо малою імовірністю помилки у випадку, якщо цю імовірність помилки необхідно ще знизити. Крім того, такі коди використовують не тільки для виявлення наявності помилок які вносять природними факторами, але і для перевірки цілісності файлів, яка може бути порушена в результаті дій зловмисника, оскільки ці задачі ідентичні. Найчастіше при цьому використовуються методи, що ґрунтуються на підрахунку контрольних сум. Контрольна сума - деяке значення, розраховане з послідовності даних шляхом застосування певного алгоритму, яке використовується для перевірки правильності передачі даних Слід зазначити, що застосування контрольних сум вносить мінімальну надлишковість в дані, що передаються, тому навіть у випадку повторної передачі цифрові потоки можуть бути значно меншими у порівнянні з корегуючими кодами.
Хоча циклічні коди можуть використовуватись для кодування з виправленням помилок, але найчастіше їх використовують саме для формування контрольних сум. Циклічні надлишкові CRC (Cyclic redundancy code) коди вже стали основою багатьох стандартів, де застосовуються контрольні суми. Тому ці коди і вибрані для подальшої реалізації та дослідження.
Метою даної роботи є (читаєш плакат 1).
У відповідності до поставленої мети в роботі вирішуються такі завдання (читаєш плакат 1).
Плакат 2 (ліва колонка)
Розглянемо більш детально циклічні коди. Циклічні коди (ЦК) складають велику групу найширше використовуваних на практиці лінійних кодів. Їх основна властивість, полягає в тому, що кожен вектор, що отримується з початкового кодового вектора шляхом циклічної перестановки його символів, також є дозволеним кодовим вектором. Циклічні коди є різновидністю поліноміальних кодів [1]. В таких кодах вважається, що елементи (біти) a1, a2, …an-1 деякого кодового слова є коефіцієнтами полінома від x. Тоді процес кодування можна подати як результат множення полінома m(x), що являє собою інформаційну послідовність на породжувальний многочлен g(x), а декодування як результат ділення на цей поліном. Ідея побудови циклічних кодів ґрунтується на використанні многочленів, що не приводяться (простий многочлен), в якості породжувального многочлена.
Найчастіше циклічні коди будують в систематичній формі, тобто спочатку передаються інформаційні біти, а потім контрольні розряди. Побудова циклічного систематичного коду виконується згідно з виразом (показуєш на плакат 2 - формулу і читаєш колонку зліва). Корегуючий код, в тому числі і циклічний, який виявляє і виправляє декілька помилок характеризується великою надлишковістю - в два і більше раз бітів потрібно передавати або зберігати.
Плакат 2 (права колонка)
Найчастіше циклічні коди використовують для контролю помилок, а саме, циклічний надлишковий код (Cyclic redundancy code, CRC) (пок. на плакат 2 права колонка). Він використовується для обчислення контрольних сум. Контрольна сума - спосіб цифрової ідентифікації деякої послідовності, який полягає в обчисленні контрольного значення її циклічного надлишкового коду. Значення CRC є по суті залишком від ділення многочлена, відповідного вхідним даним, на якийсь фіксований многочлен. CRC - коди є основою багатьох стандартів передачі даних, а також використовуються для перевірки цілісності файлів.
Розглянемо приклад побудови коду CRC-4 для повідомлення 11010111, використовуючи поліном-генератор x4+x3+x2+1. Початковому повідомленню відповідає поліном x7+x6+x4+x2+x+1. Тут нумерація бітів тут починається справа. Виконується ділення поліномів (Показуєш на плакат). В результаті отримаємо остаток від ділення R= x2| +1, якому відповідають біти 0101 - це і є CRC-4 код (показуєш на плакат 2).
Перевагою CRC-кодів є здатність виявляти майже всі помилки у файлі. Не виявляються лише помилки, з вектором помилки (двійкове число, одиничні біти якого відповідають помилковим бітам прийнятого блоку, а нульові - правильно прийнятим), що ділиться на твірний (породжуючий) поліном без остачі, а також низька надлишковість (для CRC4 - добавляється лише 4 біти у файл, CRC8 - добавляється лише 8 біти у файл, CRC32 - добавляється лише 32 біти у файл), що вигідно відрізняє їх від корегуючи кодів.
Плакат 3
Завдяки цьому CRC-коди є основою багатьох стандартів передачі даних, а також використовуються для перевірки цілісності файлів (показуєш на плакат 3). CRC - коди на відміну від кодів з перевіркою на парність або непарність дозволяють виявляти як одиничні так і пакетні помилки, що є ще однією їх перевагою.
Плакат 4
При практичній реалізації алгоритмів CRC метод ділення поліномів, який передбачає побітне зчитування файлу дуже повільний, особливо у випадках, коли файли досягають мегабайтних розмірів. На практиці застосовують табличні методи розрахунку CRC. Ідея табличного методу така: оброблятимемо по байту за один прохід циклу. Коли ми ділимо байт на поліном, у нас в залишку виходить деяке число, причому воно не залежить від інших байтів повідомлення. Ось це число ми можемо зберігати в таблиці для кожного ділимого байта. Маючи таку таблицю, отримуватимемо CRC для кожного байта за один прохід. Саме такий підхід і застосовано в даній роботі. Схема обчислення CRC для 32 бітного породжуючого полінома має такий вигляд (показуєш на плакат 4 і читаєш алгоритм).
Плакат 5
Для CRC8 алгоритм обчислення ще простіший, оскілки таблиця містить 256 байт і немає необхідності в регістрі зсуву (показуєш на плакат 5).
Плакат 6
Для розробки програми розрахунку CRC обрано середовище розробки Visual Studio 2008 і мову програмування C#. Значною перевагою C# є можливість легкого доступу до класу HashAlgorithm NET Framework Class Library. Методи цього класу значно спрощують програмну реалізацію алгоритмів обчислення CRC.
З урахуванням того, що по-перше це навчальна робота, а по-друге програма, що розробляється призначена для кодування файлів, де швидкісні характеристики не є першочерговими, мова програмування С# є найбільш придатною для даної розробки.
Програма може працювати на комп'ютері з операційною системою Windows XP та встановленою платформою Microsoft.NET Framework 3.5 або на комп'ютері з операційними системами Windows Vista або Windows 7, в які інтегрована платформа Microsoft.NET Framework.
Програма дозволяє обчислювати контрольні суми CRC8, CRC32, а інтерфейс користувача включає також CRC4, який може бути реалізований при необхідності. Програма має зручний інтерфейс користувача, тому для керування нею не потрібно мати спеціальних навиків роботи на комп'ютері.
Щоб запустити програму на виконання потрібно вибрати файл CRC32.exe, що знаходиться у папці CRC32. Після запуску програми з'явиться головне вікно (показуєш на плакат 6).
Для обчислення CRC необхідно виконати такі дії:
5. Вибрати тип полінома - CRC8 або CRC32.
6. Вибрати файл, клацнувши «мишею» на кнопці справа від поля «Шлях до файла», в результаті чого з'являється стандартне вікно вибору файла. Після вибору файла активується кнопка «Підрахувати».
7. Клацнути «мишею» по кнопці «Підрахувати». В полі «Результат обчислень» появиться CRC вибраного файлу.
8. При необхідності можна зберегти цей результат в файл клацнувши «мишею» по кнопці справа від поля «Результат обчислення». СRC буде збережено у файл ім'я, якого має такий формат:
Префікс Ім'я початкового файлу Розширення
Префікс - CRC8 або CRC32
Розширення - crc
Приклад для файлу read.txt - crc32read.txt.
Після цього файл з CRC можна записати на змінний носій, а потім видалити його з диска комп'ютера. Під час наступного включення комп'ютера з'являється можливість перевірити чи не змінив зловмисник файли на комп'ютері.
Для виконання перевірки необхідно вибрати команду «Перевірити». Відкриється стандартне вікно вибору файла, у якому необхідно вибрати файл, який ми хочемо перевірити і натиснути на кнопку «Открыть». Після чого відкриється друге стандартне вікно вибору файлу, у якому необхідно вибрати відповідний файл з розширенням .crc.
При виборі кнопки «Про програму» буде виведена інформація про дану роботу та її розробника.
Плакат 7-8
Для тестування програми було взято файл поекту CRC32.sln (показуєш на плакат 7), у який було внесено зміни замість - EndGlobal записано EndLocal (показуєш на плакат 8) і було виконано перевірки програми на всіх режимах роботи.
Плакат 9-10
Як в режимі CRC32 так і в CRC8 програма виявила зміни (пок. на плакат 9-10). Тобто вона працездатна.
Плакат 11
Таким чином основні результати роботи такі - читаєш плакат 11.
Крім того, в роботі виконано розрахунок економічних показників. Термін окупності розробки - 0,7 року, прибуток від впровадження програми складе 10 338,3 грн.
Крім того розглянуто питання охорони праці при експлуатації даного програмного продукту.
Дякую за увагу, доповідь закінчено.
ВІДГУК
на дипломну роботу студента групи 1ПЗ-09сп, Кравця В'ячеслава В'ячеславовича на тему “ Розробка та дослідження програмного забезпечення для завадостійкого кодування на основі циклічних кодів”
Циклічні коди, можуть використовуватись як для кодування з виправленням помилок так і для формування контрольних сум, але найчастіше їх використовують саме для формування контрольних сум. За допомогою контрольних сум можна перевіряти і цілісність файлів, яка може бути порушена в результаті дій зловмисника, оскільки задача виявлення помилок в каналі передачі ідентична задачі перевірки цілісності файлів на диску комп'ютера. Незамінними тут є циклічні надлишкові коди (Cyclic redundancy code - CRC), які вже стали основою багатьох стандартів. Слід зазначити, що застосування CRC-кодів вносить мінімальну надлишковість в дані, що передаються, тому навіть у випадку повторної передачі цифрові потоки можуть бути значно меншими у порівнянні з корегуючими кодами. Тому тема дипломної роботи є досить актуальною.
В роботі розроблено алгоритми та програмне забезпечення для обчислення контрольних сум для поліномів CRC8 та CRC32 табличним методом. Тестування програми показало, що навіть короткі поліноми здатні виявляти значні зміни файлів, що для кодів, які виправляють помилки вкрай важко. Крім того, обґрунтовано вибір середовища програмування Visual Studio 2008 та мови програмування C#.
Під час дипломного проектування студент Кравець В. В. проявив себе грамотним, кваліфікованим спеціалістом здатним приймати самостійно складні технічні рішення. Поставлені в дипломній роботі завдання виконано доволі якісно та в повному обсязі.
Вважаю, що дипломна робота заслуговує на оцінку «добре», а Кравець В. В. - присвоєння кваліфікації «спеціаліст».
Керівник дипломної роботи к.т.н., доцент каф. ПЗ В. П. Майданюк
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
