信息論編碼作業(yè)-小組

1、 一信息論編碼作業(yè)小組成員：吳湛S1209G106、彭利S1409W0516、王紅建S140900748文件說明：信息論作業(yè)。要求是信源編碼、信道編碼、信道加噪聲、信道譯碼、信源譯碼。此程序已實(shí)現(xiàn)信源編碼和信源譯碼，信道加噪聲，信道編碼和信道譯碼的功能。信源編碼的具體實(shí)現(xiàn)方法：對(duì)于霍夫曼編碼時(shí)的字符概率統(tǒng)計(jì)方法（這里并非是求出字符概率，因?yàn)楦怕屎妥址霈F(xiàn)的頻率是倍數(shù)關(guān)系，所以這里直接使用字符的頻率），首先創(chuàng)建一個(gè)表頭，當(dāng)讀入一個(gè)字符時(shí)就去查尋這個(gè)鏈表（詳見link_func.c中的find函數(shù)），若發(fā)現(xiàn)已有讀入的這個(gè)字符，那么就在匹配的結(jié)構(gòu)單元中num成員加一，如果沒有匹配的結(jié)構(gòu)單元說明發(fā)現(xiàn)了

2、一個(gè)新字符，就在鏈表最后加一節(jié)點(diǎn)（詳見link_func.c中的add_unit函數(shù)）。對(duì)于霍夫曼編碼時(shí)的編碼具體實(shí)現(xiàn)方法如下示意圖所示：1） 對(duì)鏈表進(jìn)行排序（詳見link_func.c中的char_sort函數(shù)），并將最后兩個(gè)分別賦1和0，如圖一所示。（這里排序用冒泡法的思想對(duì)鏈表排序，當(dāng)兩個(gè)字符的次數(shù)相等時(shí)，也進(jìn)行字符的交換，這樣可減小編碼長(zhǎng)度的方差。對(duì)于節(jié)點(diǎn)的賦值，見link_func.c中的set_num函數(shù)，當(dāng)被賦值的節(jié)點(diǎn)存在brothe支鏈時(shí)，該支鏈上的所有節(jié)點(diǎn)都賦于此值）。 圖一2）將最后一個(gè)num的值加到前一個(gè)num的值上，并將最后一個(gè)節(jié)點(diǎn)掛到前一個(gè)節(jié)點(diǎn)的brothe支鏈上的最

3、后一個(gè)位置，排序，再將最后兩個(gè)節(jié)點(diǎn)分別賦1和0，若存在brothe 支鏈，則連同支鏈上的所有節(jié)點(diǎn)設(shè)置相應(yīng)的值。如圖二所示。 圖二2） 將最后一個(gè)num的值加到前一個(gè)num的值上，并將最后一個(gè)節(jié)點(diǎn)掛到前一個(gè)節(jié)點(diǎn)的brothe支鏈上的最后一個(gè)位置，排序，再將最后兩個(gè)節(jié)點(diǎn)分別賦1和0，若存在brothe 支鏈，則連同支鏈上的所有節(jié)點(diǎn)設(shè)置相應(yīng)的值。如圖三所示。 圖三3） 將最后一個(gè)num的值加到前一個(gè)num的值上，并將最后一個(gè)節(jié)點(diǎn)掛到前一個(gè)節(jié)點(diǎn)的brothe支鏈上的最后一個(gè)位置，排序，再將最后兩個(gè)節(jié)點(diǎn)分別賦1和0，若存在brothe 支鏈，則連同支鏈上的所有節(jié)點(diǎn)設(shè)置相應(yīng)的值。如圖四所示。 圖四4） 將

4、最后一個(gè)num的值加到前一個(gè)num的值上，并將最后一個(gè)節(jié)點(diǎn)掛到前一個(gè)節(jié)點(diǎn)的brothe支鏈上的最后一個(gè)位置，排序，再將最后兩個(gè)節(jié)點(diǎn)分別賦1和0，若存在brothe 支鏈，則連同支鏈上的所有節(jié)點(diǎn)設(shè)置相應(yīng)的值。如圖五所示。 圖五5） 最后將編碼后的字符組成字符編碼鏈表。如圖六所示。 圖六信道編碼和信道譯碼，是參考教材（7，4）漢明碼，小組討論認(rèn)為沒有創(chuàng)新，這里不細(xì)述，詳見channel_coding.c和channel_decoding.c文件。信道加噪聲的實(shí)現(xiàn)方法是將信道編碼的生成文件中的數(shù)據(jù)取出來，然后改變其中的某些數(shù)據(jù)后再寫回去。小組討論認(rèn)為沒有什么技巧，這里不述，具體實(shí)現(xiàn)見add_nois

5、e.c文件。下面論述信源譯碼的具體實(shí)現(xiàn)方法：在整理結(jié)構(gòu)單元char_unit中coding數(shù)組時(shí)（詳見link_func.c文件中的clean_up函數(shù)），coding數(shù)組的第一個(gè)位存放的是該字符的編碼長(zhǎng)度，從第二位開始存放字符的編碼。1） 建一個(gè)長(zhǎng)為最大編碼長(zhǎng)度的數(shù)據(jù)數(shù)組，（這個(gè)數(shù)組近似一個(gè)隊(duì)列，這里它只有一個(gè)游動(dòng)的指針和一個(gè)指向數(shù)組首地址的數(shù)組名）。2） 第一次從信道譯碼生成文件中讀出最大編碼長(zhǎng)度的數(shù)據(jù)，然后將這串?dāng)?shù)據(jù)與編碼鏈表進(jìn)行比對(duì)，當(dāng)然，必然能成功比對(duì)一個(gè)字符，否則這個(gè)程序是有問題的。3） 利用指向數(shù)據(jù)數(shù)組的游動(dòng)指針同coding數(shù)組中的編碼進(jìn)行比對(duì)，若比對(duì)成功一次，就將該字符寫入信

6、源譯碼生成文件中，并且將未對(duì)比的數(shù)據(jù)依次向前移動(dòng)該字符編碼長(zhǎng)度位到數(shù)據(jù)數(shù)組前端。4）從信道譯碼生成文件中讀出成功比對(duì)字符的編碼長(zhǎng)度數(shù)據(jù)到數(shù)據(jù)數(shù)組，也就是說將數(shù)據(jù)數(shù)組補(bǔ)充滿，重復(fù)3）、4）直到信道譯碼生成文件結(jié)束。接著上文的例子，些例的最大編碼長(zhǎng)度為3，所以建立一長(zhǎng)度為3的數(shù)據(jù)數(shù)組。然后從信道譯碼生成文件中讀入3個(gè)數(shù)據(jù)，假如讀入如下所示的數(shù)據(jù)：按照?qǐng)D六，它將成功比對(duì)出字符a，則將a寫入信源譯碼生成文件，然后未比對(duì)的數(shù)據(jù)0前移2位，如下圖所示：從信道譯碼生成文件中讀出2個(gè)數(shù)據(jù)到數(shù)據(jù)數(shù)組中，將數(shù)組填滿，如下圖所示：這串?dāng)?shù)據(jù)將成功比對(duì)出字符d，重復(fù)上述步驟，直到信道譯碼生成文件結(jié)束。最終運(yùn)行效果如下：

7、 圖七全部運(yùn)行時(shí)間為7.3s。圖八是依次是信源編碼生成文件、信道編碼生成文件、信道加噪聲生成文件、信道譯碼生成文件截圖。 圖八圖九右邊是源文件，左邊是經(jīng)譯碼后的文件。 圖九接下來扼要說明一下附錄中的各個(gè)源文件。此程序的測(cè)試環(huán)境是c-free 5.0，編譯器類型是MinGW。建立的huffman_whj 工程包含七個(gè)源文件和一個(gè)頭文件。Huffman.c是包含這個(gè)工程的主程序和一個(gè)信源字符統(tǒng)計(jì)函數(shù)和信源字符編碼函數(shù)。Link_func.c是包含所有的鏈表操作函數(shù)，比如鏈表的排序，鏈表打印等等。File_coding.c是對(duì)文檔進(jìn)行huffman編碼。Channel_coding.c是信道編碼文件

8、。Add_noise.c 是實(shí)現(xiàn)信道加噪聲。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記錄字符，字符出現(xiàn)的次數(shù) *和字符的編碼 */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*文件說明：信息論作業(yè)。要求是信源編碼、信道編碼、信道加噪* 聲、信道譯碼、信源譯碼。* 此程序已實(shí)現(xiàn)信源編碼和信源譯碼，信道加噪聲，信* 道編碼和信

12、道譯碼的功能。 */#include <stdio.h>#include "huffman.h"#include <time.h>/*函數(shù)名： source_read*作者： 小組*日期： 2015-01-11*函數(shù)描述：讀取文檔，完成信源符號(hào)鏈表的* 建立和符號(hào)的計(jì)數(shù)*參數(shù)描述：char_coding_head指向符號(hào)表首的指針*/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個(gè)字符*/ read_time +; /*將讀到的字符送入計(jì)數(shù)統(tǒng)計(jì)函數(shù)*/ char_static(c_buf, char_coding_head); /*關(guān)閉文檔*/ fclose(fd

14、); /*字符總數(shù)統(tǒng)計(jì)*/ char_total = read_time * READ_SIZE; printf("char_total is %ldn", char_total);/*函數(shù)名： huffman_coding*作者： 小組*日期： 2015-01-18*函數(shù)描述：利用字符統(tǒng)計(jì)的結(jié)果，對(duì)字符* 進(jìn)行huffman編碼 *參數(shù)描述：char_coding_head為字符鏈表的* 指針，由于鏈表的排序會(huì)影響鏈表* 的頭指針，所為該函數(shù)要反回最終* 的鏈表頭指針 */link huffman_coding(link char_coding_head, int c_n

15、um) int i; link head_coding_char; point tem1, tem2, last_bro; /*預(yù)先對(duì)信源字符按出現(xiàn)次數(shù)從大到小排序*/ 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); /* *將最后一個(gè)節(jié)點(diǎn)中的num值加到最后第二個(gè)節(jié)點(diǎn)的num值上 *并將最后一個(gè)節(jié)點(diǎn)掛到最后第二個(gè)節(jié)點(diǎn)的brothe鏈上最后 *一個(gè)指針上，且最后第二個(gè)節(jié)點(diǎn)的next指針置為NULL，變 *為最后一個(gè)節(jié)點(diǎn) */ tem2->num += tem1->num; last_bro = bro_last(tem2); last_bro->brothe = tem1; tem2->next = NULL; /*對(duì)信源字符按出現(xiàn)次數(shù)從大到小

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; /*運(yùn)行起始時(shí)刻*/ star = clock(); /*首節(jié)點(diǎn)初始化*/ unit_init( &char_coding_head, 'e'); char_coding_head.num = 0; /*讀取文檔,建立字符鏈表，并完成字符統(tǒng)計(jì)*/ source_read(&char_coding_head); /*計(jì)算字符鏈表的大小*/ c_num = list_size(&char_coding_head); /*對(duì)每個(gè)字符編碼，制作編碼表，由于排序影響表頭，所以亥函數(shù)返回最終的表頭*/ head_coding_

19、char = huffman_coding(&char_coding_head, c_num); /*整理char_unit中coding的編碼數(shù)據(jù)并將編碼長(zhǎng)度放在coding0中*/big_len = clean_up(head_coding_char); /*對(duì)文檔進(jìn)行huffman 編碼*/ file_coding(head_coding_char);#if 1 /*打印編碼表，字符個(gè)數(shù)，最大編碼長(zhǎng)度*/ print(head_coding_char, 1);printf("char list is %d %dn", c_num, big_len); #end

20、if /*信道編碼*/ chan_coding(); /*信道譯碼*/ chan_decoding();#if 1 /*對(duì)huffman編碼的文檔進(jìn)行譯碼*/ decoding(head_coding_char, big_len);#endif /*運(yùn)行結(jié)束時(shí)刻*/end = clock();printf("the time of running is %dn", end - star); return 0; Link_func.c文件/*文件名： link_func.c*作者: 小組*日期： 2015-01-21*文件說明：這個(gè)文件主要是放一些基本的鏈表操作函數(shù)*/#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; /*查表函數(shù)，若找到反回該地址，否則反回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;/*追加函數(shù)，在字符表最后加入一個(gè)新的字符*/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;/*結(jié)構(gòu)單元初始化函數(shù)*/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的編碼數(shù)據(jù)并將編碼長(zhǎng)度放在coding0中*返回最小編碼長(zhǎng)度 */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支鏈上最后一個(gè)節(jié)點(diǎn)*/point bro_last(struct char_unit *tem2) struct char_unit *p; p = tem2; while (p->brothe !=NULL) p = p->brothe; return p;/*找出鏈表的最后一節(jié)點(diǎn)位置，返回此節(jié)點(diǎn)指針 */ 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;/*查找當(dāng)前位置的前一位置，反回前一位置 */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;/*設(shè)置編碼函數(shù) ，若存在brothe 支鏈，則連同支鏈上的所有節(jié)點(diǎn)設(shè)置

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;/*打印字符表函數(shù)，當(dāng)print_coding為0時(shí)按next指針尋徑顯示字符和字條出現(xiàn)次數(shù) *不為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; /*對(duì)信源字符按出現(xiàn)次數(shù)從大到小排序*采用冒泡泡法的想法，先比較兩個(gè)字符次數(shù)的大小，然后交換位置*（這里兩數(shù)相等也交換位置） */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); /*當(dāng)pro1為首地址 *1）pro2與pro1相鄰的情況 *2）pro2與pro1不相鄰的情況 */ if (p5 = pro1) /*保存當(dāng)前pro1,pro2的值*/ p1 = pro1; p2 = pro2; /*交換位置*/ p3 = pro2->next; pro1->next = p3; pro2

31、->next = pro1; /*恢復(fù)pro1,pro2的指向位置*/ pro1 = p2; pro2 = p1; else /*保存當(dāng)前pro1,pro2的值*/ p1 = pro1; p2 = pro2; /*節(jié)點(diǎn)交換位置*/ p4 = pro2->next; p3 = pro1->next; /*pro2的前一位置*/ pro1->next = p4; p5->next = pro1; pro2->next = p3; /*恢復(fù)pro1,pro2指向的位置*/ pro1 = p2; pro2 = p1; /*當(dāng)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; /*恢復(fù)pro1,pro2指向的位置*/ p1 = pro1; pro1 = pro2; pro2 = p1; else

33、/*節(jié)點(diǎn)交換位置*/ p5 = pro1->next; pro1->next = pro2->next; p3->next = pro1; pro2->next = p5; p1->next = pro2; /*恢復(fù)pro1,pro2當(dāng)前值*/ p1 = pro1; pro1 = pro2; pro2 = p1; /*返回首地址*/ return p2;/*建立字符并對(duì)表字符進(jìn)行計(jì)數(shù)統(tǒng)計(jì)，*由于字符出現(xiàn)的概率與它的次數(shù)是一*個(gè)倍數(shù)關(guān)系，所以這里不求字符的*的概率*/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;); /*對(duì)該單元進(jìn)行初始化*/ 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文件/*函數(shù)名: file_coding*作者： 小組*日期： 2015-01-18*函數(shù)說明： 利用編碼表對(duì)文檔進(jìn)行編碼 ，生成二進(jìn)制* 文檔 *參數(shù)描述： head_coding_char 為編碼表指針 */

36、#include <stdio.h>#include "huffman.h"/*查編碼表函數(shù)，若找到反回該地址，否則反回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;/*對(duì)照碼表，對(duì)第個(gè)c_buf中的字符編碼 *返回未對(duì)c_buf中字符進(jìn)行編碼的個(gè)數(shù) */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 /*將字符編碼寫進(jìn)二進(jìn)制文檔，一次寫一位*/for (i = 1; i <= re_unit->coding0; i +) putc(re_unit->codingi, fd); #endif #if 0 /*將字符編碼寫進(jìn)二進(jìn)制文檔，一次寫一個(gè)字符編碼*/ 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"); /*創(chuàng)建要生成的二進(jìn)制文檔*/ 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 /*關(guān)閉文件*/fclose(fd);fclose(fs);printf("file coding is okn");Channel_coding.c文件/*函數(shù)名： chan_coding *作者： 小組 *日期： 2015-01-21 *函數(shù)描述：使用教材（7，4）漢明碼，實(shí)現(xiàn)*信道編碼 *參數(shù)描述：無參數(shù) */#include <std

42、io.h> #include "huffman.h"/*漢明碼，檢驗(yàn)元的個(gè)數(shù)為3，信息元的個(gè)數(shù)為4*這樣生成矩陣和校驗(yàn)矩陣都 已知了，用兩個(gè)二維*數(shù)組存放這個(gè)校驗(yàn)矩陣 *設(shè)為全局 */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;/*生成漢明碼所使用矩陣計(jì)算函數(shù) */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的個(gè)數(shù)*/ if (*p = 1 && successrowcolu = 1) num +; #if 0 printf("