Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дослідження коректуючих кодів Хемінга
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Теорія інформації та кодування
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
/
Лабораторна робота № 2
з дисципліни
«Теорія інформації та кодування»
На тему:”Дослідження коректуючих кодів Хемінга”
Теоретичні відомості:
В системах передачі данних відбувається обмін дискретною інформацією між двома абонентами, одним із яких є комп'ютер, і ця інформація або вироблена комп’ютером, або буде ним використана. Фактично передача ведеться за допомогою двох значень сигналу, одне з яких відповідає двійковій цифрі 0, а друге 1, тобто двійковими n-розрядними комбінаціями. В таких комбінаціях елементи повідомлення (букви, цифри, інші символи) представляються побайтно. Одна з найважливих вимог- висока достовірність правильності прийому інформації, яка характеризується імовірністю помилкового прийняття одного елемента повідомлення. В окремих випадках вимагається, щоб ця імовірність не перевищувала 10-6, а інколи 10-8 - 10-9. При цьому передача інформації може здійснюватися на малі та значні відстані – в межах міста, республіки, всієї країни,між континентами - по існуючим або знову утвореним каналам зв’язку. Добре відомо, що в каналах зв’язку на сигнал діють шуми (завади), які його спотворюють, що в кінцевому рахунку призводить до помилкового прийому окремих елементів кодових комбінацій. Імовірність помилок залежить від інтенсивності завад. Найбільш часто використовуються комутовані телефонні канали, які характеризуються різними шумами досить високої інтенсивності. Це, як показує досвід, може приводити до досить частих спотворень елементів комбінацій, а нерідко – до “пакетів” (груп) спотворень.
Завадостійкі коди – один з найбільш ефективних засобів забезпечення високої вірності як при зберіганні, так і при передачі дискретної інформації. Створено спеціальну теорію завадостійкості кодування, що швидко розвивається останнім часом.
Основні принципи завадостійкого кодування
Для з'ясування ідеї завадостійкого кодування розглянемо двійковий код, що знайшов на практиці найбільш широке застосування. Нагадаємо, що двійковий код – це код із основою m = 2. Кількість розрядів n у кодовій комбінації прийнято називати довжиною або значністю коду. Символи кожного розряду можуть приймати значення 0 і 1. Кількість одиниць у кодовій комбінації називають вагою кодової комбінації і позначають w.
Ступінь відмінності будь-яких двох кодових комбінацій даного коду характеризується так званою відстанню між кодами d. Вона виражається числом позицій або символів, у яких комбінації відрізняються одна від одної, і визначається як вага суми за модулем два цих кодових комбінацій.
Помилки, внаслідок впливу завад, виявляються в тому, що в однім або декількох розрядах кодової комбінації нулі переходять в одиниці і, навпаки, одиниці переходять у нулі. В результаті створюється нова - помилкова кодова комбінація.
Якщо помилки відбуваються тільки в одному розряді кодової комбінації, то їх називають однократними. При наявності помилок у двох, трьох і т. д. розрядах помилки називають дворазовими, триразовими і т. д.
Експериментальні дослідження каналів зв'язку показали, що помилки символів при передачі по каналу зв'язку, як правило, групуються в пачки різної тривалості. Під пачкою помилок розуміють ділянку послідовності, що починається і закінчується помилково прийнятими символами. Всередині пачки можуть бути і правильно прийняті елементи.
Для вказання місць у кодовій комбінації, де є перекручування символів, використовується вектор помилки е. Вектор помилки n-розрядного коду – це n-розрядна комбінація, одиниці в якій указують положення перекручених символів кодової комбінації.
Вага вектора помилки we характеризує кратність помилки. Сума за модулем два для перекрученої кодової комбінації і вектори помилки дають вихідну невикривлену комбінацію.
Індивідуальне завдання:
Написати програму реалізації коду Хемінга. В програмі передбачити наступні функції:
• задання кількості перевірних символів;
• після цього слід знайти параметри коду;
• відобразити перевірні співвідношення;
• виконати кодування заданого інформаційного
блоку;
• дати можливість внести помилки;
• виконати декодування та виправлення однієї помилки.
2. Оформити звіт.
Проведені розахунки
Оскільки, усю програму було реалізовано мовою С++, то й усі обчислення було здійснено в ході виконання програми. Тому, вказую лише формули, які були необхідні для здіснення відповідних обчислень, а самі результати обчислень можна простежити на скріншоті реалізації програми та у С++-коді, який знаходиться у звіті:
Довжина коду Хемінга:
/
де, r – число перевірних розрядів коду.
Кількість інформаційних розрядів:
/
Кількість кодових комбінацій:
/
Потужність коду:
/
Надлишковість:
/
Імовірність невиявлених помилок:
/
де dmin – мінімальна кодова відстань, r – число перевірних розрядів коду; р0 – ймовірність спотворення двійкового символу (ймовірність помилки). Сni – кількість комбінацій.
Текст програми з коментарями:
#include<iostream>
#include<String.h>
#include<math.h>
using namespace std;
int main()
{
int a[32], a2[64],a3[10], c[10];
char a1[32];
cout << "\nEnter the bits ";
cin >> a1;
for (size_t i = 0; i < 32; i++)
{
a[i] = -1;
}
for (size_t i = 0; i < 10; i++)
{
a3[i] = pow(2, i);
}
int len_c = 0;
if (strlen(a1)+5 < pow(2, 5))
len_c = 5;
if (strlen(a1)+len_c-1 < pow(2, 4))
len_c = 4;
if (strlen(a1) + len_c - 1 < pow(2, 3))
len_c = 3;
if (strlen(a1) + len_c - 1 < pow(2, 2))
len_c = 2;
int k = 0;
int p = 0;
for (size_t i = 0; i < 64; i++)
{
k = 0;
for (size_t j = 0; j < 10; j++)
{
if (a3[j] == i)
k++;
}
if (k == 0)
a2[i - p] = i;
else
p++;
}
int a4[5][31];
int k1 = 0,b1 = 1;
for (size_t i = 0; i < 5; i++)
{
for (size_t j = 0; j <= 31; j++)
{
if (b1 == 0) {
a4[i][j] = 1;
k1--;
}
else {
a4[i][j] = 0;
k1++;
}
if (k1 == pow(2, i))
b1 = 0;
if (k1 == 0)
b1 = 1;
}
b1 = 1;
k1 = 0;
}
k1 = 0;
for (size_t i = 1; i < strlen(a1) + 1; i++)
{
a[a2[i]] = a1[i - 1] - 48;
}
for (size_t i = 1; i <= strlen(a1) + len_c; i++)
{
if (a[i] == -1) {
a[i] = 0;
for (size_t z = 1; z <= strlen(a1)+len_c; z++)
{
if (a4[k1][z] == 1 && z != pow(2, k1))
a[i] ^= a[z];
}
k1++;
}
}
//
cout << endl;
for (int i = 1; i<=strlen(a1)+len_c; i++)
cout << " " << a[i];
cout << "\nEnter number of wrong bit: ";
int z1;
cin >> z1;
//
a[z1] ^= 1;
k1 = 0;
//
cout << endl;
for (int i = 1; i <= strlen(a1) + len_c; i++)
cout << " " << a[i];
//
for (size_t i = 1; i <= len_c; i++)
{
c[i] = 0;
for (size_t z = 1; z <= strlen(a1) + len_c; z++)
{
if (a4[k1][z] == 1)
c[i] ^= a[z];
}
k1++;
}
//
int p1 = 0;
for (size_t i = 0; i < len_c; i++)
{
p1 += c[i + 1] * pow(2, i);
}
if (p1 == 0)
{
cout << "\nthere is no error in the data";
}
else
{
cout << "\nThere is error in the position " << p1;
if (a[p1] == 0)
a[p1] = 1;
else
a[p1] = 0;
cout << "\nThe correct code after error correction is\n";
for (int i = 1; i<=strlen(a1)+len_c; i++)
cout << " " << a[i];
cout << endl;
}
//декодування
cout << "\nThe decoding code is\n";
for (int i = 1; i <= strlen(a1) + len_c; i++) {
k = 0;
for (size_t j = 0; j < 10; j++)
{
if (a3[j] == i)
k++;
}
if (k == 0)
cout << " " << a[i];
}
cout << endl;
int h = (int)(pow(2, len_c) - 1);
k = strlen(a1);
double R = len_c / h;
setlocale(LC_ALL, "rus");
cout << "\nКiлькiсть iнформацiйних розрядiв: k = " << k;
cout << "\nКiлькiсть надлишкових розрядiв: r = " << len_c;
cout << "\nПотужнiсть коду: N(p) = " << pow(2, k);
cout << "\nНадлишковiсть: R = " << R;
cout << endl;
system("pause");
return 0;}
Реалізація програми:
/
Рис1. Реалізація програми.
Висновок:
На цій лабораторній роботі я вивчив побудову і основні характеристики коректуючих кодів Хемінга. Практично, я переконався, що при передачі по каналах зв'язку можуть виникаюти помилки. Причини їх можуть бути різні, але результат видається один – дані спотворюються і не можуть бути використані на прийомній стороні для подальшого опрацювання. Як правило, можливість перекручування біта в потоку переданих даних на рівні фізичного каналу знаходиться в межах 102...10-6. У той же час із боку користувачів і багатьох прикладних процесів часто висовується вимога до можливості помилок у прийнятих даних не гірше 10-6... 10-12. Для боротьби з виникаючими помилками відомо багато різноманітних способів.
Я використав один з таких способів, а саме, оскільки зрозуміло по умові завдання про наявність лише однієї помилки, то це упростило загальну картину реалізованого алгоритму. За допомогою кількох перевірок вдалось знайти необхідний біт з наявною у ньому помилкою, та просто проінвертувати відповідний біт.
14.10.2018 20:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора