Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ КОДІВ ХЕМІНГА
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
РТ
Кафедра:
Кафедра Телекомунікації
Інформація про роботу
Рік:
2017
Тип роботи:
Інші
Предмет:
Інші
Група:
ТК-33
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка” Кафедра “Телекомунікації”
/
ДОСЛІДЖЕННЯ КОДІВ ХЕМІНГА
Львів 2017
Мета роботи
Дослідити процес виправлення однократних незалежних помилок систематичними кодами на прикладі досконалого коду Хемінга та ефекти розмноження помилок вищої кратності.
Теоретична частина.
Одним з найбільш поширених систематичних кодів є код Хемінга. Відомо декілька різновидностей цих кодів, що характеризуються різними коректуючими здатностями. До них кодів звичайно відносяться коди з мінімальною кодовою відстанню dmin=3, які виправляють всі одиночні помилки, і коди з відстанню dmin=4, які виправляють всі одиночні і виявляють всі подвійні помилки, або ж виявляють всі потрійні помилки.
Код Хемінга є одним з небагатьох досконалих кодів, для яких виконується ідеальне співвідношення між довжиною коду п та кількістю перевірочних r або інформаційних к розрядів, що випливає з виразу (1) для границі Хемінга:
п≤2 r-1 (1)
Досконалий код Хемінга має кодову відстань dmin=3 і відповідає випадку, коли досягається крайнє значення границі Хемінга: n=2 r-1.
Отже, його параметри
(n, k) = (2 r-1, 2 r-1-r),’
де r=2, 3,... - кількість перевірочних розрядів.
В табл.1 наведені параметри деяких кодів Хеммінга.
Коди Хемінга відносяться до швидких кодів.
Характерною особливістю матриці перевірки Н коду з dmin=3 є те, що її стовбці представляють собою будь-які ненульові комбінації довжиною r. Отже ми, наприклад, можемо отримати матрицю Н для коду (15, 11), з r=4 i n=15, записавши у двійковому вигляді всі числа від 1 до (2 r-1)=15 у вигляді стовбчиків матриці:
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
Н15,11= (2)
1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1
Перестановкою стовбців, що містять одну одиницю, дану матрицю можна звести до канонічної форми:
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0
1 1 1 0 0 0 1 1 1 1 0 1 0 0
Н15,11= (3)
0 1 1 0 1 1 0 0 1 1 0 0 1 0
1 1 0 1 1 0 1 0 1 0 1 0 0 0 1
Кодування
Знаючи матрицю Н, легко побудувати матрицю G і всі її робочі кодові комбінації.
Декодування
Отримавши кодову комбінацію (КК), ми обчислюємо синдром і дивимось, з яким стовбцем матриці він співпадає:
якщо синдром рівний нулеві, прийнята КК вважається правильною і з неї видаляємо перевірочні розряди;
якщо синдром не нульовий, тоді знаходимо номер стовбчика матриці Н, що рівний синдромові, і виправляємо помилку у розряді прийнятої КК, що має цей же номер, або робимо висновок, що прийнята КК - помилкова.
Хемінг запропонував використовувати матрицю Н не в канонічному вигляді (3), а у вигляді (2) -номер стовбчика у двійковому вигляді співпадає з елементами у цьому ж стовбчику.
Тоді перевірочні розряди КК повинні знаходитись не в кінці КК, а на номерах позицій, що відповідають степені 2: 20, 21, 22,..., 2 r-1.
У цьому випадку синдром, отриманий з прийнятої КК, буде двійковим номером розряда КК, у якому виникла помилка, що значно полегшує процес декодування.
Наприклад, для матриці (2) перевірочними будуть 1, 2, 4 та 8 розряди, а інформаційними - 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15. Повідомлення 11010101011 після кодування матиме вигляд 011110100101011. Якщо помилка виникла в 7-ому розряді, тоді прийнята КК буде 01110000101011 синдром, після підрахунку, буде мати вигляд 0111, тобто 710. Отже, помилка виникла в 7-у розряді.
Таблиця 1. Параметри кодів Хеммінга
k
r
n
R=r/n
d
k
r
n
R=r/n
d
4
3
7
0.429
3
4
4
8
0.5
4
11
4
15
0.267
3
11
5
16
0.312
4
26
5
31
0.161
3
26
6
32
0.188
4
57
6
63
0.095
3
57
7
64
0.109
4
120
7
127
0.055
3
120
8
128
0.063
4
247
8
255
0.031
3
247
9
256
0.035
4
502
9
511
0.0177
3
502
10
512
0.0195
4
1013
10
1023
0.0098
3
1013
11
1024
0.0107
4
Розширений код Хемінга має кодову відстань dmin=4 і може бути отриманий з досконалого коду Хеммінга шляхом додавання до нього перевірочного розряду, що є результатом суми по модулю два всіх символів кодової комбінації. Це код виду (2 r-1, 2 r-1-r), n ≤ 2 r-1.
Кодування виконується в два етапи:
-визначаєтся КК з використанням матриці H що відповідає досконалому коду
Хеммінга;
- додається ще один розряд, що дорівнює сумі по модулю два всіх розрядів КК, отриманої на першому етапі.
Матриця Н розширеного коду Хемінга буде мати вигляд (тобто (3) доповнена справа нулями, а знизу - одиницями):
0 0 0 0 0 0 1 1 1 1 1 1 1 1 0
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0
1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
H= (4)
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Декодування:
-обчислюється синдром, який відповідає досконалому коду Хеммінга; -перевіряється останнє перевірочне співвідношення.
При декодуванні може виникнути чотири наступні ситуації:
Синдром не дорівнює нулю, перевірка на парність виконується - двократна помилка.
Синдром не дорівнює нулю, перевірка на парність не виконується - однократна помилка.
Синдром дорівнює нулю, перевірка на парність виконується - нема помилок (до 2-х кратної включно).
Синдром дорівнює нулю, перевірка на парність не виконується - потрійна чи інша непарна помилка >3.
Хід роботи:
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
int main() {
bool array[6], array_2[6];
bool a,b,c,d,r1=0,r2=0,r3=0;
cout << "Enter your first binary number: "<<endl;
cin >> a;
cout << "Enter your second binary number: "<<endl;
cin >> b;
cout << "Enter your third binary number: "<<endl;
cin >> c;
cout << "Enter your fourth binary number: "<<endl;
cin >> d;
cout <<"Our code is: "<< a<< b<< c<< d<<endl;
cout <<"Add control bites, than our code is: "<<r1<<r2<<a<<r3<<b<<c<<d<<endl;
if ((a&b&d)==1) {
r1=1; }
else if (((a&b)==1)&(d==0)){
r1=0; }
else if (((a&d)==1)&(b==0)){
r1=0; }
else if (((d&b)==1)&(a==0)){
r1=0; }
else if ((a&b==0) & !(d==0)){
r1=1; }
else if (((a&d)==0) & (b==1)){
r1=1; }
else if (((d&b)==0) & (a==1)){
r1=1; }
else if ((a||b||d)==0) {
r1=0; }
else {
r1=1; }
cout <<"First control bit: "<<r1<<endl;
if ((a&c&d)==1) {
r2=1; }
else if (((a&c)==1)&(d==0)){
r2=0; }
else if (((a&d)==1)&(c==0)){
r2=0; }
else if (((d&c)==1)&(a==0)){
r2=0; }
else if ((a&c==0) & !(d==0)){
r2=1; }
else if (((a&d)==0) & (c==1)){
r2=1; }
else if (((d&c)==0) & (a==1)){
r2=1; }
else if ((a||c||d)==0) {
r2=0; }
else {
r2=1; }
cout <<"Second control bit: "<<r2<<endl;
if ((c&b&d)==1) {
r3=1; }
else if (((c&b)==1)&(d==0)){
r3=0; }
else if (((c&d)==1)&(b==0)){
r3=0; }
else if (((d&b)==1)&(c==0)){
r3=0; }
else if ((c&b==0) & !(d==0)){
r3=1; }
else if (((c&d)==0) & (b==1)){
r3=1; }
else if (((d&b)==0) & (c==1)){
r3=1; }
else if ((c||b||d)==0) {
r3=0; }
else {
r3=1; }
cout <<"First control bit: "<<r3<<endl;
array[0]=r1; array[1]=r2; array[2]=a; array[3]=r3; array[4]=b; array[5]=c; array[6]=d;
cout<<"Our code looks like: ";
for (int i = 0; i < 7; i++) {
cout << array[i]; }
//Decoder
int p,n0,n1,n2,n3,n4,n5,n6,m;
cout<<"Write in which number (1..7) of code was mistake: "<<endl;
cin>>p;
if (p==1){
r1=!r1; }
else {
r1=r1;}
if (p==2){
r2=!r2; }
else {
r2=r2;}
if (p==3){
a=!a;}
else {
a=a;}
if (p==4){
r3=!r3;}
else {
r3=r3;}
if (p==5){
b=!b;}
else {
b=b;}
if (p==6){
c=!c;}
else {
c=c;}
if (p==7){
d=!d;}
else {
d=d;}
bool p1,p2,p3;
cout <<"Our code with mistake is: "<< r1<< r2<< a<< r3<<b<< c<< d<<endl;
//FIRST CONTROL BIT
if ((r1||a||b||d)==0) {
p1=0; }
else if ((!r1||a||d||b)==0) {
p1=1; }
else if ((r1||!a||d||b)==0) {
p1=1; }
else if ((r1||a||!d||b)==0) {
p1=1; }
else if ((r1||a||d||!b)==0) {
p1=1; }
else if ((!r1||!a||!d||b)==0) {
p1=1; }
else if ((!r1||a||!d||!b)==0) {
p1=1; }
else if ((!r1||!a||d||!b)==0) {
p1=1; }
else if ((r1||!a||!d||!b)==0) {
p1=1; }
else if ((r1&a&b&d)==1) {
p1=0; }
else {
p1=0; }
cout <<"First control bit: "<<p1<<endl;
//SECOND CONTROL BIT
if ((r1||r2||b||c)==0) {
p2=0; }
else if ((!r1||r2||c||b)==0) {
p2=1; }
else if ((r1||!r2||c||b)==0) {
p2=1; }
else if ((r1||r2||!c||b)==0) {
p2=1; }
else if ((r1||r2||c||!b)==0) {
p2=1; }
else if ((!r1||!r2||!c||b)==0) {
p2=1; }
else if ((!r1||r2||!c||!b)==0) {
p2=1; }
else if ((!r1||!r2||c||!b)==0) {
p2=1; }
else if ((r1||!r2||!c||!b)==0) {
p2=1; }
else if ((r1&r2&b&c)==1) {
p2=0; }
else {
p2=0; }
cout <<"Second control bit: "<<p2<<endl;
//THIRD CONTROL BIT
if ((b||c||d)==0) {
p3=0; }
else if ((b&c&d)==1) {
p3=1; }
else if ((b&!c&!d)==1) {
p3=1; }
else if ((!b&c&!d)==1) {
p3=1; }
else if ((!b&!c&d)==1) {
p3=1; }
else {
p3=0; }
cout <<"Third control bit: "<<p3<<endl;
cout <<"Our code with contol bit is: "<<p1<<p2<<a<<p3<<b<<c<<d<<endl;
array_2[0]=p1; array_2[1]=p2; array_2[2]=a; array_2[3]=p3; array_2[4]=b; array_2[5]=c;
array_2[6]=d;
cout<<"Our code looks like: ";
for (int i = 0; i < 7; i++) {
cout << array_2[i]; }
cout<<endl;
if (array[0]!=array_2[0]) {
n0=1;
cout<<"Mistake is in first control bit"<<endl; }
else {
n1=0; }
if (array[1]!=array_2[1]) {
n1=2;
cout<<"Mistake is in second control bit"<<endl; }
else {
n1=0; }
if (array[2]!=array_2[2]) {
n2=3;
cout<<"Mistake is in first information bit"<<endl;}
else {
n2=0; }
if (array[3]!=array_2[3]) {
n3=4;
cout<<"Mistake is in third control bit"<<endl; }
else {
n3=0; }
if (array[4]!=array_2[4]) {
n4=5;
cout<<"Mistake is in second information bit"<<endl;}
else {
n4=0; }
if (array[5]!=array_2[5]) {
n5=6;
cout<<"Mistake is in third information bit"<<endl; }
else {
n5=0; }
if (array[6]!=array_2[6]) {
n6=7;
cout<<"Mistake is in fourth information bit"<<endl; }
else {
n6=0; }
m=n0+n1+n3;
if (m==3) {
a=!a; }
else {
a=a; }
if (m==5) {
b=!b; }
else {
b=b; }
if (m==6) {
c=!c; }
else {
c=c; }
if (m==7) {
d=!d; }
else {
d=d; }
cout<<"The source code was: "<<a<<b<<c<<d<<endl;
system("pause");
return 0;
}
22.12.2017 00:00
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора