香农三大定理的香农第一定理
香农第一定理(可变长无失真信源编码定理)设离散无记忆信源X包含N个符号{x1,x2,…,xi,..,xN}，信源发出K重符号序列，则此信源可发出N^k个不同的符号序列消息，其中第j个符号序列消息的出现概率为PKj，其信源编码后所得的二进制代码组长度为Bj，代码组的平均长度B为B=PK1B1+PK2B2+…+PKN^kBN^k当K趋于无限大时，B和信息量H(X)之间的关系为B*K=H(X)(K趋近无穷）香农第一定理又称为无失真信源编码定理或变长码信源编码定理。香农第一定理的意义：将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽量少的码符号传输信源信息。
信源编码的信源编码定理
不同类型的信源，是否存在有每种信源的最佳的信源编码，这通常是用信源编码定理来表示。最简单、最有实用指导意义的信源编码定理是离散、无记忆型信源的二进制变长编码的编码定理。它证明，一定存在一种无失真编码，当把N个符号进行编码时，平均每个符号所需二进码的码长满足。其中H（U）是信源的符号熵（比特），这就是说，最佳的信源编码应是与信源信息熵H（U）统计匹配的编码，代码长度可接近符号熵。这一结论不仅表明最佳编码存在，而且还给出具体构造码的方法，即按概率特性编成不等长度码。对不同类型信源，如离散或连续、无或有记忆、平稳或非平稳、无或限定失真等，可以构成不同的组合信源，它们都存在各自的信源编码定理。但它们中绝大部分仅是属于理论上的存在性定理，这给具体寻找和实现不同类型信源的信源编码，带来了相当的难度。
信源编码和信道编码的作用是什么？
信源编码是对输入信息进行编码，优化信息和压缩信息并且打成符合标准的数据包。信道编码是在数据中加入验证码，并且把加入验证码的海据进行调制。 2者的作用完全不一样的。
信源编码的分类
信源编码根据信源的性质进行分类，则有信源统计特性已知或未知、无失真或限定失真、无记忆或有记忆信源的编码；按编码方法进行分类可分为分组码或非分组码、等长码或变长码等。然而最常见的是讨论统计特性已知条件下，离散、平稳、无失真信源的编码，消除这类信源剩余度的主要方法有统计匹配编码和解除相关性编码。比如仙农码、费诺码、赫夫曼码，它们属于不等长度分组码，算术编码属于非分组码；预测编码和变换编码是以解除相关性为主的编码。对限定失真的信源编码则是以信息率失真R（D）函数为基础，最典型的是矢量量化编码。对统计特性未知的信源编码称为通用编码。
用C语言编无失真信源编码（哈夫曼编码）
#include
#include
#include
typedef unsigned char U8;
typedef unsigned short U16;
typedef unsigned long U32;
typedef struct HuffmanNode
{
double prob;
struct HuffmanNode *left;
struct HuffmanNode *right;
}huffmancode;
void Init ( U32*, double** );
huffmancode* Encode ( double*, U32 );
huffmancode* CreateBinaryTree ( huffmancode**, int );
void Print ( huffmancode*, char* );
void DeleteBinaryTree ( huffmancode* );
void main()
{
U32 n;
double *p;
huffmancode *pHuffman;
Init ( &n, &p );
pHuffman = Encode ( p, n );
Print ( pHuffman, "" );
DeleteBinaryTree ( pHuffman );
}
void DeleteBinaryTree ( huffmancode *pHuffman )
{
if ( pHuffman->left != NULL )
DeleteBinaryTree ( pHuffman->left );
if ( pHuffman->right != NULL )
DeleteBinaryTree ( pHuffman->right );
free ( pHuffman );
return;
}
void Print ( huffmancode *pHuffman, char *code )
{
int numChild = 0;
int strLen = strlen(code);
char *nextCode = (char*) malloc ( strLen + 2 );
if ( pHuffman->left != NULL )
{
numChild++;
strcpy ( nextCode, code );
nextCode[strLen] = '0';
nextCode[strLen+1] = '\0';
Print ( pHuffman->left, nextCode );
}
if ( pHuffman->right != NULL )
{
numChild++;
strcpy ( nextCode, code );
nextCode[strLen] = '1';
nextCode[strLen+1] = '\0';
Print ( pHuffman->right, nextCode );
}
if ( numChild == 0 )
{
printf ( "%lf\t==>......余下全文>>
哈弗曼编码方法和香农编码方法的理论依据
霍夫曼编码的基本思想：输入一个待编码的串，首先统计串中各字符出现的次数，称之为频次，假设统计频次的数组为count[ ]，则霍夫曼编码每次找出count数组中的值最小的两个分别作为左右孩子，建立他们的父节点，循环这个操作2*n-1-n（n是不同的字符数）次，这样就把霍夫曼树建好了。建树的过程需要注意，首先把count数组里面的n个值初始化为霍夫曼树的n个叶子节点，他们的孩子节点的标号初始化为-1，父节点初始化为他本身的标号。接下来是编码，每次从霍夫曼树的叶子节点出发，依次向上找，假设当前的节点标号是i，那么他的父节点必然是myHuffmantree[i].parent，如果i是myHuffmantree[i].parent的左节点，则该节点的路径为0，如果是右节点，则该节点的路径为1。当向上找到一个节点，他的父节点标号就是他本身，就停止（说明该节点已经是根节点）。还有一个需要注意的地方：在查找当前权值最小的两个节点时，那些父节点不是他本身的节点不能考虑进去，因为这些节点已经被处理过了
香农第一定理(可变长无失真信源编码定理)
设离散无记忆信源X包含N个符号{x1,x2,…,xi,..,xN}，信源发出K重符号序列，则此信源可发出N^k个不同的符号序列消息，其中第j个符号序列消息的出现概率为PKj，其信源编码后所得的二进制代码组长度为Bj，代码组的平均长度B为
B=PK1B1+PK2B2+…+PKN^kBN^k
当K趋于无限大时，B和信息量H(X)之间的关系为B*K=H(X)(K趋近无穷）
香农第一定理又称为无失真信源编码定理或变长码信源编码定理。
香农第一定理的意义：将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽量少的码符号传输信源信息。
香农第二定理（有噪信道编码定理）
有噪信道编码定理。当信道的信息传输率不超过信道容量时，采用合适的信道编码方法可以实现任意高的传输可靠性，但若信息传输率超过了信道容量，就不可能实现可靠的传输。
设某信道有r个输入符号，s个输出符号，信道容量为C，当信道的信息传输率R 香农第三定理（保失真度准则下的有失真信源编码定理） 保真度准则下的信源编码定理，或称有损信源编码定理。只要码长足够长，总可以找到一种信源编码，使编码后的信息传输率略大于率失真函数，而码的平均失真度不大于给定的允许失真度，即D'<=D. 设R(D)为一离散无记忆信源的信息率失真函数，并且选定有限的失真函数，对于任意允许平均失真度D>=0，和任意小的a>0，以及任意足够长的码长N，则一定存在一种信源编码W，其码字个数为M<=EXP{N[R(D)+a]}，而编码后码的平均失真度D'(W)<=D+a。 请采纳。 1．统计编码原理──信息量和信息熵 根据香农信息论的原理，最佳的数据压缩方法的理论极限是信息熵。如果要求在编码过程中不丢失信息量，即要求保存信息熵，这种信息保持的编码又叫熵保存编码，或叫熵编码。熵编码是无失真压缩。当然在考虑人眼失真不易察觉的生理特性时，有些图像编码不严格要求熵保存，信息允许通过部分损失来换取高的数据压缩比。这种编码属于有失真数据压缩。 信息是用不确定性的量度定义的，也就是说信息被假设为由一系列的随机变量所代表，它们往往用随机出现的符号来表示。我们称输出这些符号的源为“信源”。也就是要进行研究与压缩的对象。 信息量 信息量指从N个相等可能事件中选出一个事件所需要的信息度量或含量，也可以说是辨别N个事件中特定事件过程中所需提问“是”或“否”的最小次数。 例如：从64个数（1～64的整数）中选定某一个数（采用折半查找算法），提问：“是否大于32？”，则不论回答是与否，都消去半数的可能事件，如此下去，只要问6次这类问题，就可以从64个数中选定一个数，则所需的信息量是 =6（bit）。 我们现在可以换一种方式定义信息量，也就是信息论中信息量的定义。 设从N中选定任一个数X的概率为P(x)，假定任选一个数的概率都相等，即P(x)=1/N，则信息量I (x)可定义为： 上式可随对数所用“底”的不同而取不同的值，因而其单位也就不同。设底取大于1的整数α，考虑一般物理器件的二态性，通常α取2，相应的信息量单位为比特（bit）；当α=e，相应的信息量单位为奈特（Nat）；当α=10，相应的信息量单位为哈特（Hart）。 显然，当随机事件x发生的先验概率P(x)大时，算出的I(x)小，那么这个事件发生的可能性大，不确定性小，事件一旦发生后提供的信息量也少。必然事件的P(x)等于1， I(x)等于0，所以必然事件的消息报导，不含任何信息量；但是一件人们都没有估计到的事件（P(x)极小），一旦发生后，I(x)大，包含的信息量很大。所以随机事件的先验概率，与事件发生后所产生的信息量，有密切关系。I(x)称x发生后的自信息量，它也是一个随机变量。 P(x)大时，算出的I(x)小 必然事件的P(x)等于1， I(x)等于0。 P(x)小时，算出的I(x)大 必然事件的P(x)等于0， I(x)等于1。 I(x)称x发生后的自信息量，它也是一个随机变量。 信息熵 现在可以给“熵”下个定义了。信息量计算的是一个信源的某一个事件（X）的自信息量，而一个信源若由n个随机事件组成，n个随机事件的平均信息量就定义为熵(Entropy)。 熵的准确定义是：信源X发出的xj(j=1,2,……n), 共n个随机事件的自信息统计平均（求数学期望），即 H(X)在信息论中称为信源X的“熵 （Entropy）” ，它的含义是信源X发出任意一个随机变量的平均信息量。 更详细的说，一般在解释和理解信息熵有4种样式 （1） 当处于事件发生之前，H(X)是不确定性的度量； （2） 当处于事件发生之时，是一种惊奇性的度量； （3） 当处于事件发生之后，是获得信息的度量； （4） 还可以理解为是事件随机性的度量． 下面为了掌握信息熵的概念，我们来做一道计算题。 例如：以信源X中有8个随机事件，即n=8。每一个随机事件的概率都相等，即P(x1)=P(x2)=P(x3)……P(x8)=1/8 ，计算信源X的熵。 应用“熵”的定义可得其平均信息量为3比特 ......余下全文>> 香农三大定理是信息论的基础理论。香农三大定理是存在性定理，虽然并没有提供具体的编码实现方法，但为通信信息的研究指明了方向。香农第一定理是可变长无失真信源编码定理。香农第二定理是有噪信道编码定理。香农第三定理是保失真度准则下的有失真信源编码定理。 一般说的香农定理,指 香农定理给出了信道信息传送速率的上限（比特每秒）和信道信噪比及带宽的关系。香农定理可以解释现代各种无线制式由于带宽不同，所支持的单载波最大吞吐量的不同。 在有随机热噪声的信道上传输数据信号时，信道容量Rmax与信道带宽W，信噪比S/N关系为： Rmax=W*log2(1+S/N)。注意这里的log2是以2为底的对数。 更多详情请度娘吧,贴得到了又犯规了...什么是信源在允许一定失真的条件下，信源熵所能压缩的极限
什么是香农定理
扫一扫手机访问
