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

Основні принципи кодування в циклічному коді полягають в наступному. Двійково-кодоване 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.4 Аналіз CRC-кодів

Прикладом використання сімейства циклічних кодів є контроль помилок за допомогою циклічного надлишкового коду, тобто CRC - коду ( Cyclic redundancy check), які називають також кодом Абрамсона [1-3]. При передачі даних в пакетних режимах, ці коди використовуються для визначення цілісності блоків даних (FCS - Frame Checking Sequence). Прикладом систем з FCS є стандарти передачі даних Х.25 (HDSL), ISDN, DECT і LAN.

CRC кодами є розширення циклічних код Хеммінга. Хай р(Х) - примітивний многочлен степеня m, тоді породжуючий многочлен g(x) CRC коду, можна записати у вигляді добутку:

g(x)= (1 + Х)р(x). (2.3)

За допомогою породжуючого многочлена g(Х) може бути побудований циклічний CRC (n,k) -код з параметрами n = 2r - 1, k = 2r - r -2, що має r + 1 перевірочних символів і dmin = 4.

CRC-коди| володіють п'ятьма важливими властивостями:

Таблиця 2.3 - Породжувальні многочлени CRCкоду

1. Всі помилки кратності 3 або менше виявляються.

2. Всі помилки непарної кратності виявляються.

3. Всі пакети помилок довжини L = r + 1 або менше виявляються.

4. Частка пакетів помилок довжини L= r + 2, що не виявляються, складає 2-r .

5. Частка пакетів помилок довжини L ? r + 3, що не виявляються складає 2-(r-1).

Всі перераховані властивості дозволяють ефективно використовувати CRC-| код при передачі даних з (протокол ARQ). На практиці часто використовуються укорочені коди CRC У таблиці 2.3 приведені породжуючі многочлени CRC кодів, що найбільш вживаються а також вказані сфери їх застосування.

Здатність контрольної суми виявляти помилки логічніше вимірювати не в кількості помилкових бітів, а у ймовірності не виявлення помилки. При використанні CRC проходить непоміченими лише поєднання помилок, що задовольняють вельми спеціальній умові, а саме такі, вектор помилок (двійкове число, одиничні біти якого відповідають помилковим бітам прийнятого блоку, а нульові - правильно прийнятим) яких ділиться на G (твірний поліном) без остачі. При випадковому розподілі помилок ймовірність цього може бути грубо оцінена як 1/G, тому збільшення розрядності контрольної суми у поєднанні з вибором простих G забезпечує досить швидкий і дешевий спосіб перевірки цілісності навіть досить довгих блоків. 32- розрядний CRC забезпечує практично повну гарантію того, що дані не були пошкоджені, а 8-розрядний - упевненість, достатню для багатьох цілей.

Обчислення значення коду CRC| виконується за допомогою ділення многочлена, що відповідає початковому (поліном-повідомлення), на фіксований многочлен (поліном-генератор). Залишо від такого ділення і є код CRC, що відповідає початковому повідомленню. Для коду CRC-16 поліном-генератор має степінь 16, а для CRC-32 - 32. Поліноми-генератори підбираються спеціальним чином і стандартизовані Міжнародним консультативним комітетом з телеграфного і телефонного зв'язку (CCITT). Для CRC-16, наприклад, стандартним є поліном-генератор x16 + x12 + x5 + 1.

Розглянемо приклад побудови коду CRC-4 для повідомлення 11010111, використовуючи поліном-генератор x4+x3+x2+1. Початковому повідомленню відповідає поліном x7+x6+x4+x2+x+1, тобто нумерація бітів тут починається справа:

Поліному x2+1 відповідають біти 0101 - це і є CRC-4 код. Існують швидкі алгоритми для розрахунку CRC-кодів, що використовують спеціальні таблиці, а не ділення многочленів із залишком

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

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

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

Всі схеми завадостійкого кодування можна розділити на дві групи: кодування з виявленням помилок і кодування з виправленням помилок (корегуючі коди).

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

Коди Хеммінга це лінійні коди з відстанню dmin=3 та коди з відстанню dmin=4. Перші, виправляють всі одиничні помилки, а другі виправляють всі одиничні помилки і виявляють подвійні.

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

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

D=d1•d2, (2.4)

де d1 і d2 - мінімальні відстані складових кодів.

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

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

Найважливішими відмінностями згортних кодів від блокових є такі [8].

1. Згортні коди дозволяють проводити кодування і декодування потоків даних безперервно в часі.

2. Згортні коди не потребують блокової синхронізації.

3. Застосування згортних кодів дозволяє досягти дуже високої надійності передачі інформації.

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

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

