信息论编码作业-小组

1、 一信息论编码作业小组成员：吴湛S1209G106、彭利S1409W0516、王红建S140900748文件说明：信息论作业。要求是信源编码、信道编码、信道加噪声、信道译码、信源译码。此程序已实现信源编码和信源译码，信道加噪声，信道编码和信道译码的功能。信源编码的具体实现方法：对于霍夫曼编码时的字符概率统计方法（这里并非是求出字符概率，因为概率和字符出现的频率是倍数关系，所以这里直接使用字符的频率），首先创建一个表头，当读入一个字符时就去查寻这个链表（详见link_func.c中的find函数），若发现已有读入的这个字符，那么就在匹配的结构单元中num成员加一，如果没有匹配的结构单元说明发现了

2、一个新字符，就在链表最后加一节点（详见link_func.c中的add_unit函数）。对于霍夫曼编码时的编码具体实现方法如下示意图所示：1） 对链表进行排序（详见link_func.c中的char_sort函数），并将最后两个分别赋1和0，如图一所示。（这里排序用冒泡法的思想对链表排序，当两个字符的次数相等时，也进行字符的交换，这样可减小编码长度的方差。对于节点的赋值，见link_func.c中的set_num函数，当被赋值的节点存在brothe支链时，该支链上的所有节点都赋于此值）。 图一2）将最后一个num的值加到前一个num的值上，并将最后一个节点挂到前一个节点的brothe支链上的最

3、后一个位置，排序，再将最后两个节点分别赋1和0，若存在brothe 支链，则连同支链上的所有节点设置相应的值。如图二所示。 图二2） 将最后一个num的值加到前一个num的值上，并将最后一个节点挂到前一个节点的brothe支链上的最后一个位置，排序，再将最后两个节点分别赋1和0，若存在brothe 支链，则连同支链上的所有节点设置相应的值。如图三所示。 图三3） 将最后一个num的值加到前一个num的值上，并将最后一个节点挂到前一个节点的brothe支链上的最后一个位置，排序，再将最后两个节点分别赋1和0，若存在brothe 支链，则连同支链上的所有节点设置相应的值。如图四所示。 图四4） 将

4、最后一个num的值加到前一个num的值上，并将最后一个节点挂到前一个节点的brothe支链上的最后一个位置，排序，再将最后两个节点分别赋1和0，若存在brothe 支链，则连同支链上的所有节点设置相应的值。如图五所示。 图五5） 最后将编码后的字符组成字符编码链表。如图六所示。 图六信道编码和信道译码，是参考教材（7，4）汉明码，小组讨论认为没有创新，这里不细述，详见channel_coding.c和channel_decoding.c文件。信道加噪声的实现方法是将信道编码的生成文件中的数据取出来，然后改变其中的某些数据后再写回去。小组讨论认为没有什么技巧，这里不述，具体实现见add_nois

5、e.c文件。下面论述信源译码的具体实现方法：在整理结构单元char_unit中coding数组时（详见link_func.c文件中的clean_up函数），coding数组的第一个位存放的是该字符的编码长度，从第二位开始存放字符的编码。1） 建一个长为最大编码长度的数据数组，（这个数组近似一个队列，这里它只有一个游动的指针和一个指向数组首地址的数组名）。2） 第一次从信道译码生成文件中读出最大编码长度的数据，然后将这串数据与编码链表进行比对，当然，必然能成功比对一个字符，否则这个程序是有问题的。3） 利用指向数据数组的游动指针同coding数组中的编码进行比对，若比对成功一次，就将该字符写入信

6、源译码生成文件中，并且将未对比的数据依次向前移动该字符编码长度位到数据数组前端。4）从信道译码生成文件中读出成功比对字符的编码长度数据到数据数组，也就是说将数据数组补充满，重复3）、4）直到信道译码生成文件结束。接着上文的例子，些例的最大编码长度为3，所以建立一长度为3的数据数组。然后从信道译码生成文件中读入3个数据，假如读入如下所示的数据：按照图六，它将成功比对出字符a，则将a写入信源译码生成文件，然后未比对的数据0前移2位，如下图所示：从信道译码生成文件中读出2个数据到数据数组中，将数组填满，如下图所示：这串数据将成功比对出字符d，重复上述步骤，直到信道译码生成文件结束。最终运行效果如下：

7、 图七全部运行时间为7.3s。图八是依次是信源编码生成文件、信道编码生成文件、信道加噪声生成文件、信道译码生成文件截图。 图八图九右边是源文件，左边是经译码后的文件。 图九接下来扼要说明一下附录中的各个源文件。此程序的测试环境是c-free 5.0，编译器类型是MinGW。建立的huffman_whj 工程包含七个源文件和一个头文件。Huffman.c是包含这个工程的主程序和一个信源字符统计函数和信源字符编码函数。Link_func.c是包含所有的链表操作函数，比如链表的排序，链表打印等等。File_coding.c是对文档进行huffman编码。Channel_coding.c是信道编码文件

8、。Add_noise.c 是实现信道加噪声。Channel_decoding.c是信道译码文件。Decoding.c是信源译码文件。Huffman.h是头文件。 附录Huffman.h 头文件#ifndef _huffman_h#define CHAR_SIZE 80#define READ_SIZE 1struct char_unit;typedef struct char_unit *point;typedef point link;void decoding(link head_coding_char, int big_len );void file_coding(link head_c

9、oding_char);int list_size(link char_coding_head);point find(link char_coding_head, unsigned char ch);void add_unit(link char_coding_head, point tem_unit);void unit_init(point tem_unit, unsigned char ch);int clean_up(link head_coding_char);point bro_last(struct char_unit *tem2);point last_point(struc

10、t char_unit *char_coding_head);point find_pro_point(link char_coding_head, point pro1);void set_num(point tem, int sit, int value);void print(link char_coding_head, int print_coding);link char_sort(link char_coding_head);void char_static(unsigned char* c_buf, link char_coding_head);void chan_coding(

11、);void chan_decoding();#endif /* *char_unit记录字符，字符出现的次数 *和字符的编码 */struct char_unit char ch; long num; short codingCHAR_SIZE; struct char_unit *next; struct char_unit *brothe; Huffman.c 文件/*文件名： huffman.c*作者： 小组*日期： 2015-01-11*文件说明：信息论作业。要求是信源编码、信道编码、信道加噪* 声、信道译码、信源译码。* 此程序已实现信源编码和信源译码，信道加噪声，信* 道编码和信

12、道译码的功能。 */#include <stdio.h>#include "huffman.h"#include <time.h>/*函数名： source_read*作者： 小组*日期： 2015-01-11*函数描述：读取文档，完成信源符号链表的* 建立和符号的计数*参数描述：char_coding_head指向符号表首的指针*/void source_read(link char_coding_head) FILE *fd; int read_time = 0; long char_total = 0; unsigned char c_bufR

13、EAD_SIZE; /*打开方档*/ fd = fopen("gone-with-wind.txt", "r"); /*观察打开文件是否成功*/ if (fd = NULL) printf("error when opening.n"); while ( fread(c_buf, READ_SIZE, 1, fd) ) /*一次读入READ_SIZE个字符*/ read_time +; /*将读到的字符送入计数统计函数*/ char_static(c_buf, char_coding_head); /*关闭文档*/ fclose(fd

14、); /*字符总数统计*/ char_total = read_time * READ_SIZE; printf("char_total is %ldn", char_total);/*函数名： huffman_coding*作者： 小组*日期： 2015-01-18*函数描述：利用字符统计的结果，对字符* 进行huffman编码 *参数描述：char_coding_head为字符链表的* 指针，由于链表的排序会影响链表* 的头指针，所为该函数要反回最终* 的链表头指针 */link huffman_coding(link char_coding_head, int c_n

15、um) int i; link head_coding_char; point tem1, tem2, last_bro; /*预先对信源字符按出现次数从大到小排序*/ head_coding_char = char_sort(char_coding_head);#if 0 print(head_coding_char, 0); #endiffor (i = c_num; i > 1; i -) /* *最小的两位分别赋0和1 */*找出表的最后一位*/ tem1 = last_point(head_coding_char); set_num(tem1, i, 1); /*找出表的最后第

16、二位*/tem2 = find_pro_point(head_coding_char,tem1); set_num(tem2, i, 0); /* *将最后一个节点中的num值加到最后第二个节点的num值上 *并将最后一个节点挂到最后第二个节点的brothe链上最后 *一个指针上，且最后第二个节点的next指针置为NULL，变 *为最后一个节点 */ tem2->num += tem1->num; last_bro = bro_last(tem2); last_bro->brothe = tem1; tem2->next = NULL; /*对信源字符按出现次数从大到小

17、排序*/ head_coding_char = char_sort(head_coding_char); /*建立完整的编码链表*/ last_bro = bro_last(head_coding_char); last_bro->brothe = head_coding_char->next; head_coding_char->next = NULL; return head_coding_char;/*/int main() int c_num, big_len; int star, end; struct char_unit char_coding_head; lin

18、k head_coding_char; /*运行起始时刻*/ star = clock(); /*首节点初始化*/ unit_init( &char_coding_head, 'e'); char_coding_head.num = 0; /*读取文档,建立字符链表，并完成字符统计*/ source_read(&char_coding_head); /*计算字符链表的大小*/ c_num = list_size(&char_coding_head); /*对每个字符编码，制作编码表，由于排序影响表头，所以亥函数返回最终的表头*/ head_coding_

19、char = huffman_coding(&char_coding_head, c_num); /*整理char_unit中coding的编码数据并将编码长度放在coding0中*/big_len = clean_up(head_coding_char); /*对文档进行huffman 编码*/ file_coding(head_coding_char);#if 1 /*打印编码表，字符个数，最大编码长度*/ print(head_coding_char, 1);printf("char list is %d %dn", c_num, big_len); #end

20、if /*信道编码*/ chan_coding(); /*信道译码*/ chan_decoding();#if 1 /*对huffman编码的文档进行译码*/ decoding(head_coding_char, big_len);#endif /*运行结束时刻*/end = clock();printf("the time of running is %dn", end - star); return 0; Link_func.c文件/*文件名： link_func.c*作者: 小组*日期： 2015-01-21*文件说明：这个文件主要是放一些基本的链表操作函数*/#in

21、clude "huffman.h"#include <stdio.h>#include <stdlib.h>/*璁畻骞惰繑鍥為摼琛殑澶皬 */int list_size(link char_coding_head) int i = 0; struct char_unit * p; p = char_coding_head; while (p != NULL) i +; p = p->next; return i; /*查表函数，若找到反回该地址，否则反回NULL*/point find(link char_coding_head, unsign

22、ed char ch) point tem_unit; tem_unit = char_coding_head; while (tem_unit != NULL && tem_unit->ch != ch) tem_unit = tem_unit->next; return tem_unit;/*追加函数，在字符表最后加入一个新的字符*/void add_unit(link char_coding_head, point tem_unit) point tem_unit1; tem_unit1 = char_coding_head; while (tem_unit1

23、->next != NULL) tem_unit1 = tem_unit1->next; tem_unit1->next = tem_unit;/*结构单元初始化函数*/void unit_init(point tem_unit, unsigned char ch)int i; tem_unit->ch = ch; tem_unit->num = 1; tem_unit->next = NULL; tem_unit->brothe = NULL; for (i = 0; i < CHAR_SIZE; i +) tem_unit->codin

24、gi = 2;/*整理char_unit中coding的编码数据并将编码长度放在coding0中*返回最小编码长度 */int clean_up(link head_coding_char)int i, j, re = 1;struct char_unit *p;p = head_coding_char;while (p != NULL)for (i = 1, j = 1; i < CHAR_SIZE; i +) if (p->codingi != 2)p->codingj = p->codingi;p->codingi = 2;j +;p->coding0

