当前位置:   article > 正文

应用信息论基础 第五章 信道编码 笔记_联合典型序列

联合典型序列

学习要点:

  • 信道编码分析
  1. 联合典型序列
  2. 信道编码定理
  3. 信源信道联合编码定理
  • 信道编码设计
  1. 经验主义设计
  2. 编码错误概率
  3. 典型信道编码

5.1 基本概念

在这里插入图片描述

  • 从通信角度看信道编码:
    • 信道不可靠
    • W ^ \hat{W} W^ 与传输的消息 W W W 不同
  • 研究目标:
    • 使信息经信道传输后出现的差错最小!
  • 信道构成 { X , q ( y ∣ x ) , Y } \{\mathcal{X},q(y|x),\mathcal{Y}\} {X,q(yx),Y}
    • 输入:符号集合 { 1 , 2 , . . . , M } \{1,2,...,M\} {1,2,...,M}
    • 编码函数: X n : { 1 , 2 , . . . , M } → X n X^n:\{1,2,...,M\}\to\mathcal{X}^n Xn:{1,2,...,M}Xn
    • 译码函数: g : Y n → { 1 , 2 , . . . , M } g:\mathcal{Y}^n\to\{1,2,...,M\} g:Yn{1,2,...,M}
  • 信道编码 ( M , n ) (M,n) (M,n)

信道编码

  • 原理:
    • 增加冗余位,扩大信号空间,增大信号间距离
  • 分类:
    在这里插入图片描述
  • 比如线性码(linear code)
    • 编码函数为线性函数
    • 任意个码字的线性组合仍然是码字

性能指标——错误概率:

  • 条件错误概率:

λ i = P r { g ( Y n ) ≠ i ∣ X n = x n ( i ) } = ∑ y n q ( y n ∣ x n ( i ) ) I ( g ( y n ) ≠ i )

λi=Pr{g(Yn)i|Xn=xn(i)}=ynq(yn|xn(i))I(g(yn)i)
λi=Pr{g(Yn)=iXn=xn(i)}=ynq(ynxn(i))I(g(yn)=i)

其中 I ( ⋅ ) I(\cdot) I() 为指示函数

  • 最大错误概率:

λ ( n ) = max ⁡ i ∈ { 1 , . . . , M } λ i \lambda^{(n)}=\max_{i\in\{1,...,M\}}\lambda_i λ(n)=i{1,...,M}maxλi

  • 算术平均错误概率:

P e ( n ) = 1 M ∑ i = 1 M λ i P_e^{(n)}=\frac{1}{M}\sum_{i=1}^M\lambda_i Pe(n)=M1i=1Mλi

  • 若输入等概,则算术平均错误概率等于译码错误概率
  • 算术平均错误概率 ≤ \le 最大错误概率

性能指标——码率:

  • 码率: R = log ⁡ ∣ X ∣ M n R=\dfrac{\log_{|\mathcal{X}|}M}{n} R=nlogXM
    • 表示的是每个码字母所能携带的最大信息量,其中 log ⁡ ∣ X ∣ M \log_{|\mathcal{X}|}M logXM 是一个发送的消息可能具有的最大熵, n n n 为信道编码的长度,除以 n n n 表示信道码中每个码字所能携带的最大信息量(从原理上讲 R < 1 R<1 R<1),对应的单位是 bits/传输。(每一传输实际上就是发送一个信道码的一位,因为对于一个消息来说其信道码有 n n n 位,所以需要 n n n 次传输)
  • 可达:
    • 若存在(二元)序列 ( ⌈ 2 n R ⌉ , n ) (\lceil2^{nR}\rceil,n) (2nR,n) 满足: n → ∞ n\to\infty n 时, λ ( n ) → 0 \lambda^{(n)}\to 0 λ(n)0,则称码率 R R R 是可达的(achievable)
      • 2 n R ≤ ⌈ 2 n R ⌉ < 2 n R + 1 2^{nR}\le\lceil2^{nR}\rceil<2^{nR}+1 2nR2nR<2nR+1
      • ( ⌈ 2 n R ⌉ , n ) (\lceil 2^{nR}\rceil,n) (2nR,n) 简记为 ( 2 n R , n ) (2^{nR},n) (2nR,n)

信道容量的定义:

  • 离散无记忆信道(DMC)的信道容量为所有可达码率的上确界(上确界指的是最小上界), C = sup ⁡ R C=\sup{R} C=supR
    • 小于信道容量的码率可以获得任意小的差错概率
    • 蕴含着渐进无差错和码的存在性,指导工程实践
    • 信道容量定义: C = max ⁡ I ( X ; Y ) C=\max I(X;Y) C=maxI(X;Y),相对容易求解,但无法保证信道无差错传输
    • 香农第二定理说明了上述两种定义等价
      C = sup ⁡ R    ⟺    C = max ⁡ I ( X ; Y ) C=\sup{R}\iff C=\max I(X;Y) C=supRC=maxI(X;Y)

5.2 典型设计

  • 信道传输中如何减少差错?
  • 香农公式: C = W log ⁡ ( 1 + P s N 0 W ) C=W\log{(1+\dfrac{P_s}{N_0W})} C=Wlog(1+N0WPs)
  • 提高抗干扰能力的方法:
    • 增加功率(提高信噪比)
    • 加大带宽(信号变化剧烈)
    • 延长时间(降低速率)
  • 最直观的设计:重复和增加冗余

重复码:
在这里插入图片描述
在这里插入图片描述
二进制信道编码的码率-误差分析:

在这里插入图片描述

  • 码率 R = k n R=\dfrac{k}{n} R=nk
  • 误码率 P e = 1 k ∑ i = 1 k P e i , P e i = { v i ≠ u i } , i = 1 , . . . , k P_e=\frac{1}{k}\sum_{i=1}^kP_e^i,P_e^i=\{v_i\not=u_i\},i=1,...,k Pe=k1i=1kPei,Pei={vi=ui},i=1,...,k
  • 码率 R R R 和误码率 P e P_e Pe 在二进制独立信源以及二进制独立信道下的关系:

R ≤ 1 − H ( p ) 1 − H ( P e ) R\le\frac{1-H(p)}{1-H(P_e)} R1H(Pe)1H(p)

证明:

  1. Fano 不等式(二进制)
    H ( X ∣ Y ) ≤ H ( P e ) + P e log ⁡ ( K − 1 ) = H ( P e ) H(X|Y)\le H(P_e)+P_e\log(K-1)=H(P_e) H(XY)H(Pe)+Pelog(K1)=H(Pe)
  2. 互信息
    I ( X ; Y ) ≥ I ( U , V ) ≥ ∑ i = 1 k I ( U i ; V i ) = ∑ i = 1 k ( H ( U i ) − H ( U i ∣ V i ) ) = k − ∑ i = 1 k H ( U i ∣ V i ) ≥ k − k H ( P e )
    I(X;Y)I(U,V)i=1kI(Ui;Vi)=i=1k(H(Ui)H(Ui|Vi))=ki=1kH(Ui|Vi)kkH(Pe)
    I(X;Y)I(U,V)i=1kI(Ui;Vi)=i=1k(H(Ui)H(UiVi))=ki=1kH(UiVi)kkH(Pe)

n C ≥ k ( 1 − H ( P e ) )    ⟹    k n ≤ 1 − H ( p ) 1 − H ( P e ) nC\ge k(1-H(P_e))\implies\frac{k}{n}\le\frac{1-H(p)}{1-H(P_e)} nCk(1H(Pe))nk1H(Pe)1H(p)

在这里插入图片描述
无差错传输的要求:

  • 传输速率与信道容量 R ≤ 1 − H ( p ) 1 − H ( P e ) = C 1 − H ( P e ) R\le\dfrac{1-H(p)}{1-H(P_e)}=\dfrac{C}{1-H(P_e)} R1H(Pe)1H(p)=1H(Pe)C
  • 误码率 P e ≥ H − 1 ( 1 − C R ) P_e\ge H^{-1}(1-\dfrac{C}{R}) PeH1(1RC)
  • R > C R>C R>C,则 P e > 0 P_e>0 Pe>0,传输有差错,通信不可靠
  • R < C R<C R<C R = C R=C R=C P e P_e Pe 可以等于零

好码的要求:

  1. 相同误码率下,码率越高越好
  2. P e = 0 P_e=0 Pe=0 R R R 能无限提高吗?(信道编码定理想要回答的问题)

5.3 信道编码定理

