精华内容
下载资源
问答
  • 信道极化图解,信道在经过极化后,有的性能接近1,有的接近0,保证正确
  • 极化码信道极化仿真

    2019-01-18 15:30:40
    根据Arikan的论文自己编写的信道极化的仿真matlab程序。。
  • 信道极化编码

    2014-08-19 18:28:43
    对于对称二进制无记忆信道,通过信道极化可以构造趋于信道容量的编码。
  • 金属V形槽引导信道极化等离子体激元
  • 信道极化:信道分裂和合并 这一部分讲的是:把信道区分出两个极端,用传输信息位和冻结比特位(信道只有一个,只是不断的在复用) 构造——讲的如何把这些hao

    信道极化:信道分裂和合并

    这一部分讲的是:把信道区分出两个极端,用传输信息位和冻结比特位(信道只有一个,只是不断的在复用,可以把这个信道看成一个广义,就是说用的是一个信道,比特是一个一个传输,通过极化把好的和坏的区分开来,我们看做把比特传输一次看成一次在信道中传输,传1024个比特看成在1024个信道中传输)
    合并和分裂可以用下图表示:
    (作用:选出好的信道传输信息比特,不好的信道传输冻结比特位)
    在这里插入图片描述

    信道合并可以看成编码,信道分裂看成译码:
    信道合并:信道的合并就是将 N 个独立并且相同的 B-DMC 信道W 递归地结合,得到一个 N维的复合信道 。
    两个二维信道合并成一个四维
    在这里插入图片描述
    在这里插入图片描述
    我们上述图表示的过程看成编码过程,如下面的公式:
    在这里插入图片描述
    信道分裂:
    在这里插入图片描述

    信道分裂可以用上图表示
    无论是信道合并还是信道分裂都是一个迭代递归的过程,公式如下:
    在这里插入图片描述

    构造——

    展开全文
  • 作者为:Erdal Arıkan 本文参考了些此网站上的翻译:https://marshallcomm.cn/2017/03/04/polar-code-2-encoding-principle/ 摘要 提出了一种称为信道极化的方法来构造达到任意给定二进制输入离散无记忆信道(B-DMC...

    论文原文为:《Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels》本文为其翻译。
    作者为:Erdal Arıkan
    本文参考了些此网站上的翻译:https://marshallcomm.cn/2017/03/04/polar-code-2-encoding-principle/

    摘要

    提出了一种称为信道极化的方法来构造达到任意给定二进制输入离散无记忆信道(B-DMC) W W W的对称容量 I ( W ) I(W) I(W)的码序列。对称容量是使用具有相等概率的信道的输入字符可以达到的最高速率。信道极化是指可以从给定B-DMC W W W N N N个独立副本中合成第二组 N N N个二进制输入信道 { W N ( i ) : 1 ≤ i ≤ N } \{W^{(i)}_N:1≤i≤N\} {WN(i):1iN},使得当 N N N变大时, W N ( i ) W^{(i)}_N WN(i)接近1的索引 i i i的分数接近 I ( W ) I(W) I(W) W N ( i ) W^{(i)}_N WN(i)接近0的索引 i i i的分数接近 1 − I ( W ) 1-I(W) 1I(W)。极化信道 { W N ( i ) } \{W^{(i)}_N\} {WN(i)}对于信道编码是条件良好的:只需要通过容量接近1的通道以速率1发送数据,其余通道以速率0发送数据。基于此思想构造的代码称为极性代码。本文证明了,给定任意 I ( W ) > 0 I(W)>0 I(W)>0的B-DMCW和任意目标码率 R < I ( W ) R<I(W) R<I(W),存在一个极化码序列{CN;n≥1},使得Cn的块长 N = 2 n N=2^n N=2n,码率 ≥ R ≥R R,在与码速率无关的情况下,逐次抵消译码下块差错概率有界为 P e ( N , R ) ≤ O ( N − 14 ) Pe(N,R)≤O(N−14) Pe(NR)O(N14)。这种性能可以通过编码器和解码器来实现,每个编码器和解码器的复杂度分别为 O ( N l o g N ) O(NlogN) O(NlogN)

    I.引言与概述

    香农关于有噪的信道编码定理的一个令人着迷的证明是,他使用随机编码方法来显示容量实现代码序列的存在,而不给出任何特定的这种序列[1]。从那时起,构造具有低编码和解码复杂度的可证明容量的代码序列成为了一个遥不可及的目标。 本文是针对B-DMC类的这一目标的尝试。
    在这一部分中,我们将对本文的主要观点和结果进行说明。 首先,我们给出了一些定义,并陈述了通篇使用的一些基本事实。

    A.前期工作

    一个二进制输入离散无记忆信道(B-DMC)可表示为 W : X → Y W:X→Y WXY表示为具有输入字母X,输出字母Y和转移概率W(y | x),x∈X,y∈Y。由于信道是二进制输入,集合 X = 0 , 1 X={0,1} X=0,1 Y Y Y W ( y ∣ x ) W(y|x) W(yx)是任意值。我们用 W N W^N WN表示 N N N次使用 W W W时对应的信道。因此, W N : X N → Y N W^N:X^N → Y^N WN:XNYN的转移概率为 W N ( y 1 N ∣ x 1 N ) = ∏ i = 1 N W ( y i ∣ x i ) W^N (y^N_1 | x^N_1) = \prod^N_{i = 1}W (y_i | x_i) WN(y1Nx1N)=i=1NW(yixi)
    在给定B-DMCW的情况下,本文主要关注两个信道参数:对称容量
    在这里插入图片描述
    和巴氏指标参数

    在这里插入图片描述
    这些参数分别被用作速率和可靠性的度量。 I ( W ) I(W) I(W)是信道 W W W在等概率输入下的进行可靠传输的最高速率, Z ( W ) Z(W) Z(W)是当W仅使用一次发送0或1时最大似然(ML)判决错误概率的上界。
    很容易看到 Z ( W ) Z(W) Z(W)取值于 [ 0 , 1 ] [0,1] [0,1]。 自始至终,我们将使用以2为底的对数;因此, I ( W ) I(W) I(W)也将取值于 [ 0 , 1 ] [0,1] [0,1]。 码率和信道容量的单位将是比特。
    且仅当 Z ( W ) ≈ 0 Z(W)≈0 Z(W)0时, I ( W ) ≈ 1 I(W)≈1 I(W)1;当且仅当 Z ( W ) ≈ 1 Z(W)≈1 Z(W)1时, I ( W ) ≈ 0 I(W)≈0 I(W)0。附录中证明的以下界限可以使这一点更加精确。
    命题1:对于任何B-DMCW,我们都有
    在这里插入图片描述
    当W是对称信道时,对称容量I(W)等于香农容量,即存在输出字母 Y Y Y的置换 π π π的信道,使得(I) π − 1 = π π^{−1}=π π1=π和(ii) W ( y ∣ 1 ) = W ( π ( y ) ∣ 0 ) W(y|1)=W(π(y)|0) W(y1)=W(π(y)0)对于所有y∈Y。二进制对称信道(Binary Symmetric Channel,BSC)和二进制删除信道(Binary Erasure Channel,BEC)都是满足对称性的B-DMC。具体地说,对于 Y = { 0 , 1 } Y=\{0,1\} Y={0,1},满足 W ( 0 ∣ 0 ) = W ( 1 ∣ 1 ) W(0|0)=W(1|1) W(00)=W(11) W ( 1 ∣ 0 ) = W ( 0 ∣ 1 ) W(1|0)=W(0|1) W(10)=W(01)的B-DMC是为BSC。对于 y ∈ Y y∈Y yY,满足 W ( y ∣ 0 ) W ( y ∣ 1 ) = 0 W(y|0)W(y|1)=0 W(y0)W(y1)=0 W ( y ∣ 0 ) = W ( y ∣ 1 ) W(y|0)=W(y|1) W(y0)=W(y1)的B-DMC是为BEC。对于BEC,符号 y y y称为删除符号(Erasure Symbol)所有删除符号上的总和 W ( y ∣ 0 ) W(y|0) W(y0)称为BEC的删除概率。

    我们用大写字母(如 X , Y X,Y XY)表示随机变量(RVs),用相应的小写字母(如 x , y x,y xy)表示它们的实现(样本值)。对于 X X X 是RV, P X P_X PX表示X上的概率分配,对于 R V ( X , Y ) RV(X,Y) RV(XY)的联合集合, P X , Y P_{X,Y} PXY表示联合概率分配,我们用标准记号 I ( X ; Y ) I(X;Y) I(XY) I ( X ; Y ∣ Z ) I(X;Y|Z) I(XYZ)分别表示互信息及其条件形式。
    行向量 ( a 1 , … , a N ) (a1,…,aN) (a1,,aN)在这里简写为 a 1 N a^N_1 a1N。对于给定的行向量 a 1 N a^N_1 a1N,其子向量表示为 a i j a^j_i aij, 1 ≤ i , j ≤ N 1≤i,j≤N 1i,jN,且 i ≤ j i≤j ij。如果 j < i j <i j<i a i j a^j_i aij被视为无效。对于给定的 a 1 N a^N_1 a1N A ⊂ { 1 , … , N } A⊂\{1,…,N\} A{1,,N},记 a A a_A aA表示子向量 ( a i : i ∈ A ) (a_i:i∈A) (ai:iA)。记 a 1 , o j a^j_{1,o} a1,oj表示奇数索引的子向量
    ( a k : 1 ≤ k ≤ j ; k   o d d ) (a_k:1≤k≤j;k\ odd) (ak:1kj;k odd),记 a 1 , e j a^j_{1,e} a1,ej表示偶数索引的子向量 ( a k : 1 ≤ k ≤ j ; k   e v e n ) (a_k:1≤k≤j;k\ even) (ak:1kj;k even)。例如,对于向量 a 1 5 = ( 5 , 4 , 6 , 2 , 1 ) a^5_1=(5,4,6,2,1) a15=(5,4,6,2,1),有 a 2 4 = ( 4 , 6 , 2 ) a^4_2=(4,6,2) a24=(4,6,2) a 1 , e 5 = ( 4 , 2 ) , a 1 , o 4 ( 5 , 6 ) a^5_{1,e}=(4,2),a^4_{1,o}(5,6) a1,e5=(4,2)a1,o4(5,6)。全零向量则记为 0 1 N 0^N_1 01N

    本文中的码构造将在二进制域GF(2)上的向量空间中进行。 除非另有说明,否则所有的向量、矩阵和对它们的运算都将是GF(2)上的。

    特别地,对于GF(2)上的 a 1 N a^N_1 a1N b 1 N b^N_1 b1N向量,我们写 a 1 N ⊕ b 1 N a^N_1⊕b^N_1 a1Nb1N表示它们的分量mod-2和。 m × n m×n m×n矩阵 A = [ A i j ] A = [A_{ij}] A=[Aij] r × s r×s r×s矩阵 B = [ B i j ] B = [B_{ij}] B=[Bij]的Kronecker乘积定义为
    在这里插入图片描述
    这是一个mr-by-ns矩阵。 对于所有n≥1,克罗内克积 A ⊗ n A^{⊗n} An被定义为 A ⊗ A ⊗ ( n − 1 ) A⊗A^{⊗(n-1)} AA(n1)。 并定义 A ⊗ 0 ≜ [ 1 ] A^{⊗0} \triangleq [1] A0[1]的约定。
    我们用 ∣ A ∣ | A | A来表示集合 A A A中元素的数目,我们用 1 A 1_A 1A来表示集合的指示函数;因此,如果 x ∈ A x∈A xA,则 1 A ( x ) 1_{A(x)} 1A(x)等于1,否则为0。

    B.信道极化

    通道极化是一种操作,通过该操作,从给定B-DMC W W W N N N个独立副本中制造第二组N个信道 { W N ( i ) : 1 ≤ i ≤ N } \{W^{(i)}_N:1≤i≤N\} {WN(i)1iN},其显示极化效应的意义是,对称容量项 { W N ( i ) } \{W^{(i)}_N\} {WN(i)}对于除索引 i i i的消失部分之外的所有项都趋向于0或1。 该操作由信道合并阶段和信道分裂阶段组成。

    1)信道合并:

    此阶段以递归方式合并给定B-DMC W的副本,以产生向量通道 W N : X N → Y N W_N:X_N→Y_N WNXNYN,其中 N N N可以是2的任意幂, N = 2 n , n ≥ 0 N = 2^n,n≥0 N=2nn0。 递归从第0级( n = 0 n = 0 n=0)开始,只有一个W副本,并且我们设置 W 1 ≜ W W_1\triangleq W W1W。 递归的第一级( n = 1 n = 1 n=1)组合了 W 1 W_1 W1的两个独立副本,如图1所示,并获得了具有转移概率的通道 W 2 : X 2 → Y 2 W_2:X^2→Y^2 W2X2Y2
    在这里插入图片描述
    在这里插入图片描述
    第2级(n=2)递归如图2所示,联合信道 W 2 W_2 W2的2个独立副本得到信道 W 4 : X 4 → Y 4 W_4:X^4→Y^4 W4:X4Y4,其转移概率为
    在这里插入图片描述
    在这里插入图片描述
    在图2中, R 4 R_4 R4是完成从 ( s 1 , s 2 , s 3 , s 4 ) (s_1,s_2,s_3,s_4) (s1,s2,s3,s4) v 1 4 = ( s 1 , s 3 , s 2 , s 4 ) v^4_1=(s_1,s_3,s_2,s_4) v14=(s1,s3,s2,s4)的置换操作(排序)。从信道 W 4 W_4 W4的输入 W 4 W^4 W4的输入的映射 u 1 4 → x 1 4 u^4_1→x^4_1 u14x14可用公式表示为 x 1 4 = u 1 4 G 4 x^4_1=u^4_1G_4 x14=u14G4.
    在这里插入图片描述
    因此 W 4 W_4 W4 W 4 W^4 W4的转移概率有关系式 W 4 ( y 1 4 ∣ u 1 4 ) = W 4 ( y 1 4 ∣ u 1 4 G 4 ) W_4(y^4_1|u^4_1)=W^4(y^4_1|u^4_1G_4) W4(y14u14)=W4(y14u14G4)

    图3所示为递归结构的一般形式。 W N / 2 W_{N/2} WN/2的2个独立副本联合产生信道 W N W_N WN。输入向量 u 1 N u^N_1 u1N进入信道 W N W_N WN,首先被转换为 s 1 N s^N_1 s1N s 2 i − 1 = u 2 i − 1 ⊕ u 2 i , s 2 i = u 2 i , 1 ≤ i ≤ N / 2 s_{2i−1}=u_{2i−1}⊕u_{2i},s_{2i}=u_{2i},1≤i≤N/2 s2i1=u2i1u2is2i=u2i1iN/2 R N R_N RN是一个排列,称为反向洗牌运算,输入为 s 1 N s^N_1 s1N,输出为 v 1 N = ( s 1 , s 3 , … , s N − 1 , s 2 , s 4 , … , s N ) v^N_1=(s_1,s_3,…,s_{N−1},s_2,s_4,…,s_N) v1N=(s1,s3,,sN1,s2,s4,,sN) v 1 N v^N_1 v1N则成为2个 W N / 2 W_{N/2} WN/2独立副本的输入。
    在这里插入图片描述
    映射 u 1 N ↦ v 1 N u^N_1\mapsto v^N_1 u1Nv1N是二元域GF(2)上的线性变换。 通过归纳法得出,从合成通道 W N W_N WN的输入到基础原始通道 W N W^N WN的输入的总体映射 u 1 N ↦ x 1 N u^N_1\mapsto x^N_1 u1Nx1N也是线性的,可以用矩阵 G N G_N GN表示,即 x 1 N = u 1 N G N x^N_1 = u^N_1G_N x1N=u1NGN
    我们称 G N G_N GN大小为 N N N的生成器矩阵
    两个信道 W N W_N WN W N W^N WN的转移概率由下式关联
    在这里插入图片描述
    其中 y 1 N ∈ Y N , u 1 N ∈ X N y^N_1∈ Y^N,u^N_1∈ X^N y1NYN,u1NXN.我们将在第VII节中证明,对于任何 N = 2 n N=2^n N=2n n ≥ 0 n≥0 n0 G N G_N GN等于 B N F ⊗ n B_NF^{⊗n} BNFn,其中 B N B_N BN是称为比特反转的置换矩阵,F= [ 1 0 1 1 ] \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} [1101]。 请注意,信道合并操作由矩阵 F F F完全指定。另请注意, G N G_N GN F ⊗ n F^{⊗n} Fn具有相同的行集,但顺序不同(位反转);我们将在第VII节中更详细地讨论此主题。

    2) 信道分裂

    W N W^N WN合成矢量通道 W N W_N WN之后,信道极化的下一步是将 W N W_N WN拆分为由转移概率定义的一组 N N N个二进制输入坐标信道 W N ( i ) : X → Y N × X i − 1 , 1 ≤ i ≤ N W^{(i)}_N:X→Y^N×X^{i-1},1≤i≤N WN(i)XYN×Xi1,1iN,已定义 由转移概率

    在这里插入图片描述
    其中 ( y 1 N , u 1 i − 1 ) (y^N_1,u^{i-1}_1) (y1Nu1i1)表示 W N ( i ) W^{(i)}_N WN(i)的输出, u i u_i ui表示其输入。
    为了直观理解信道 { W N ( i ) } \{W^{(i)}_N\} {WN(i)},考虑一个genie辅助的逐次消除解码器,其中第i个判决单元在观察到 y 1 N y^N_1 y1N和过去的信道输入 u 1 i − 1 u^{i−1}_1 u1i1(由genie正确地提供,而不考虑早期的任何判决错误)之后估计 u i u_i ui。如果 u 1 N u^N_1 u1N X N X^N XN上是先验一致的,则 W N ( i ) W^{(i)}_N WN(i)是第 i i i个判决单元在该场景中看到的有效信道。

    3)信道极化

    定理1:对于任何B-DMC W信道,信道 { W N ( i ) } \{W^{(i)}_N\} {WN(i)}在某种意义上是极化的,对于任意的 δ ∈ ( 0 , 1 ) δ∈(0,1) δ(0,1),当 N N N通过2的幂变为无穷大时,索引 i ∈ { 1 , . . . , N } i∈\{1, ... ,N\} i{1,...,N},其中满足 I ( W N ( i ) ) ∈ ( 1 − δ , 1 ] I(W^{(i)}_N)∈(1-δ,1] I(WN(i))(1δ1]的信道数占总信道数N的比例趋于 I ( W ) I(W) I(W),而满足 I ( W N ( i ) ) ∈ [ 0 , δ ) I(W^{(i)}_N)∈[0,δ) I(WN(i))[0δ)的信道所占的比例趋于 1 − I ( W ) 1- I(W) 1I(W)
    该定理在第IV节中得到了证明。

    对于具有擦除概率 ϵ = 0.5 \epsilon= 0.5 ϵ0.5的BEC的情况,极化效应在图4中示出。 已经使用递归关系计算了数字 { W N ( i ) } \{W^{(i)}_N\} {WN(i)}
    在这里插入图片描述
    在这里插入图片描述
    其中 i ( W 1 ( 1 ) ) = 1 − ϵ i(W^{(1)}_1)=1−\epsilon i(W1(1))=1ϵ。 这种递推只对BEC有效,第III节证明了这一点。对于一般的B-DMC W,目前还没有有效的算法来计算 { W N ( i ) } \{W^{(i)}_N\} {WN(i)}

    图4显示 I ( W ( i ) ) I(W^{(i)}) I(W(i))对于小的i趋向于接近0,对于大的i趋向于接近1.然而, I ( W N ( i ) ) I(W^{(i)}_N) I(WN(i)) i i i的中间范围内表现出不稳定的行为.对于一般的B-DMC,确定 I ( W N ( i ) ) I(W^{(i)}_N) I(WN(i))高于给定阈值的索引的子集是一个重要的计算问题,将在第IX节中讨论.

    4)极化率

    为了证明编码定理,极化效应随N的变化而保持极化速度是很重要的。我们在这方面的主要结果是根据参数给出的

    在这里插入图片描述
    定理2:对于任何 I ( W ) > 0 I(W)> 0 I(W)>0且任意 R < I ( W ) R <I(W) R<I(W)的B-DMC 信道W,都存在一个序列集 A N ⊂ { 1 , . . . , N } , N ∈ { 1 , 2 , . . . , 2 n , . . . } A_N⊂\{1,... ,N\},N∈\{1,2,... ,2^n,...\} AN{1,...,N}N{1,2,...,2n,...},例如对于所有 i ∈ A N , ∣ A N ∣ ≥ N R i∈AN,| A_N |≥NR iANANNR并且 Z ( W N ( i ) ) ≤ O ( N − 5 / 4 ) Z(W^{(i)}_N)≤O(N^{−5 / 4}) Z(WN(i))O(N5/4)
    该定理在IV-B节中得到了证明。
    我们用 { Z ( W N ( i ) ) } \{Z(W^{(i)}_N)\} {Z(WN(i))}而不是 { I ( W N ( i ) ) } \{I(W^{(i)}_N)\} {I(WN(i))}来表示定理2中的极化结果,因为这种形式更适合我们将要开发的编码结果。 在定理1的帮助下,从定理2可以得到以 { I ( W N ( i ) ) } \{I(W^{(i)}_N)\} {I(WN(i))}表示的偏振率结果。

    C. Polar coding

    我们利用极化效应来构造实现对称信道容量 I ( W ) I(W) I(W)的码,我们称之为极性编码。

    极化编码的基本思想是建立一种编码系统,在该编码系统中,人们可以单独访问每个坐标信道 W N ( i ) W^{(i)}_N WN(i),并且只通过 Z ( W N ( i ) ) Z(W^{(i)}_N) Z(WN(i))接近0的那些信道发送数据。

    1) G N G_N GN-coset codes 陪集编码

    首先,作为特殊情况,我们描述一类包含极性代码(主要关注的代码)的分组代码。 此类的块长度N被限制为2的幂,对于 n ≥ 0 , N = 2 n n≥0,N = 2^n n0N=2n。 对于给定的N,该类中的每个代码都以相同的方式编码,即
    在这里插入图片描述
    其中 G N G_N GN是上面定义的N阶生成矩阵。
    对于{1,…,N}的任意子集A,我们可以将(8)写为
    在这里插入图片描述
    其中 G N ( A ) G_N(A) GN(A)表示由 A A A中具有索引的行组成的 G N G_N GN的子矩阵。

    如果现在固定 A A A u A c u_{A^c} uAc,并且将 u A u_A uA保留为自由变量,则将获得从源块 u A u_A uA到代码字块 x 1 N x^N_1 x1N的映射。该映射是陪集编码:它是线性块码与生成器矩阵 G N ( A ) G_N(A) GN(A)的陪集,该陪集由固定向量 u A c G N ( A c ) u_{Ac}G_N(A^c) uAcGN(Ac)确定。 我们将此类代码统称为 G N G_N GN-coset代码。(陪集代码)
    我们将这类码统称为 G N G_N GN-陪集码,单个 G N G_N GN-陪集码将由一个参数向量 ( N , K , A , u A c ) (N,K,A,u_{A^c}) (NKAuAc)来标识,其中K是码的维数,指定A的大小。 比率 K / N K / N K/N称为编码率。我们将 A A A(我们将冗余参数K包括在参数集中,因为我们通常考虑K固定而A自由的码集。)设为信息集,将 u A c ∈ X N − K u_{Ac}∈X^{N−K} uAcXNK称为冻结位或向量。
    例如,(4,2,{2,4},(1,0))代码具有编码映射

    在这里插入图片描述
    对于源块 ( u 2 , u 4 ) = ( 1 , 1 ) (u_2,u_4)=(1,1) (u2u4)=(11),编码块是 x 1 4 = ( 1 , 1 , 0 , 1 ) x^4_1=(1,1,0,1) x14=(1101)
    不久将通过给出选择信息集合 A A A的特定规则来指定极性码。

    2)A successive cancellation decoder 连续消除解码器

    考虑带有参数 ( N , K , A , u A c ) (N,K,A,u_{A^c}) NKAuAc G N G_N GN陪集代码。 令 u 1 N u^N_1 u1N被编码为码字 x 1 N x^N_1 x1N,使 x 1 N x^N_1 x1N通过信道 W N W^N WN被发送,并且使信道输出 y 1 N y^N_1 y1N被接收。 在已知 A , u A c 和 y 1 N A,u_{Ac}和y^N_1 AuAcy1N的情况下,解码器的任务是生成 u 1 N u^N_1 u1N的估计值 u ^ 1 N \hat{u}^N_1 u^1N
    由于解码器可以通过设置 u ^ A c = u A c \hat{u}_{Ac} = u_{Ac} u^Ac=uAc来避免冻结部分中的错误,因此真正的解码任务是生成 u A u_A uA的估计 u ^ A \hat{u}_A u^A
    除非提到其他解码器,否则本文将针对特定的连续消除(SC)解码器给出编码结果。 给定任何 ( N , K , A , u A c ) (N,K,A,u_{{A}^ c}) NKAuAcGN陪集码,我们将使用SC解码器,该解码器通过计算生成其决策 u ^ 1 N \hat{u}^N_1 u^1N
    在这里插入图片描述
    i i i 1 到 N 1到N 1N的顺序,其中 h i : Y N × X i − 1 → X , i ∈ A h_i:Y^N×X^{i-1}→X,i∈A hiYN×Xi1XiA是定义为
    在这里插入图片描述
    对于所有 y 1 N ∈ Y N y^N_1∈Y^N y1NYN u ^ 1 i − 1 ∈ X i − 1 \hat{u}^{i-1}_1∈X^{i-1} u^1i1Xi1。 我们将说如果 u ^ 1 N ≠ u 1 N \hat{u}^N_1 \neq u^N_1 u^1N=u1N或等效地如果 u ^ A ≠ u A \hat{u}^A\neq uA u^A=uA则发生解码器块错误。
    上面定义的决策函数 h i {hi} hi与ML(最大似然)决策函数相似,但并不完全一样,因为它们将冻结的未来比特 ( u j : j > i , j ∈ A c ) (u_j:j> i,j∈A^c) ujj>ijAc视为RV(随机向量),而不是已知比特。 作为这种次优的交换,可以使用递归公式有效地计算{hi},如我们在第II节中所示。 除算法效率外,决策函数的递归结构非常重要,因为它会使解码器的性能分析变得易处理。幸运的是,由于不使用真正的ML决策函数而导致的性能损失可忽略不计: I ( W ) I(W) I(W)仍可实现。

    3) Code performance代码性能

    符号 P e ( N , K , A , u A c ) Pe(N,K,A,u_{{A}^ c}) Pe(NKAuAc)将表示 ( N , K , A , u A c ) (N,K,A,u_{{A}^ c}) (NKAuAc)码的块差错概率,假设每个数据向量 u A ∈ X K u_A∈X^K uAXK以概率 2 − K 2^{−K} 2K发送,并且解码由上述SC解码器完成。 更准确地说,
    在这里插入图片描述
    u A c u_{{A}^ c} uAc的所有选择的 P e ( N , K , A , u A c ) Pe(N,K,A,u_{{A}^ c}) Pe(NKAuAc)的平均值将由 P e ( N , K , A ) Pe(N,K,A) Pe(NKA)表示:
    在这里插入图片描述
    SC解码下的块错误概率的关键范围如下。

    命题2:对于任何B-DMC W和参数 ( N , K , A ) (N,K,A) (NKA)的任何选择,
    在这里插入图片描述
    因此,对于每个 ( N , K , A ) (N,K,A) NKA,都有一个冻结的向量 u A c u_{A^c} uAc
    在这里插入图片描述
    V-B节证明了这一点。 这一结果建议从{1,…,N}的所有K个子集中选择A以便最小化(13)的RHS。这个想法导致了极坐标的定义。

    在这里 u A c u_{{A}^ c} uAc直接写为uAc

    4) Polar codes

    在给定B-DMC W的情况下,如果选择信息集A作为{1,…, N}的K元素子集,则具有参数(N,K,A,uAc)的GN陪集代码将被称为W的极化码。 对于所有 i ∈ A , j ∈ A c , Z ( W N ( i ) ) ≤ Z ( W N ( j ) ) i∈A,j∈Ac,Z(W^{(i)}_N)≤Z(W^{(j)}_N) iAjAcZWN(i)ZWN(j)
    极化码是信道特定的设计:一个信道的极化码可能不是另一个信道的极化码。 本文的主要结果是证明了极性编码可以达到任意给定B-DMCW的对称容量 I ( W ) I(W) I(W)
    极化码定义的另一种规则是将A指定为 { 1 , . . . , N } \{1,...,N\} {1,...,N}的K个元素子集,使得对于所有 i ∈ A , j ∈ A c i∈A,j∈A^c iAjAc I ( W N ( i ) ) ≥ I ( W N ( j ) ) I(W^{(i)}_N)≥I(W^{(j)}_N) IWN(i)IWN(j) 。 此替代规则也将达到 I ( W ) I(W) IW。 但是,基于Bhattacharyya参数的规则具有与块错误概率的显式界限相联系的优点。
    极性代码定义未指定如何选择冻结向量uAc; 可以随意选择。 uAc选择的这种自由度通过允许对总体进行平均,从而简化了极性代码的性能分析。 但是,我们并没有为选择uAc指定精确的规则,不仅仅是为了分析方便,还因为代码性能似乎对该选择相对不敏感。 实际上,我们在VI-B节中证明,对于对称通道,任何选择的foruAcis都与其他方法一样好。

    5)编码定理:

    对于一个固定的B-DMC W,编号R≥0。 设 P e ( N , R ) Pe(N,R) PeNR定义为 P e ( N , ⌊ N R ⌋ , A ) Pe(N,⌊NR⌋,A) PeNNRA,根据W的极性编码规则选择A.因此, P e ( N , R ) Pe(N,R) PeNR是针对W上具有块长度N和速率R的极性编码的SC解码下的块差错概率,在冻结位uAc的所有选择上取平均值。 本文的主要编码结果如下:

    定理3:对于任何给定的B-DMCW和固定的R <I(W),连续消除解码下极性编码的块错误概率都满足
    在这里插入图片描述
    这个定理是定理2和界(13)的一个简单推论,如我们在V-B节中所示。 对于对称通道,我们有以下定理3的增强版本。
    定理4:对于任何对称的B-DMC W和任何固定的 R < I ( W ) R <I(W) R<IW,考虑GN陪集码的任何序列 ( N , K , A , u A c ) (N,K,A,uAc) NKAuAc,其中N递增到无穷大, K = ⌊ N R ⌋ K =⌊NR⌋ K=NR A A A根据W的极性编码规则选择,并且uAc取任意值。 连续消除解码后的块错误概率满足
    在这里插入图片描述
    第VI-B节证明了这一点。 注意,对于对称信道, I ( W ) I(W) I(W)等于W的香农容量

    6)复杂度:

    极化码的一个重要问题是编码、译码和码构造的复杂性,信道极化构造的递归结构使得GN陪集码,特别是极化码的编译码算法复杂度较低。

    定理5:对于GN陪集码的类别,编码的复杂度和连续消除解码的复杂度均为 O ( N l o g N ) O(NlogN) O(NlogN)作为代码块长度N的函数。
    这一定理在第VII节和第VIII节中得到了证明。注意,定理5中的复杂性界限与码率和冻结向量的选择方式无关。 即使在I(W)以上的利率下,这个界限仍然存在,但显然这没有实际意义。

    对于码构造,我们没有发现用于构造极性代码的低复杂度算法。 一个例外是BEC,对于该BEC,我们有一个极性代码构造算法,其复杂度为O(N)。 我们将在第九节中进一步讨论代码构造问题,并提出一种用于近似精确极性代码构造的低复杂度统计算法。

    D.与以前工作的关系

    本文是文献[2]工作的推广,文中用通道合并和分裂的方法证明了某些特定DMC的总截止率可以得到改善。 然而,没有任何递归方法被建议达到这种改进的极限。

    随着当前工作的进展,很明显极性编码与Reed-Muller(RM)编码有很多共同之处[3],[4]。 实际上,递归代码构造和SC解码是极性编码的两个基本要素,似乎已经被RM代码引入了编码理论。
    根据RM代码的一种构造,对于任何 N = 2 n N = 2^n N=2n n ≥ 0 n≥0 n0 0 ≤ K ≤ N 0≤K≤N 0KN,将块长度为 N N N,尺寸为 K K K的RM代码(表示为 R M ( N , K ) RM(N,K) RMNK)定义为线性代码,其生成器矩阵 G R M ( N , K ) G_{RM}(N,K) GRMNK是通过删除 F ⊗ n F^{⊗n} Fn行的 ( N − K ) (N-K) NK获得的,因此删除的行中的汉明权重(该行中的1的个数)都不比其余K行中的汉明权重大 。
    例如
    在这里插入图片描述
    这种构造体现了RM码和极性码之间的相似性。 由于对于任意 N = 2 n N=2^n N=2n G N G_N GN F ⊗ n F^{⊗n} Fn具有相同的行集(只是顺序不同),显然RM码属于GN-陪集码的类,例如, R M ( 4 , 2 ) RM(4,2) RM(42)是参数为 ( 4 , 2 , 2 , 4 , ( 0 , 0 ) ) (4,2,{2,4},(0,0)) (4224(00))的G4-陪集码。 因此,RM编码和极化码可以被认为是用于选择给定大小 ( N , K ) (N,K) (NK)的GN陪集码的信息集合A的两个可选规则。 与极化编码不同,RM编码以与信道无关的方式选择信息集;它不像极性编码那样对信道极化现象进行微调。 我们将在X节中证明,至少对于这类BEC,信息集选择的RM规则在SC译码下导致渐近不可靠的码。 因此,通过更密切地关注信道极化,极性编码以非平凡的方式超越了RM编码。

    通过注意极化码是多级 ∣ u ∣ u + v ∣ |u|u+v| uu+v码,它是源于Plotkin码组合方法的一类码[5],可以建立到现有工作的另一种联系。
    鉴于RM码也是多级 ∣ u ∣ u + v ∣ |u|u+v| uu+v码[6,pp.。 114-125]。
    然而,与典型的多级码构造不同的是,在典型的多级码构造中,人们从特定的小码位开始以构建较大的码位,在极性编码中,多级码是通过相对于信道特定的准则清除全阶生成矩阵GN的行来获得的。 GN的特殊结构确保了无论如何删除,结果代码都是多级 ∣ u ∣ u + v ∣ |u|u+v| uu+v代码。 本质上,极性编码享有从这种编码的集合中选择多级编码的自由,以便适合手头的信道,而传统的多级编码方法没有这种程度的灵活性。

    最后,我们希望提及极化码的“频谱”解释,类似于Blahut对BCH代码的处理[7,Ch。 9]; 这种相似性已经被Forney 证明[8,Ch。 11]与RM代码有关。 从频谱观点来看,编码操作(8)被视为“频率”域信息矢量uN1到“时间”域码字矢量 x 1 N x^N_1 x1N的变换。 变换是可逆的,其中 G N − 1 = G N G^{-1}_N = G_N GN1=GN。 解码操作被视为一种频谱估计问题,其中给了一个时域观测值 y 1 N y^N_1 y1N,它是 x 1 N x^N_1 x1N的嘈杂版本,并被要求估计 u 1 N u^N_1 u1N。 为了帮助进行估算,允许冻结一定数量的uN1光谱分量。 极性编码的这种频谱解释表明,有可能在统一框架中处理极性代码和BCH代码。 频谱解释也为在极性编码中使用各种信号处理技术打开了大门。 确实,在第七节中,我们在设计极坐标编码器时采用了一些快速的变换技术。

    E.论文大纲

    论文的其余部分组织如下。 第二节探讨了信道分割的递归性质。 在第三节中,我们重点介绍了I(W)和Z(W)是如何通过信道合并和分离的单一步骤进行变换的。 我们将其推广到第四节的渐近分析,完成了定理1和定理2的证明,从而完成了本文关于信道极化的部分,其余部分主要是关于极性编码的。 第五节给出了SC译码下极化编码误块率的一个上界,并证明了定理3。第六节考虑了对称B-DMCS的极性编码,证明了定理4。第七节分析了编码器映射GN,从而得到了有效的编码器实现。 在第八节中,我们给出了一种复杂度为 O ( N l o g N ) O(NlogN) O(NlogN)的SC译码的实现。 在第九节中,我们讨论了码构造的复杂度,并提出了一种 O ( N l o g N ) O(NlogN) O(NlogN)统计近似码构造算法。 在十节中,我们解释了为什么RM码在SC译码下具有较差的渐近性能。 在第十一节中,我们指出了对目前工作的一些概括,给出了一些补充意见,并说明了一些有待解决的问题。

    II.递归通道变换

    我们通过(4)和(5)定义了逐块通道合并和拆分操作,该操作将W的N个独立副本转换为 W N ( 1 ) , . . . , W N ( N ) W^{(1)}_N,...,W^{(N)}_N WN(1),...,WN(N)。 本节的目的是表明可以将该块状通道转换递归分解为单步通道转换。

    我们说一对二进制输入通道 W ′ : X → Y ~ W':X→\tilde{Y} WXY~ W ′ ′ : X → Y ~ × X W'':X→\tilde{Y}×X WXY~×X是通过二进制输入通道 W : X → Y W:X→Y WXY的两个独立副本的单步变换获得的,并且 写

    在这里插入图片描述
    当且仅当存在一对一的映射 f : Y 2 → Y ~ f:Y^2→\tilde{Y} fY2Y~使得
    在这里插入图片描述
    据此,我们可以为任何给定的B-DMCW写 ( W , W ) ↦ ( W 2 ( 1 ) , W 2 ( 2 ) ) (W,W)\mapsto (W^{(1)}_2,W^{(2)}_2) WWW2(1)W2(2)

    在这里插入图片描述
    f f f为单位映射,其形式为(17)和(18)。

    事实证明,更广泛地说,我们可以写,

    在这里插入图片描述
    这是对以下内容的推论:
    命题3:
    在这里插入图片描述
    该建议在附录中得到了证明。 现在可以通过以下方式证明(21)和(23)在形式上分别与(17)和(18)相同,从而证明变换关系(21)是合理的:

    在这里插入图片描述
    在这里插入图片描述
    图5.N=8个信道的信道转换过程。

    因此,我们已经表明,从 W N W^N WN ( W N ( 1 ) , . . . , W N ( N ) ) (W^{(1)}_N,...,W^{(N)}_N) WN(1)...WN(N)的块状通道转换在局部级别上分解为形式为(21)的单步通道转换。 对于 N = 8 N = 8 N=8,全套这样的变换形成如图5所示的结构。从右向左读取,该图从变换 ( W , W ) ↦ ( W 2 ( 1 ) , W 2 ( 2 ) ) (W,W)\mapsto(W^{(1)}_2,W^{(2)}_2) (WW)(W2(1)W2(2))的四个副本开始并以蝶形模式继续,每个蝶形模式表示形式为 ( W 2 i ( j ) , W 2 i ( j ) ) ↦ ( W 2 i + 1 ( 2 j − 1 ) , W 2 i + 1 ( 2 j ) ) (W^{(j)}_{2^i},W^{(j)}_{2^i})\mapsto(W^{(2j−1)}_{2^{i+1}},W^{(2j)}_{2^{i+1}}) (W2i(j)W2i(j))(W2i+1(2j1)W2i+1(2j)) 。 蝶形阀的右端点处的两个通道始终相同且独立。 在最右侧,有W的8个独立副本;在左边的下一个级别有4个独立的 W 2 ( 1 ) W^{(1)}_2 W2(1) W 2 ( 2 ) W^{(2)}_2 W2(2)副本;依此类推。 向左的每一步都会使通道类型的数量加倍,但会使独立副本的数量减半。

    III. 速率与可靠性转换

    现在我们研究速率和可靠性参数 I ( W N ( i ) ) I(W^{(i)}_N) I(WN(i)) Z ( W N ( i ) ) Z(W^{(i)}_N) Z(WN(i))是如何通过局部(单步)变换(21)改变的。 通过了解局部行为,我们将能够得出从 W N W^N WN ( W N ( 1 ) , W N ( N ) ) (W^{(1)}_N,W^{(N)}_N) (WN(1)WN(N))的整体转换的结论。 附录中给出了本节结果的证明。

    A.速率和可靠性的局部转换

    命题4:假设对于某些二进制输入信道集合, ( W , W ) ↦ ( W ′ , W ′ ′ ) (W,W)\mapsto(W',W'') (WW)(WW)。 那么,
    在这里插入图片描述
    当且仅当 I ( W ) I(W) I(W)等于0或1。
    等式(24)表示单步通道变换保持了对称容量。 不等式(25)与(24)表明,在单步变换下,对称容量保持不变,当且仅当 W W W是理想信道或完全噪声信道, I ( W ′ ) = I ( W ′ ′ ) = I ( W ) I(W')= I(W'')= I(W) IW=IW=IW。如果 W W W既不是完全噪声也不是完全噪声,则单步变换会在 I ( W ′ ) < I ( W ) < I ( W ′ ′ ) I(W')<I(W)<I(W'') IW<IW<IW的情况上使对称容量偏离中心,从而有助于极化。

    命题5:假设对于某些二进制输入信道集合, ( W , W ) ↦ ( W ′ , W ′ ′ ) (W,W)\mapsto(W',W'') (WW)(WW)。 那么,
    在这里插入图片描述
    当且仅当W是 BEC,等式成立于(27)。 当且仅当 Z(W)等于0或1,我们有 Z ( W ′ ) = Z ( W ′ ) Z (W ′) =Z(W ′) Z(W)=Z(W),或等效地,当且仅当 I ( W ) I(W) I(W)等于1或0。
    这一结果表明,只有在单步信道变换下,可靠性才能在以下意义上提高
    在这里插入图片描述
    由于BEC在可靠性的w.r.t.极值行为中起着特殊的作用,因此它值得特别关注。

    命题6:考虑信道变换 ( W , W ) ↦ ( W ′ , W ′ ′ ) (W,W)\mapsto(W',W'') (WW)(WW)。 如果W是具有一定擦除概率 ϵ \epsilon ϵ的BEC,则信道 W ′ W' W W ′ ′ W'' W分别是具有擦除概率为 2 ϵ − ϵ 2 和 ϵ 2 2\epsilon-\epsilon^2和\epsilon^2 2ϵϵ2ϵ2的BEC。 相反,如果W’或W’'是BEC,则W是BEC。

    B.速率和可靠性 W N ( i ) W^{(i)}_N WN(i)

    现在我们回到第二节末尾的上下文。
    命题7:对于任何B-DMC W, N = 2 n , n ≥ 0 , 1 ≤ i ≤ N N=2^n,n≥0,1≤i≤N N=2nn01iN,变换 ( W N ( i ) , W N ( i ) ) → ( W 2 N ( 2 i − 1 ) , W 2 N ( 2 i ) ) (W^{(i)}_N,W^{(i)}_N)→(W^{(2i−1)}_{2N},W^{(2i)}_{2N}) (WN(i)WN(i))(W2N(2i1)W2N(2i))在以下意义上是保持速率和提高可靠性的
    在这里插入图片描述
    在等式(31)中,如果W是BEC。 信道分裂使速率和可靠性偏离中心,这意味着
    在这里插入图片描述
    (32)和(33)中的等式(如果I(W)等于0或1)。可靠性项进一步满足
    在这里插入图片描述
    当W是BEC时,在(34)中有等式。累积率和可靠性满足
    在这里插入图片描述
    当W是BEC时,与(37)中的等式相等。
    这一结果是从命题4和命题5作为特例得出的,不需要单独证明。 累积关系(36)和(37)分别分别重复使用(30)和(31)。命题4中的相等条件是用公式 W W W而不是 W N ( i ) W^{(i)}_N WN(i)表示的;这是可能的,因为:(i)命题4, I ( W ) ∈ 0 , 1 I(W)∈{0,1} I(W)01当且仅当 I ( W N ( i ) ) ∈ 0 , 1 I(W^{(i)}_N)∈{0,1} I(WN(i))01;(ii) W W W是BEC当且仅当 W N ( i ) W^{(i)}_N WN(i)是BEC,这是从命题6归纳而来的。

    对于 W W W是擦除概率为 ϵ \epsilon ϵ的BEC的特殊情况,从命题4和命题6推导出参数 { Z ( W N ( i ) ) } \{Z(W^{(i)}_N)\} {Z(WN(i))}可以通过递归计算
    在这里插入图片描述
    其中 Z ( W 1 ( 1 ) ) = ϵ Z(W^{(1)}_1)=\epsilon Z(W1(1))=ϵ。 参数 Z ( W N ( i ) ) Z(W^{(i)}_N) Z(WN(i))等于信道 W N ( i ) W^{(i)}_N WN(i)的擦除概率。递推关系(6)遵循(38)的事实,对于W信道一个BEC I ( W N ( i ) ) = 1 − Z ( W N ( i ) ) I(W^{(i)}_N) = 1−Z(W^{(i)}_N ) I(WN(i))=1Z(WN(i))

    IV.信道极化

    我们在本节中证明了有关信道极化的主要结果。 该分析基于图5中所示的递归关系。 但是,将图5重新绘制为如图6所示的二叉树会更加方便。树的根节点与通道W相关联。根W产生上通道 W 2 ( 1 ) W^{(1)}_2 W2(1)和下通道 W 2 ( 2 ) W^{(2)}_2 W2(2),这两个通道与级别1的两个节点相关联。通道 W 2 ( 1 ) W^{(1)}_2 W2(1)依次产生通道 W 4 ( 1 ) W^{(1)}_4 W4(1) W 4 ( 2 ) W^{(2)}_4 W4(2),依此类推。 通道 W 2 n ( i ) W^{(i)}_{2^n} W2n(i)位于树的级别n处,节点号i,从顶部开始计数。
    在图6中,按位序列对树的节点进行自然索引。根节点使用空序列进行索引。级别1的上部节点使用0进行索引,下部节点使用1进行索引。给定具有索引 b 1 b 2 … b n b1b2…bn b1b2bn的n级节点,从其发出的上节点具有标签 b 1 b 2... b n 0 b1b2...bn0 b1b2...bn0和下节点 b 1 b 2... b n 1 b1b2...bn1 b1b2...bn1。根据该标记,信道 W 2 n ( i ) W^{(i)}_{2^n} W2n(i)位于节点 b 1 b 2... b n b1b2...bn b1b2...bn处, i = 1 + ∑ j = 1 n b j 2 n ⋅ − j i=1+ \sum^n_{j=1}b_j2^{n·-j} i=1+j=1nbj2nj。我们将位于节点 b 1 b 2... b n b1b2...bn b1b2...bn处的信道 W 2 n ( i ) W^{(i)}_{2^n} W2n(i)表示为 W b 1 … b n W_{b_1…b_n} Wb1bn
    在这里插入图片描述
    图6递归通道构建的树过程

    结合图6,我们定义了一个随机树过程,表示为 K n ; n ≥ 0 {K_n;n≥0} Knn0。该过程从树的根部开始, K 0 = W K_0=W K0=W。对于任意 n ≥ 0 n≥0 n0,给定 K n = W b 1 . . . . b n K_n=W_{b_1....b_n} Kn=Wb1....bn K n + 1 K_{n+1} Kn+1都等于 W b 1 ⋅ ⋅ ⋅ b n 0 W_{b_1···b_{n0}} Wb1bn0 W b 1 ⋅ ⋅ ⋅ b n 1 W_{b_1···b{n1}} Wb1bn1,概率各为1/2。因此, { K n } \{K_n\} {Kn}通过信道树所采取的路径可以被认为是由i.i.d.伯努利RVs { B n ; n = 1 , 2 , . . . . } \{B_n;n=1,2,... .\} {Bnn=12....},其中 B n B_n Bn以相等的概率等于0或1。 假定 B 1 , . . . , B n B_1,...,B_n B1,...,Bn已经采用样本值 b 1 , . . . , b n b1,...,bn b1...bn,则随机信道过程采用值 K n = W b 1... b n K_n=W_{b1...bn} Kn=Wb1...bn。 为了跟踪信道随机序列 K n K_n Kn的速率和可靠性参数,我们定义了随机过程 I n = I ( K n ) 和 Z n = Z ( K n ) I_n=I(K_n)和Z_n=Z(K_n) In=I(Kn)Zn=Z(Kn)

    为了更精确地描述这个问题,我们考虑了概率空间 ( Ω , F , P ) (Ω,F,P) ΩFP,其中Ω是所有二进制序列 ( b 1 , b 2 , … ) (b1,b2,…) b1b2的空间是由圆柱集 S ( b 1 , … b n ) S(b1,…bn) Sb1bn生成的Borel场(BF), S ( b 1 , … b n ) = { ω ∈ Ω : ω 1 = b 1 , . . . , ω n = b n } , n ≥ 1 , b 1 , . . . , b n ∈ { 0 , 1 } S(b1,…bn)=\{ω∈Ω:ω1=b1,...,ωn=bn\},n≥1,b1,...,bn∈\{0,1\} Sb1bn={ωΩω1=b1,...,ωn=bn}n1b1,...,bn{0,1},P是定义在F上的概率测度,使得 P ( S ( b 1 , … , b n ) ) = 1 / 2 n P(S(b1,…,bn))=1/2^n PSb1bn=1/2n。对于每个n≥1,我们将 F n Fn Fn定义为cylinder 组 S ( b 1 , … , b i ) , 1 ≤ i ≤ n , b 1 , . . . , b i ∈ 0 , 1 S(b1,…,bi),1≤i≤n,b1,...,bi∈{0,1} Sb1bi,1inb1,...,bi0,1生成的BF。我们将 F 0 F0 F0定义为仅由空集和Ω组成的无关BF。显然, F 0 ⊂ F 1 ⊂ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ F F0⊂F1⊂·········F F0F1F
    现在可以如下正式定义上述随机过程。
    在这里插入图片描述

    后面的以后再写吧

    展开全文
  • 极化码极化信道仿真,信道极化是信道合并与信道分裂两种信道操作的结果。在上述两种操作下,原本相同的N个W信道产生了极化现象,其中一部分信道的信道容量趋近于1,另一部分信道的信道容量趋近于0。
  • 极化信道,极化信道 转移概率,matlab源码
  • Arikan在讨论信道极化时,采用的是B-DMC(二进制离散无记忆信道),然而在构造极化码时需要使用的计算巴氏参数Z(W)Z(W)Z(W)方法的适用范围是BEC信道。又因为BEC是B-DMC的子集。因此在Polar Code编码时只能回落到BEC...

    前言

    由Arikan发明的Polar Code的经典编码算法已经在第二节基本阐述完毕,第三节则是对前文的举例。在编码实例中,有两个前提假设:
    1.假设采用二进制删除信道
    2.假设采用巴氏参数来评估各分裂子信道的可靠性。
    Arikan在讨论信道极化时,采用的是B-DMC(二进制离散无记忆信道),然而在构造极化码时需要使用的计算巴氏参数 Z ( W ) Z(W) Z(W)方法的适用范围是BEC信道。又因为BEC是B-DMC的子集。因此在Polar Code编码时只能回落到BEC上来构造。
    注意:当信道不是BEC信道时,比如二进制对称信道(BSC)信道或二进制高斯白噪声信道(BAWGNC),则超出了 Z ( W ) Z(W) Z(W)的适用范围,原因是各个分裂信道的 Z ( W ) Z(W) Z(W)的数值无法精确得到。
    为了更精确的估计信道极化中各分裂子信道的可靠性,Mori等人提出了密度进化(Density Evolution,DE)的构造方法。该方法使用与所有类型的B-DMC。
    定义错误概率
    对信道 W W W N N N个独立时隙上进行信道极化以后,得到极化信道 Z ( W N ( i ) ) Z(W_N^{(i)}) Z(WN(i)),其中 i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N。令事件 A i A_i Ai表示序号为 i i i的极化信道 W N ( i ) W_N^{(i)} WN(i)所承载的比特经过传输后发生错误,即
    A i = { u i N , y 1 N : W N ( i ) ( y 1 N , u 1 i − 1 ∣ u i ) < W N ( i ) ( y 1 N , u 1 i − 1 ∣ u i ⊕ 1 ) } A_i=\{u_i^N,y_1^N:W_N^{(i)}(y_1^N,u_1^{i-1}|u_i)<W_N^{(i)}(y_1^N,u_1^{i-1}|u_i\oplus 1)\} Ai={uiN,y1N:WN(i)(y1N,u1i1ui)<WN(i)(y1N,u1i1ui1)}
    则极化信道 W N ( i ) W_N^{(i)} WN(i)的错误概率为 P ( A i ) P(A_i) P(Ai)
    注解:关于事件 A i A_i Ai的定义,后续会有文章专门作解释。

    密度进化(DE)

    类似于LDPC码等信道编码,信道极化也可以使用Tanner图的结构来表示。下图给了一个 N = 8 N=8 N=8的例子,图中圆圈表示表示变量节点,每一个变量节点代表一个比特,同时也存储了该比特取值为0或1时的概率;而方框则表示校验节点,表示与之相连的各变量节点比特值的校验和为0。
    在这里插入图片描述
    由于变量节点的比特值仅可能有0或1两种取值,因此,存储与变量节点的消息往往用对数似然比(LLR)值来表示。
    L N ( i ) = l n ( W N ( i ) W N ( i ) ( y 1 N , u ^ 1 ( i − 1 ) ∣ 0 ) W N ( i ) ( y 1 N , u ^ 1 ( i − 1 ) ∣ 1 ) ) L_N^{(i)}=ln(W_N^{{(i)}} \frac{W_N^{(i)}(y_1^N,\hat{u}_1^{(i-1)}|0)}{W_N^{(i)}(y_1^N,\hat{u}_1^{(i-1)}|1)}) LN(i)=ln(WN(i)WN(i)(y1N,u^1(i1)1)WN(i)(y1N,u^1(i1)0))
    根据《Polar Code(2)编码原理》中的递归式 W N ( 2 i − 1 ) ( y 1 N , u 1 2 i − 2 ∣ u 2 i − 1 ) W_N^{(2i-1)}(y_1^N,u_1^{2i-2}|u_{2i-1}) WN(2i1)(y1N,u12i2u2i1)与式 W N ( 2 i ) ( y 1 N , u 1 2 i − 1 ∣ u 2 i ) W_N^{(2i)}(y_1^N,u_1^{2i-1}|u_{2i}) WN(2i)(y1N,u12i1u2i),Tanner图中各个变量节点的LLR值可以递归地计算得到:
    L N ( i ) ( y 1 N , u ^ 1 ( 2 i − 2 ) ) = 2 t a n h − 1 ( t a n h ( L N / 2 ( i ) ( y 1 N / 2 , u ^ 1 , o 2 i − 2 ⊕ u ^ 1 , e 2 i − 2 ) 2 ) ) ⋅ t a n h ( L N / 2 ( i ) ( y N / 2 + 1 N , u ^ 1 , e 2 i − 2 ) 2 ) L_N^{(i)}(y_1^N,\hat{u}_1^{(2i-2)})=2tanh^{-1}(tanh(\frac{L_{N/2}^{(i)}(y_1^{N/2},\hat{u}_{1,o}^{2i-2}\oplus\hat{u}_{1,e}^{2i-2})}{2})) \\ \cdot tanh(\frac{L_{N/2}^{(i)}(y_{N/2+1}^N,\hat{u}_{1,e}^{2i-2})}{2}) LN(i)(y1N,u^1(2i2))=2tanh1(tanh(2LN/2(i)(y1N/2,u^1,o2i2u^1,e2i2)))tanh(2LN/2(i)(yN/2+1N,u^1,e2i2))
    L N ( 2 i ) ( y 1 N , u ^ 1 2 i − 1 ) = L N / 2 2 i − 1 ( y N / 2 + 1 N , u ^ 1 , e 2 i − 2 ) + ( − 1 ) u ^ 2 i − 1 ⋅ L N / 2 2 i − 1 ( y 1 N / 2 , u ^ 1 , o 2 i − 2 ⊕ u ^ 1 , e 2 i − 2 ) L_N^{(2i)}(y_1^N,\hat{u}_1^{2i-1})=L_{N/2}^{2i-1}(y_{N/2+1}^{N},\hat{u}_{1,e}^{2i-2})+(-1)^{\hat{u}_{2i-1}}\cdot L_{N/2}^{2i-1}(y_1^{N/2},\hat{u}_{1,o}^{2i-2}\oplus \hat{u}_{1,e}^{2i-2}) LN(2i)(y1N,u^12i1)=LN/22i1(yN/2+1N,u^1,e2i2)+(1)u^2i1LN/22i1(y1N/2,u^1,o2i2u^1,e2i2)
    若最终得到的 L N ( i ) = ( y 1 N , u ^ 1 i − 1 ) ≥ 0 , 则 判 决 为 u ^ i = 0 L_N^{(i)}=(y_1^N,\hat{u}_1^{i-1})\ge 0,则判决为\hat{u}_i=0 LN(i)=(y1N,u^1i1)0u^i=0;否则,则判决为 u ^ i = 1 \hat{u}_i=1 u^i=1
    将某一个变量节点的LLR视为一个随机变量,用 a ( z ) a(z) a(z)来表示该随机变量的概率密度函数(PDF)。由于信道满足对称性,可以假设发送的比特为全0,从而该变量节点的比特判决值错误的概率为:
    P e = ∫ − ∞ 0 a ( z ) d z P_e= \int _{-\infty}^{0}a(z)dz Pe=0a(z)dz
    在对第 i i i个信道进行可靠性估计时,如上图中加粗线条所示,以比特 u i u_i ui对应的节点为根节点,逐层扩散,直至最右侧一列变量节点,构成译码树。
    a w a_w aw表示信道输入到最右侧一列变量节点的LLR值的PDF;用 a N ( i ) a_N^{(i)} aN(i)表示 L N ( i ) ( y 1 N , u ^ 1 ( i − 1 ) ) L_N^{(i)}(y_1^N,\hat{u}_1^{(i-1)}) LN(i)(y1N,u^1(i1))值的PDF。根据密度进化理论以及式(2)和式(3),假设发送的是全零比特序列,在 u 1 i − 1 u_1^{i-1} u1i1值已知条件下,序号为 i i i的极化信道LLR值可以递归的计算如下:
    a 2 N ( 2 i − 1 ) = a N ( i ) ⊙ a N ( i ) \mathbf{a}_{2N}^{\left( 2i-1 \right)}=\mathbf{a}_{N}^{\left( i \right)}\odot \mathbf{a}_{N}^{\left( i \right)} a2N(2i1)=aN(i)aN(i)
    a 2 N ( 2 i ) = a N ( i ) ∗ a N ( i ) \mathbf{a}_{2N}^{\left( 2i \right)}=\mathbf{a}_{N}^{\left( i \right)}*\mathbf{a}_{N}^{\left( i \right)} a2N(2i)=aN(i)aN(i)
    a 1 ( 1 ) = a w \mathbf{a}_{1}^{\left( 1 \right)}\text{=}{\mathbf{a}_{w}} a1(1)=aw
    其中,运算符 ⊙ \odot ∗ * 分别表示校验节点与变量节点上的卷积操作。通过概率密度函数 a N ( i ) a_N^{(i)} aN(i)与式(4)可以得到各个极化信道 W N ( i ) W_N^{(i)} WN(i)的可靠性度量值 P ( A i ) P(A_i) P(Ai)

    高斯近似(GA)

    通过密度进化,对极化信道 W N ( i ) W_N^{(i)} WN(i)的可靠度度量 P ( A i ) P(A_i) P(Ai)进行计算,可以适用于任意类型的B-DMC信道。然而,在实际算法实现时,需要维护一个高维的向量以存储量化过后的概率密度函数 a N ( i ) \mathbf{a_{N}^{(i)}} aN(i)。为保证计算结果的精确,该向量的维度常取到 1 0 6 10^6 106,对如此高维的向量进行式(5)和式(6)的卷积操作,计算复杂度非常高。
    大多数研究场景下,信道编码的传输信道模型均为BAWGNC信道。在BAWGNC信道下,可以将密度进化中的LLR值的概率密度函数用一族方差为均值2倍的高斯分布来近似,从而简化成了对一维均值的计算,大大降低计算量,这种对DE的简化计算即为高斯近似(Gaussian Approximation,GA)。
    对噪声方差为 σ 2 \sigma ^2 σ2的BAWGNC信道,调制方式为BPSK,若从信道获取的接收信号为 y y y
    y = − 2 x + 1 + z y=-2x+1+z y=2x+1+z
    注解:这里存在疑问,个人理解BPSK应该是 y = 2 x − 1 + z y=2x-1+z y=2x1+z
    其中发送比特 x ∈ { 0 , 1 } x\in \{0,1\} x{0,1} z ∼ N ( 0 , σ 2 ) z\sim N\left( 0,{\sigma ^{2}} \right) zN(0,σ2)
    假设发送比特为全零序列,则对应的LLR值为:
    L L R ( y ) = ln ⁡ p ( y ∣ x = 0 ) p ( y ∣ x = 1 ) = 2 σ 2 y LLR\left( y \right)=\ln \frac{p\left( y|x=0 \right)}{p\left( y|x=1 \right)}=\frac{2}{\sigma ^{2}}y LLR(y)=lnp(yx=1)p(yx=0)=σ22y
    其中 y ∼ N ( 1 , σ 2 ) y\sim N\left( 1,{\sigma ^{2}} \right) yN(1,σ2)。因此,式(9)中的LLR值符合均值为 2 σ 2 \frac{2}{\sigma^2} σ22,方差为 4 σ 2 \frac{4}{\sigma^2} σ24的高斯分布。根据已有的高斯近似理论,若输入的消息 a N / 2    ( i ) \mathbf{a}_{N/{2}\;}^{\left( i \right)} aN/2(i)服从独立的高斯分布,对式(6)所示的变量节点上操作,则其输出 a N ( i ) \mathbf{a}_{N}^{\left( i \right)} aN(i)也服从高斯分布;对式(5)所示的变量节点上的操作,其输出 a N ( 2 i − 1 ) \mathbf{a}_{N}^{\left( 2i-1 \right)} aN(2i1)也非常接近高斯分布。由于高斯分布可以由其均值和方差决定,因此在概率密度函数的计算过程中值需要考虑均值和方差,但必须满足密度进化的对称条件。
    如果用 f ( z ) f(z) f(z)表示LLR的概率密度,则对称条件表示为 f ( z ) = f ( − z ) e z f(z)=f(-z)e^z f(z)=f(z)ez。对于均值为 m m m,方差为 σ 2 \sigma^2 σ2的高斯分布,该对称条件可以简化为 σ 2 = 2 m \sigma^2=2m σ2=2m。因此,在高斯近似中仅需要考虑一维的变量,即均值 m m m。设 a N ( i ) \mathbf{a}_{N}^{\left( i \right)} aN(i)可以用 N ( m N ( i ) , 2 m N ( i ) ) N\left( m_{N}^{\left( i \right)},2m_{N}^{\left( i \right)} \right) N(mN(i),2mN(i))表示,则式(5)、式(6)和式(7)中所示的LLR计算过程可以用高斯近似成为 m 2 N ( 2 i ) = φ − 1 ( 1 − [ 1 − φ ( m N ( i ) ) ] 2 ) m_{2N}^{\left( 2i \right)}={ {\varphi }^{-1}}\left( 1-{ {\left[ 1-\varphi \left( m_{N}^{\left( i \right)} \right) \right]}^{2}} \right) m2N(2i)=φ1(1[1φ(mN(i))]2)
    m 2 N ( 2 i ) = 2 m N ( i ) m_{2N}^{\left( 2i \right)}=2m_{N}^{\left( i \right)} m2N(2i)=2mN(i)
    m 1 ( 1 ) = 2 / σ 2    m_{1}^{\left( 1 \right)}={2}/{ { {\sigma }^{2}}}\; m1(1)=2/σ2
    其中函数
    φ ( x ) = { 1 − 1 4 π x ∫ − ∞ ∞ tanh ⁡ u 2 ⋅ exp ⁡ ( − ( u − x ) 2 4 x ) d u , x > 0 1                                                         , x = 0 \varphi \left( x \right)=\left\{ \begin{matrix} 1-\frac{1}{\sqrt{4\pi x}}\int_{-\infty }^{\infty }{\tanh \frac{u}{2}\cdot \exp \left( -\frac{ { {\left( u-x \right)}^{2}}}{4x} \right)du,x>0} \\ 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ,x=0 \\ \end{matrix} \right. φ(x)={14πx 1tanh2uexp(4x(ux)2)du,x>01                                                       ,x=0
    φ ( x ) \varphi \left( x \right) φ(x) [ 0 , ∞ ) [0,\infty) [0,)上连续单调递减, φ ( 0 ) = 1 \varphi \left( 0 \right)\text{=}1 φ(0)=1 φ ( ∞ ) =0 \varphi \left( \infty \right)\text{=0} φ()=0,其反函数用 φ − 1 ( x ) { {\varphi }^{-1}}\left( x \right) φ1(x)表示。一般情况下,函数 φ ( x ) { {\varphi }}\left( x \right) φ(x)可以用如下的近似计算 φ ( x ) = { π x ( 1 − 10 7 x ) exp ⁡ ( − x 4 ) , x ≥ 10 exp ⁡ ( − 0.4527 x 0.86 + 0.0218 ) , 0 < x < 10 \varphi \left( x \right)=\left\{ \begin{matrix} \sqrt{\frac{\pi }{x}}\left( 1-\frac{10}{7x} \right)\exp \left( -\frac{x}{4} \right),x\ge 10 \\ \exp \left( -0.4527{ {x}^{0.86}}+0.0218 \right),0<x<10 \\ \end{matrix} \right. φ(x)={xπ (17x10)exp(4x),x10exp(0.4527x0.86+0.0218),0<x<10
    在得到 m N ( i ) m_N^{(i)} mN(i)后,各极化信道 W N ( i ) W_N^{(i)} WN(i)在发送全零时对应的接收信号LLR值服从分布 N ( m N ( i ) , 2 m N ( i ) ) N\left( m_{N}^{\left( i \right)},2m_{N}^{\left( i \right)} \right) N(mN(i),2mN(i)),于是可靠度量 N ( m N ( i ) , 2 m N ( i ) ) N\left( m_{N}^{\left( i \right)},2m_{N}^{\left( i \right)} \right) N(mN(i),2mN(i))即可计算如下 P ( A i ) = ∫ − ∞ 0 1 2 π m N ( i ) ⋅ exp ⁡ ( − ( x − m N ( i ) ) 2 4 m N ( i ) ) d x P\left( { {A}_{i}} \right)\text{=}\int\limits_{-\infty }^{0}{\frac{1}{2\sqrt{\pi m_{N}^{\left( i \right)}}}\cdot \exp \left( \frac{-{ {\left( x-m_{N}^{\left( i \right)} \right)}^{2}}}{4m_{N}^{\left( i \right)}} \right)}dx P(Ai)=02πmN(i) 1exp4mN(i)(xmN(i))2dx

    总结

    巴氏参数、密度进化和高斯近似法都是计算各分裂子信道错误概率 P ( A i ) P(A_i) P(Ai)的方法,不同的方法有各自的适用范围。巴氏参数仅适用于BEC信道,密度进化法适用于所有类型的B-DMC,而高斯近似法适用于更加实际的BAWGNC。

    最后

    构造极化码的第一步信道可靠性估计是最关键的,本文讲了三种估计方法,分别是巴氏参数(仅适用于BEC)、密度进化(复杂度很高)和高斯近似(最贴近实际的信道)。
    此CSDN上的文章基本为全文摘录,修改部分主要是基于自己的理解,仅供读者参考。
    本文作者: Marshall
    本文链接: https://marshallcomm.cn/2017/03/05/polar-code-3-encoding-example/

    展开全文
  • 电信设备-极化信道的去极化效应分析方法及系统.zip
  • 信道极化图解,信道在经过极化后,有的性能接近1,有的接近0,保证正确
  • 量子去极化信道

    2019-06-21 22:42:58
    译自维基百科Quantum depolarizing ...d维去极化信道可以被认为是一个完全正的迹保持映射,它取决于一个参数,将量子态映射为自身与最大混合态的线性组合上: 完全正性的条件为满足: 经典容量 HSW定理...

    译自维基百科Quantum depolarizing channel https://en.wikipedia.org/wiki/Quantum_depolarizing_channel

    量子去极化通道是量子系统中的噪声模型。d维去极化信道可以被认为是一个完全正的迹保持映射\Delta _{\lambda },它取决于一个参数\lambda,将量子态\rho映射为自身与最大混合态的线性组合上:

    完全正性的条件为\lambda满足:

    经典容量

    HSW定理说明了量子信道的经典容量\Psi可以描述为正则化的Holevo信息:

    这个量很难计算,这反映了我们在量子信道方面知识的匮乏。但是,如果Holevo信息是信道\Psi的附加信息,即

    然后通过计算信道的Holevo信息,得到其经典容量。

    Holevo信息对所有信道的可加性是量子信息论中一个著名的开放猜想,但现在我们知道这个猜想并不适用于一般情况。通过证明所有信道的最小输出熵的可加性不成立来证明这一点,这是一个等价的猜想。

    尽管如此,Holevo信息的可加性被证明对量子去极化通道是成立的,并且下面给出了证明的概要。因此,跨信道的多种用途的纠缠不能增加经典容量。从这个意义上说,信道的表现类似于经典通道。为了达到最佳的通信速率,只需选择一个标准正交基来编码消息,并在接收端执行投射到相同基上的测量。

    探讨

    该证明中使用的主要技术,即将interest(不知道在这里怎么翻译)的信道重写为其他更简单信道的凸组合,是前面用于证明单位量子比特信道的类似结果的方法的推广。

    去极化信道的经典容量等于信道的Holevo信息,这意味着我们不能真正利用纠缠等量子效应来提高经典信息的传输速率。 在这个意义上,去极化通道可以被视为经典通道。

    然而,Holevo信息的可加性一般不成立的事实,提出了一些未来的工作领域,即寻找违反可加性的信道,换句话说,可以利用量子效应来改善超出其Holevo信息之外的经典容量的信道。

     

    展开全文
  • 基于极化码的信源信道联合编码研究
  • 非马尔可夫信道极化编码BB84量子密钥分配系统的性能分析
  • 在5.8 GHz频段上设计了天线实物,然后测量体域传播特性并建立离体分集信道模型,进而研制了信道仿真器,并与线极化天线分集情况进行比较。实验与仿真结果表明,同等条件下圆极化分集的等增益合并功率电平比线极化...
  • 该模型可通过已知的多天线配置、极化场辐射模式及散射体的空间分布,建立去极化效应模型,从而将信道的去极化效应由交叉极化鉴别度——XPD(cross polarization discrimination)的值表示,以拓展极化调制在V2V系统...
  • BCH码,汉明码,极化码,卷积码,循环码
  • 电信设备-利用极化码的广播信道增强.zip
  • 本文利用量子过程层析成像建立了一个适用于多次量子纠错的通用方案,以去极化信道为例,说明了此方案的可行性。发现单次纠错之后等价量子噪声信道。依然可以看作是保真度提高的去极化信道,且保真度的提高有着严格的...
  • 多用户超宽带(UWB)信道严重地遭受了实际的损害。 其中,多径衰落和干扰(例如多路访问干扰(MAI)和符号间干扰(ISI))会严重降低系统性能。 本文提出了一种由Arikan最初开发的极性编码技术,旨在提高基于室内UWB...
  • 电信设备-基于ISLS的极化信道XPD估计算法.zip
  • 电信设备-在极化信道之间具有高绝缘的双极化辐射元件.zip
  • 这些挑战激发了最新的进展,特别是与极化信道极化技术(例如基于极化的调制,基于极化的信号感测,基于极化的正交传输和基于极化的滤波)有关的新进展,以及它们的应用。到新兴的通信场景,包括节能通信,认知无线...
  • Polar Code是通过引入信道极化的概念而建立的。信道极化分两个阶段,分别是信道联合和信道分裂。通过信道的联合和分裂,各个子信道的对称容量将呈现两极分化的趋势:随着码长NNN的增加,一部分子信道的容量趋于1,而...
  • 天线电流分布对自由空间和地面反射信道上六极化MIMO系统特性的影响
  • x+y=zx+y=zx+y=z 重大时间节点 2016年11月18日,在美国内华达州里诺召开的3GPP RAN1...2009年在“IEEE Transaction on Information Theory”期刊上发表了一篇长达23页的论文更加详细地阐述了信道极化,并基于信道极化
  • 体育馆中具有交叉极化的三维无线电信道的测量和建模
  • 电信设备-极化编码调制中信道可靠度的确定方法及装置.zip
  • 极化码的小白之路

    2020-07-19 15:23:11
    信道极化:信道在一系列的组合和分裂后一部分的信道的信道容量趋于1,另一部分的信道容量趋于0。这种现象就叫信道极化。 信道数量N越大,信道极化就越充分,且信道容量趋于1的比例是可求的。这里不做细节讨论。 极化...
  • 极化码小结

    千次阅读 2017-09-10 13:29:59
     极化码建立在信道极化这一现象之上。  信道极化现象来自于信道合并与信道分裂这两种信道操作。 信道合并:  将N个独立信道W通过变换使之变为一个具有“集体意义”的信道WN,这里“集体意义”的产生来源于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,021
精华内容 4,808
关键字:

信道极化