前言
在《Polar Code（2）编码原理》中详细阐述了Polar Code的编码原理。为了更好的理解编码的过程，本文将给出一个编码实例。

设码长$N=8$，信息比特数$K=4$，下面列出所有使用到的公式。

$c_1^N=u_1^NG_N$

$G_N=B_NF ^{\otimes n}$

$F^{\otimes n}= F\otimes F^{\otimes (n-1)}$

$F=\left [
 \begin{matrix}
   1 & 0\\
   1 & 1
  \end{matrix}
  \right]$

$B_N=R_N(I_2\otimes B_{N/2})$

$B_2=I_2$
编码步骤
1.信道可靠性估计
假设对于各二进制删除信道（BEC），已计算出各个分裂信道的巴氏参数$Z(W_N^{(i)})$。
2.比特混合
假设通过第一步得到巴氏参数最小的4个子信道的序号为$\{4,6,7,8\}$，则信息比特序号集合记为

$A=\{4,6,7,8\}$

则冻结比特序号集合为

$A^c=\{1,2,3,5\}$

设信息比特集合为$(i_1,i_2,i_3,i_4)=(1,1,1,1)$，冻结比特集合为$\{0,0,0,0\}$，则最终得到

$u_1^8={0,0,0,i_1,0,i_2,i_3,i_4}=[0,0,0,1,0,1,1,1]$
3.构造生成矩阵
回忆：$G_N=B_NF ^{\otimes n}$

$B_8=R_8(I_2\otimes B_4)$

$B_4=R_4(I_4\otimes B_2)$

计算：

$B_2=\left [
 \begin{matrix}
   1 & 0\\
   0 & 1
  \end{matrix}
  \right]$

$I_2\otimes B_2=\left [
 \begin{matrix}
   1 & 0 & 0 & 0\\
   0 & 1 & 0 & 0\\
   0 & 0 & 1 & 0\\
   0 & 0 & 0 & 1
  \end{matrix}
  \right]$

$R4$是由$I_4$变换而来，先排$I_4$的奇数列，再排$I_4$的偶数列：

$R_4=\left [
 \begin{matrix}
   1 & 0 & 0 & 0\\
   0 & 0 & 1 & 0\\
   0 & 1 & 0 & 0\\
   0 & 0 & 0 & 1
  \end{matrix}
  \right] \Leftarrow I_4=\left [
 \begin{matrix}
   1 & 0 & 0 & 0\\
   0 & 1 & 0 & 0\\
   0 & 0 & 1 & 0\\
   0 & 0 & 0 & 1
  \end{matrix}
  \right]$

$B_4=R_4(I_2\otimes B_2)=\left [
 \begin{matrix}
   1 & 0 & 0 & 0\\
   0 & 1 & 0 & 0\\
   0 & 0 & 1 & 0\\
   0 & 0 & 0 & 1
  \end{matrix}
  \right] \cdot \left [
 \begin{matrix}
   1 & 0 & 0 & 0\\
   0 & 1 & 0 & 0\\
   0 & 0 & 1 & 0\\
   0 & 0 & 0 & 1
  \end{matrix}
  \right]=\left [
 \begin{matrix}
   1 & 0 & 0 & 0\\
   0 & 0 & 1 & 0\\
   0 & 1 & 0 & 0\\
   0 & 0 & 0 & 1
  \end{matrix}
  \right]$

$I_2\otimes B_4=\left [
 \begin{matrix}
   1 & 0 \\
   0 & 1
  \end{matrix}
  \right] \otimes \left [
 \begin{matrix}
   1 & 0 & 0 & 0\\
   0 & 0 & 1 & 0\\
   0 & 1 & 0 & 0\\
   0 & 0 & 0 & 1
  \end{matrix}
  \right]=\left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
   0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
  \end{matrix}
  \right]$

同理推导$B_8$：

$B_8=R_8(I_2 \otimes B_4)$

$R_8=\left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
   0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
   0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
  \end{matrix}
  \right] \Leftarrow I_8=\left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
  \end{matrix}
  \right]$

所以，容易推导出$B_8$：

$B_8=R_8(I_2\otimes B_4)=
\left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
   0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
   0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
  \end{matrix}
  \right] \cdot \left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
   0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
  \end{matrix}
  \right] \\
  =\left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
   0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
   0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
  \end{matrix}
  \right]$
推导$F ^{\otimes 3}$
有递归式：

$F ^{\otimes 3}=F \otimes F ^{\otimes 2}$

$F ^{\otimes 2}=F \otimes F ^{\otimes 1}$

计算：

$F ^{\otimes 1}=F=\left [
 \begin{matrix}
   1 & 0 \\
   1 & 1
  \end{matrix}
  \right]$

$F\otimes 2=F\otimes F ^{\otimes 1}=\left [
 \begin{matrix}
   1 & 0 \\
   1 & 1
  \end{matrix}
  \right] \otimes F ^{\otimes 1}=\left [
 \begin{matrix}
   F ^{\otimes 1} & 0 \\
   F ^{\otimes 1} & F ^{\otimes 1}
  \end{matrix}
  \right]=\left [
 \begin{matrix}
   1 & 0 & 0 & 0\\
   1 & 1 & 0 & 0\\
   1 & 0 & 1 & 0\\
   1 & 1 & 1 & 1
  \end{matrix}
  \right]$

$F \otimes 3=F \otimes F^{\otimes 2}=\left [
 \begin{matrix}
   1 & 0 \\
   1 & 1
  \end{matrix}
  \right] \otimes F^{\otimes 2}=\left [
 \begin{matrix}
   F^{\otimes 2} & 0 \\
   F^{\otimes 2} & F^{\otimes 2}
  \end{matrix}
  \right] = \left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
   1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   1 & 1 & 0 & 0 & 1 & 1 & 0 & 0\\
   1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
   1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
  \end{matrix}
  \right]$
得出生成矩阵$G_N$
$G_8=B_8F^{\otimes 3}=\left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
   0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
   0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
   0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
  \end{matrix}
  \right] \cdot \left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
   1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   1 & 1 & 0 & 0 & 1 & 1 & 0 & 0\\
   1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
   1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
  \end{matrix}
  \right]=\\ =\left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
   1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   1 & 1 & 0 & 0 & 1 & 1 & 0 & 0\\
   1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
   1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
  \end{matrix}
  \right]$
生成Polar Code
$c_1^8=u_1^8G_8=[0\ 0\ 0\ 1\ 0\ 1\ 1\ 1] \cdot \left [
 \begin{matrix}
   1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
   1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
   1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
   1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
   1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
   1 & 1 & 0 & 0 & 1 & 1 & 0 & 0\\
   1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
   1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
  \end{matrix}
  \right] \\
  =[0\ 1\ 1\ 0\ 1\ 0\ 0\ 1]$
最后
本文主要给了一个Polar Code的编码实例，码长为8，码率为1/2，未编码的码字是$[0\ 0\ 0\ 1\ 0\ 1\ 1\ 1]$生成的码字是$[0\ 1\ 1\ 0\ 1\ 0\ 0\ 1]$，介绍了$B_N$和$F^{\otimes 3}$的推导。

此CSDN上的基本为全文摘录，修改部分主要是基于自己的理解，仅供读者参考。

本文作者： Marshall

本文链接： https://marshallcomm.cn/2017/03/05/polar-code-3-encoding-example/

实例
一串消息包含A，B，C，D，E共5类符号，其内容为AABBBBAAAACCCCCCCCCEEEEEEDDDDEEEEEEEEEEEEE，分别对其进行香农编码和霍夫曼编码
我们可以看到内容总共含42个符号，其中6个A，4个B,9个C，4个D，19个E，其对应的概率分别为1/7,2/21,3/14,2/21,19/42

可以看到其概率分布如下




A
B
C
D
E




1/7
2/21
3/14
2/21
19/42


信息熵计算为2.043
香农编码
编码步骤
(1)将信源符号按概率从大到小顺序排列，为方便起见
(2)按计算第i个符号对应的码字的码长(取整)；
(3) 计算第i个符号的累加概率 ；
(4)将累加概率变换成二进制小数，取小数点后 位数作为第i个符号的码字。





实例演示




E
C
A
B
D




19/42
3/14
1/7
2/21
2/21






最终编码结果：




E
C
A
B
D




00
01
10
110
111






A
B
C
D
E




6
4
9
4
19



霍夫曼编码
香农-范诺编码算法并非总能得到最优编码。1952年, David A. Huffman提出了一个不同的算法，这个算法可以为任何的可能性提供出一个理想的树。
香农-范诺编码是从树的根节点到叶子节点所进行的的编码，哈夫曼编码算法却是从相反的方向，暨从叶子节点到根节点的方向编码的。
编码步骤
1.为每个符号建立一个叶子节点，并加上其相应的发生频率

2.当有一个以上的节点存在时，进行下列循环：

把这些节点作为带权值的二叉树的根节点，左右子树为空
选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
把权值最小的两个根节点移除
将新的二叉树加入队列中。

3.最后剩下的节点暨为根节点，此时二叉树已经完成。




实例演示




E
C
A
B
D




19/42
3/14
1/7
2/21
2/21









E
C
A
B
D




0
10
110
1110
1111






A
B
C
D
E




6
4
9
4
19



比较
香农编码：



霍夫曼编码：



理论熵：2.043

可以看到霍夫曼编码的压缩率更好
参考资料
香农-范诺编码

文章目录
一、 什么是信息熵？
二、压缩编码方式
三、BMP 图像字节计算
四、参考

一、 什么是信息熵？
以下内容来自百度百科：

信息是个很抽象的概念。人们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。

直到1948年，香农提出了“信息熵”的概念，才解决了对信息的量化度量问题。信息熵这个词是C.E.Shannon（香农）从热力学中借用过来的。热力学中的热熵是表示分子状态混乱程度的物理量。香农用信息熵的概念来描述信源的不确定度。

信息论之父克劳德·艾尔伍德·香农第一次用数学语言阐明了概率与信息冗余度的关系。

信息熵的计算公式：


二、压缩编码方式
问题：

一串消息包含A，B，C，D，E共5类符号，其内容是：AABBBBAAAACCCCCCCCCEEEEEEDDDDEEEEEEEEEEEEE,

请问其信息熵是多少？如果分别采用香农-凡诺编码，霍夫曼编码，压缩率分别是多少？

解答：

出现概率统计：



信息熵：


香农-范诺编码：


将所有的字母按照出现的次数由多到少、从左到右进行排序，如下图所示：




划分两边，使两边出现次数的差最小




编码完成如下图所示（需要的位数 = 编码位数 × 出现的次数）：



所以由以上过程可知：编码前5 种符号至少需要 3 位二进制编码，共 42 个字符，则需 3 × 42 = 126 3×42=1263×42=126 位。编码后共 87 8787 位。压缩比为126 : 87 = 1.45 : 1 126:87=1.45:1126:87=1.45:1


霍夫曼编码：

从最小概率的两个符号开始，可选其中一个支路为 0，另一支路为 1，再合并两个支路，并重新排队，多次重复这一过程，直到最后概率为 1



需要的位数 = 编码位数 × 出现的次数：


由以上可知编码前5 种符号至少需要 3 位二进制编码，共 42 个字符，则需 3 × 42 = 126 3×42=1263×42=126 位。编码后共 87 8787 位。压缩比为126 : 87 = 1.45 : 1
三、BMP 图像字节计算
问题：

一幅1024*768的24位RGB彩色图像一共在内存中占有多少字节？ 如果将其保存为非压缩格式的BMP文件，文件有多少字节？请用实例验证



解答：

一张图共 1024 × 768 × 3 = 2 , 359 , 296 1024×768×3=2,359,2961024×768×3=2,359,296 个字节

BMP 文件由文件头、位图信息头、颜色信息和图形数据四部分组成。

对于 24 位真彩色图像就不使用彩色板，因为位图中的 RGB 值就代表了每个像素的颜色。

故此图片的文件头+位图信息头+颜色信息为 54 字节，再加上图形数据，就是 2359350 字节
四、参考
详解信息熵、两种编码方式示例、BMP 字节计算方法



信息熵及其相关概念

    
.net实例:Asp.net把UTF-8编码转换为GB2312编码（转）
最近在做的系统中，碰到了一个问题，交易系统采用的UTF-8编码，而一些支持系统使用的是GB2312编码。 
   
  不同编码的页面、脚本之间互相引用，就会产生乱码的问题，解决方法就是统一成一种编码。 
  asp.net 中，如果要修改输出页面的编码，可以通过修改web.config中以下配置信息 
   
   
  <globalization requestEncoding="utf-8" responseEncoding="utf-8" /> 
  以上只是修改整体的默认编码，如果只有某个页的编码需要修改，ASP.net 中则可以简单的使用下面代码： 
   
   
  注:加到Page_Load()事件下面就可以了 
  Encoding gb2312 = Encoding.GetEncoding("gb2312"); 
  Response.ContentEncoding = gb2312; 
  在非ASP.net 应用中，可能你读到的数据是UTF-8编码，但是你要转换为GB2312编码，则可以参考以下代码： 
   
   
   
  string utfinfo = "document.write(\"alert('你好么？？');\");"; 
  string gb2312info = string.Empty; 
   
  Encoding utf8 = Encoding.UTF8; 
  Encoding gb2312 = Encoding.GetEncoding("gb2312"); 
   
  // Convert the string into a byte[]. 
  byte[] unicodeBytes = utf8.GetBytes(utfinfo); 
  // Perform the conversion from one encoding to the other. 
  byte[] asciiBytes = Encoding.Convert(utf8, gb2312, unicodeBytes); 
   
  // Convert the new byte[] into a char[] and then into a string. 
  // This is a slightly different approach to converting to illustrate 
  // the use of GetCharCount/GetChars. 
  char[] asciiChars = new char[gb2312.GetCharCount(asciiBytes, 0, asciiBytes.Length)]; 
  gb2312.GetChars(asciiBytes, 0, asciiBytes.Length, asciiChars, 0); 
  gb2312info = new string(asciiChars); 
   
  当然，其他各种编码之间的转换，跟上述代码也类似的，

转载于:https://www.cnblogs.com/szxgwp/archive/2010/05/28/1746530.html