25、 = j - 1;re = (re > (j - 1)? re : (j - 1);p = p->brothe; return re;/*找出brothe支链上最后一个节点*/point bro_last(struct char_unit *tem2) struct char_unit *p; p = tem2; while (p->brothe !=NULL) p = p->brothe; return p;/*找出链表的最后一节点位置，返回此节点指针 */ point last_point(struct char_unit *char_coding_head)str

26、uct char_unit *p;p = char_coding_head;while (p->next != NULL) p = p->next; return p;/*查找当前位置的前一位置，反回前一位置 */point find_pro_point(link char_coding_head, point pro1) struct char_unit *p; p = char_coding_head; while (p->next != pro1) p = p->next; return p;/*设置编码函数 ，若存在brothe 支链，则连同支链上的所有节点设置

27、value值 */void set_num(point tem, int sit, int value)struct char_unit *p;p = tem;while (p != NULL)p->codingsit = value;p = p->brothe;/*打印字符表函数，当print_coding为0时按next指针寻径显示字符和字条出现次数 *不为0是按brothe指针寻径显示字符和字符编码 */void print(link char_coding_head, int print_coding) int i; point p; p = char_coding_hea

28、d; if (print_coding = 0) while (p != NULL) printf(" %c %ld n", p->ch, p->num); p = p->next; if (print_coding != 0) while (p != NULL) printf(" %c %ld ", p->ch, p->num); printf("n"); for (i = 1; i <= p->coding0; i +) printf("%d", p->codin

29、gi); printf("n"); p = p->brothe; /*对信源字符按出现次数从大到小排序*采用冒泡泡法的想法，先比较两个字符次数的大小，然后交换位置*（这里两数相等也交换位置） */link char_sort(link char_coding_head) int i = 0; point pro1, pro2, p1, p3, p4, p5; point p2; /保存排序后，表的首地址 for (pro1 = char_coding_head; pro1 != NULL; pro1 = pro1->next, i +) for (pro2 =

30、pro1->next; pro2 != NULL; pro2 = pro2->next) if (i = 0 && pro2->num >= pro1->num) p5 = find_pro_point(pro1, pro2); /*当pro1为首地址 *1）pro2与pro1相邻的情况 *2）pro2与pro1不相邻的情况 */ if (p5 = pro1) /*保存当前pro1,pro2的值*/ p1 = pro1; p2 = pro2; /*交换位置*/ p3 = pro2->next; pro1->next = p3; pro2

31、->next = pro1; /*恢复pro1,pro2的指向位置*/ pro1 = p2; pro2 = p1; else /*保存当前pro1,pro2的值*/ p1 = pro1; p2 = pro2; /*节点交换位置*/ p4 = pro2->next; p3 = pro1->next; /*pro2的前一位置*/ pro1->next = p4; p5->next = pro1; pro2->next = p3; /*恢复pro1,pro2指向的位置*/ pro1 = p2; pro2 = p1; /*当pro1不为首地址 *1）pro2与pro

32、1相邻的情况 *2）pro2与pro1不相邻的情况 */ else if (pro2->num >= pro1->num && i != 0) p1 = find_pro_point(p2, pro1); p3 = find_pro_point(p2, pro2); if (p3 = pro1) pro1->next = pro2->next; pro2->next = pro1; p1->next = pro2; /*恢复pro1,pro2指向的位置*/ p1 = pro1; pro1 = pro2; pro2 = p1; else

33、/*节点交换位置*/ p5 = pro1->next; pro1->next = pro2->next; p3->next = pro1; pro2->next = p5; p1->next = pro2; /*恢复pro1,pro2当前值*/ p1 = pro1; pro1 = pro2; pro2 = p1; /*返回首地址*/ return p2;/*建立字符并对表字符进行计数统计，*由于字符出现的概率与它的次数是一*个倍数关系，所以这里不求字符的*的概率*/void char_static(unsigned char* c_buf, link cha

34、r_coding_head) point tem_unit, re_unit; for (; *c_buf != '0' c_buf +) if (int)*c_buf > 0 && (int)*c_buf < 160 ) && (re_unit = find(char_coding_head, *c_buf) = NULL) tem_unit = (point) malloc ( sizeof(struct char_unit); if (tem_unit = NULL) printf("error:没有空间可分配n&qu

35、ot;); /*对该单元进行初始化*/ unit_init(tem_unit, *c_buf); /*将该单元加到字符表中*/ add_unit(char_coding_head, tem_unit); else if (int)*c_buf > 0 && (int)*c_buf < 160) re_unit->num +; File_coding.c文件/*函数名: file_coding*作者： 小组*日期： 2015-01-18*函数说明： 利用编码表对文档进行编码 ，生成二进制* 文档 *参数描述： head_coding_char 为编码表指针 */

