Курсовая работа по «Теории информации и кодирования»

printf("%d     ",c);

}

puts("");

}

//ниже правильным образом  считаются вероятности Х/У и  У/Х

puts("\n\nUslovnie veroyatnosti");

printf("X/Y   a     b     c     d     \n");

for (ch1=0;ch1<=3;ch1++) {

printf("%c    ",(char)('a'+ch1));

for (ch2=0;ch2<=3;ch2++) {

verXY[ch1][ch2]=(double)cXY[ch1][ch2]/cY[ch2];//тут  двигаемся по строчкам и делим  на С(у)

printf("%.3f ",verXY[ch1][ch2]);

}

puts("");

} 

puts("\n\nUslovnie veroyatnosti");

printf("Y/X   a     b     c     d     \n");

for (ch1=0;ch1<=3;ch1++) {

printf("%c    ",(char)('a'+ch1));

for (ch2=0;ch2<=3;ch2++) { 

verYX[ch1][ch2]=(double)cXY[ch2][ch1]/cX[ch2];//тут двигаемся по столбцам и делим на С(х)

printf("%.3f ",verYX[ch1][ch2]);

}

puts("");

}

//По матрицам P(X/Y) и P(Y/X) считаем H(X/Y) и H(Y/X)

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

temp=0.0;

for (i=0;i<4;i++)

            if (verXY[i][j]>=0.0000000001) temp+=-verXY[i][j]*log(verXY[i][j])/log(2.0);

entXlY+=verY[j]*temp;

}

printf("\nEntropiya X/Y %.3f",entXlY);

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

temp=0.0;

for (i=0;i<4;i++)

            if (verYX[i][j]>=0.0000000001) temp+=-verYX[i][j]*log(verYX[i][j])/log(2.0);;

entYlX+=verX[j]*temp;

}

printf("\nEntropiya Y/X %.3f",entYlX); 

printf("\nEntropiya nezav (X,Y) %.3f",entX+entY);

printf("\nEntropiya zav (X,Y) %.3f %.3f",entXlY+entY,entYlX+entX);

printf("\nVzaimnaya inf Y->X %.3f",entX-entXlY);

printf("\nVzaimnaya inf X->Y %.3f",entY-entYlX);

printf("\nOb`em %d",2*strlen(a));

getch();

}

 

 

 

Приложение 2. Листинг tik_lab2.

#include "stdio.h"

#include "conio.h"

#include "string.h"

#include "math.h"

 

//Максимальная длина строки

const int MAXL=150;

 

//структура сочетания

typedef struct

{

char x[MAXL];//комбинация

char code[MAXL];//код

double ver;//вероятность

} soch;

 

void show(soch *sochet[],int n);

 

//Кодирование сообщения  по готовым кодам

//soch- сочетания, n- колво, in- входная строка, out- полученный код, k- количество символов в комбинации

//Примечание: Из строки  берётся количество символов  кратное k, остальные отбрасываются

void encode(soch *sochet[],int n,char in[MAXL],char out[MAXL*5],int k) {

char tofind[MAXL];

int i=0,j;

out[0]='\0';

while (i<strlen(in)/k*k) {//отбрасываем  неполные комбинации

 

strncpy(tofind,in+i,k);tofind[k]='\0';//берём  нужную нам комбинацию из строки

 

for (j=0;(strcmp(tofind,sochet[j]->x));j++);//находим  соответсвующий код

 

strcpy(out+strlen(out),sochet[j]->code);//приписываем  код

i+=k;

}

}

 

//Декодирование сообщения  по готовым кодам

void decode(soch *sochet[],int n,char in[MAXL*5],char out[MAXL]) {

char tofind[MAXL];

soch *sortsochet[MAXL]; //копия входных  сочетаний, будет отсортирована

int i=0,j,ncode=0,scode=0;

char ch;

out[0]='\0';

//Sort

for(i=0; i<n; i++) sortsochet[i]=sochet[i];

soch *t;

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

for(int j=n-1; j>i; j--)

if (strcmp(sortsochet[j-1]->code,sortsochet[j]->code)>0){

t=sortsochet[j];sortsochet[j]=sortsochet[j-1];sortsochet[j-1]=t;

}

}

//

i=0;

while (i<strlen(in)) {//пока не прочитаем всё сообщение

ch=in[i];//берём символ текущий (1 или 0)

//находим подходящую комбинацию

while (sortsochet[ncode]->code[scode]!=ch)

ncode++;

scode++;//сдвигаемся к следующему символу

//Если код полный, значит  мы нашли комбинацию символов

if (sortsochet[ncode]->code[scode]=='\0') {

strcpy(out+strlen(out),sortsochet[ncode]->x);//сохраняем  её

scode=0;

ncode=0;

}

i++;

}

}

 

//вывод кодов

void show(soch *sochet[],int n)

{

double sredn=0,//среднее

ent=0;//энтропия

for (int i=0; i<n; i++) {

sredn+=sochet[i]->ver*strlen(sochet[i]->code);//копим  среднюю длину

ent-=sochet[i]->ver*log(sochet[i]->ver)/log(2.0);//энтропию

 

    printf("\n%s %.6f %s",sochet[i]->x,sochet[i]->ver,sochet[i]->code);//выводим

}

printf("\nEntropiya %f\n",ent);//выводим  энтропию

printf("Sr dlina %f\n",sredn);//среднюю  длину

printf("Izbitochnost %f\n",1-ent/sredn);//избыточность

}

 

//Построение кодов хаффмана

void haffman(soch *sochet[],int n){

//Сортируем вероятности  (методом пузырька)

soch *t;

for(int i=0; i<n; i++)

for(int j=n-1; j>i; j--)

if ((sochet[j-1]->ver < sochet[j]->ver)){

t=sochet[j];sochet[j]=sochet[j-1];sochet[j-1]=t;

}

//создаем дерево (с помощью  параллельных массивов)

int der_rod[2*MAXL];//родитель вершины

int der_bit[2*MAXL]={0};//бит вершины (символ)

double der_ver[2*MAXL]={0};//вероятность

int res_ver[2*MAXL]={0};

int res_i[2*MAXL]={0};

//задаем листья (все исходные  комбинации)

for (int i=0; i<n; i++) {

der_bit[i]=-1;

der_rod[i]=-1;

der_ver[i]=sochet[i]->ver;

}

//начинаем кодировку

int count=n;

while (1) {

int minn1,minn2;

//находим минимальные  вершины без кодов (и соответственно  без родителя)

//первая вершина

double min=2.0;

for (int i=0; i<count; i++) {

if (der_bit[i]==-1 && der_ver[i]<=min) {min=der_ver[i];minn1=i;}

}

//вторая вершина

min=2.0;

for (int i=0; i<count; i++) {

if (der_bit[i]==-1 && der_ver[i]<=min && minn1!=i) {min=der_ver[i];minn2=i;}

}

//присваиваем им коды

der_bit[minn1]=1;

der_bit[minn2]=0;

 

//если постороенно полное  дерево, то выходим

if (count==2*n-2) break;//условие выхода 

 

//иначе добавляем родителя 

der_bit[count]=-1;//бит родителя пока неизвестен

der_rod[count]=-1;//родителей пока нет

der_rod[minn1]=count;//приписываем первому сыну номер родителя

der_rod[minn2]=count;//приписываем второму сыну номер родителя

der_ver[count]=der_ver[minn1]+der_ver[minn2];//вероятность родителя = сумме вер. сыновей

 

count++; 

}

//от каждого листа идём  к корню дерева и запоминаем  код

for (int i=0; i<n; i++) {

int p=i,k=0;

while (p!=-1) {//пока не придём к корню

sochet[i]->code[k]='0'+der_bit[p];//приписываем символ 1 или 0

p=der_rod[p];

k++;

}

sochet[i]->code[k]='\0';//приписываем символ конца строки

//"разворачиваем" код,  т.к. он получился задом наперёд

for (int j=0;j<k/2;j++) {

char temp=sochet[i]->code[j];

sochet[i]->code[j]=sochet[i]->code[k-1-j];

sochet[i]->code[k-1-j]=temp;

}

}

}

 

//Построение кодов Шеннона-Фано: рекурсивная функция

//Аргументы:указатель на  сочетания,начало и конец кодируемого  участка, сумма вер-тей, номер  шага(глубина)