(2.5)

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

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

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

Основні переваги і недоліки завадостійких кодів зведемо в табл. 2.4.

Таблиця 2.4 - Характеристики завадостійких кодів

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

Висновки

1. Корегуючі коди - основний метод захисту від дії завад при передачі і зберіганні даних.

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

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

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

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

І так CRC це залишок від ділення повідомлення на поліном. Тобто все повідомлення (файл, архів) ділимо згідно модулю на деяку константу (її називають поліномом). Залишок від ділення і є CRC. Ділення виконується з використанням поліноміальної арифметики, тобто арифметики без перенесень і позик. У поліноміальній арифметиці:

0+0= 0 0-0=0

0+1 = 1 0-1=1

1+0 = 1 1-0=1

1+1 = 0 1-1=0

Видно, що додавання в поліноміальній арифметиці - це те ж, що і віднімання, тобто це операція XOR - виключне або. У підручниках із дискретної математики її позначають кружком з косим хрестиком усередині. Ми позначатиму цю операцію значком ^, як в Сі або просто «+». У поліноміальній арифметиці 100 плюс 110 рівне 10, але 100 мінус 110 теж рівне 10. Немає ні знаку, ні певного порядку бітів. Всі біти рівнозначні, і це дуже важлива властивість для CRC. Якщо переставити декілька бітів в обох доданках, ті ж біти будуть переставлені в сумі: 1010 ^ 1100=0110.

Поміняємо місцями перші два і останні два біта: 1010 ^ 0011=10 01.

Біти можна представити як коефіцієнти многочлена (полінома). Тому арифметику називають поліноміальною, а дільник в алгоритмах CRC - поліномом.

При практичній реалізації зрозуміло, ділення поліномів відрізняється від наведеного в п. 2.2. Розглянемо два алгоритми обчисленні CRC [17].

Перший простий алгоритм, у якому виконується звичайне ділення в стовпчик, але замість віднімання використовують операцію XOR:

Нехай необхідно поділити повідомлення: 1101010 на число 101 (поліном):

1101010

^101

111010

^101

10010

^101

=====

110

^101

===

11

Тобто CRC=11. Саме так рахують CRC. Зауважте, що в кожному стовпчику ми віднімаємо старші біти 1-1=0. У наступних бітах можуть бути будь-які числа. Один раз ми отримали нуль в старшому біті, і нам довелося зсунути управо на 2 біта, а не на один. Отже, можна записати такий алгоритм (це не робочий код, він тільки показує алгоритм):

data - повідомлення (бітовий рядок), POLY - поліном

while(length(data)> length(POLY))

{r = TORBIT(data); // Виділяємо старший біт data

data <<= 1; //І викидаємо його з основного числа data

if(r)

data ^= POLY;

}

У стовпчиках ми зсували поліном 101 управо, кожного разу віднімаючи його з повідомлення. У цьому алгоритмі поліном залишається на місці, але ми «рухаємо» ділиме вліво. Якщо старший біт r дорівнює нулю, ми зсуваємо ще на один біт, не віднімаючи POLY. Константа POLY дорівнює поліному без старшої одиниці, тобто 01. Першу одиницю писати немає чого, оскільки двійкове число завжди починається з одиниці. Як працює цей код, легко зрозуміти на прикладі. Візьмемо те ж повідомлення 1101010 і той же поліном 101:

Крок 1. r = 1 // Відокремили перший біт

data = 101010 // r=1, тому виконуємо операцію XOR

^01

==

111010

Крок 2. r = 1

data = 11010

^01=====

10010

Крок 3. r = 1

data = 0010

^01

====

0110

Крок 4. r = 0 // XOR не виконуємо

data = 110

Крок 5. r = 1

data = 10

^01

==

11

Отже, алгоритм в цілому зрозумілий: ділимо data на POLY, отримуємо остачу CRC. І при діленні 0-1=1, 1+1=0 без перенесення.

Складність полягає в тому, що повідомлення може важити декілька мегабайт. Як же розділити його на поліном? Зверніть увагу, що при кожному проході циклу у нас міняються тільки 2 перших біта data. Значить, можна проходити через все повідомлення, читаючи в кожен момент часу невелику порцію даних (у нашому випадку - перші два біта).

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

Ідея табличного методу така: оброблятимемо по байту за один прохід циклу. Коли ми ділимо байт на поліном, у нас в залишку виходить деяке число, причому воно не залежить від інших байтів повідомлення. Ось це число ми можемо зберігати в таблиці для кожного ділимого байта. Маючи таку таблицю, отримуватимемо CRC для кожного байта за один прохід. Для прикладу, візьмемо слово, рівне 3 бітам, і короткий поліном 111. Хай повідомлення складається з 5 бітів, назвемо його abcde. Пройдемо наш старий алгоритм по кроках:

Крок 1. if(a)

bc ^= 11;

Крок 2. if(b)

cd ^= 11;

Крок 3. if(c)

de ^= 11;

Коли ми підрахували bcd і перейшли на другий крок, біт а вже не потрібний, і на подальші підрахунки він ніяк не впливає. Коли дійшли до останнього кроку, виявилися непотрібними біти а і b. А після третього кроку зіграв свою роль біт c, який тепер сходить із сцени. Те, що помінялися біти abc, вже не важливе, тому що на четвертому, п'ятому і так далі кроці вони не використовуватимуться. Але на цих трьох кроках якось змінилися біти de. І змінилися вони залежно від бітів abc.

Переберемо всі значення abc, починаючи з 000 і до 111:

000 (a=0, b=0, c=0) - жодне з умов не виконується, тому біти def не змінилися.

001 (a=0, b=0, c=1) - умова if(c) виконалася:

001def

^11

010 - умова if(b) виконалася, але після додавання одиниці до с виконалося також if(c). Запишемо під межею результат операції XOR над двома відповідними числами в бітах de:

Abc

010de

^11

^11

==

01

011 -- виконалася умова if(b), але біт с був при цьому обнулений, тому if(c) не спрацювало:

Abc

011de

^11

==

10

100 -- спрацювала умова if(a), яка викликало if(b). В результаті біт d буде підданий операції XOR з одиницею:

Abc

100de

^11

^11

==

10

101 - аналогічно, але біт «c» обнулився, і результат - нульовий:

Abc 101de

^11

^11

^11

==

01

Те ж саме ти можеш написати для 110 і 111. Зробимо масив t з індексами від 000 до 111, в якому зберігатимемо результати наших обчислень:

індекс значення

000 00

001 11

010 01

011 10

100 10

101 01

110 11

111 00

Тепер, використовуючи цю таблицю, розрахувати CRC можна значно швидше:

t - масив, abcdefghi - повідомлення

de ^= t[abc];

gh ^= t[def];

crc = ghi;

Якщо розширити 3-х бітне слово до 8 біт (байт) і взяти 8-бітний або 32-бітний поліном, то отримаємо готовий алгоритм для розрахунку CRC табличним методом. Схема обчислення CRC для випадку 32-бітного полінома наведена на рис. 3.1.

А на рис. 3.2 наведена граф-схема алгоритму обчислення CRC8. Тут Crc8Table це таблиця, що містить 256 байт, а змінна crc - обчислений CRC вхідного файлу.

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

3.2.1 Вибір мови програмування

Для розробки програми розрахунку CRC обрано середовище розробки Visual Studio 2008 і мову програмування C#.

Вибір мови C# пояснюється тим, що ця мова спеціально розроблена для нової платформи Microsoft. Вона, подібно до Java, дуже багато з погляду синтаксису запозичила в C++. На С# також сильно вплинув і Visual| Basic 6.0. В загальному можна сказати, що С# ввібрав в себе краще від самих різних мовах програмування.

У загальному можливості С# такі.

- Чітко визначений набір базових типів.

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

- Автоматична генерація XML-документів.

- Автоматичне очищення пам'яті.

- Підтримка бібліотеки базових класів .NET, але і з легким доступом до Windows API.

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

- Можливість використання для написання динамічних Wcb-сторінокNET і Web-служб

Зрозуміло, що більша частина перерахованого також торкаєтьсястосується Basic 2005 і керованого C++. Однак, оскільки С# спеціально спроектований для роботи з .NET, то він підтримує засоби .NET у повнішій мірі, і пропонує в цьому контексті| більш відповідний синтаксис, ніж інші мови.

Але є і ряд обмежень С#. Дана мова не призначена для критичних за часом додатків. Тут C++ продовжує залишатися лідером серед високорівневих мов програмування у цій області. С# бракує деяких ключових засобів для побудови високопродуктивних додатків, включаючи можливість специфікувати вбудовані функції і деструкції, які гарантовано запускаються в визначеній| точці коду. Проте пропорційне відношення таких додатків до їх загального числа надзвичайно низьке.

Щодо даної розробки, то значною перевагою C# є можливість легкого доступу до класу HashAlgorithm NET Framework Class Library. Методи цього класу значно спрощують програмну реалізацію алгоритмів обчислення CRC. Зокрема метод Clear() звільняє ресурси, які використовуються у класі HashAlgorithm, метод ComputeHash () обчислює CRC для вхідних даних, TransformBlock обчислює CRC для визначеної області даних.

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

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

