编码理论基础概念

1 .第二章 基础理论 1 

2 . 本章内容  第二章 基础理论  2.1 信道编码定理  2.2 硬判决与软判决  2.3 基本信道模型及其信道容量  2.4 MAP与ML算法  2.5 因子图与和积算法 2 

3 . 2.1 信道编码定理  信道编码定理：对于一个有噪信道，信道容量为C，只要数 据传输速率R<C，总会存在一种编码方法，使编码错误概率 p随着码长n的增加，按指数下降到任意小的值（用最大似然 译码）。即可以通过编码使通信过程实际上不发生错误，或 使错误控制在允许的数值下。  根据信息论，信道容量是由输入和输出的最大互信息量决定 的，即 C  max p( x) I ( X ,Y ) 其中X和Y分别代表信道的输入和输出；p(x)是X的概率密度 函数；I(X,Y)为变量X和Y的互信息，其定义将根据具体信道 类型（BSC、AWGN等）的不同有所区别。 3 

4 . 2.2 硬判决和软判决  假设X和Y分别为q元符号和Q元符号，对于离散信道，输入 变量X和输出变量Y之间的互信息I(X,Y)定义为： q 1 Q 1 p( yi | x j ) I ( X , Y )   p( x j ) p( yi | x j ) log 2 j 0 i 0 p( yi ) 对上式取最大值，就得到硬判决的信道容量Chard。当输入输 出均为二元离散符号时，信道就可以用BSC模型来描述。  若系统采用软判决译码，信道译码器的输入为连续值，即 y  (, ) ，则信道等效为离散输入连续输出信道，X和 Y之间的互信息I(X,Y)为： q 1  p( y | x j ) I ( X ,Y )    p( x j ) p( y | x j ) log 2 dy  p( y ) j 0 其中p(y|xj)表示发送xj时解调器输出y的概率密度函数。对上 式取最大值，就得到软判决时的信道容量Csoft。 4 

5 . 2.3 基本信道模型及其信道容量 2.3.1 BSC信道 0 1-p 0 p  设传错概率为p，二进制对称信道(BSC)模型为： p 1 1-p 其信道容量为： 1 1 1 p( yi | x j ) C  max I ( X , Y )   p( x j ) p( yi | x j ) log 2  1  p log 2 ( p)  (1  p) log 2 (1  p) p( x) j 0 i 0 p( yi ) 1 我们知道，对于一个集合X，其熵为： H ( X )   p( x) log xX p ( x) 因此，BSC的信道容量为： C  max I ( X , Y )  1  H ( p) p( x) 即每个信息比特携带1－H(p)的信息。若采用码率为R的编码，在传输错 误概率为p时，每个码字比特携带的信息量为R(1-H(p))，它不能超过信道 容量，因此有： C R(1  H ( p))  C  R  1  H ( p) 张忠培等著，《现代编码理论与应用》，国防工业出版社，2007 5 

6 . 对于AWGN信道，采用BPSK调制时BSC信道传输错误概率p为：  2 Es   2 REb  p  Q    Q    N0   N0   若要 p  0 ，则实际信噪比只需大于 R  0 时的信噪比（临界点） 即可。 C 1  p log 2 ( p)  (1  p) log 2 (1  p)  进行求导  lim(1  H ( p))  lim  lim   p 0 R 0 R R 0 R  ln( p)的导数为p / p   1 1   lim  p log 2 ( p)  p p  p log 2 (1  p)  (1  p) (  p)  R 0  (ln 2) p (ln 2)(1  p)   2 REb  1  由于 lim p  lim Q    R 0 R 0  N0  2 1    y2 / 2  错误概率p是一个Q函数，Q ( x )  e dy ，其导数为： 2 x  REb 1 Eb p   e N0 2  RN 0 6 

7 . C 2 Eb  这样 lim  R 0 R  ln(2) N 0 实现无差错传输时，p＝0，从而H(b)＝0，因此 Eb  ln(2) SNR    0.37dB N0 2 即只有在信道SNR大于0.37dB时才能实现无错传输，该值称为BSC信道 的Shannon限。 7 

8 . 2.3.2 AWGN信道的容量  连续输入、连续输出AWGN信道容量  带限AWGN信道的信道容量公式为：  S  S  C  W log 2 1    W log 2 1    N  N 0W  其中W为信道带宽，噪声的双边功率谱密度为N0/2。 当编码速率为R，信息比特能量为Eb时，有 C  REb   log 2 1   W  N 0W  当 W   时，得到Shannon限的渐近值为： Eb 2R /W  1 SNR   lim  ln 2  1.6dB N0 W  C /W 即只有当SNR不小于－1.6dB时才可能实现无错传输，这就是理想情 况下AWGN信道的Shannon限。 8 

9 . 对于带限信道上的二元符号而言，在满足Nyquist的理想情况下（W ＝1/2T），S=REb/T，T为符号周期，AWGN信道的信道容量（每符 号所承载的信息量）为：  S 1  REb  1  2REb  C   C  T  W  T log 2 1    log 2 1    log 2 1    N  2  N 0WT  2  N 0  1  2 REb  则由  R  C  log 2 1   ，可得 2  N0  Eb 22 R  1  N0 2R 当R＝1/2时，Shannon容量限为0dB。 9 

10 . 输入离散、输出连续AWGN信道容量  输入为二元符号，电平幅度为  Es ，与BSC类似，只有在输入符 号等概时才能使互信息值达到最大，即信道容量。此时输入符号的概 1  率密度函数为 p( x)    x  Es   x  Es 。 2     设y(t)=x(t)+n(t)，其中n(t)服从均值为0、方差为  2 ＝N0/2的高斯分 布，x(t)=  Es ，条件概率密度函数为：  y    2 Es  N0   p y | x   Es   1 2  exp    2   n (t ) N  0,  2     s  X  E 2   y (t )  ,   根据信道容量定义，有： AWGN信道模型 C  max I ( X , Y )  max  H ( X )  H ( X | Y )  p( x) p( x) H ( X )   p( x) log 2 p( x)  1 x 10 

11 .  H (X |Y)      p( x, y ) log 2 p( x | y )dy x  Es   p ( y | x) p ( x)      p( y | x) p( x) log 2   dy x  Es  p( y )   y  RE    2 C  1  max   1  b  log 1  exp   4 y REb  exp    2    dy   N0   p( x)  N0    N0     由 R  C 即可求得Eb/N0的Shannon限。 下表表示在不同编码速率、不同BER要求下，二元输入、连续输 出AWGN信道下，系统所需的最小SNR。 编码速率 Pb(e)=10-2 Pb(e)=10-3 Pb(e)=10-4 Pb(e)=10-5 Pb(e)=0 1/2 -0.357 0.112 0.117 0.185 0.187 1/3 -0.961 -0.559 -0.502 -0.496 -0.495 11 

12 . 2.3.3 Rayleigh衰落信道的容量  在无线环境中，接收信号中包含很多反射波，根据中心极限定理，信道 冲激响应可看作是两个正交的0均值、σs方差的高斯分量的组合，因此， 信号的包络服从Rayleigh分布，相位服从{-π,+π}的均匀分布。信号在 Rayleigh衰落信道中传输会引入乘性干扰和加性噪声，接收信号为： y(t)=A(t)x(t)+n(t) j ( t ) n(t )  N0  A(t )   (t )e N  0,    2 X   Es   y (t )  ,  其中 A(t )   (t )e j (t ) 为乘性干扰， (t ) 称为信道增益，若仅仅考虑信号 的包络，则接收信号可表示为y=αx+n，其概率密度函数为Rayleigh分布，   /  s2 p( )  2 e ,  0 2 即 s 式中 σs为高斯分布的方差，由上式可得Rayleigh分布的均值mα和方差σα分别为   m   / 2 s  2   2    s2 2   12 

13 . 将乘性因子归一化，即E{α2}=1，则其分布可表示为： p( )  2 e  2 ,  0  若信道增益已知，则称有信道边信息(Side Information, SI)，否则，就称 无信道边信息（NSI）。下面给出这两种情况下的信道容量  有信道边信息 1  C     p( ) p( y | x  Es ,  ) log  1  ( y,  )  dyd  y 2  其中p(α)归一化的Rayleigh分布的PDF，p(y|x, α)是均值为α，方差为σ2的 高斯PDF，ψ(y, α)=exp(-2αy/σ2)。容量可通过数值积分得到。  无信道边信息 1  C    y p ( ) p ( y | x  E s ,  ) log  2 1   ( y )  dyd  其中  ( y )   p( ) p( y | x   Es ,  )d  p  ( ) p ( y | x   E s ,  ) d  容量通过数值积分得到。 E. K. Hall, S.G. Wilson. Design and analysis of Turbo codes on Rayleigh fading channels. IEEE JSAC, Vol.16, No.2, 1998. p160～174. 13 

14 . 2.4 MAP与ML算法  设s表示发送端的编码序列，其中s  S的选择概率为p(s)，接收机用接收 到的序列r来判决发送信号s是什么。设估计的判决 sˆ  S 。  定理：最小化错误概率的判决准则是选择能使p(s|r)最大的那个s，即 sˆ  arg max p( s | r ) sS  根据Bayes准则，上式可写成 p(r | s ) p( s ) sˆ  arg max p( s | r )  arg max sS sS p(r )  由于分母不依赖于s，上式可进一步写成 sˆ  arg max p(r | s) p(s) 最大后验概率准则 sS 如果所有先验概率是相同的，该 准则可简化为： sˆ  arg max 最大似然判决准则 p( r | s ) sS 如果所有先验概率是相 思考一下：最大似然准则在什么 同的，两者是等价的！ 情况下不是最优算法，为什么？ 14 

15 . 2.5 因子图与和积算法  在1981年Tanner的论文中，介绍了一种可以用来表示码字的图形，称为 Tanner图。Tanner图包含两类节点：码元（变量）节点和校验节点，然 后通过边连接这两种不同的节点，并且同种节点间不能有直接的边连接。 如果给定一个码字的码元数和它的校验方程，则用Tanner图可以唯一地 确定该码字。例如一个（7, 3）线性分组码，其校验方程为： v1 v2 v3 v4 v5 v6 v7 1 1 1 0 1 0 0  s1 v1～v7是变量节点， H   1 1 0 1 0 1 0  s2 s1～s3是校验节点。  1 0 1 1 0 0 1  s3 v1 v2 v3 v4 v5 v6 v7 在用Tanner图表示的过程中，码的译 码算法是可以用明确的公式反映并可 程式化进行，即有很强的可实现性。 Tanner图从本质上讲是用码字的校验 方程来表述码字。 s1 s2 s3 R.M. Tanner. A recursive approach to low complexity codes. IEEE Trans. On Inform. Theory. Vol.27, No.5, 1981. p533-547. 15 

16 . 2.5.1 消息传递算法  和 积 算 法 (Sum-Product Algorithm) 作 为 一 种 通 用 的 消 息 传 递 算 法 (Message Passing Algorithm)，描述了因子图中顶点（变量节点和校验节 点）处的信息计算公式，而在基于图的编译码系统中，我们首先需要理 解的是顶点之间是如何通过边来传递信息。  例如，若干士兵排成一队列，每个士兵只能与他相邻的士兵交流，问如 何才能使每个士兵都知道总的士兵数？ L L+1 总人数：L+R+1 R+1 R 16 

17 . 将上面的情况抽象成一般模型，如下图所示，图中每个点可看作是一个 士兵，对应到编码理论中则可看作因子图中对应的节点（如前述的变量 节点和校验节点，或卷积码的BCJR算法中的状态点）。 (a) 先验信息 1 1 1 1 1 1 1 2 3 4 5 5 4 3 2 1 (b) 前向后向计算 1 1 1 1 1 1 1 2 3 4 5 5 4 3 2 1 (c) 前向后向计算 5 1 5 1 5 1 5 1 5 1 5 1 对应上图，引入几个概念：先验信息P、外信息E以及后验信息A。在上例中，先 验信息P表示每个士兵自身的数字1，如图（a）所示；外信息E表示从其他相邻的 士兵获取的信息，如图（c）所示，即每个士兵的外信息均为5；后验信息A＝P＋ E，在这里表示队列的总人数，即为6。从图中可以看出，得到最后的结果是通过 前向计算和后向计算得到的。 17 

18 .两 第1步 个 1 1 1 1 1 1 方 1 向 1 第2步  从图中可以看出，经过5 同 1 1 1 1 1 1 时 1 2 步计算第3、第4个士兵 计 第3步 可以得到总人数6(5+1)， 2 1 算 1 1 1 1 1 1 经过6步计算第2、第5个 的 1 2 3 士兵可以得到总人数， 前 第4步 经过7步计算所有士兵均 3 2 1 向 1 1 1 1 1 1 / 知道了总人数。 1 2 3 4 后 第5步 4 3 2 1 向 1 1 5 1 5 1 1 1 消 1 2 3 4 5 第6步 问题：如果士兵不是 息 5 4 3 2 1 传 1 5 1 1 1 5 1 1 按照队列排列，怎么 递 1 2 3 4 5 过 5 4 3 2 1 第7步 办呢？ 程 5 1 1 1 1 1 5 1 18 

19 . 8 1 1 1 7 1 1 2 2 8 7 4 1 1 1 5 7 8 8 2 1 1 （b） （a） 1  该图(a)与前图不同之处在于，有些士兵不止有2个相邻的士兵，可能有 3个或更多。具体信息传递流程如图(b)所示。每个士兵同样可以获得其 相邻士兵给他的外信息，同时加上自身的信息然后传递给相邻的士兵。  在上面的两个例子中，每个士兵节点的信息只需在所有其相邻节点上 进行一次前向和后向的计算，则每个士兵就可知道总人数。这样的图 有一个共同特点：所有节点构成一棵树，而树结构中是没有环路的。 如果有环路，会导致什么结果？ 19 

20 . 1 1 1 1 1 1  由于有环路的存在，如果用上述信息更新方法来确定总人数，将会导致 无法确定何时中止信息的传递，因此也就无法确定士兵人数。对应到编 码理论，则在设计LDPC码的校验矩阵时，应尽量避免校验矩阵对应的因 子图中出现短环（如4循环、6循环、8循环等）。 20 

21 . 2.5.2 因子图  将前述消息传递算法中的节点构成的图(Tanner图)更一般化就得到了因子 图。因子图是一种用于描述多变量函数的“二部图”(Bipartite Graph)。 一般来说，在因子图中存在两类节点：变量节点和对应的函数节点，变量 节点所代表的变量是函数节点的自变量。同类节点之间没有边直接相连。  例如：图（a）表示有5个自变量的函数g的因子图。假定函数g可以分解成 几个“局部函数”之积的形式，即： g(x1,x2,x3,x4,x5)=fA(x1)fB(x2)fC(x1,x2,x3)fD(x3,x4)fE(x3,x5) 则函数g的因子图表示如图（b）所示 x1 x1 x2 x3 x4 x5 x2 g （b） （a） x5 x3 x4 fA fB fC fD fE 局部函数节点与它相关联的自变量节点用边直接连 接，它反映了全局函数g和局部函数之间的关系。 F.R. Kschischang, B.R. Frey, H.A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Trans. On Inform. Theory. Vol.47, No.2, 2001. p498-519. 21 

22 . 2.5.3 边缘函数  在上一页的图（a）中，反映的是全局函数g(…)，但我们希望得到的往往 是通过这个全局函数计算出的各个边缘函数，如求上例中的 g~( x1 ) 。 设： g~( x1 )   g( x , x , x , x , x ) x2 , x3 , x4 , x5 1 2 3 4 5 g~( x1 ) 是函数g(x1,x2,x3,x4,x5)当变量为x2～x5时的和函数。将p21页的公 式带入上式，可写为： g~( x1 )   f A ( x1 ) f B ( x2 ) f C ( x1 , x2 , x3 ) f D ( x3 , x4 ) f E ( x3 , x5 ) x2 x3 x4 x5  f A ( x1 ) f B ( x2 ) f C ( x1 , x2 , x3 ) f D ( x3 , x4 ) f E ( x3 , x5 ) x2 x3 x4 x5 也可写为        f A ( x1 )   f B ( x2 ) fC ( x1 , x2 , x3 )    f D ( x3 , x4 )     f E ( x3 , x5 )   { x1 }    { x3 }   { x3 }   h( x , x , x )   h( x , x , x ) { x2 } 1 2 3 x1A1 x3A3 1 2 3 22 

23 . g(x1, x2, x3, x4, x5)=fA(x1)fB(x2)fC(x1, x2, x3)fD(x3, x4)fE(x3, x5)  如果求 g ( x3 ) ，即将x1、x2、x4、x5作为变量时， g(x1,x2,x3,x4,x5)的和函数。 g ( x3 )   x1 , x2 , x4 , x5 g ( x1 , x2 , x3 , x4 , x5 )          f A ( x1 ) f B ( x2 ) fC ( x1 , x2 , x3 )     f D ( x3 , x4 )     f E ( x3 , x5 )   { x3 }   { x3 }   { x3 }   推广到一般情况， g ( xi ) 为： g ( xi )   g ( x1 , x2 , , xi , , xN ) xj 其中 i {1, 2,..., N}, j {1, 2,..., N}\{i} 表示除去i的部分 计算复杂，如何简化呢？ 23 

24 .首先进行一些数学定义： f I ( x3 )   f E ( x3 , x5 ) x5 f II ( x3 )   f D ( x3 , x4 ) x4 f III ( x3 )  f I ( x3 )  f II ( x3 ) 可得到： f IV ( x1 , x2 )   fC ( x1, x2 , x3 ) f III ( x3 ) x3 fV ( x1 )   f B ( x2 ) f IV ( x1, x2 ) x2 最终： g~( x1 )  f A ( x1 )  fV ( x1 ) 简化的思想是基于将一个复杂任务分解成多个小任务，每个小任务对应 到因子图上就是一个函数节点。这使得其计算时不需要来自因子图其他 部分的信息，且传送其计算结果仅由这些局部函数的自变量来承担，从 而简化了计算。 24 

25 . 2.5.4 和积算法的表示及工作原理  和积算法从本质上就是一种消息传递算法，它可从全局函数计算出各个 不同的边缘函数。我们在前面求出了边缘函数 g~( x1 ) ，其因子图表示如 （a）所示。因子图只包含了变量与函数的对应关系，而运算关系并没有 得到明确、具体的可视化，因此人们又提出了表达式树图（expression trees）的概念， g~( x1 ) 的表达式树图如（b）所示。 g(x1,x2,x3,x4,x5)=fA(x1)fB(x2)fC(x1,x2,x3)fD(x3,x4)fE(x3,x5)       g ( x1 )  f A ( x1 )   f B ( x2 ) f C ( x1 , x2 , x3 )    f D ( x3 , x4 )     f E ( x3 , x5 )   { x1 }    { x3 }   { x3 }  x1 x1 fA fC  { x1 }  { x1 } x2 x3 fC （b） fA fB fD x2 x3 fE x4 x5  { x2 }  { x3 }  { x3 } （a） fB fD fE 25 

26 . 再例如，我们希望得到边缘函数 g ( x3 ) 。根据下式，我们可以画出其因 子图，如图（a）所示，其表达式树图如（b）所示。 g(x1,x2,x3,x4,x5)=fA(x1)fB(x2)fC(x1,x2,x3)fD(x3,x4)fE(x3,x5)       g ( x3 )    f A ( x1 ) f B ( x2 ) fC ( x1 , x2 , x3 )     f D ( x3 , x4 )     f E ( x3 , x5 )   { x3 }   { x3 }   { x3 }  x3 x3 fC fD fE  { x3 }  { x3 }  { x3 } x1 x2 x4 x5 fC fD fE fA fB （a） x1 x2 （b） 因子图和表达式树图  { x1 }  { x2 } 的对应关系？ fA fB 26 

27 . 从表示全局函数的因子图到表示各边缘函数 g ( xi ) 的表达式树图的转 换，应注意以下几点： ① 因子图中的每个变量用乘积运算符 “  ”代替； ② 因子图中的函数节点用“ f ”运算符代替（“form product and multiply f”）； ③ 在函数节点 f 和其parent x之间插入“ Σ {x} ”和式运算符；  这些局部转换如下图所示。图（a）对应于变量节点，图（b）对应于有 parent x的函数节点。  { x} 没有操作对象的乘积运算符“  ” ... f 可当作乘以1对待，或当它处在表达 （a） 式树图的末端时，可以忽略； 如果和 ... （b） 式运算符“Σ {x} ”运用到只有一 个自变量的函数中时，可以省略； 27 

28 . 在消息传递的过程中，需要计算不同的和与积，因此又称为和积算法（ Sum-Product Algorithm）。和积算法的更新如下图所示 h1 y1 h  x ( x ) 1  y  f ( x) 1 h2  x f ( x ) y1 x  f x ( x) ... ... f n( x ) \ { f } n( f ) \ {x} 设uxf(x)表示消息是从节点x到节点f， ufx(x)表示消息是从节点f到节点x， n(v)表示在因子图中给定节点v的邻居集合。 变量到局部函数： x f ( x )   hn ( x )\{ f } hx ( x)   局部函数到变量：  f x ( x)    f ( X )    y f ( y )  { x}  yn ( f )\{ x}  其中X＝n(f)是函数f的自变量集合 28 

29 .  例：前面的因子图如图（a）所示，和积算法产生的消息流如图（b）所 示，这些消息的产生有五步： ① fD ⑤ fA x1 ② ④ x4 x1 x2 x3 x4 x5 ⑤ ① ④ ③ ② x3 ② ④ ① fC ③ ⑤ fB x2 ④ ② x5 fA fB fC fD fE ⑤ fE ① （a） （b） 步骤1：  f A  x1 ( x1 )  f { x1 } A ( x1 )  f A ( x1 ) x  f ( x4 )  1 4 D f ( x2 )   f B ( x2 )  f B ( x2 ) x  f ( x5 )  1 B  x2 5 E { x2 } 步骤2： x  f ( x1 )   f 1 C A  x1 ( x1 ) f D  x3 ( x3 )  f { x3 } D ( x3 , x4 )  x4  f D ( x4 )  x  f ( x2 )   f 2 C B  x2 ( x2 ) f E  x3 ( x3 )  f { x3 } E ( x3 , x5 )   x5  f E ( x5 )  29