void fano_rec(soch *sochet[],int first,int last,double sump,int k){

double sum=0,//сумма первой группы

razn=2.0;//разница между группами

int i=first,//номер рассматриваемой комбинации

ss=-1;//количество комбинаций в первой группе

 

//в первую группу заносим  новые комбинации, пока разница  сумм вероятностей у групп  не будет минимальна

//Т.е. если при добавлении  новой комбинации разница групп  уменьшится, то добавляем

while (((razn > fabs(sump-2*(sum+sochet[i]->ver)) ) && (i<last))) {

sum+=sochet[i]->ver;//увеличиваем суммму вер-стей первой группы

sochet[i]->code[k]='0';//пишем нолm в код комбинации (она уже в первой группе)

ss+=1;

razn=fabs(sump-2*sum);

//во второй групппе  сумма (sump-sum), в первой sum, разница равна (sump-sum-sum) по модулю

i++;

}

while (i<=last) {sochet[i]->code[k]='1';i++;}//во второй группе прописываем нули

//запускаем рекурсию в  каждой из групп или заканчиваем  коды

    if (ss>0) fano_rec(sochet,first,first+ss,sum,k+1);

else sochet[first]->code[k+1]='\0';

    if (last-first-ss>1) fano_rec(sochet,first+ss+1,last,sump-sum,k+1);

else sochet[last]->code[k+1]='\0';

}

 

//Построение кодов Шеннона-Фано

void fano(soch *sochet[],int n){

//Сортируем вероятности

soch *t;

for(int i=0; i<n; i++)

for(int j=n-1; j>i; j--)

if ((sochet[j-1]->ver < sochet[j]->ver)){

t=sochet[j];sochet[j]=sochet[j-1];sochet[j-1]=t;

}

//Запускаем рекурсивную  функцию

fano_rec(sochet,0,n-1,1.0,0);

}

 

//Основная функция

int main(){

char str[]="abcaaaaabbacbaacccabaccbbaccbbddadda";

int i,j,n1=0,n2=0,n3=0;

char ch,ch1,ch2,ch3;

int c;

double ent=0;

double p[4];

soch *sochet3[64],*sochet2[16], *sochet1[4];

 

puts("Veroyatnosti");

printf("     p      c\n");

for (ch='a';ch<='d';ch++) {

printf("%c    ",ch);

c=0;

for (i=0;i<=strlen(str);i++)

if (str[i]==ch) c++;

        p[ch-'a']=(double)c/strlen(str);

printf("%.3f  %d\n",p[ch-'a'],c);

ent+=-p[ch-'a']*log(p[ch-'a'])/log(2.0);

}

printf("Entropiya %.3f\n",ent);

 

//формирование сочетаний

for (ch1='a';ch1<='d';ch1++) {

sochet1[n1]= new soch;

sochet1[n1]->ver=p[ch1-'a'];

sochet1[n1]->x[0]=ch1;

sochet1[n1]->x[1]='\0';

n1++;

for (ch2='a';ch2<='d';ch2++) {

sochet2[n2]= new soch;

sochet2[n2]->ver=p[ch1-'a']*p[ch2-'a'];

sochet2[n2]->x[0]=ch1;

sochet2[n2]->x[1]=ch2;

sochet2[n2]->x[2]='\0';

n2++;

for (ch3='a';ch3<='d';ch3++) {

sochet3[n3]= new soch;

sochet3[n3]->ver=p[ch1-'a']*p[ch2-'a']*p[ch3-'a'];

sochet3[n3]->x[0]=ch1;

sochet3[n3]->x[1]=ch2;

sochet3[n3]->x[2]=ch3;

sochet3[n3]->x[3]='\0';

n3++;

}

}

}

char kod[MAXL*5]={0};

char source[MAXL]={0};

fano(sochet1,n1);

fano(sochet2,n2);

fano(sochet3,n3);

printf("\nFano 1sim:");

show(sochet1,n1);

encode(sochet1,n1,str,kod,1);printf("kod: %s\n",kod);

decode(sochet1,n1,kod,source);printf("str: %s\n",source);

printf("\nFano 2sim:");

show(sochet2,n2);

encode(sochet2,n2,str,kod,2);printf("kod: %s\n",kod);

decode(sochet2,n2,kod,source);printf("str: %s\n",source);

printf("\nFano 3sim:");

show(sochet3,n3);

encode(sochet3,n3,str,kod,3);printf("kod: %s\n",kod);

decode(sochet3,n3,kod,source);printf("str: %s\n",source);

 

haffman(sochet1,n1);

haffman(sochet2,n2);

haffman(sochet3,n3);

printf("\nHaffman 1sim:");

show(sochet1,n1);

encode(sochet1,n1,str,kod,1);printf("kod: %s\n",kod);

decode(sochet1,n1,kod,source);printf("str: %s\n",source);

printf("\nHaffman 2sim:");

show(sochet2,n2);

encode(sochet2,n2,str,kod,2);printf("kod: %s\n",kod);

decode(sochet2,n2,kod,source);printf("str: %s\n",source);

printf("\nHaffman 3sim:");

show(sochet3,n3);

encode(sochet3,n3,str,kod,3);printf("kod: %s\n",kod);

decode(sochet3,n3,kod,source);printf("str: %s\n",source);

 

getch();

for (i=0;i<n1;i++) delete sochet1[i];

for (i=0;i<n2;i++) delete sochet2[i];

for (i=0;i<n3;i++) delete sochet3[i];

}

 

Приложение 3. Листинг tik_lab3.

 

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <math.h>

 

const int MAXL=200;

 

//Получение циклического  кода

void get_cicl_code(char *comb, char *poly, int r, char *code) {

__int64 a=0,b=0,c=2;

strcpy(code,comb);

//припишем к комбинации  нужное количество нулей

for (int i=0;i<r;i++) {

code[strlen(code)+1]='\0';

code[strlen(code)]='0';

 

}

 

//проведем деление по  модулю

for (int i=0;i<strlen(code)-strlen(poly)+1;i++) {

if (code[i]=='0') continue;

else {

for (int j=0;j<strlen(poly);j++) {

if (poly[j]=='1') {

if (code[i+j]=='1')

code[i+j]='0';

else code[i+j]='1';

}

}

}

}

//припишем 

for (int i=0;i<strlen(comb);i++) {

code[i]=comb[i]; 

}

}

 

//Получение номера разряда  с ошибкой

int get_cicl_mistake(char *code, char *poly) {

char temp[MAXL],ostatok[MAXL],ostatok2[MAXL];

strcpy(temp,code);

 

//проведем деление по  модулю

for (int i=0;i<strlen(temp)-strlen(poly)+1;i++) {

if (temp[i]=='0') continue;

else {

for (int j=0;j<strlen(poly);j++) {

if (poly[j]=='1') {

if (temp[i+j]=='1')

temp[i+j]='0';

else temp[i+j]='1';

}

}

}

}

 

//перепишем остаток

for (int i=0;i<strlen(poly)-1;i++)

ostatok[i]=temp[strlen(temp)-strlen(poly)+1+i];

ostatok[strlen(poly)-1]='\0';

//

temp[0]='1';

for (int i=0;i<strlen(code)-1;i++) temp[i+1]='0';

temp[strlen(code)]='\0';

 

int c=-1;

//проведем деление по  модулю

for (int i=0;i<strlen(temp)-strlen(poly)+1;i++) {

 

if (temp[i]=='1'){

for (int j=0;j<strlen(poly);j++) {

if (poly[j]=='1') {

if (temp[i+j]=='1')

temp[i+j]='0';

else temp[i+j]='1';

}

}

}

for (int j=0;j<strlen(ostatok);j++) ostatok2[j]=temp[1+i+j];//берём  остаток 

ostatok2[strlen(ostatok)]='\0';

if (strcmp(ostatok,ostatok2)==0) {c=i;break;}//если он равен полученному прежде, то выходим

}

 

if (c!=-1)

return strlen(temp)-strlen(poly)-c+1;//получаем номер разряда с ошибкой

else return -1;

}

 

//Код с постоянным весом

void get_code_ves(char *comb,char *code,int cz, int co) {

strcpy(code,comb);

int ccz=0,cco=0;

for (int i=0;i<strlen(code);i++) {

if (code[i]=='0') ccz++; else cco++;

}

for (int i=0;i<cz-ccz;i++) {

code[strlen(code)+1]='\0';

code[strlen(code)]='0';

}

for (int i=0;i<co-cco;i++) {

code[strlen(code)+1]='\0';

code[strlen(code)]='1';

}

}

 

//Код с проверкой на  четность

void get_code_chetn(char *comb,char *code) {

strcpy(code,comb);

int ccz=0,cco=0;

for (int i=0;i<strlen(code);i++) {

if (code[i]=='0') ccz++; else cco++;

}

 

if (cco%2==1) {

code[strlen(code)+1]='\0';

code[strlen(code)]='1';

} else {

code[strlen(code)+1]='\0';

code[strlen(code)]='0';

}

}

 

//Код с инверсией

void get_code_invers(char *comb,char *code) {

strcpy(code,comb);

int ccz=0,cco=0;

for (int i=0;i<strlen(code);i++) {

if (code[i]=='0') ccz++; else cco++;

}

 

if (cco%2==0) {

for (int i=0;i<strlen(comb);i++)

code[i+strlen(comb)]=comb[i]; }

else {

for (int i=0;i<strlen(comb);i++)

if (comb[i]=='0') code[i+strlen(comb)]='1'; else code[i+strlen(comb)]='0';

}

 

code[strlen(comb)*2-1]='\0';

}

 

//Код с удвоением

void get_code_udv(char *comb,char *code) {

strcpy(code,comb);

int ccz=0,cco=0;

for (int i=0;i<strlen(comb);i++) {

if (comb[i]=='0') {

code[i*2]='0';

code[i*2+1]='1';

} else {

code[i*2]='1';

code[i*2+1]='0';

}

}

code[strlen(comb)*2]='\0';

}

 

//Код грея

void get_code_grei(char *comb,char *code) {

strcpy(code,comb);

int ccz=0,cco=0;

for (int i=1;i<strlen(comb);i++) {

if (comb[i-1]=='1') {

if (code[i]=='0') code[i]='1'; else code[i]='0';

}

}

 

}

 

 

 

int main(){

char comb[]="10010";

char g[]="10011";

char code[MAXL];

int r=4;

 

printf("\nkomb %s",comb);

get_cicl_code(comb,g,r,code);

printf("\ncycle code %s",code);

code[3]='0';

int raz=get_cicl_mistake(code,g);

printf("\nrazr %d",raz);

 

get_code_ves(comb,code,15,15);

printf("\ncode_ves %s",code);

get_code_chetn(comb,code);

printf("\ncode_chetn %s",code);

 

get_code_invers(comb,code);

printf("\ncode_invers %s",code);

 

get_code_udv(comb,code);

printf("\ncode_udv %s",code);

 

get_code_grei(comb,code);

printf("\ncode_grey %s",code);

 

getch();

return 0;

}

 

Приложение 4. Листинг ЛабТиик№4.

 

#include "stdafx.h"

#include <stdio.h>

#include <string.h>

#include <conio.h>

 

#include <clocale>

#include <iostream>

 

 

#include <cstdlib>

 

 

using namespace std;

struct alphabet

{

char name;

int code;

};

 

void ABCFeling(struct alphabet A[])

{

A[0].name='a';

A[1].name='b';

A[2].name='c';

A[3].name='d';

A[4].name='e';

A[5].name='f';

A[6].name='g';

A[7].name='h';

A[8].name='i';

A[9].name='j';

A[10].name='k';

A[11].name='l';

A[12].name='m';

A[13].name='n';

A[14].name='o';

A[15].name='p';

A[16].name='q';

A[17].name='r';

A[18].name='s';

A[19].name='t';

A[20].name='u';

A[21].name='v';

A[22].name='w';

A[23].name='x';

A[24].name='y';

A[25].name='z';

 

for(int i=0;i<26;i++) A[i].code=0;

for(int i=0;i<26;i++) A[i].code=i+1;

//////////test 

//for(int i=0;i<26;i++) printf("%c  %d\n",A[i].name,A[i].code);

 

}

void GetClue(int C[],int n,struct alphabet ABC[])

{

  

   char s[12];

   puts("Введите ключ");

   scanf("%s",&s);

   for(int i=0;i<n; i++)

   { 

for(int j=0;j<26;j++)

if(s[i]==ABC[j].name) C[i]=ABC[j].code;

   }

  /////test

  // puts("Kluch\n"); for(int i=0;i<n; i++) printf("%d ",C[i]);

}

void Shifrovanie(struct alphabet STR[],int n, int C[],int nc,struct alphabet ABC[])