Будемо використовувати проект WindowsFormsApplication та табличний метод розрахунку CRC. Програма дозволяє обчислювати CRC8, CRC32.

При програмній реалізації розроблених алгоритмів кодування використовуються такі керуючі форми Windows:

1. Windows Forms Controls by Function - головна форма додатку, на якій розміщуються інші компоненти.

2. Button Control - використовується п'ять форм Button для подачі команд підрахувати CRC, перевірити CRC файла, відкриття файлу для підрахунку CRC і запису CRC файлу на диск.

3. GroupBox Control - використовується дві форми даного типу - GroupBox1 та GroupBox2. Вони призначені для групування інших форм Windows.

4. TextBox Control - одина форма TextBox використовується для виведення шляху до файлу, CRC якого обраховується, а друга для виведення результатів обрахунку CRC. Обидві форми TextBox розміщені на формі GroupBox1.

5. Label Control - компоненти Label (2 шт.) призначені для виведення повідомлень оператору про інші компоненти інтерфейсу. Обидві форми Label Control розміщені на формі GroupBox1.

6. RadioButton Control - використовуються для вибору полінома для підрахунку CRC. Використовується три форми даного типу, які дозволяють вибирати поліном CRC4, CRC8 та CRC32, які розміщуються на формі GroupBox2.

Розташування форм наведено на рис. 3.8.

Для програмної реалізації запропонованих алгоритмів CRC-кодування розроблено такі основні процедури і функції:

1. Метод класу Form1 btBrowse_Click () відкриває стандартне вікно Windows вибору файла для підрахунку CRC:

var open = new OpenFileDialog

;

if (open.ShowDialog() == DialogResult.OK)

{

filename = open.FileName;

tbSource.Text = filename;

}

Метод класу Form1 btSave_Click () зберігає обчислений CRC в окремий файл на диск, додаючи перед іменем файлу, CRC якого обчислювався, префікс CRC32 або CRC8 в залежності від вибраного полінома і розширення CRC. Це текстовий файл, який містить 4 рядки:

D:\CRC32\CRC32.sln

23.05.2010 0:27:23

crc8

9F

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

2. Метод класу Form1 btCalc Click визначає вибраний поліном і викликає методи відповідного класу CRC для виконання обчислень:

if (CRC8.Checked)

{ var crc8 = new Crc8();

using (var f = File.Open(filename, FileMode.Open))

crc8.ComputeHash(f);

states = false;

tbResult.Text = crc8.CrcValue.ToString("x2").ToUpper();

} else

if (CRC32.Checked)

{

var crc32 = new Crc32();

using (var f = File.Open(filename, FileMode.Open))

crc32.ComputeHash(f);

states = true;

tbResult.Text = crc32.CrcValue.ToString("x2").ToUpper(); }

Тут використовуються методи класів CRC32 та CRC8, які є дочірніми для класу HashAlgorithm, зокрема метод..:: ComputeHash (), які обчислюють CRC табличним методом. Викликається на виконання при виборі кнопки «Підрахувати».

3. Метод класу Form1 btCheck_Click() обчислює CRC табличним методом і порівнює його з результатом, отриманим під час попередньої перевірки і збереженим на диск. Для цього необхідно вказати на початковий файл та файл з CRC цього файлу:

ініціалізація діалогу відкриття файлів

для файла що перевірятиметься

var open = new OpenFileDialog

;

додавання файла

if (open.ShowDialog() == DialogResult.OK)

{

fnm = open.FileName;

tbSource.Text = fnm;

}

ініціалізація фільтра для файла хеш-суми

open.Filter = "Хеш-сума (*.crc)|*.crc";

додавання файла

if (open.ShowDialog() == DialogResult.OK)

{

csm = open.FileName;

tbResult.Text = csm;}

А потім перевіряється рядок 3 файла з попереднім результатом:

if (crc == "crc8")

{ }

або

if (crc == "crc32")

{ }

І в залежності від цього обирається відповідний поліном, обчислюється CRC вибраного файла і порівнюється з попередньо обчисленим (рядок 4 у файлі з розширенням CRC). Викликається на виконання при виборі кнопки «Перевірити».

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

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

Дослідження виконувались з метою перевірки працездатності програми в двох режимах:

- CRC8 - використовувався поліном восьмої степені такого виду:

x8 + x5 + x4 + 1;

- CRC32 - використовувався поліном 32-ї степені такого виду:

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1.

Для прикладу візьмемо файл CRC32.sln (файл даного проекта) і підрахуємо його контрольну суму з використанням полінома CRC32. Для цього запустимо на виконання файл CRC.exe, виберемо файл CRC32.sln та тип полінома CRC32 і клацнемо по кнопці «Підрахувати». Головне вікно програми для цього випадку наведено на рис. 3.3.

Рисунок 3.3 - Результати роботи програми в режимі CRC32 для файла CRC32.sln

Крім того результати запишемо у файл crc32CRC32.crc клацнувши «мишею» по кнопці з зображенням дискети. Вміст цього файлу такий:

D:CRC32CRC32.sln

23.05.2010 0:24:49

crc32

6E1BD466

Тепер в початковий вміст файлу CRC32.sln внесемо зміни - останній рядок EndGlobal замінимо на EndLocal (рис. 3.4)

а)

б)

Рисунок 3.4 - Вміст файлу CRC32.sln: а - початковий вміст файлу; б - вміст файлу після зміни останнього рядка

Для зміненого файлу виконаємо перевірку, вибравши команду «Перевірити», яка пропонує вибрати початковий файл та файл CRC, а потім обчислює CRC для початкового файлу і порівнює його з результатом попереднього обчислення. Для даного випадку результати наведені на рис. 3.5.

Рисунок 3.5 - Перевірка зміненого файлу

Тобто зафіксовано зміну файлу і виведено новий CRC. Для незміненого файла аналогічна перевірка виведе інше повідомлення (рис. 3.6).

Рисунок 3.6 - Перевірка не зміненого файлу

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

Перевірку режиму CRC8 виконаємо з тим же файлом, внесемо аналогічні зміни і застосуємо ту ж саму методику. Результати наведені на рис. 3.7.

а) б)

Рисунок 3.7 - Тестування полінома CRC8: а - CRC8 до внесення змін; б- CRC8 після внесення змін

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

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

Представлена програма призначена для обчислення контрольних сум з використанням циклічних CRC - кодів і була розроблена в середовищі Visual Studio 2008 на мові програмування C#. Програма може працювати на комп'ютері з операційною системою Windows XP та встановленою платформою Microsoft.NET Framework 3.5 або на комп'ютері з операційними системами Windows Vista або Windows 7, в які інтегрована платформа Microsoft.NET Framework.

Програма дозволяє обчислювати контрольні суми CRC8, CRC32, а інтерфейс користувача включає також CRC4, який може бути реалізований при необхідності. Програма має зручний інтерфейс користувача, тому для керування нею не потрібно мати спеціальних навиків роботи на комп'ютері.

Щоб запустити програму на виконання потрібно вибрати файл CRC32.exe, що знаходиться у папці CRC32. Після запуску програми з'явиться головне вікно, яке наведено на рис. 3.8.

Рисунок 3.8 - Головне вікно програми

Для обчислення CRC необхідно виконати такі дії:

1. Вибрати тип полінома - CRC8 або CRC32.

2. Вибрати файл, клацнувши «мишею» на кнопці справа від поля «Шлях до файла», в результаті чого з'являється стандартне вікно вибору файла. Після вибору файла активується кнопка «Підрахувати».

3. Клацнути «мишею» по кнопці «Підрахувати». В полі «Результат обчислень» появиться CRC вибраного файлу.

4. При необхідності можна зберегти цей результат в файл клацнувши «мишею» по кнопці справа від поля «Результат обчислення». СRC буде збережено у файл ім'я, якого має такий формат:

Префікс Ім'я початкового файлу Розширення

Префікс - CRC8 або CRC32

Розширення - crc

Приклад для файлу read.txt - crc32read.txt.

Цей файл містить 4 рядки (див. також п. 3.3):

Перший рядок - шлях до файлу

Другий рядок - дата і час перевірки

Третій рядок - тип полінома

Четвертий рядок - обчислений CRC.

Приклад:

D:CRC32CRC32.sln

23.05.2010 0:24:49

crc32

6E1BD466

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

Для виконання перевірки необхідно вибрати команду «Перевірити». Відкриється стандартне вікно вибору файла, у якому необхідно вибрати файл, який ми хочемо перевірити і натиснути на кнопку «Открыть» (рис. 3.9). Після чого відкриється друге стандартне вікно вибору файлу, у якому необхідно вибрати відповідний файл з розширенням .crc.

а)

б)

Рисунок 3.9 - Вибір файлів при перевірці: а - вибір файлу для перевірки; б - вибір файлу з попереднім CRC для файлу, що перевіряється

Після виконання перевірки будуть виведені повідомлення про результати перевірки (рис. 3.5 - 3.6).

При виборі кнопки «Про програму» буде виведена інформація про дану роботу та її розробника (рис. 3.10).

Рисунок 3.10 - Вікно «Про програму»

Висновки

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

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