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

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

Міністерство освіти і науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп'ютерної інженерії

Факультет комп'ютерного інтелекту

ЗАТВЕРДЖУЮ

Завідувач кафедри ПЗ

д.т.н., проф. А.М. Пєтух

«_____» ________ 2010 р.

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

Пояснювальна записка

До дипломної роботи за спеціальністю

7. 080403 - Програмне забезпечення автоматизованих систем

08-24.ДР.008.00.000 ПЗ

Керівник дипломної роботи

к.т.н., доцент В. П. Майданюк

«____» __________ 2010

Розробив студент гр. 1ПЗ-09сп

В. В. Кравець

«____» __________ 2010

Вінниця ВНТУ 2010

ЗАВДАННЯ

на дипломну роботу зі спеціальності 7.080403

«Програмне забезпечення автоматизованих систем»

студенту групи 1ПЗ-09сп Кравець В. В.

Тема проекту: Розробка та дослідження програмного забезпечення для завадостійкого кодування на основі циклічних кодів .

Вихідні дані: операційна система - Windows XP, Windows Vista

мова програмування - C# метод кодуванн - CRC - код .

Короткий зміст частин роботи

1. Графічна: - мета і задачі робот; .

- циклічні коди; .

- стандартні циклічні CRC-коди; .

- обчислення CRC32 табличним методом; .

- граф-схема алгоритму обчислення CRC8; .

- головна форма програми; .

- тестування програми .

2. Текстова (пояснювальна записка)

- вступ;

-техніко-економічне обґрунтування доцільності розробки програми;

- аналіз циклічних кодів; .

- розробка алгоритму і програми для кодування на основі CRC-коду;

- економічний розділ;

- безпека життєдіяльності;

- висновки

АНОТАЦІЯ

Дипломна робота присвячена розробці програмного продукту для завадостійкого кодування даних з використанням корегуючих кодів. Високий рівень рішення поставленої задачі досягнутий, за рахунок використання програмного середовища Visual Studio 2008 та мови програмування C#.

Результатом проведення досліджень є розроблений програмний продукт, який призначений як для завадостійкого кодування файлів з використанням CRC-коду так і для вивчення самого методу.

ANNOTATION

Diploma work is devoted development of software product for | encoding of data with the use of error correcting codes. The high level of decision of the put task is attained, due to of software environment of Visual Studio 2008 and programming of C#.

The result of lead through of researches is the developed software product, is intended as for encoding of files with the use of CRC codes so for the study of method.

ЗМІСТ

ВСТУП

1 ТЕХНІКО-ЕКОНОМІЧНЕ ОБГРУНТУВАННЯ ДОЦІЛЬНОСТІ РОЗРОБКИ ПРОГРАМНОГО ПРОДУКТУ

1.1 Суть технічної проблеми, що виникла на сучасному етапі

1.2 Аналіз існуючих програм

1.3 Вибір і обґрунтування аналогу

1.4 Уточнення технічних вимог

1.5. Прогноз величини попиту

1.6 Цінова політика

1.7. Визначення конкурентів

1.8 Проведення розрахунків, що підтверджують економічну доцільність нового програмного продукту

Висновок

2 АНАЛІЗ ЦИКЛІЧНИХ КОДІВ

2.1 Основні підходи до застосування завадостійких кодів

2.2 Класифікація завадостійких кодів

2.3 Принципи побудови циклічних кодів

2.4 Аналіз CRC-кодів

2.5 Варіантний аналіз основної проектної задачі і технічне обґрунтування вибору оптимального алгоритму завадостійкого кодування

Висновки

3 РОЗРОБКА АЛГОРИТМУ І ПРОГРАМНИХ МОДУЛІВ ДЛЯ КОДУВАННЯ ДАНИХ НА ОСНОВІ CRC-КОДІВ

3.1 Розробка алгоритму кодування на основі CRC-кодів

3.2 Розробка програми захисту файлів на основі CRC - кодів

3.3 Тестування програми

3.4 Керівництво оператора

Висновки

4 ЕКОНОМІЧНА ЧАСТИНА

4.1 Розрахунок кошторису витрат на розробку програмного продукту

4.2 Розрахунок собівартості матеріального носія з програмним продуктом

4.3 Розрахунок ціни реалізації матеріального носія із записаним програмним продуктом

4.4 Розрахунок прибутку для виробника

4.5 Розрахунок експлуатаційних витрат у споживача, пов'язаних з використанням програмного продукту

4.6 Розрахунок умовних обсягів робіт, який може бути виконаний із застосуванням нового програмного продукту

4.7 Розрахунок річного економічного ефекту від впровадження нового програмного продукту

