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

Висновок

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

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

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|.

Основні принципи кодування в циклічному коді полягають в наступному. Двійково-кодоване n - розрядне число представляється поліномом (n-1|) - ої степені деякої змінної х, причому коефіцієнтами полінома є двійкові знаки відповідних розрядів. Запис, читання і передача кодових комбінацій в циклічному коді проводиться починаючи із старшого розряду. Відповідно до цього правила, надалі самі числа і відповідні ним поліноми записуватимемо так, щоб старший розряд виявлявся справа.

Наприклад, число 110101 (нумерація розрядів, згідно вище приведеного правила, ведеться зліва направо від 0 до 5) буде представлено поліномом п'ятого ступені: 1 + х + х3. Слід зазначити, що циклічна перестановка розрядів в двійковому представленні числа відповідає множенню полінома на х, при якому хn замінюється 1 і переходить в початок полінома.

Здійснимо множення полінома, отриманого в попередньому прикладі на х. Отриманий поліном х + х2| + х4| + х6. Замінивши х6| на 1, остаточно 1 + х + х2| + х4| , що відповідає числу 111010.

Циклічний систематичний код n-значного числа складається з k інформаційних і r контрольних знаків, причому останні займають r молодших розрядів систематичного коду. Оскільки послідовна передача кодових комбінацій проводиться, як ми вже указували, починаючи із старших розрядів, контрольні знаки передаються в кінці коду. Утворення коду здійснюється за допомогою так званого твірного (породжуючого) полінома G(x), степені r і саме видом цього полінома визначаються всі властивості коду - надмірність і корегуюча здатність.

Кодовим поліномом, F(x), є поліном степені менше (k+r|), якщо він ділиться без залишку на твірний поліном G(x). Після передачі повідомлення, декодування полягає у виконанні ділення полінома H(x), що відповідає прийнятому коду, на G(x). За відсутності помилок H(x)=F(x) і ділення виконується без залишку. Наявність ненульового залишку указує на те, що при передачі або зберіганні сталися спотворення інформації. Для отримання систематичного циклічного коду використовується наступне співвідношення:

F(x)= xr| C(x)+ R(x) (2.2)

де C(x) - поліном, що представляє інформаційні символи (інформаційний поліном);

R(x) - залишок від ділення xk C(x) на G(x).

Розглянемо кодування 8-значного числа 10110111. Хай для кодування заданий твірний поліном 3-ої| степені G(x) = 1 + x + x3. Ділимо x3• C(x) на G(x):

C(x)= 1 + x2| + x3+| x5| + x6+| x7 |

x3| C(x)= x3| + x5+| x6| + x8+| x9| + x10|

Використовуючи співвідношення (2.2) знаходимо|находимо| F(x):

F(x)= ( x3| + x5+| x6| + x8+| x9| + x10| ) + x2|

Таким чином остаточно кодова комбінація, що відповідає F(x) має вигляд|вид|:

де 001 - контрольні розряди.

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

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

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

Дано твірний поліном G(1,0) =1101. Потрібно побудувати циклічний код з простого чотиризначного коду другим способом. Як приклад для побудови використовуємо початкову комбінацію С (1,0)=0011. Операція множення цієї комбінації на твірний поліном запишеться таким чином:

0010111 - це і є циклічний код для 0011.

В таблиці 2.2 наведені не систематичні циклічні коди для інформаційної послідовності при k=4.

Таблиця 2.2 - Циклічні коди (7,4)

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13