Міністерство освіти і науки
Відкритий міжнародний університетрозвитку людини ”Україна”
Лабораторна робота №1
З предмету:
Контроль і діагностика програмних систем
На тему:
Перевірка коду на парність
Виконала
студенткагрупи ПА-41
РуденкоО.М.
Перевіриввикладач
КапшукО.О.
Київ – 2010
Лабораторнаробота №1
Теоретична частина
Припустимо,що ми передаємо інформацію, використовуючи деякий канал зв’язку (наприклад,телефонну лінію). В процесі передачі інформація може спотворюватися, томувиникає задача розроблення прийомів, які дали б змогу або зробити такіспотворення неможливими або звести можливі спотворення до мінімуму. Суть такихприйомів полягає в тому, що перед відсиланням інформації до каналу зв’язкурозкодовують.
Найпростішийкод з перевіркою на парність полягає в тому, що ми дописуємо до послідовності знулів та одиниць, яку збираємося пропустити через канал зв’язку, ще один символ(0 або 1) так, щоб загальна кількість одиниць стала парною. Наприклад до слова00101 дописуємо 0, а до слова10101 дописуємо 1. одержуємо довші слова 001010 та101011, які передаємо. На виході з каналу зв’язку спочатку підраховуютьпарність кількості входжень одиниць в одержаному слові. Якщо ця кількістьпарна, то роблять висновок, що помилки при передачі не з’явилося, а процесдекодування полягає просто у закресленні останнього символу в одержаному слові.Якщо ж кількість одиниць в одержаному слові виявилась непарною, то можна лишезробити висновок, що при передачі з’явились помилки, але не можна відновитипередане слово. Кажуть, що такий код виявляє помилки, тоді як розглянутий вищекод з повтореннями не лише їх виявляє, а й виправляє.
Розглянутийкод дуже елементарний, тому має серйозні недоліки. Предмет теорії кодуванняполягає у створенні досконаліших кодів, які б об’єднували переваги і не малинедоліків щойно розглянутих кодів.
Практична частина
1Запишемо усі інформаційні розряди в комірки B11: I11.
2.У комірку J11 запишемо формулу для підрахунку парності або непарності одиниць вінформаційних розрядах — =ОСТАТ(СУММ($B11:$I11)+1;2) .
/>
/>
Формулазаписує 1 в розряд контролю, якщо кількість одиниць в інформаційних полях парнаабо 0 — якщо непарна.
3Аналогічно заповнюємо комірки B19: J19
/>
4.Почергово вносимо однократну, двократну та трьохкратну помилки.
/>
5.З наведених результатів видно програма в змозі знаходити непарну кількістьпомилок, але не здатна знаходити парну кількість
Висновок
Підчас виконання роботи я засвоїла основні методи контролю помилок.
Міністерство освіти і науки
Відкритий міжнародний університетрозвитку людини ”Україна”
Лабораторна робота №2
З предмету:
Контроль і діагностика програмних систем
На тему:
Построение груповыхкодов и их применение для обнаружения и исправления ошибок
Виконавстудент групи ПА-41
РуденкоО.
Перевіриввикладач
КапшукО.О.
Київ – 2010
Лабораторнаробота №2
Теоретична частина
Лінійним блоковим(n,k)кодом – називається безліч N послідовностей довжини n над GF(q),званих кодовими словами, які характеризується тим, що сума двох кодових слів єкодовим словом, а твір будь-якого кодового слова на елемент поля також єкодовим словом.
ЗазвичайN=qk, де до — деяке ціле число.Якщо q=2, лінійні коди називаютьсягруповими, оскільки кодові слова утворюють математичну структуру, звану групою.При формування цієї коди лінійною операцією є підсумовування по mod2. Способи завданнялінійних кодів
1.Перерахуванням кодових слів, тобто складанні списку всіх кодових слів коди.
Приклад.У таблиці 1 представлені всі кодові слова (5,3) — коди (ai — інформаційні, а bi — перевірочні символи). Таблиця 1
№/> a1 a2 a3 b1 b2 1 1 1 2 1 1 1 3 1 1 1 4 1 1 5 1 1 1 1 6 1 1 1 7 1 1 1 8
2.Системою перевірочних рівнянь, що визначають правила формування перевірочнихсимволів по відомих інформаційних:
/>
де
j — номер перевірочного символу;
i — номер інформаційного символу;
hij — коефіцієнти, що приймаютьзначення 0 або 1 відповідно до правил формування конкретних групових код.
Приклад.Для коди (5,3) перевірочні рівняння мають вигляд:
b1= a2 + a3;
b2= a1 + a2.
3.Матричне, засноване на побудові матриць, що породжують і перевірочної.
Векторнийпростір Vn над GF(2) включає 2n векторів (n-последовательностей), а підпростором його ємножина з 2k кодових слів довжини n, якеоднозначно визначається його базисом, що складається з до лінійно незалежнихвекторів. Тому лінійний (n,k) — код повністю визначаєтьсянабором з до кодових слів, що належать цьому коду. Набір з до кодових слів,відповідних базису, зазвичай представляється у вигляді матриці, яка називаєтьсятакою, що породжує.
Приклад.(5,3) — код, який був представлений в таблиці 1, може бути заданий матрицею
/>
Рештакодових слів виходить складанням рядків матриць в різних поєднаннях.
Загальнакількість різних варіантів що породжують матрицю визначається виразом
/>
Длявиключення неоднозначності в записі G(n,k) вводять поняття про канонічну або систематичну форму матриці, яка маєвигляд
/>
де
Ik — одинична матриця, щомістить інформаційні символи;
Rk,r — прямокутна матриця,складена з перевірочних символів.
Приклад.Матриця, що породжує, в систематичному вигляді для (5,3) — коди
/>
МатрицяG(n,k), що породжує, в систематичномувигляді може бути отримана з будь-якої іншої матриці за допомогою елементарнихоперацій над рядками (перестановкою двох довільних рядків, заміною довільногорядка на суму її самій і ряду інших) і подальшою перестановкою стовпців.
Перевірочнаматриця в систематичному вигляді має вигляд
/>
де Ir — одинична матриця;/> — прямокутна матриця втранспонованому виді матриці Rk,r зматриці, що породжує.
Приклад.Перевірочна матриця (5,3) — коди
/>
Практична частина
1. Запишемо генеруючу матрицю.
кол строк = длине инфор = 4 1 1 1
G 7,4 = 1 1 1 1 1 1 1 1 1 1
информационая часть = 10 => 1 0 1 0
X = 1 1 1 1
2. На основі неї створимо перевірочну.
кол строк =
длине пров
= 3 1 1 1 1
H = 1 1 1 1 1 1 1 1
3. Запишемо наші інформаційні поля та згенеруємоперевірочні поля.Х= 1 1 1 1
исползуя соотношение H * X^T = S если S = 0 то ош в код комб нет в прот случ с имеет вид s1 1 результат декодиров
S = s2
s3 error
4. Внесемо помилку.
X = 1 1 1
5. Ми отримали скореговане значення.
1 1 1 1
s1 результат декодиров
S = s2
s3 знач верно /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Висновок
Під час виконання роботи я написала програму щовиявляє та виправляє однократну помилку в повідомленні, а також знаходить багатократніпомилки.
Міністерство освіти і науки
Відкритий міжнародний університетрозвитку людини ”Україна”
Лабораторна робота №3
З предмету:
Контроль і діагностика програмних систем
На тему:
КодиХемминга
Виконаластудентка групи ПА-41
РуденкоО.
Перевіриввикладач
КапшукО.О.
Київ – 2010
/>
Теоретична частина
/>
/>
/>
Практична частина
Проверочная матрица для кода Хемминга
кол строк =
длине инфор. = 4 1 1 1 1 1 1 1 1
H 15,4 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
перепишем ее, переставив столбцы с одной единицей вконецa1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 b1 b2 b3 b4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
на ее основе создадим генерирующюю матрицу
информационая часть = 10 => 1 0 1 0
кол строк = длине инфор. = 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
G 15,4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Кодер
информационая часть = 10 => 1 0 1 0
1
1
X отпр = 1 1 1
Декодер
Х получ 1 1 1
исползуя соотношение H * X^T = S если S = 0 то ош в код комб нет в прот случ с имеет вид
результат декодиров
знач верно
s1
S = s2 s3 s4
Скоректированоезначение 1 1 1