4.8 Розрахунок для споживача економічного ефекту на ціні від придбання нового програмного продукту

4.9 Розрахунок терміну окупності витрат

Висновки

5 БЕЗПЕКА ЖИТТЄДІЯЛЬНОСТІ

5.1 Основні принципи конструювання робочого місця користувача ЕОМ

5.2 Принципи конструювання робочого місця користувача ЕОМ

5.3 Вимоги до організації робочих місць користувачів ЕОМ

5.4 Технічне рішення щодо забезпечення електробезпеки до робочого місця користувача ЕОМ

Висновок

ВИСНОВКИ

ПЕРЕЛІК ПОСИЛАНЬ

ДОДАТОК А Технічне завдання на роботу

ДОДАТОК Б Текст програми CRC - кодування

ДОДАТОК В Ілюстративний матеріал до захисту дипломної роботи

ВСТУП

Важливим способом боротьби з завадами в системах передачі та обробки інформації є застосування кодів, що виявляють і виправляють помилки. Відомі два взаємодоповнювальних методи боротьби з завадами [1]:

- кодування з виправленням помилок (корегуючі коди) - приймач виявляє і виправляє помилки;

- кодування з виявленням помилок - приймач розпізнає помилки і, у разі потреби, проводить запит на повторну передачу помилкового блока.

Корегуючі коди формуються шляхом введення значної надлишковості в дані, що передаються, цифрові потоки можуть зростати в два і більше раз. Крім того, вони працюють з блоками обмеженої довжини і при певних конфігураціях помилок або не виявляють їх зовсім, або невірно інтерпретують характер помилок. Це робить їх майже непридатними для перевірок цілісності даних в умовах одночасної дії завад та можливого несанкціонованого порушення цілісності даних.

Другий метод припускає наявність каналу зворотного зв'язку і знаходить своє застосування в каналах з достатньо малою імовірністю помилки у випадку, якщо цю імовірність помилки необхідно ще знизити. Крім того, такі коди використовують не тільки для виявлення наявності помилок які вносять природними факторами, але і для перевірки цілісності файлів, яка може бути порушена в результаті дій зловмисника, оскільки задача виявлення помилок ідентична цій задачі. Найчастіше при цьому використовуються методи, що ґрунтуються на підрахунку контрольних сум. Контрольна сума - деяке значення, розраховане з|із| послідовності даних шляхом застосування|вживання| певного алгоритму, яке використовується для перевірки правильності передачі даних [2]. Популярність використання контрольних сум для перевірки цілісності даних обумовлена тим, що подібна перевірка просто реалізовується і добре підходить для виявлення загальних помилок, викликаних наявністю шуму в каналах передачі даних або спробами несанкціонованої зміни даних. Слід зазначити, що застосування контрольних сум вносить мінімальну надлишковість в дані, що передаються, тому навіть у випадку повторної передачі цифрові потоки можуть бути значно меншими у порівнянні з корегуючими кодами.

Хоча циклічні коди можуть використовуватись для кодування з виправленням помилок, але найчастіше їх використовують саме для формування контрольних сум. Циклічні надлишкові CRC (Cyclic redundancy code) коди [1-3] вже стали основою багатьох стандартів, де застосовуються контрольні суми. Тому ці коди і вибрані для подальшої реалізації та дослідження.

Метою даної роботи є розробка та дослідження алгоритмів і програм кодування даних з виявленням помилок на основі циклічних CRC-кодів.

У відповідності до поставленої мети в роботі вирішуються такі завдання:

- аналіз циклічних кодів;

- розробка алгоритму кодування даних з виявленням помилок на основі CRC-кодів;

- вибір програмних засобів для вирішення поставлених завдань;

- розробка та тестування програмних модулів;

- розрахунок економічних показників;

- вирішення питань охорони праці.

1 ТЕХНІКО-ЕКОНОМІЧНЕ ОБҐРУНТУВАННЯ ДОЦІЛЬНОСТІ РОЗРОБКИ ПРОГРАМНОГО ПРОДУКТУ

1.1 Суть технічної проблеми, що виникла на сучасному етапі

Реальні системи передачі та зберігання даних не ідеальні. Застосовуючи інформаційну техніку, ми повинні враховувати можливість виникнення помилок при передачі і зберіганні інформації. Причиною можуть бути як завади (noise), що діють в інформаційній системі, так і свідомі дії зловмисників, направлені на порушення цілісності даних.

Важливим способом боротьби з завадами в системах передачі та обробки інформації є застосування кодів, що виявляють і виправляють помилки. Теорія завадостійкого кодування для кожного конкретного каналу дозволяє вибрати найбільш ефективний метод виявлення і виправлення помилок. Відомі два взаємодоповнювальних методи боротьби з завадами:

