«Московский государственный технический университет имени Н.Э. Баумана» (МГТУ им. Н.Э. Баумана)

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Московский государственный технический университет имени Н. Э. Баумана» (МГТУ им. Н. Э. Баумана)

Факультет информатика и управление (ИУ)

Кафедра Информационные системы и телекоммуникации (ИУ-3)

По курсу лекций «Теория информационных процессов и систем»,

3-й курс, 5-й семестр.

Отчет

по лабораторной работе №3

«Линейные блоковые коды»

Группа ИУ3-51 Б

Выполнила: Седов М. А.

Проверила: Руденкова Ю. С.

Москва, 2016

Цель работы:

Научиться кодировать и декодировать, используя линейные блоковые коды.

Задание:

1. Для порождающей матрицы

𝐺 =

найти проверочную матрицу H.

2. Спроектировать кодер и декодер для полученного линейного блокового кода.

3. Реализовать классы помехоустойчивого кодера и помехоустойчивого декодера.

4. Реализовать следующие интерфейсы передачи данных между объектами классов:

a. Кодер канала – помехоустойчивый кодер (передаются двоичные символы).

b. Помехоустойчивый кодер - канал передачи данных (передаются двоичные символы).

c. Канал передачи данных - помехоустойчивый декодер (передаются двоичные символы).

d. Помехоустойчивый декодер - декодер канала (передаются двоичные символы)

5. Реализовать схему, показанную на рис. 1, опираясь на результаты первой лабораторной работы.

6. Подать на вход источника данных текст длиной 10000 символов.

7. Смоделировать шум в канале, инвертируя каждый двоичный символ, который передается через канал связи, с вероятностью P(для моделирования можно использовать встроенный генератор случайных чисел). Подавая на вход источника данных текст длиной 10000 символов, и варьируя параметр P, сделать вывод о том, как влияют ошибки в канале на текст, полученный в приемнике.

Ход работы:

Найдем проверочную матрицу:

𝐻 = [ |𝐼 ]

, которая будет равна:

H =

Проверочная матрица обладает свойством:

· Вычисление размера алфавита, количество информационных битов, количество проверочных битов, создание таблицы символ-код (без проверочных символов).

map< char, int> map_c_i;

long k = 0; //количество символов в исходной файле

while(true)

{

char c = f. get();

if (f. eof()) break;

map_c_i[c]++;

k++;

}

intsizeAlph = 55; //Блок: длина блока 10 символов: из них 6 информационные и 4 проверочные.

intcorsizeAlph=map_c_i. size();

intlen_code, c_checkbits, c_databits;

c_databits=ceil(log(sizeAlph)/log(2)); //вычислениедлиныкодовогословапоформуле l=log2(sizeAlph)

c_checkbits=amount_check_bits(c_databits);

cout< < " c_databits: " < < c_databits< < " c_checkbits: " < < c_checkbits< < endl;

len_code=c_databits + c_checkbits;

cout< < " real: " < < corsizeAlph;

int count=0;

vector< shortint> code; //созданиевектора

int *ar = newint [c_databits];

map< char, vector< shortint> > table; //создание ассоциативного массива для таблицы соответствия символа и его кода

for (map< char, int>:: iteratoritr = map_c_i. begin(); itr! = map_c_i. end(); ++itr)