典型序列(Typical Sequence)

  • 渐进均分性定理(AEP)
    • X 1 , . . . X n ∼ p ( x ) , i . i . d . , E X n = μ < ∞ X_1,...X_n\sim p(x),i.i.d.,EX_n=\mu<\infty X1,...Xnp(x),i.i.d.,EXn=μ<,则
      1 n log ⁡ p ( X 1 , . . . , X n ) ⟶ 依概率 H ( X ) \frac{1}{n}\log{p(X_1,...,X_n)}\overset{\text{依概率}}{\longrightarrow} H(X) n1logp(X1,...,Xn)依概率H(X)
  • 典型序列及典型集(typical set)
    • 序列 ( x 1 , . . . , x n ) ∈ X n (x_1,...,x_n)\in\mathcal{X}^n (x1,...,xn)Xn 满足 2 − n ( H ( X ) + ϵ ) ≤ p ( x 1 , . . . , x n ) ≤ 2 − n ( H ( X ) − ϵ ) 2^{-n(H(X)+\epsilon)}\le p(x_1,...,x_n)\le 2^{-n(H(X)-\epsilon)} 2n(H(X)+ϵ)p(x1,...,xn)2n(H(X)ϵ),典型序列的集合称为典型集 A ϵ ( n ) A_\epsilon^{(n)} Aϵ(n)
  • 性质:
    • 典型集的概率近似为 1
    • 典型集中所有元素几乎是等概的
    • 典型集的元素个数几乎等于 2 n H ( X ) 2^{nH(X)} 2nH(X)

联合典型序列(Jointly Typical Sequence, JTS)

  • 联合典型序列
    • ( X , Y ) ∼ p ( x , y ) (X,Y)\sim p(x,y) (X,Y)p(x,y),随机序列对 ( x n , y n ) ∈ X n × Y n (x^n,y^n)\in\mathcal{X}^n\times\mathcal{Y}^n (xn,yn)Xn×Yn
      • ∣ − 1 n log ⁡ p ( x n ) − H ( X ) ∣ < ϵ |-\frac{1}{n}\log{p(x^n)}-H(X)|<\epsilon n1logp(xn)H(X)<ϵ
      • ∣ − 1 n log ⁡ p ( y n ) − H ( Y ) ∣ < ϵ |-\frac{1}{n}\log{p(y^n)}-H(Y)|<\epsilon n1logp(yn)H(Y)<ϵ
      • ∣ − 1 n log ⁡ p ( x n , y n ) − H ( X , Y ) ∣ < ϵ |-\frac{1}{n}\log{p(x^n,y^n)-H(X,Y)}|<\epsilon n1logp(xn,yn)H(X,Y)<ϵ
      • 其中 p ( x n , y n ) = ∏ i = 1 n p ( x i , y i ) p(x^n,y^n)=\prod_{i=1}^np(x_i,y_i) p(xn,yn)=i=1np(xi,yi)
  • 联合典型集
    • 联合典型序列构成的集合记为 A ϵ ( n ) A_\epsilon^{(n)} Aϵ(n)

联合渐进均分性(Joint AEP)

  • ( X n , Y n ) ∼ p ( x n , y n ) = ∏ i = 1 n p ( x i , y i ) , i . i . d . (X^n,Y^n)\sim p(x^n,y^n)=\prod_{i=1}^np(x_i,y_i),i.i.d. (Xn,Yn)p(xn,yn)=i=1np(xi,yi),i.i.d.
    • n → ∞ n\to\infty n 时, P r { ( X n , Y n ) ∈ A ϵ ( n ) } → 1 \mathrm{Pr}\{(X^n,Y^n)\in A_\epsilon^{(n)}\}\to 1 Pr{(Xn,Yn)Aϵ(n)}1
    • ∣ A ϵ ( n ) ∣ ≤ 2 n ( H ( X , Y ) + ϵ ) , ∣ A ϵ ( n ) ∣ ≥ ( 1 − ϵ ) 2 n ( H ( X , Y ) − ϵ ) |A_\epsilon^{(n)}|\le 2^{n(H(X,Y)+\epsilon)},|A_\epsilon^{(n)}|\ge(1-\epsilon)2^{n(H(X,Y)-\epsilon)} Aϵ(n)2n(H(X,Y)+ϵ),Aϵ(n)(1ϵ)2n(H(X,Y)ϵ)
    • 如果 X ~ n \tilde{X}^n X~n Y ~ n \tilde{Y}^n Y~n 独立且 ( X ~ n , Y ~ n ) ∼ p ( x n ) p ( y n ) (\tilde{X}^n,\tilde{Y}^n)\sim p(x^n)p(y^n) (X~n,Y~n)p(xn)p(yn),则 P r { ( X ~ n , Y ~ n ) ∈ A ϵ ( n ) } ≤ 2 − n ( I ( X ; Y ) − 3 ϵ ) \mathrm{Pr}\{(\tilde{X}^n,\tilde{Y}^n)\in A_\epsilon^{(n)}\}\le 2^{-n(I(X;Y)-3\epsilon)} Pr{(X~n,Y~n)Aϵ(n)}2n(I(X;Y)3ϵ),且对于充分大的 n n n,有 P r { ( X ~ n , Y ~ n ) ∈ A ϵ ( n ) } ≥ ( 1 − ϵ ) 2 − n ( I ( X ; Y ) + 3 ϵ ) \mathrm{Pr}\{(\tilde{X}^n,\tilde{Y}^n)\in A_\epsilon^{(n)}\}\ge(1-\epsilon)2^{-n(I(X;Y)+3\epsilon)} Pr{(X~n,Y~n)Aϵ(n)}(1ϵ)2n(I(X;Y)+3ϵ)

在这里插入图片描述
信道编码定理(Channel Coding Theorem, CCT)

  • 信息论最重要的结论
    • Shannon Theorem II (Noisy-channel coding theorem)
    • 有噪信道可实现几乎无失真传输
  • 该定理的结果与直观感觉正好相反
    • 若信道有错误,如何能够完全纠正?
    • 尤其是:纠正的过程本身也受错误的影响
  • 基本思想:
    • 允许任意小的非零错误概率存在
    • 构造码列 C ( n ) , n → ∞ C^{(n)},n\to\infty C(n),n,保证大数定律或 AEP 生效
    • 计算随机码的平均错误概率,随机码=所有码的平均=存在至少一个满足要求的码,即由于随机码

表述:

正定理:对于离散无记忆信道(DMC),小于其容量 C C C 的所有码率是可达的,即对于任意 R < C R<C R<C,可以找到一个信道编码方案 ( 2 n R , n ) (2^{nR},n) (2nR,n),使得最大错误概率 λ ( n ) → 0 \lambda^{(n)}\to0 λ(n)0

逆定理:对于任意编码方案 ( 2 n R , n ) (2^{nR},n) (2nR,n),若 λ ( n ) → 0 \lambda^{(n)}\to0 λ(n)0,则必有 R ≤ C R\le C RC

证明正定理

  • 已知:DMC, X , Y , p ( y ∣ x ) , X ∼ p ( x ) \mathcal{X},\mathcal{Y},p(y|x),X\sim p(x) X,Y,p(yx),Xp(x)
  1. 编码:
  • p ( x ) p(x) p(x) 达到信道容量 C C C ,即 I ( X ; Y ) = C I(X;Y)=C I(X;Y)=C ,对于充分大的 n n n,根据 p ( x ) p(x) p(x) 独立生成 ( 2 n R , n ) (2^{nR},n) (2nR,n) C ( n ) C^{(n)} C(n)
    • ∀ x n ∈ C ( n ) , p ( x n ) = ∏ i = 1 n p ( x i ) \forall x^n\in C^{(n)},p(x^n)=\prod_{i=1}^np(x_i) xnC(n),p(xn)=i=1np(xi) C ( n ) C^{(n)} C(n) 2 n R 2^{nR} 2nR 个码字
    • 设接收向量为 y n y^n yn ,则 p ( y n ∣ x n ) = ∏ i = 1 n p ( y i ∣ x i ) p(y^n|x^n)=\prod_{i=1}^np(y_i|x_i) p(ynxn)=i=1np(yixi)
  1. 译码(前两种最优,第三种简单):
  • 最大后验概率(MAP):选择 x ^ n ∈ C ( n ) \hat{x}^n\in C^{(n)} x^nC(n) 满足 p ( x ^ n ∣ y n ) p(\hat{x}^n|y^n) p(x^nyn) 最大。
  • 最大似然(ML):选择 x ^ n ∈ C ( n ) \hat{x}^n\in C^{(n)} x^nC(n) 满足 p ( y n ∣ x ^ n ) p(y^n|\hat{x}^n) p(ynx^n) 最大。
  • 典型集译码:选择 x ^ n ∈ C ( n ) \hat{x}^n\in C^{(n)} x^nC(n) 满足 x ^ n \hat{x}^n x^n y n y^n yn 联合典型。
  • 若接收到的序列 y n y^n yn 存在唯一的发送序列 x ^ n \hat{x}^n x^n 与其具有联合典型性,则解码成功;
  • 否则,解码错误,记为事件 E \mathcal{E} E
  • 目标:将证明若 R < C R<C R<C,则 P r { E } → 0 \mathrm{Pr}\{\mathcal{E}\}\to0 Pr{E}0
    • 若平均错误概率 → 0 \to0 0 ,则 λ ( n ) → 0 \lambda^{(n)}\to0 λ(n)0,从而 R R R 可达。
  1. 错误事件(两种情形):
  • 存在 x ^ n \hat{x}^n x^n y n y^n yn 联合典型, x n x^n xn y n y^n yn 联合典型,但 x ^ n ≠ x n \hat{x}^n \neq x^n x^n=xn
  • x n x^n xn y n y^n yn 非联合典型
  1. 错误概率:
  • x n ( i ) x^n(i) xn(i) 为第 i i i 个码字, i = 1 , . . . , M , M = 2 n R i=1,...,M,M=2^{nR} i=1,...,M,M=2nR ,假设发送 x n ( 1 ) x^n(1) xn(1)
  • E i ≜ { ( x n ( i ) , y n ) ∈ A ϵ ( n ) } E_i\triangleq\{(x^n(i),y^n)\in A_\epsilon^{(n)}\} Ei{(xn(i),yn)Aϵ(n)}

  • λ 1 = P r { E ∣ x n ( 1 ) } = P r { E ˉ 1 ∪ E 2 ∪ . . . ∪ E M } ≤ P r { E ˉ 1 } + ∑ i = 2 M P r { E i } ≤ ϵ + ( M − 1 ) 2 − n [ I ( X ; Y ) − 3 ϵ ] ≤ ϵ + 2 3 n ϵ ⋅ 2 − n ( C − R ) ≤ 2 ϵ
    λ1=Pr{E|xn(1)}=Pr{E¯1E2...EM}Pr{E¯1}+i=2MPr{Ei}ϵ+(M1)2n[I(X;Y)3ϵ]ϵ+23nϵ2n(CR)2ϵ
    λ1=Pr{Exn(1)}=Pr{Eˉ1E2...EM}Pr{Eˉ1}+i=2MPr{Ei}ϵ+(M1)2n[I(X;Y)3ϵ]ϵ+23nϵ2n(CR)2ϵ

    由对称性 λ i = λ 1 ≤ 2 ϵ    ⟹    P e ( n ) = P r { E } ≤ 2 ϵ \lambda_i=\lambda_1\le2\epsilon\implies P_e^{(n)}=\mathrm{Pr}\{\mathcal{E}\}\le2\epsilon λi=λ12ϵPe(n)=Pr{E}2ϵ
  1. 码率的可达性
  • C ( n ) C^{(n)} C(n) 是按照 p ( x ) p(x) p(x) 随机生成的 ( M , n ) (M,n) (M,n) 码,译码错误概率记为 P e ( n ) P_e^{(n)} Pe(n)
  • C ( n ) C^{(n)} C(n) 为所有服从 p ( x ) p(x) p(x) ( M , n ) (M,n) (M,n) 码的平均
    • ∃ \exists 最优的 ( M , n ) (M,n) (M,n) C ( n ) ∗ C^{(n)*} C(n) ,使得 P r { C ( n ) 出 错 } ≤ 2 ϵ \mathrm{Pr}\{C^{(n)}出错\}\le2\epsilon Pr{C(n)}2ϵ
    • 不妨设 λ 1 ∗ ≤ λ 2 ∗ ≤ . . . ≤ λ M ∗ \lambda_1^*\le\lambda_2^*\le...\le\lambda_M^* λ1λ2...λM,则 λ M / 2 ∗ ≤ 4 ϵ \lambda_{M/2}^*\le4\epsilon λM/24ϵ
  • 构造新码 C ~ ( n ) ∗ = { C ( n ) ∗ 错 误 概 率 最 小 的 一 半 码 字 } \tilde{C}^{(n)*}=\{C^{(n)*}错误概率最小的一半码字\} C~(n)={C(n)}
    • 最大错误概率 λ ~ ( n ) ∗ ≤ 4 ϵ \tilde{\lambda}^{(n)*}\le4\epsilon λ~(n)4ϵ
    • C ~ ( n ) ∗ \tilde{C}^{(n)*} C~(n) M 2 = 2 n R − 1 \frac{M}{2}=2^{nR-1} 2M=2nR1 个码字,码率为 R ( 1 − 1 n ) R(1-\frac{1}{n}) R(1n1)
    • n → ∞ n\to\infty n 时, C ~ ( n ) ∗ \tilde{C}^{(n)*} C~(n) 满足 R ( 1 − 1 n ) → R R(1-\frac{1}{n})\to R R(1n1)R λ ~ ( n ) ∗ → 0 \tilde{\lambda}^{(n)*}\to0 λ~(n)0
    • 因此 R R R 可达

在这里插入图片描述

证明逆定理

需证明:

∀ \forall 可达速率 R R R ,有 R ≤ C R\le C RC    ⟺    \iff ∀ R > C \forall R>C R>C R R R 不可达,即 P e ( n ) ↛ 0 P_e^{(n)}\not\to0 Pe(n)0

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5.4 典型信道编码

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5.5 信源信道联合编码定理

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号