ОТ - ДЗ (ещё одно готовое ДЗ)

Министерство образования РФ

Государственное образовательное учреждение

высшего профессионального образования

"Московский государственный технический университет

им. Н. Э. Баумана"

Домашнее задание

по предмету: "Основы телекоммуникаций"

Выполнил студент группы ИУ5-69:

Сидякин А.А.

Проверил преподаватель:

Галкин В.А.

Москва 2011

Корректирующая способность кода Хэмминга

Имеется канал связи, на вход которого подается закодированная кодом Хэмминга кодовая последовательность. В канале возможны ошибки любой кратности. Вектор ошибки может принимать значения от единицы в младшем разряде до единицы во всех разрядах кодового вектора. Для каждого значения вектора ошибки на выходе канала после декодирования определяется факт наличия ошибки и предпринимается попытка ее исправления.

Корректирующая способность кода определяется как отношение числа исправленных ошибок к общему числу ошибок данной кратности, которое определяется как число сочетаний из (длина кодовой комбинации) по (кратность ошибки – число единиц в векторе ошибок) - .

16 вариант:

Программная реализация кодирования информационного вектора кодом Хэмминга и алгоритм обнаружения и коррекции ошибки:

#include <stdlib.h>

#include <iostream.h>

#include <windows.h>

#include <math.h>

using namespace std;

const int d15[4] = {1,1,1,1},

d14[4] = {1,1,1,0},

d13[4] = {1,1,0,1},

d12[4] = {1,1,0,0},

d11[4] = {1,0,1,1},

d10[4] = {1,0,1,0},

d9[4] = {1,0,0,1},

d8[4] = {1,0,0,0},

d7[4] = {0,1,1,1},

d6[4] = {0,1,1,0},

d5[4] = {0,1,0,1},

d4[4] = {0,1,0,0},

d3[4] = {0,0,1,1},

d2[4] = {0,0,1,0},

d1[4] = {0,0,0,1};

// подсчёт контрольной суммы

void hash(int *codeham, int *codecrc)

{

int y, z, *code1 = codeham, *code2 = codecrc;

for(y=14; y>=0; y--)

{

if(code1[y]==1)

{

switch(y) {

case 14: for(z=0; z<4; z++) code2[z]=(code2[z]!=d1[z]); break;

case 13: for(z=0; z<4; z++) code2[z]=(code2[z]!=d2[z]); break;

case 12: for(z=0; z<4; z++) code2[z]=(code2[z]!=d3[z]); break;

case 11: for(z=0; z<4; z++) code2[z]=(code2[z]!=d4[z]); break;

case 10: for(z=0; z<4; z++) code2[z]=(code2[z]!=d5[z]); break;

case 9: for(z=0; z<4; z++) code2[z]=(code2[z]!=d6[z]); break;

case 8: for(z=0; z<4; z++) code2[z]=(code2[z]!=d7[z]); break;

case 7: for(z=0; z<4; z++) code2[z]=(code2[z]!=d8[z]); break;

case 6: for(z=0; z<4; z++) code2[z]=(code2[z]!=d9[z]); break;

case 5: for(z=0; z<4; z++) code2[z]=(code2[z]!=d10[z]); break;

case 4: for(z=0; z<4; z++) code2[z]=(code2[z]!=d11[z]); break;

case 3: for(z=0; z<4; z++) code2[z]=(code2[z]!=d12[z]); break;

case 2: for(z=0; z<4; z++) code2[z]=(code2[z]!=d13[z]); break;

case 1: for(z=0; z<4; z++) code2[z]=(code2[z]!=d14[z]); break;

case 0: for(z=0; z<4; z++) code2[z]=(code2[z]!=d15[z]); break;

}

}

}

}

// сравнение с исходной кодовой последовательностью

int checkwithhamm(int *crpthamm, int *hamming)

{

int ahm, erro = 0, *code1 = crpthamm, *code2 = hamming;

for(ahm=0; ahm<15; ahm++) {

if(code1[ahm]!=code2[ahm]) erro = 1;

}

return erro;

}

// сравнение с нулевой контрольной суммой

int checkcrc(int *codecrc)

{

int ac, err = 0, *code = codecrc;

for(ac=0; ac<4; ac++) {

if(code[ac]!=0) err = 1;

}

return err;

}

// перевод из двоичной в десятичную

int crc2digit(int *codecrc)

{

char bin[] = "0000";

int aa, b, c[4] = {0,0,0,0}, *code = codecrc;

for(aa=0; aa<4; aa++) bin[aa] = code[aa]+48;

b = atoi(bin);

for(aa=3; aa>=0; aa--) {

c[aa] = b%10;

b=b/10;

}

b = c[0]*pow(2,3)+c[1]*pow(2,2)+c[2]*pow(2,1)+c[3]*pow(2,0);

return b;

}

// коррекция

void correct(int *crpthamm, int dig)

{

int *code = crpthamm;

switch(dig){

case 15: code[0]=!code[0]; break;

case 14: code[1]=!code[1]; break;

case 13: code[2]=!code[2]; break;

case 12: code[3]=!code[3]; break;

case 11: code[4]=!code[4]; break;

case 10: code[5]=!code[5]; break;

case 9: code[6]=!code[6]; break;

case 8: code[7]=!code[7]; break;

case 7: code[8]=!code[8]; break;

case 6: code[9]=!code[9]; break;

case 5: code[10]=!code[10]; break;

case 4: code[11]=!code[11]; break;

case 3: code[12]=!code[12]; break;

case 2: code[13]=!code[13]; break;

case 1: code[14]=!code[14]; break;

}

}

// вывод результатов на экран

void display(int frst, int scnd, int thrd, int frth)

{

cout.width(10); cout << frst;

cout.width(10); cout << scnd;

cout.width(15); cout << thrd;

cout.width(30); cout << frth << endl;

}

int main()

{

// информация, красявости, приветствие

char greet1[38] = "16 вариант - Сидякин Артём, ИУ5-64(9)";

CharToOem(greet1, greet1);

char greet2[46] = "Домашнее задание по Основам Телекоммуникаций";

CharToOem(greet2, greet2);

char greet3[50] = "------------------------------------------------";

CharToOem(greet3, greet3);

char greet4[50] = "Корректирующая способность кода Хэмминга (15:11)";

CharToOem(greet4, greet4);

char greet5[35] = "Информационный вектор: 01010101111";

CharToOem(greet5, greet5);

cout << greet1 << endl << greet2 << endl << endl << greet4 << endl

<< greet3 << endl << endl << greet5 << endl;

int hamming[15] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

int infovect[11] = {0,1,0,1,0,1,0,1,1,1,1};

int crc[4] = {0,0,0,0}; // контрольная сумма

int i, a; // просто левые переменные для циклов и прочих нужд

// перенос из информационого вектора в код Хэмминга

a = 0;

for(i=0; i<15; i++) {

if(i!=14 && i!=13 && i!=11 && i!=7)

{

hamming[i]=infovect[a];

a++;

}

}

// проверка успешной подстановки информационного вектора в Хэмминга

// for(i=0; i<15; i++) cout << hamming[i]; cout << endl << endl;

for(i=14; i>=0; i--)

{

if(i!=14 && i!=13 && i!=11 && i!=7)

{

if(hamming[i]==1)

{

switch(i) {

case 12: for(a=0; a<4; a++) crc[a]=(crc[a]!=d3[a]); break;

case 10: for(a=0; a<4; a++) crc[a]=(crc[a]!=d5[a]); break;

case 9: for(a=0; a<4; a++) crc[a]=(crc[a]!=d6[a]); break;

case 8: for(a=0; a<4; a++) crc[a]=(crc[a]!=d7[a]); break;

case 6: for(a=0; a<4; a++) crc[a]=(crc[a]!=d9[a]); break;

case 5: for(a=0; a<4; a++) crc[a]=(crc[a]!=d10[a]); break;

case 4: for(a=0; a<4; a++) crc[a]=(crc[a]!=d11[a]); break;

case 3: for(a=0; a<4; a++) crc[a]=(crc[a]!=d12[a]); break;

case 2: for(a=0; a<4; a++) crc[a]=(crc[a]!=d13[a]); break;

case 1: for(a=0; a<4; a++) crc[a]=(crc[a]!=d14[a]); break;

case 0: for(a=0; a<4; a++) crc[a]=(crc[a]!=d15[a]); break;

}

}

}

}

char wait1[37] = "...идёт подсчёт контрольной суммы...";

CharToOem(wait1, wait1);

cout << wait1 << endl;

Sleep(1432); // прогресс-бар

char crcinfo[20] = "Контрольная сумма: ";

CharToOem(crcinfo, crcinfo);

cout << crcinfo;

for(a=0; a<4; a++) cout << crc[a];

cout << endl << endl;

char hamm[15] = "Код Хэмминга: ";

CharToOem(hamm, hamm);

cout << hamm;

for(i=0; i<15; i++) {

switch(i) {

case 7: hamming[i]=crc[3]; break;

case 11: hamming[i]=crc[2]; break;

case 13: hamming[i]=crc[1]; break;

case 14: hamming[i]=crc[0]; break;

}

}

for(i=0; i<15; i++) cout << hamming[i]; cout << endl;

cout << wait1 << endl;

Sleep(1432);

cout << crcinfo;

for(i=0; i<4; i++) crc[i]=0;

hash(hamming, crc);

for(a=0; a<4; a++) cout << crc[a];

cout << endl << endl;

system("PAUSE");

cout << endl << endl;

// -----------------------------------------------------------------------------

/*

Всякие нужные штуки

-------------------

for(i=0; i<15; i++) crpthamm[i] = hamming[i]; - восстановление исходной КП

for(i=0; i<4; i++) crc[i]=0; - обнуление контрольной суммы

*/

// копия кодовой последовательности для экспериментов

int crpthamm[15] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

for(i=0; i<15; i++) crpthamm[i] = hamming[i];

// сколько исправлено ошибок каждой разрядности

int errors[15] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, m = 0, x;

for(i=0; i<4; i++) crc[i]=0;

for(a=0; a<15; a++) {

crpthamm[a]=!crpthamm[a];

hash(crpthamm, crc);

correct(crpthamm, crc2digit(crc));

if(checkwithhamm(crpthamm, hamming)!=1) errors[0]++;

for(i=0; i<4; i++) crc[i]=0;

for(i=0; i<15; i++) crpthamm[i] = hamming[i];

}

x = 1;

for(a=13; a>=0; a--) {

for(i=14; i>=a; i--)

{

crpthamm[i]=!crpthamm[i];

}

// можно посмотреть повреждённую КП

// for(m=0; m<15; m++) cout << crpthamm[m];

hash(crpthamm, crc);

if (checkcrc(crc)==1) correct(crpthamm, crc2digit(crc));

if(checkwithhamm(crpthamm, hamming)!=1) errors[x]++;

for(m=0; m<4; m++) crc[m]=0;

for(m=0; m<15; m++) crpthamm[m] = hamming[m];

x++;

// cout << endl; - это относится к просмотру КП, феншуй

}

char kratn[10] = "Кратность";

CharToOem(kratn, kratn);

cout.width(10); cout << kratn;

char er[7] = "Ошибок";

CharToOem(er, er);

cout.width(10); cout << er;

char cor[11] = "Исправлено";

CharToOem(cor, cor);

cout.width(15); cout << cor;

char abil[27] = "Корректирующая способность";

CharToOem(abil, abil);

cout.width(30); cout << abil << endl;

cout << "-----------------------------------------------------------------"

<< endl;

display(1, 15, errors[0], 1);

display(2, 105, errors[1], 0);

display(3, 455, errors[2], 0);

display(4, 1365, errors[3], 0);

display(5, 3003, errors[4], 0);

display(6, 5005, errors[5], 0);

display(7, 6435, errors[6], 0);

display(8, 6435, errors[7], 0);

display(9, 5005, errors[8], 0);

display(10, 3003, errors[9], 0);

display(11, 1365, errors[10], 0);

display(12, 455, errors[11], 0);

display(13, 105, errors[12], 0);

display(14, 15, errors[13], 0);

display(15, 1, errors[14], 0);

// -----------------------------------------------------------------------------

cout << endl << endl;

system("PAUSE");