{

if (itr-> second)

{

dec_into_bin(count, c_databits, ar);

code. clear();

for (inti=0; i< c_databits; i++)

code. push_back(ar[i]);

table[itr-> first]=code;

count++;

}

delete[] ar;

for (map< char, vector< shortint> >:: iteratoriter = table. begin(); iter! = table. end(); ++iter) //Выводтаблицы: символ - код (безконтрольныйбитов)

{

cout< < " Символ: " < < iter-> first< < " Кодсимвола: ";

for(inti = 0; i< c_databits; i++)

cout< < iter-> second[i];

cout< < endl;

}

· Помехоустойчивый кодер – кодирует информацию, внося избыточность. Таким образом символы в пакете становятся связаны между собой некоторыми математическими операциями

f. clear(); f. seekg(0); // перемещаем указатель снова в начало файла

ofstream g(" encoded. bin", ios:: out | ios:: binary);

if (! g. is_open())

throw 12;

vector< int> check(4);

while(true)

{

char c = f. get();

if (f. eof()) break;

vector< shortint> x = table[c];

check[0]=x[0]^x[1]^x[3]^x[4];

check[1]=x[0]^x[2]^x[3]^x[5];

check[2]=x[1]^x[2]^x[3];

check[3]=x[4]^x[5];

g< < check[0]< < check[1]< < x[0]< < check[2];

for (inti=1; i< 4; i++)

g< < x[i];

g< < check[3]< < x[4]< < x[5];

}

g. close();

· Помехоустойчивый декодер – декодирует информацию и проверяет, возникли ли ошибки в канале связи, и если находит их, то пытается их исправить.

ifstream F(" encoded. bin", ios:: in | ios:: binary);

ofstream G(" output. txt", ios:: out);

if (! F. is_open())

throw 13;

if (! G. is_open())

throw 14;

int index;

vector< int> out(10);

vector< int> mis(4);

vector< int> res(6);

double noise;

constdoublever = 0. 9; // Вероятность инверсии символа (имитация шума)

while(true)

{

index=-1;

for (inti=0; i< 10; i++)

{

char c = F. get();

if (c=='0') out[i]=0;

else out[i]=1;

noise = ( 1 + rand() % 100 ) /100; //Добавлениешума noise[0; 1]

if (noise> ver)

out[i]=inverse(out[i]); //

}

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

if (out[0]^out[2]^out[4]^out[6]^out[8]! =0) mis[0]=1;

if (out[1]^out[2]^out[5]^out[6]^out[9]! =0) mis[1]=1;

if (out[3]^out[4]^out[5]^out[6]! =0) mis[2]=1;

if (out[7]^out[8]^out[9]) mis[3]=1;

if (mis[0]+mis[1]+mis[2]+mis[3]==0) index=-5;

elseif ((mis[0]==0) & & (mis[1]==0)) index=3;

elseif ((mis[0]==0) & & (mis[2]==0)& & (mis[3]==0)) index=1;

elseif ((mis[0]==0) & & (mis[2]==0)& & (mis[1]==0)) index=9;

elseif ((mis[1]==0) & & (mis[2]==0)& & (mis[3]==0)) index=8;

elseif ((mis[1]==0) & & (mis[2]==0)& & (mis[0]==0)) index=7;

elseif ((mis[2]==0) & & (mis[1]==0)& & (mis[3]==0)) index=0;

elseif ((mis[2]==0) & & (mis[3]==0)) index=2;

elseif (mis[3]==0) index=6;

elseif ((mis[0]==0) & & (mis[3]==0)) index=5;

elseif ((mis[1]==0) & & (mis[3]==0)) index=4;

if (index> 0)

out[index]=inverse(out[index]);

res[0]=out[2]; res[1]=out[4]; res[2]=out[5]; res[3]=out[6]; res[4]=out[8]; res[5]=out[9];

for (map< char, vector< shortint> >:: iteratoriter = table. begin(); iter! = table. end(); ++iter)

{

c4et=0;

for(inti = 0; i< 6; i++)

if(iter-> second[i]==res[i]) c4et++;

if (c4et==6) G< < iter-> first;

}

if (F. eof()) break;

}

F. close();

G. close();

Работапрограммы:

Программа использует файл input. txtдля считывания исходных данных. Затем кодирует (помехоустойчиво) полученное сообщение и записывает закодированный результат в файл code. txt. Затем в канал связи добавляется шум и происходит декодирование (помехоустойчивое) и его результат сохраняется в файл output. txt. Используется входной файл с текстом, размером в 10000 символов.

Рис. 1 - Входной файл input. txt

После помехоустойчивого декодирования текст остается вполне читаемым, хоть немного и отличается от исходного.

Рис. 2 - Выходной файл output. txt

Рис. 3 – Результат работы программы

Вывод:

• Добавление значительного шума(P=0. 9) малозаметно искажает текст, по сравнению с кодом без исправления ошибок. Там даже при P=0. 95 текст заметно искажался.

• С увеличением объема входного алфавита, уменьшается отношение проверочных битов к информационным, и как следствие уменьшается избыточность кода. Если входной алфавит 1 символ, то избыточность 66%; однако для объема алфавита в 1023 символа, избыточность меньше 1%.

• Так как данное кодирование равномерное, то размер закодированного файла больше, чем при оптимальном кодировании. Также увеличивают размер проверочные биты.

• Время выполнения кодирования и декодирования больше, по сравнению с кодированием Хаффмана, из-за исправления превентивных ошибок.

Листинг:

#include" stdafx. h"

#include< cmath>

#include< string>

#include< cstdio>

#include< iostream> //Библиотекадляпотокаввода\вывода

#include< vector> //Библиотека для вектора(однономерный массив)

#include< map> //Библиотека для ассоциативного массива

#include< list> //Библиотека для списка(дерева)

#include< fstream> //Бибилотка для работы с файлами

#include< ctime> //Библиотека для подсчета времени работы программы

#include< io. h> //Библиотека для определения размера файла

usingnamespacestd; //Объявление пространства имен

intsum = 0;

boolflag=false; //флаг, чтобы первый элемент имел код 0.. 00, а не 0.. 01

voiddec_into_bin(intdec, intsize, int *ar)

{

for (inti=0; i< size; i++) ar[i]=0;

int k=size-1;

while(dec> 1)

{

ar[k]=(dec%2);

dec=floor(dec/2);

k--;

}

if (flag) ar[k]=1;

flag=true;

//for (int i=0; i< size; i++) cout< < dec< < " -dec " < < ar[i]< < " -ar[i]" < < endl;

}

intamount_check_bits(intm)

{

int k=2;

while (k< log(k+m+1)/log(2))

k++;

return k;

}

int inverse(intk)

{

if (k==0) return 1;

elsereturn 0;

}

bool is_extend2 (intk, intlen_code)

{

flag=false;

for (inti=0; i< len_code; i++)

if (k==pow(2, i)) returntrue;

returnfalse;

}

int main(intargc, char *argv[])

{

clock_tstart_time = clock();

setlocale(LC_ALL, " Russian" );

cout< < " Программавыполняется. Ожидайте: " < < endl< < endl;

try

{

remove(" encoded. bin" );

remove(" output. txt" );

ifstream f(" input. txt", ios:: in);

if (! f. is_open())

throw 11;

//Начало: вычисление размера алфавита, количество информационных битов, количество проверочных битов, создание таблицы символ: код (без проверочных символов)

map< char, int> map_c_i;

long k = 0; //количество символов в исходной файле

while(true)

{

char c = f. get();

if (f. eof()) break;

map_c_i[c]++;

k++;

}

intsizeAlph = 55; //Блок: длина блока 10 символов: из них 6 информационные и 4 проверочные.

intcorsizeAlph=map_c_i. size();

intlen_code, c_checkbits, c_databits;

c_databits=ceil(log(sizeAlph)/log(2)); //вычислениедлиныкодовогословапоформуле l=log2(sizeAlph)

c_checkbits=amount_check_bits(c_databits);

cout< < " c_databits: " < < c_databits< < " c_checkbits: " < < c_checkbits< < endl;

len_code=c_databits + c_checkbits;

cout< < " real: " < < corsizeAlph;

int count=0;

vector< shortint> code; //созданиевектора

int *ar = newint [c_databits];

map< char, vector< shortint> > table; //создание ассоциативного массива для таблицы соответствия символа и его кода

for (map< char, int>:: iteratoritr = map_c_i. begin(); itr! = map_c_i. end(); ++itr)

{

if (itr-> second)

{

dec_into_bin(count, c_databits, ar);

code. clear();

for (inti=0; i< c_databits; i++)

code. push_back(ar[i]);

table[itr-> first]=code;

count++;

}

delete[] ar;

for (map< char, vector< shortint> >:: iteratoriter = table. begin(); iter! = table. end(); ++iter) //Выводтаблицы: символ - код (безконтрольныйбитов)

{

cout< < " Символ: " < < iter-> first< < " Кодсимвола: ";

for(inti = 0; i< c_databits; i++)

cout< < iter-> second[i];

cout< < endl;

}

//Конец: вычисление размера алфавита, количество информационных битов, количество проверочных битов, создание таблицы символ: код (без проверочных символов)

// Начало: кодирование(помехазащищенное) в файл

f. clear(); f. seekg(0); // перемещаем указатель снова в начало файла

ofstream g(" encoded. bin", ios:: out | ios:: binary);

if (! g. is_open())

throw 12;

vector< int> check(4);

while(true)

{

char c = f. get();

if (f. eof()) break;

vector< shortint> x = table[c];

check[0]=x[0]^x[1]^x[3]^x[4];

check[1]=x[0]^x[2]^x[3]^x[5];

check[2]=x[1]^x[2]^x[3];

check[3]=x[4]^x[5];

g< < check[0]< < check[1]< < x[0]< < check[2];

for (inti=1; i< 4; i++)

g< < x[i];

g< < check[3]< < x[4]< < x[5];

}

g. close();

// Конец: кодирование (помехазащищенное) в файл

f. close();

int c4et;

// Начало: декодирование из файла

ifstream F(" encoded. bin", ios:: in | ios:: binary);

ofstream G(" output. txt", ios:: out);

if (! F. is_open())

throw 13;

if (! G. is_open())

throw 14;

int index;

vector< int> out(10);

vector< int> mis(4);

vector< int> res(6);

double noise;

constdoublever = 0. 9; // Вероятность инверсии символа (имитация шума)

while(true)

{

index=-1;

for (inti=0; i< 10; i++)

{

char c = F. get();

if (c=='0') out[i]=0;

else out[i]=1;

noise = ( 1 + rand() % 100 ) /100; //Добавлениешума noise[0; 1]

if (noise> ver)

out[i]=inverse(out[i]); //

}

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

if (out[0]^out[2]^out[4]^out[6]^out[8]! =0) mis[0]=1;

if (out[1]^out[2]^out[5]^out[6]^out[9]! =0) mis[1]=1;

if (out[3]^out[4]^out[5]^out[6]! =0) mis[2]=1;

if (out[7]^out[8]^out[9]) mis[3]=1;

if (mis[0]+mis[1]+mis[2]+mis[3]==0) index=-5;

elseif ((mis[0]==0) & & (mis[1]==0)) index=3;

elseif ((mis[0]==0) & & (mis[2]==0)& & (mis[3]==0)) index=1;

elseif ((mis[0]==0) & & (mis[2]==0)& & (mis[1]==0)) index=9;

elseif ((mis[1]==0) & & (mis[2]==0)& & (mis[3]==0)) index=8;

elseif ((mis[1]==0) & & (mis[2]==0)& & (mis[0]==0)) index=7;

elseif ((mis[2]==0) & & (mis[1]==0)& & (mis[3]==0)) index=0;

elseif ((mis[2]==0) & & (mis[3]==0)) index=2;

elseif (mis[3]==0) index=6;

elseif ((mis[0]==0) & & (mis[3]==0)) index=5;

elseif ((mis[1]==0) & & (mis[3]==0)) index=4;

if (index> 0)

out[index]=inverse(out[index]);

res[0]=out[2]; res[1]=out[4]; res[2]=out[5]; res[3]=out[6]; res[4]=out[8]; res[5]=out[9];

for (map< char, vector< shortint> >:: iteratoriter = table. begin(); iter! = table. end(); ++iter)

{

c4et=0;

for(inti = 0; i< 6; i++)

if(iter-> second[i]==res[i]) c4et++;

if (c4et==6) G< < iter-> first;

}

if (F. eof()) break;

}

F. close();

G. close();

//Конец: декодированиеизфайла

clock_tend_time = clock();

cout< < " Время выполнения программы: " < < (end_time - start_time) / 1000. 0 < < " сек. " < < endl;

}

catch (inter)

{

switch (er)

{

case 11:

cout< < " Error: Невозможно открыть исходный файл";

break;

case 12:

cout< < " Error: Невозможно создать файл для кодирования";

break;

case 13:

cout< < " Error: Невозможно открыть файл для кодирования";

break;

case 14:

cout< < " Error: Невозможно создать выходной файл";

break;

default:

cout< < " Error: Возникла неизвестная ошибка";

break;

}

cout< < endl< < endl;

system(" pause" );

return -1;

}

system(" pause" );

return 0;

}