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

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

5. В середовищі Visual Studio 2008 на мові програмування C# , розроблено програмне забезпечення яке дозволяє виконувати обчислення СRC8 та СRC32 табличним методом.

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

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

перелік посилань

1. Вернер М. Основы кодирования. Учебник для ВУЗов. Москва: Техносфера, 2004. - 288с.

2. http://ru.wikipedia.org/wiki/Crc

3. Лидовский В. В. Теория информации: Учебное пособие. - М.: Компания Спутник, 2004. - 111 с.

4. http://www.rarlab.com/

5. http://www.softsoft.ru/

6. Козловский В.О. Методические указания к выполнению экономической части дипломных проектов студентами технических специальностей. - Винница: ВГТУ, 1998. - 85 с.

7. Золотарёв В. В., Овечкин Г. В. Помехоустойчивое кодирование. Методы и алгоритмы: Справочник / Под. ред. чл.-кор. РАН Ю. Б. Зубарева. - М.: Горячая линия-Телеком, 2004. - 126 с.

8. Майданюк В. П. Кодування та захист інформації. Навчальний посібник. - Вінниця: ВНТУ, 2009. - 164 с.

9. Основы теории информации и кодирования/И. В. Кузьмин, В. А. Кедрус. - К: Вища шк., 1986. - 238 с.

10. Дмитриев В. И. Прикладная теория информации. - М.: Высш. шк., 1989. - 420 с.

11. Хэмминг Р. В. Теория кодирования и теория информации. Пер. с англ. - М.: Радио и связь, 1983. - 176 с.

12. Харкевич А. А. Борьба с помехами. - М.: Наука, 1965. - 270 с.

13. Блейхут Р. Теория и практика кодов контролирующих ошибки: Пер. с англ. - М.: Мир, 1986. - 576 с.

14. Основы теории передачи информации. Ч. 2. Помехоустойчивое кодирование/ В. И. Шульгин. - Учебное пособие. - Харьков: Нац. аэрокосм. ун-т «Харьк. авиац. ин-т», 2003. - 87 с.

15. Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. Пер. с англ. - М.: Радио и связь, 1987. - 392 с.

16. Банкет В. Л. Сверточные коды в системах передачи информации: Учеб. Пособие / Одесск. электротехн. ин-т связи им. А. С. Попова. Одесса, 1986. - 57 с.

17. http://www.xakep.ru/post/21788/default.asp?print=true

18. Троелсен. Э. С# и платформа .NET. Библиотека программиста. -- СПб.: Питер, 2004. --796 с.

19. Нейгел К. и др. C# 2005 и платформа .NET 3.0 для профессионалов.: Пер. с англ. - М.: ООО «И. Д. Вильямс», 2008. - 1376 с.

20. Навакатікян О.О., Кальниш В.В., Стрюков С.М.. Охорона праці користувачів комп'ютерних відеодисплейних терміналів. - К., 1997. - 400 с.

21. Правила охорони праці під час експлуатації електронно-обчислюваних машин.

22. Збірник нормативних актів, 2001.23. Є.А. Бондаренко. Використання нормативних актів про охорону праці користувачів електронно-обчислювальних машин. // Вінниця: ВДТУ, 2003. -100с.

23. Державні санітарні правила та норми 3.3.3.007-90. Вимоги електробезпеки до приміщень з електронно-обчислювальними машинами.

24. Методичні вказівки до виконання курсової роботи з дисципліни «Охорона праці». Захист від ураження електричним струмом . Загальні відомості безпеки та розрахунок занулення / Якубович В.П. - Вінниця: ВДТУ, 1997. 40.

Додаток А

(обов'язковий)

ВНТУ

ЗАТВЕРДЖУЮ

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

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

«_____» ________ 2010 р.

Технічне завдання

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

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

1.1 Найменування та галузь застосування

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

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

1.2 Підстава для проведення робіт

Завдання на роботу, яке затверджене на засіданні кафедри програмного забезпечення - протокол ______ від _______.

1.3 Мета та призначення роботи

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

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

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

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

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

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

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

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

1.4 Технічні вимоги

1. Тип коду - циклічний CRC-код.

2. Довжина поліномів - CRC8, CRC32.

3. Операційна система - Windows XP.

4. Мова програмування - C#

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

технічне завдання;

техніко-економічне обґрунтування;

лістинг програми.

1.6 Економічні показники

1. Сума усіх витрат на розробку програмного продукту - не більше 8000 грн.

2. Собівартість однієї копії - не більше 200 грн.

1.7 Стадії і етапи розробки

Завдання на проектування видане ___________ 2010 року. Проектування та дослідження повинно бути завершеним до __________ 2010 року.

1. Техніко-економічне обґрунтування технічного завдання на роботу _.

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

3. Розробка алгоритму кодування ___________.

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

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

6. Аналіз економічної ефективності розробки - ____________.

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

8. Оформлення пояснювальної записки і графічних матеріалів - __.

1.8 Порядок контролю і приймання

Порядок контролю і приймання роботи регламентується відповідними документами ВНТУ і державними стандартами.

Додаток Б

Текст програми CRC - кодування

using System;

using System.Collections.Generic;

using System.Linq;

using System.Windows.Forms;

namespace CRC32

{

static class Program

{

/// <summary>

/// The main entry point for the application.

/// </summary>

[STAThread]

static void Main()

{

Application.EnableVisualStyles();

Application.SetCompatibleTextRenderingDefault(false);

Application.Run(new Form1());

}

}

}

using System;

using System.IO;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using CRC;

namespace CRC32

{

public partial class Form1 : Form

{

public Form1()

{ InitializeComponent(); }

private string filename;

private bool states = false;

private void btBrowse_Click(object sender, EventArgs e)

{

var open = new OpenFileDialog

{

Multiselect = false,

Filter = "Всі файли(*.*)|*.*"

};

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

{

filename = open.FileName;

tbSource.Text = filename;

}

btCalc.Enabled = true;

}

private void btCalc_Click(object sender, EventArgs e)

{

try

{

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();

}

btSave.Enabled = true;

}

catch { MessageBox.Show("Вкажіть файл!!!","Увага!"); }

}

private void btAbout_Click(object sender, EventArgs e)

{

var f = new About();

f.Visible = false;

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

{ }

}

private void btCheck_Click(object sender, EventArgs e)

{

try

{ var fnm = "";

var csm = "";

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

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

var open = new OpenFileDialog

{

Multiselect = false,

Filter = "Всі файли(*.*)|*.*"

};

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

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;

}

//визначення crc32 для файла

//створення потоку та зчитування інформації

var fs = new StreamReader(csm);

fs.ReadLine();

fs.ReadLine();

var crc = fs.ReadLine();

var fcrc = fs.ReadLine();

fs.Close();

if (crc == "crc32")

{

var crc32 = new Crc32();

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

crc32.ComputeHash(f);

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

//порівняння нового CRC32 і добутого з файла

if (fcrc == crc32.CrcValue.ToString("x2").ToUpper())

{ MessageBox.Show("Файл переданий правильно!", "Увага!"); }

else

{ MessageBox.Show("Файл переданий неправильно!", "Увага!"); }

}

if (crc == "crc8")

{

var crc8 = new Crc8();

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

crc8.ComputeHash(f);

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

//порівняння нового CRC32 і добутого з файла

if (fcrc == crc8.CrcValue.ToString("x2").ToUpper())

{ MessageBox.Show("Файл переданий правильно!", "Увага!"); }

else

{ MessageBox.Show("Файл переданий неправильно!", "Увага!"); }

}

}

catch { MessageBox.Show("Помилка відкриття файлів!", "Увага!"); }

}

private void btSave_Click(object sender, EventArgs e)

{

try

{ var fi = new FileInfo(filename);

//визначення довжини імені файла без розширення

var index = fi.Name.Length - fi.Extension.Length;

var crc = states ? "crc32" : "crc8";

//генерування імені та шляху нового файла

var fname = fi.DirectoryName + "\\" + crc + fi.Name.Remove(index) + ".crc";

//створення потоку та запис даних про файл

var fs = new StreamWriter(fname);

fs.WriteLine(fi.FullName);

fs.WriteLine(DateTime.Now);

fs.WriteLine(crc);

fs.WriteLine(tbResult.Text);

fs.Close();

btSave.Enabled = false;

MessageBox.Show("Дані збережено\nШлях: " + fi.DirectoryName,"Увага!");

}

catch { MessageBox.Show("Помилка при збереженні файла!", "Увага!"); }

}

}

}

using System;

using System.Security.Cryptography;

namespace CRC

{

//CRC-32-IEEE 802.3 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 (V.42, MPEG-2, PNG[17], POSIX cksum)

public class Crc32 : HashAlgorithm

{

public const uint DefaultSeed = 0xffffffff;

readonly static uint[] CrcTable = new uint[] {

0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419,

0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4,

0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07,

0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,

0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856,

0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,

0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4,

0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,

0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3,

0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC, 0x51DE003A,

0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599,

0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,

0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190,

0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F,

0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E,

0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,

0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED,

0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,

0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3,

0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,

0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A,

0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5,

0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA, 0xBE0B1010,

0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,

0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17,

0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6,

0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615,

0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,

0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344,

0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,

0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A,

0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,

0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1,

0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA, 0xAF0A1B4C,

0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF,

0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,

0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE,

0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31,

0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C,

0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,

0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B,

0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,

0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1,

0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,

0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 0xA00AE278,

0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7,

0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66,

0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,

0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605,

0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8,

0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B,

0x2D02EF8D

};

uint crcValue = 0;

public override void Initialize()

{

crcValue = 0;

}

protected override void HashCore(byte[] buffer, int start, int length)

{

crcValue ^= DefaultSeed;

unchecked

{

while (--length >= 0)

{

crcValue = CrcTable[(crcValue ^ buffer[start++]) & 0xFF] ^ (crcValue >> 8);

}

}

crcValue ^= DefaultSeed;

}

protected override byte[] HashFinal()

{

this.HashValue = new byte[] { (byte)((crcValue >> 24) & 0xff),

(byte)((crcValue >> 16) & 0xff),

(byte)((crcValue >> 8) & 0xff),

(byte)(crcValue & 0xff) };

return this.HashValue;

}

public uint CrcValue

{

get

{

return (uint)((HashValue[0] << 24) | (HashValue[1] << 16) | (HashValue[2] << 8) | HashValue[3]);

}

}

public override int HashSize

{

get { return 32; }

}

}

// Поліном : 0x31 x^8 + x^5 + x^4 + 1

public class Crc8 : HashAlgorithm

{

public const ushort DefaultSeed = 0xff;

readonly static ushort[] Crc8Table = new ushort[256]{

0x00, 0x31, 0x62, 0x53, 0xC4, 0xF5, 0xA6, 0x97,

0xB9, 0x88, 0xDB, 0xEA, 0x7D, 0x4C, 0x1F, 0x2E,

0x43, 0x72, 0x21, 0x10, 0x87, 0xB6, 0xE5, 0xD4,

0xFA, 0xCB, 0x98, 0xA9, 0x3E, 0x0F, 0x5C, 0x6D,

0x86, 0xB7, 0xE4, 0xD5, 0x42, 0x73, 0x20, 0x11,

0x3F, 0x0E, 0x5D, 0x6C, 0xFB, 0xCA, 0x99, 0xA8,

0xC5, 0xF4, 0xA7, 0x96, 0x01, 0x30, 0x63, 0x52,

0x7C, 0x4D, 0x1E, 0x2F, 0xB8, 0x89, 0xDA, 0xEB,

0x3D, 0x0C, 0x5F, 0x6E, 0xF9, 0xC8, 0x9B, 0xAA,

0x84, 0xB5, 0xE6, 0xD7, 0x40, 0x71, 0x22, 0x13,

0x7E, 0x4F, 0x1C, 0x2D, 0xBA, 0x8B, 0xD8, 0xE9,

0xC7, 0xF6, 0xA5, 0x94, 0x03, 0x32, 0x61, 0x50,

0xBB, 0x8A, 0xD9, 0xE8, 0x7F, 0x4E, 0x1D, 0x2C,

0x02, 0x33, 0x60, 0x51, 0xC6, 0xF7, 0xA4, 0x95,

0xF8, 0xC9, 0x9A, 0xAB, 0x3C, 0x0D, 0x5E, 0x6F,

0x41, 0x70, 0x23, 0x12, 0x85, 0xB4, 0xE7, 0xD6,

0x7A, 0x4B, 0x18, 0x29, 0xBE, 0x8F, 0xDC, 0xED,

0xC3, 0xF2, 0xA1, 0x90, 0x07, 0x36, 0x65, 0x54,

0x39, 0x08, 0x5B, 0x6A, 0xFD, 0xCC, 0x9F, 0xAE,

0x80, 0xB1, 0xE2, 0xD3, 0x44, 0x75, 0x26, 0x17,

0xFC, 0xCD, 0x9E, 0xAF, 0x38, 0x09, 0x5A, 0x6B,

0x45, 0x74, 0x27, 0x16, 0x81, 0xB0, 0xE3, 0xD2,

0xBF, 0x8E, 0xDD, 0xEC, 0x7B, 0x4A, 0x19, 0x28,

0x06, 0x37, 0x64, 0x55, 0xC2, 0xF3, 0xA0, 0x91,

0x47, 0x76, 0x25, 0x14, 0x83, 0xB2, 0xE1, 0xD0,

0xFE, 0xCF, 0x9C, 0xAD, 0x3A, 0x0B, 0x58, 0x69,

0x04, 0x35, 0x66, 0x57, 0xC0, 0xF1, 0xA2, 0x93,

0xBD, 0x8C, 0xDF, 0xEE, 0x79, 0x48, 0x1B, 0x2A,

0xC1, 0xF0, 0xA3, 0x92, 0x05, 0x34, 0x67, 0x56,

0x78, 0x49, 0x1A, 0x2B, 0xBC, 0x8D, 0xDE, 0xEF,

0x82, 0xB3, 0xE0, 0xD1, 0x46, 0x77, 0x24, 0x15,

0x3B, 0x0A, 0x59, 0x68, 0xFF, 0xCE, 0x9D, 0xAC

};

ushort crcValue = 0;

public override void Initialize()

{

crcValue = 0;

}

protected override void HashCore(byte[] buffer, int start, int length)

{

crcValue ^= DefaultSeed;

unchecked

{

while (--length >= 0)

crcValue = Crc8Table[crcValue ^ buffer[start++]];

}

}

protected override byte[] HashFinal()

{

this.HashValue = new byte[] {(byte)(crcValue & 0xff)};

return this.HashValue;

}

public ushort CrcValue

{

get

{

return (ushort)(HashValue[0]);

}

}

public override int HashSize

{get { return 8; }}

}

}

ДОДАТОК В

ІЛЮСТРАТИВНИЙ МАТЕРІАЛ ДО ЗАХИСТУ ДИПЛОМНОЇ РОБОТИ

Завідувач кафедри ПЗ, д.т.н., професор _____________ А. М. Пєтух

Науковий керівник, к.т.н., доцент кафедри ПЗ ____ В. П. Майданюк

Рецензент, к.т.н., доцент кафедри ОТ ____________ О. І. Гороховський

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



Доповідь

шановні члени державної екзаменаційної комісії вашій увазі

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

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

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

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

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

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

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

Метою даної роботи є (читаєш плакат 1).

У відповідності до поставленої мети в роботі вирішуються такі завдання (читаєш плакат 1).

Плакат 2 (ліва колонка)

Розглянемо більш детально циклічні коди. Циклічні коди (ЦК) складають велику групу найширше використовуваних на практиці лінійних кодів. Їх основна властивість, полягає в тому, що кожен вектор, що отримується з початкового кодового вектора шляхом циклічної перестановки його символів, також є дозволеним кодовим вектором. Циклічні коди є різновидністю поліноміальних кодів [1]. В таких кодах вважається, що елементи (біти) a₁, a₂, …a_n-1 деякого кодового слова є коефіцієнтами полінома від x. Тоді процес кодування можна подати як результат множення полінома m(x), що являє собою інформаційну послідовність на породжувальний многочлен g(x), а декодування як результат ділення на цей поліном. Ідея побудови циклічних кодів ґрунтується на використанні многочленів, що не приводяться (простий многочлен), в якості породжувального многочлена.

Найчастіше циклічні коди будують в систематичній формі, тобто спочатку передаються інформаційні біти, а потім контрольні розряди. Побудова циклічного систематичного коду виконується згідно з виразом (показуєш на плакат 2 - формулу і читаєш колонку зліва). Корегуючий код, в тому числі і циклічний, який виявляє і виправляє декілька помилок характеризується великою надлишковістю - в два і більше раз бітів потрібно передавати або зберігати.

Плакат 2 (права колонка)

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

Розглянемо приклад побудови коду CRC-4 для повідомлення 11010111, використовуючи поліном-генератор x⁴+x³+x²+1. Початковому повідомленню відповідає поліном x⁷+x⁶+x⁴+x²+x+1. Тут нумерація бітів тут починається справа. Виконується ділення поліномів (Показуєш на плакат). В результаті отримаємо остаток від ділення R= x^2| +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#.

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

Вважаю, що дипломна робота заслуговує на оцінку «добре», а Кравець В. В. - присвоєння кваліфікації «спеціаліст».

Керівник дипломної роботи к.т.н., доцент каф. ПЗ В. П. Майданюк