36、#include <stdio.h>#include "huffman.h"/*查编码表函数，若找到反回该地址，否则反回NULL*/point cod_find(link char_coding_head, unsigned char ch) struct char_unit * tem_unit; tem_unit = char_coding_head; while (tem_unit != NULL && tem_unit->ch != ch) tem_unit = tem_unit->brothe; return tem_uni

37、t;/*对照码表，对第个c_buf中的字符编码 *返回未对c_buf中字符进行编码的个数 */int c_coding(link head_coding_char, unsigned char *c_buf, FILE *fd)int j = 2, i = 5, error_num = 0;struct char_unit *re_unit; for (; *c_buf != '0' c_buf +) #if 0 printf("1 1n"); printf("%cn", *c_buf);#endif if (int)*c_buf >

38、; 0 && (int)*c_buf < 160 ) && (re_unit = cod_find(head_coding_char, *c_buf) != NULL) #if 1 /*将字符编码写进二进制文档，一次写一位*/for (i = 1; i <= re_unit->coding0; i +) putc(re_unit->codingi, fd); #endif #if 0 /*将字符编码写进二进制文档，一次写一个字符编码*/ j = fwrite(&(re_unit->coding1), re_unit->

39、coding0, 1, fd); / printf("writed re_unit->ch %cn", re_unit->ch); if (j != 1 ) printf("error when writing.n"); #endif if ( re_unit = NULL) error_num += 1; return error_num;void file_coding(link head_coding_char) FILE *fd, *fs; int err_num = 0; unsigned char c_bufREAD_SIZE;

40、/*打开源文档*/ fs = fopen("gone-with-wind.txt", "r"); /*创建要生成的二进制文档*/ fd = fopen("coding_wind.bin", "wb+"); /*观察打开文件是否成功*/ if (fd = NULL | fs = NULL) printf("error when opening.n"); while (fread(c_buf, READ_SIZE, 1, fs) err_num = c_coding(head_coding_char

41、, c_buf, fd); err_num += err_num; #if 0 printf("the number of error when coding is %dn", err_num);#endif /*关闭文件*/fclose(fd);fclose(fs);printf("file coding is okn");Channel_coding.c文件/*函数名： chan_coding *作者： 小组 *日期： 2015-01-21 *函数描述：使用教材（7，4）汉明码，实现*信道编码 *参数描述：无参数 */#include <std

42、io.h> #include "huffman.h"/*汉明码，检验元的个数为3，信息元的个数为4*这样生成矩阵和校验矩阵都 已知了，用两个二维*数组存放这个校验矩阵 *设为全局 */int success47 = 1, 0, 0, 0, 1, 0, 1,0, 1, 0, 0, 1, 1, 1,0, 0, 1, 0, 1, 1, 0,0, 0, 0, 1, 0, 1, 1;/*生成汉明码所使用矩阵计算函数 */void hanming_coding(int *hanming_buf, int *bin_buf) int num = 0; int row, colu; int *p; p = bin_buf; for (colu = 0; colu < 7; colu +) for (row = 0; row < 4; row +) /*相加为1，则num记录1的个数*/ if (*p = 1 && successrowcolu = 1) num +; #if 0 printf("