编码理论基础概念

本章主要讲述了编码理论基础概念,包括了信道编码定理、硬判决与软判决、基本信道模型及其信道容量、MAP与ML算法、因子图与和积算法的基本知识。
展开查看详情

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