- кодування з виправленням помилок (корегуючі коди) - приймач виявляє і виправляє помилки;

- кодування з виявленням помилок - приймач розпізнає помилки і, у разі потреби, проводить запит на повторну передачу помилкового блока.

Корегуючі коди формуються шляхом введення значної надлишковості в дані, що передаються, цифрові потоки можуть зростати в два і більше раз. Крім того, вони працюють з блоками обмеженої довжини і при певних конфігураціях помилок або не виявляють їх зовсім, або невірно інтерпретують характер помилок. Це робить їх майже непридатними для перевірок цілісності даних в умовах одночасної дії завад та можливого несанкціонованого порушення цілісності даних.

Другий метод припускає наявність каналу зворотного зв'язку і знаходить своє застосування в каналах з достатньо малою імовірністю помилки у випадку, якщо цю імовірність помилки необхідно ще знизити.

Така ситуація часто виникає в обчислювальних мережах і в Інтернеті.

Типове значення імовірності помилки на біт без кодування в обчислювальних мережах складає 10-6. Використання простих кодів з невеликою надмірністю дозволяє досягти вірогідності 10-9 і нижче.

Найчастіше при цьому використовуються методи, що ґрунтуються на підрахунку контрольних сум. Контрольна сума - деяке значення, розраховане з|із| послідовності даних шляхом застосування певного алгоритму, яке використовується для перевірки правильності передачі даних. Популярність використання контрольних сум для перевірки цілісності даних обумовлена тим, що подібна перевірка просто реалізовується і добре підходить для виявлення загальних помилок, викликаних наявністю шуму в каналах передачі даних або спробами несанкціонованої зміни даних. Слід зазначити, що застосування контрольних сум вносить мінімальну надлишковість в дані, що передаються, тому навіть у випадку повторної передачі цифрові потоки можуть бути значно меншими у порівнянні з корегуючими кодами.

Контрольні суми можуть використовуватись і для перевірки цілісності файлів, яка може бути порушена в результаті дій зловмисника, оскільки задача виявлення помилок в каналі передачі ідентична задачі перевірки цілісності файлів на диску комп'ютера.

Циклічні коди, можуть використовуватись як для кодування з виправленням помилок так і для формування контрольних сум. Але як показано вище метод з формуванням контрольних сум має переваги в комп'ютерних обчислювальних мережах. Для формування контрольних сум використовують циклічні надлишкові CRC (Cyclic redundancy code) коди [2-3], які вже стали основою багатьох стандартів. Тому ці коди і вибрані для подальшої реалізації та дослідження.

1.2 Аналіз існуючих програм

Відомо безліч пакетів прикладних програм, які формують контрольні суми для перевірки цілісності файлів з використанням CRC - кодів.

В першу чергу це архіватори WinRAR, WinZIP та інші, які використовують CRC - коди для формування контрольних сум для архівів. Ці програми призначені для ущільнення даних і формування контрольних сум є допоміжною функцією збереження цілісності ущільнених даних. Більшість файлів даних на дисках персональних комп'ютерів невеликі за розміром, так що немає необхідності їх ущільнювати. Для таких файлів архіватори не дозволяють формувати контрольні суми. Це є одним з важливих недоліків програм даного типу. Іншим недоліком є закритість кодів цих програм, що не дозволяє використовувати їх для навчання програмуванню задач завадостійкого кодування. Крім того, необхідне придбання ліцензії на право їх використання.

Іншу важливу групу складають платні утиліти для формування контрольних сум з використанням CRC - кодів .

Утиліта FastCRC Library це швидка програма, яка дозволяє обчислювати контрольні суми, з використанням популярних алгоритмів CRC32, CRC16, та інші. Можна обчислювати контрольні суми для файлів, блоків пам'яті, рядків, потокових даних. Дана програма підтримує декілька інтерфейси. Довідковий файл має приклади на мовах C, C++ і Visual Basic, які показують, як додати обчислення контрольних сум до Windows додатків на максимально можливій швидкості. Недоліком цієї програми, як і попередньої, є закритість кодів цих програм та необхідність придбання ліцензії на право їх використання.

AccuHash 2,0 це Windows утиліта для захисту цілісності та перевірки точності даних, файлів за допомогою контрольної суми. Реалізовано декілька алгоритмів для обчислення контрольних сум. що дозволяє легко і швидко перевірити цілісність файлів, завантажених з Інтернету або записаних на CD / DVD диск. Недоліком цієї програми, як і попередньої, є закритість кодів цих програм та необхідність придбання ліцензії на право їх використання.

В мережі Інтернет також поширюється маса безкоштовних утиліт для обчислення контрольних сум з використанням CRC - кодів.

Arpoon обчислює контрольні суми файлів, дозволяє виявляти зміни файлів і документів. Дана програма може бути використана також для перегляду змін важливих документів. Інша програма Duplicate Checker дублює засоби операційної системи для пошуку файлів та їх знищення.

Уявіть, що необхідно знайти певний файл на вашому комп'ютері і Ви отримуєте п'ять файлів з тією ж самою назвою і тим же самим розміром.

Який файл дійсно потрібний? Щоб уникати таких проблем і організовувати файли, необхідно видалити непотрібні файли, що зберігає простір жорсткого диску. При порівнянні файлів використовується контрольна сума CRC32.

Програма Fsum - це безкоштовний і простий у використанні інструмент, який дозволяє розраховувати контрольні суми файлів. Програма підтримує "drag-and-drop" і може працювати з декількома файлами одночасно. Контрольна сума може бути використана для звірки цілісності файлів.

Загальним недоліком безкоштовних утиліт є низька достовірність їх роботи, закритість кодів цих програм та відсутність супроводження. Відповідальність за її роботу лежить повністю на користувачеві, який встановив цю програму на комп'ютері.

1.3 Вибір і обґрунтування аналогу

В якості аналога для розробки програмного продукту було обрано програму FastCRC Library. Ця програма призначена для захисту файлів шляхом формування контрольних сум з використанням майже всіх відомих популярних алгоритмів для формування контрольних сум - CRC32, CRC16, CRC16C, MD5 та інших [5]|.

Основним недоліком FastCRC Library є складність її використання через функціональну перевантаженість. Також до недоліків можна віднести відносно низьку швидкість кодування, оскільки для формування контрольних сум використовуються поліноми високої степені, а також закритість кодів цієї програми та необхідність придбання ліцензії на право їх використання.

У розробці дана проблема вирішується за рахунок використання для формування контрольної суми лише поліномів не вище восьмої степені (CRC4, CRC8), що дозволить спростити інтерфейс користувача, а також підвищити швидкість кодування. Використання поліномів вищого ступеня не має сенсу, оскільки до даних, що передаються по мережі, апаратні засоби та операційна система сама добавляє CRC-код, а для перевірка цілісності даних на диску достатньо і поліномів невисокої степені. Також програмний продукт випереджає аналог за таким параметром як сумісність з різними типами апаратних та програмних платформ, оскільки розробка нового програмного продукту планується на мові програмування C# у середовищі програмування Miscrosoft Visual Studio 2008, що дасть можливість використовувати бібліотеки Microsoft.NET Framework, які забезпечують перенесення програми на більшість апаратних та програмних платформ.

Основні технічні показники аналога і нової програми наведені в таблиці 1.1

Таблиця 1.1 - Основні технічні показники аналога і нової програми

Отже, програма, що розробляється має ряд суттєвих переваг перед аналогом. Вона не вимагає спеціальної підготовки, має вищу швидкість кодування за рахунок використання поліномів не вище восьмої степені, а також високу сумісність нової програми з найсучаснішими апаратними та програмними платформами, що досягається за рахунок використання бібліотеки Microsoft .NET Framework. вищу швидкість кодування за рахунок використання поліномів не вище восьмої степені

1.4 Уточнення технічних вимог

Вимоги до програмного забезпечення будуть розроблятись з урахуванням існуючих на сьогоднішній день машинних ресурсів і тому мінімальні вимоги до апаратури можуть бути дещо завищені. Але оскільки такі проекти розробляються на перспективу, потрібно враховувати прогрес у розвитку апаратних засобів, щоб не відставати від конкурентів.

Для рішення задачі розробки програми для захисту даних з використанням циклічних CRC кодів будемо використовувати програмне забезпечення перераховане в табл. 1.2.

Таблиця 1.2 - Перелік програмного забезпечення

Операційною системою для програми, що розроблюється, вибрана Microsoft Windows XP. Можливості ОС Windows XP достатньо широкі: це і запуск програм, і переключення між задачами, і управління вікнами, і організація зручного оточення, а також, робота в мережі та інше Вона являється найбільш оптимальною операційною системою для вирішення, існуючих задач.

До складу програмних засобів повинні входити оптимальні для реалізації існуючих задач засоби. Програма, розроблена за допомогою середовища програмування Visual Studio 2008. Мова програмування вибрана С#, оскільки вона забезпечує як високу швидкість розробки, так і добрі швидкісні характеристики програмного продукту. Крім того, висуваються такі вимоги:

- IBM сумісний комп'ютер на базі мікропроцесора Pentium II і вище;

- операційна система Windows ХР з встановленою бібліотекою Microsoft.NET Framework;

- розмір оперативної пам'яті не менш 512 Mb;

- підтримка маніпулятора типу “миша”;

- розмір простору на твердому диску 80 Гб.

1.5 Прогноз величини попиту

Одним з важливих етапів економічного прогнозування є прогнозування споживчого попиту на дану розробку. Оптимістичний прогноз визначається кількістю споживачів, які будуть застосовувати даний програмний продукт.

Сферою застосування даної розробки можуть бути будь-які користувачі та фірми для яких важливим є забезпечення цілісності файлів при їх передачі та зберіганні. Наприклад, це можуть бути фінансові дані, зміна яких в результаті природних причин або зловмисником може призвести до не передбачуваних наслідків.

Комп'ютеризація світу, в тому числі і України, набуває все більшого розмаху. Можлива кількість споживачів продукту по Україні може складати близько тисячі. Враховуючи те, що деякі фірми вже використовують програми-аналоги, можна сказати, що близько 35% споживачів не стануть використовувати новий та зовсім невідомий продукт; навіть враховуючи всі його переваги. Незважаючи на рекламу, в перший рік існування програмного продукту про нього не одержать інформації близько 5% споживачів. Тому оптимістичний прогноз (ОП) складе:

ОП = 1500 - 1500 • (0,35+0,05)=900 (шт.).

Для визначення песимістичного прогнозу (ПО) необхідно врахувати, що близько 15% споживачів не зможуть придбати новий програмний, продукт за нестачею коштів, 5% - за несумісністю з програмними та апаратними засобами, і ще близько 5% - за особистими переконаннями. Отже, песимістичний обсяг ринку буде:

ПО = 900 - 900 • (0,15+0,05+0,05) =900 - 225= 675 (шт.)

Реалістичний прогноз РП може бути визначений як середнє арифметичне оптимістичного та песимістичного прогнозів, тобто:

РП =

Якщо врахувати, що підприємство, яке буде випускати новий програмний продукт, може охопити 40% вітчизняного ринку, то величина цільового ринку складе:

ЦР = 788/10040=315 (шт.)

Отже за перший рік просування товару на ринок, планується продати приблизно 315 шт.

1.6 Цінова політика

Головною кінцевою метою цінової політики є отримання максимального прибутку від продажу нового програмного продукту. Цінова політика повинна бути орієнтована на завоювання певного сегменту ринку, що ще не завойований конкурентами.

При встановленні ціни будемо враховувати, що ціна не повинна бути занадто низькою, щоб забезпечити прибуток, і не зростати занадто високо, щоб не зменшити попит. Рекомендується продавати розробку на 10-20% дешевше ринкової вартості аналогів. Для споживача необхідною умовою є так званий супровід програмного забезпечення. Ця умова може включати в себе технічну підтримку програмного продукту та заміна старої версії новою.

Ринкова ціна аналогу становить 329,00 грн. Тому рекомендується продавати розробку за ціною, яка буде нижчою за ціну аналогу.

1.7 Визначення конкурентів

В даний час на ринку програмного забезпечення в Україні спостерігається надлишковість програмних засобів закордонних виробників. Це стосується і програм, що реалізують алгоритми завадостійкого кодування даних на основі CRC-кодів. Конкурентами на ринку є відомі продукти FastCRC Library, AccuHash 2.0, а також безкоштовні програми Arpoon Checksum, Fsum. Загальним недоліком безкоштовних утиліт є низька достовірність їх роботи, закритість кодів цих програм, відсутність супроводження програмного забезпечення, тому ці програми не можуть бути конкурентами нової розробки в сфері промислового використання.

Вітчизняні виробники програмних продуктів не акцентують великої уваги на розробці подібних засобів. Тому найбільшу конкуренцію на ринку даного виду продукції будуть складати саме закордонні виробники, аналоги яких досить часто зустрічаються на споживчому ринку.

Але всі програмні засоби, що виробляються за кордоном мають ряд недоліків. По-перше, в чистому вигляді алгоритми завадостійкого кодування з використанням циклічних CRC кодів вбудовують в інші програмні засоби, які можуть коштувати великих грошей, а це не зовсім вигідно споживачеві.

По-друге, інтерфейс користувача найчастіше англомовний, що заважає в роботі з цими програмами звичайним користувачам. Однак, якщо виключити питання мови, то слід зауважити, що закордонні виробники не жалкують часу для розробки зручного інтерфейсу користувача та оформлення своїх продуктів, тому при розробці слід врахувати естетичний вигляд та зручність в користуванні продукту, а також розробити необхідну для користування документацію у вигляді допоміжних файлів.

Практично одним з основних засобів в боротьбі із конкурентами для розробника є реклама. Реклама має великий вплив на споживачів, і повинна в повній мірі описати продукт та всі його переваги. При проведені рекламної кампанії планується акцентувати увагу споживачів на доцільності використання програмного продукту в зв'язку з його надійністю та новизною, а також на те, що купуючи новий продукт вони підтримують саме вітчизняного виробника. Зробивши акцент на перевагах нової розробки, планується дістати довіри на вітчизняному ринку.

Враховуючи той факт, що програма володіє рядом переваг, таких як зручний україномовний інтерфейс користувача, велика швидкодія та сумісність з новітніми програмними та апаратними засобами, вона буде успішно конкурувати на ринку з існуючими аналогами.

1.8 Проведення розрахунків, що підтверджують економічну доцільність нового програмного продукту

Оцінка економічної доцільності розробки нового програмного продукту проводиться шляхом співставлення капітальних вкладень та експлуатаційних витрат аналога та нового продукту .

Визначення умовного обсягу роботи при використанні програмного продукту.

Для визначення обсягу робіт Q1 без використання програмного продукту потрібно знати час виконання конкретної функції (роботи) при умові, що програмний продукт не буде застосовуватись (або при застосуванні старого програмного продукту).

Для визначення обсягу робіт Q2 при використанні нового програмного продукту потрібно знати час виконання конкретної функції (роботи) в умовах, коли буде використовуватись новий програмний продукт.

Тоді обсяги робіт можна розрахувати за формулами [6]:

та (1.1)

де Q1 - обсяг робіт при застосуванні існуючого програмного продукту, умовних одиниць, штук, тощо;

Q2 - обсяг робіт при застосуванні нового програмного продукту, умовних одиниць, штук, тощо;

F - ефективний фонд часу роботи за рік, (для однозмінної роботи

F = 1800 годин,;

- доля часу, який витрачає працівник на виконання конкретних робіт з застосуванням даного програмного продукту в загальному часі своєї роботи;

ti - час виконання конкретної функції або роботи.

Q1 = 1800 • 60 • 0,01/1= 1080[функцій/хв],

Q2 = 1800 • 60 • 0,01/0,5 = 2160 [функцій/хв].

Тобто застосування нового програмного продукту підвищує продуктивність при виконанні певної роботи у 2160/1080 = 2 рази.

Собівартість одиниці нової розробки (програмного продукту) може бути cпрогнозована методом питомої ваги. Цей метод застосовується тоді, коли є можливість розрахувати одну із прямих витрат (в даному випадку це вартість інтелектуальної власності) і установити питому вагу даної статті витрат в собівартості аналога. Собівартість одиниці продукту S можна спрогнозувати за формулою:

[грн.], (1.2)

де Вп -- величина прямих витрат нової розробки (вартість інтелектуальної власності), яка вибрана за основу, грн.;

П - питома вага витрат в собівартості аналога, %;

Кн - коефіцієнт, який ураховує конструктивні та технологічні особливості нової розробки.

(грн.),

(грн.).

Величина капітальних вкладень К може бути cпрогнозована за формулою:

K = B A S,[грн.], (1.3)

де В -- коефіцієнт, який ураховує витрати на розробку, придбання, транспортування, монтаж, налагодження нової розробки;

А -- коефіцієнт, який ураховує прогнозований прибуток та податки, які повинен сплачувати виробник;

S -- собівартість нової розробки, розрахованої приблизним способом;

Ц -- ціна реалізації нової розробки, якщо вона була визначена раніше, грн.

Кан(грн.),

Кнпп(грн.).

Експлуатаційними витратами є такі витрати, які забезпечують нормальне функціонування певного технічного рішення в період його експлуатації. Величина експлуатаційних витрат в розрахунку за 1 рік може бути cпрогнозована за формулою:

[], (1.4)

де Ц - ціна реалізації нової розробки, якщо вона була визначена раніше, грн/шт.;

k - коефіцієнт, який ураховує витрати на амортизацію, електроенергію, обслуговування, ремонти тощо.

А - коефіцієнт, який ураховує прогнозований прибуток та податки, які повинен сплачувати виробник;

S - собівартість нової розробки, яка була прогнозована приблизним способом;

- доля часу, який витрачає працівник на обслуговування технічної або інтелектуальної розробки в загальному часі своєї роботи.

Еа (грн.),

Енпп (грн.).

Отже, отримали, що експлуатаційні витрати на новий програмний продукт менші, ніж на відомий аналог. Механізм співставлення капітальних вкладень та експлуатаційних витрат наведений у таблиці 1.2.

Таблиця 1.2 - Механізм співставлення величин капітальних та експлуатаційних витрат

Отже, новий програмний продукт буде кращим за свій аналог.

Висновок

На підставі вищевикладеного можна стверджувати, що нове технічне рішення, що пропонується для розробки, буде мати кращі технічні показники, ніж існуючі, вирішить задачі щодо передачі та зберігання даних, дій зловмисників, які спрямовані на порушення цілісності даних.

Нова програма є більш економічно ефективною в порівнянні з аналогом і тому її розробка та впровадження є актуальною та доцільною.

2 Аналіз циклічних кодів

2.1 Основні до підходи до застосування завадостійких кодів

Реальні системи передачі та зберігання даних не ідеальні. Застосовуючи інформаційну техніку, ми повинні враховувати можливість виникнення помилок при передачі і зберіганні інформації. Причиною можуть бути як завади (noise), що діють в інформаційній системі, так і свідомі дії зловмисників, направлені на порушення цілісності даних.

Важливим способом боротьби з завадами в системах передачі та обробки інформації є застосування кодів, що виявляють і виправляють помилки. Теорія завадостійкого кодування для кожного конкретного каналу дозволяє вибрати найбільш ефективний метод виявлення і виправлення помилок. Відомі два взаємодоповнювальних методи боротьби з завадами

- кодування з виправленням помилок (корегуючі коди) - приймач виявляє і виправляє помилки;

- кодування з виявленням помилок - приймач розпізнає помилки і, у разі потреби, проводить запит на повторну передачу помилкового блока.

Корегуючі коди формуються шляхом введення значної надлишковості в дані, що передаються, цифрові потоки можуть зростати в два і більше раз. Крім того, вони працюють з блоками обмеженої довжини і при певних конфігураціях помилок або не виявляють їх зовсім, або невірно інтерпретують характер помилок. Це робить їх майже непридатними для перевірок цілісності даних в умовах одночасної дії завад та можливого несанкціонованого порушення цілісності даних.

Другий метод припускає наявність каналу зворотного зв'язку і знаходить своє застосування в каналах з достатньо малою імовірністю помилки у випадку, якщо цю імовірність помилки необхідно ще знизити. Така ситуація часто виникає в обчислювальних мережах і в Інтернеті. Типове значення імовірності помилки на біт без кодування в обчислювальних мережах складає 10-6. Використання простих кодів з невеликою надмірністю дозволяє досягти вірогідності 10-9 і нижче. Найчастіше при цьому використовуються методи, що ґрунтуються на підрахунку контрольних сум. Контрольна сума - деяке значення, розраховане з послідовності даних шляхом застосування певного алгоритму, яке використовується для перевірки правильності передачі даних. Популярність використання контрольних сум для перевірки цілісності даних обумовлена тим, що подібна перевірка просто реалізовується і добре підходить для виявлення загальних помилок, викликаних наявністю шуму в каналах передачі даних або спробами несанкціонованої зміни даних. Слід зазначити, що застосування контрольних сум вносить мінімальну надлишковість в дані, що передаються, тому навіть у випадку повторної передачі цифрові потоки можуть бути значно меншими у порівнянні з корегуючими кодами. Контрольні суми можуть використовуватись і для перевірки цілісності файлів, яка може бути порушена в результаті дій зловмисника, оскільки задача виявлення помилок в каналі передачі ідентична задачі перевірки цілісності файлів на диску комп'ютера.

Циклічні коди, можуть використовуватись як для кодування з виправленням помилок так і для формування контрольних сум. Але як показано вище метод з формуванням контрольних сум має переваги в комп'ютерних обчислювальних мережах. Для формування контрольних сум використовують циклічні надлишкові CRC (Cyclic redundancy code) коди, які вже стали основою багатьох стандартів [1-2]. Тому ці коди і вибрані для подальшої реалізації та дослідження.

2.2 Класифікація завадостійких кодів

Всі коди, що виявляють і корегують помилки, можна розділити на два класи: блокові і безперервні.

Блокові коди - коди, в яких кожному повідомленню (або елементу) зіставляється блок з n символів (кодовий вектор довжиною n). Операції кодування і декодування в кожному блоці проводяться окремо [8, 10].

Безперервні коди є безперервною послідовністю символів, що не підрозділяється на блоки. Такі коди називаються також рекурентними, ланцюговими, згортними, конволюціонними. Процеси кодування і декодування здійснюються безперервно. Послідовність, що передається утворюється шляхом розміщення в певному порядку перевірочних символів між інформаційними символами початкової послідовності.

Як блокові, так і безперервні коди діляться на розділимі і нерозділимі.

Розділимі коди передбачають можливість чіткого розмежування інформаційних і перевірочних символів.

Нерозділимі коди не передбачають такої можливості.

Розділимі коди діляться, у свою чергу, на|своєю чергою|:

- систематичні

- несистематичні.

Систематичні коди характеризуються тим, що інформаційні символи, як правило, не змінюються при кодуванні і займають визначені заздалегідь задані місця. Несистематичні коди не володіють відміченими вище властивостями і застосовуються значно рідше, ніж систематичні.

Якщо перевірні символи обчислюються як лінійна комбінація інформаційних, то такі коди називаються ще лінійними.

Для блокових кодів приймається позначення [n, k] - код, де k - число інформаційних символів в кодовій комбінації, n - загальне число символів в коді.

Циклічні коди (ЦК) складають велику групу найширше використовуваних на практиці лінійних кодів. Їх основна властивість, полягає в тому, що кожен вектор, що отримується з початкового кодового вектора шляхом циклічної перестановки його символів, також є дозволеним кодовим вектором. Прийнято описувати циклічні коди (ЦК) за допомогою твірних поліномів G(Х) степеня r = n-k, де r - число перевірочних символів в кодовому слові. Циклічні коди відносяться до різновиду поліноміальних кодів.

Операції кодування і декодування ЦК зводяться до відомих процедур множення і ділення поліномів. Для двійкових кодів ці операції легко реалізуються технічно за допомогою лінійних перемикальних схем (ЛПС), при цьому виходять відносно прості схеми кодеків, в чому полягає одна з практичних переваг ЦК.

Серед циклічних кодів особливе місце займає клас кодів, запропонованих Боузом і Чоудхурі і незалежно від них Хоквінгемом і CRC-коди.

Коди Боуза-Чоудхурі-Хоквінгема отримали скорочене найменування БЧХ- коди. БЧХ- коди є узагальненням коду Хеммінга на випадок виправлення декількох незалежних помилок. Окремими випадками БЧХ- коду є коди Файра, призначені для виявлення і виправлення серійних помилок, код Голея - код, що виправляє одиночні, подвійні і потрійні помилки (dmin=7), у кодах Рида-Соломона (РС- коди) символами коду є багаторозрядні двійкові числа.

Циклічний надлишковий код (Cyclic redundancy code, CRC) використовується для обчислення контрольних сум. Контрольна сума - спосіб цифрової ідентифікації деякої послідовності, який полягає в обчисленні контрольного значення її циклічного надлишкового коду. Алгоритм CRC базується на властивостях ділення із залишком двійкових многочленів, тобто многочленів над кінцевим полем GF(2). Значення CRC є по суті залишком від ділення многочлена, відповідного вхідним даним, на якийсь фіксований многочлен. CRC коди є основою багатьох стандартів передачі даних, а також використовуються для перевірки цілісності файлів.

2.3 Принципи побудови циклічних кодів

Циклічні коди є різновидністю поліноміальних кодів [1]. В таких кодах вважається, що елементи a1, a2, …an-1 деякого кодового слова є коефіцієнтами полінома від x:

(2.1)

Використовуючи це позначення можна визначити поліноміальний код як множину всіх многочленів степені не більше чим n-1, які містять як множник деякий фіксований многочлен g(x), який називається породжувальним многочленом. Тоді процес кодування можна подати як результат множення полінома m(x), що являє собою інформаційну послідовність на породжувальний многочлен g(x), а декодування як результат ділення на цей поліном.

При деяких значеннях n поліноміальні ходи характеризуються властивістю циклічності. Це означає, що циклічна перестановка кодового слова знову приводить до кодового слова даного коду.

Ідея побудови циклічних кодів ґрунтується на використанні многочленів, що не приводяться (простий многочлен). Простим многочленом називається многочлен, який не може бути поданий у вигляді добутку многочленів нижчої степені, тобто такий многочлен ділиться тільки на самого себе або на 1.

Многочлени, що не приводяться, при побудові циклічних кодів грають роль так званих твірних поліномів, від виду яких, власне і залежать основні характеристики отриманого коду: надмірність і корегуюча здатність.

У табл. 2.1 вказані многочлени, що не приводяться, із степенями k=1,2,3,4|.

Таблиця 2.1 -| Поліноми, що не приводяться, k=1,2,3,4|.

Страницы: 1, 2, 3