精华内容
下载资源
问答
  • 极化码信道极化仿真

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

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

    I.引言与概述

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

    A.前期工作

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

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

    我们用大写字母(如XYX,Y)表示随机变量(RVs),用相应的小写字母(如xyx,y)表示它们的实现(样本值)。对于XX 是RV,PXP_X表示X上的概率分配,对于RV(XY)RV(X,Y)的联合集合,PXYP_{X,Y}表示联合概率分配,我们用标准记号I(XY)I(X;Y)I(XYZ)I(X;Y|Z)分别表示互信息及其条件形式。
    行向量(a1,,aN)(a1,…,aN)在这里简写为a1Na^N_1。对于给定的行向量a1Na^N_1,其子向量表示为aija^j_i,1i,jN1≤i,j≤N,且iji≤j。如果j<ij <iaija^j_i被视为无效。对于给定的a1Na^N_1A{1,,N}A⊂\{1,…,N\},记aAa_A表示子向量(ai:iA)(a_i:i∈A)。记a1,oja^j_{1,o}表示奇数索引的子向量
    (ak:1kj;k odd)(a_k:1≤k≤j;k\ odd),记a1,eja^j_{1,e}表示偶数索引的子向量(ak:1kj;k even)(a_k:1≤k≤j;k\ even)。例如,对于向量a15=(5,4,6,2,1)a^5_1=(5,4,6,2,1),有a24=(4,6,2)a^4_2=(4,6,2)a1,e5=(4,2)a1,o4(5,6)a^5_{1,e}=(4,2),a^4_{1,o}(5,6)。全零向量则记为01N0^N_1

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

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

    B.信道极化

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

    1)信道合并:

    此阶段以递归方式合并给定B-DMC W的副本,以产生向量通道WNXNYNW_N:X_N→Y_N,其中NN可以是2的任意幂,N=2nn0N = 2^n,n≥0。 递归从第0级(n=0n = 0)开始,只有一个W副本,并且我们设置W1WW_1\triangleq W。 递归的第一级(n=1n = 1)组合了W1W_1的两个独立副本,如图1所示,并获得了具有转移概率的通道W2X2Y2W_2:X^2→Y^2
    在这里插入图片描述
    在这里插入图片描述
    第2级(n=2)递归如图2所示,联合信道W2W_2的2个独立副本得到信道W4:X4Y4W_4:X^4→Y^4,其转移概率为
    在这里插入图片描述
    在这里插入图片描述
    在图2中,R4R_4是完成从(s1,s2,s3,s4)(s_1,s_2,s_3,s_4)v14=(s1,s3,s2,s4)v^4_1=(s_1,s_3,s_2,s_4)的置换操作(排序)。从信道W4W_4的输入W4W^4的输入的映射u14x14u^4_1→x^4_1可用公式表示为x14=u14G4x^4_1=u^4_1G_4.
    在这里插入图片描述
    因此W4W_4W4W^4的转移概率有关系式W4(y14u14)=W4(y14u14G4)W_4(y^4_1|u^4_1)=W^4(y^4_1|u^4_1G_4)

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

    2) 信道分裂

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

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

    3)信道极化

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

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

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

    4)极化率

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

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

    C. Polar coding

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

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

    1)GNG_N-coset codes 陪集编码

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

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

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

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

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

    3) Code performance代码性能

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

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

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

    4) Polar codes

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

    5)编码定理:

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

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

    6)复杂度:

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

    定理5:对于GN陪集码的类别,编码的复杂度和连续消除解码的复杂度均为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=2nN = 2^nn0n≥00KN0≤K≤N,将块长度为NN,尺寸为KK的RM代码(表示为RMNKRM(N,K))定义为线性代码,其生成器矩阵GRMNKG_{RM}(N,K)是通过删除FnF^{⊗n}行的NK(N-K)获得的,因此删除的行中的汉明权重(该行中的1的个数)都不比其余K行中的汉明权重大 。
    例如
    在这里插入图片描述
    这种构造体现了RM码和极性码之间的相似性。 由于对于任意N=2nN=2^nGNG_NFnF^{⊗n}具有相同的行集(只是顺序不同),显然RM码属于GN-陪集码的类,例如,RM(42)RM(4,2)是参数为(4224(00))(4,2,{2,4},(0,0))的G4-陪集码。 因此,RM编码和极化码可以被认为是用于选择给定大小(NK)(N,K)的GN陪集码的信息集合A的两个可选规则。 与极化编码不同,RM编码以与信道无关的方式选择信息集;它不像极性编码那样对信道极化现象进行微调。 我们将在X节中证明,至少对于这类BEC,信息集选择的RM规则在SC译码下导致渐近不可靠的码。 因此,通过更密切地关注信道极化,极性编码以非平凡的方式超越了RM编码。

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

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

    E.论文大纲

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

    II.递归通道变换

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

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

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

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

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

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

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

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

    III. 速率与可靠性转换

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

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

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

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

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

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

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

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

    IV.信道极化

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

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

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

    后面的以后再写吧

    展开全文
  • 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)方法的适用范围是BEC信道。又因为BEC是B-DMC的子集。因此在Polar Code编码时只能回落到BEC上来构造。
    注意:当信道不是BEC信道时,比如二进制对称信道(BSC)信道或二进制高斯白噪声信道(BAWGNC),则超出了Z(W)Z(W)的适用范围,原因是各个分裂信道的Z(W)Z(W)的数值无法精确得到。
    为了更精确的估计信道极化中各分裂子信道的可靠性,Mori等人提出了密度进化(Density Evolution,DE)的构造方法。该方法使用与所有类型的B-DMC。
    定义错误概率
    对信道WWNN个独立时隙上进行信道极化以后,得到极化信道Z(WN(i))Z(W_N^{(i)}),其中i=1,2,...,Ni=1,2,...,N。令事件AiA_i表示序号为ii的极化信道WN(i)W_N^{(i)}所承载的比特经过传输后发生错误,即
    Ai={uiN,y1N:WN(i)(y1N,u1i1ui)<WN(i)(y1N,u1i1ui1)}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)\}
    则极化信道WN(i)W_N^{(i)}的错误概率为P(Ai)P(A_i)
    注解:关于事件AiA_i的定义,后续会有文章专门作解释。

    密度进化(DE)

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

    高斯近似(GA)

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

    最后

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

    展开全文
  • 量子去极化信道

    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信息之外的经典容量的信道。

     

    展开全文
  • 多用户超宽带(UWB)信道严重地遭受了实际的损害。 其中,多径衰落和干扰(例如多路访问干扰(MAI)和符号间干扰(ISI))会严重降低系统性能。 本文提出了一种由Arikan最初开发的极性编码技术,旨在提高基于室内UWB...
  • 该模型可通过已知的多天线配置、极化场辐射模式及散射体的空间分布,建立去极化效应模型,从而将信道的去极化效应由交叉极化鉴别度——XPD(cross polarization discrimination)的值表示,以拓展极化调制在V2V系统...
  • 在5.8 GHz频段上设计了天线实物,然后测量体域传播特性并建立离体分集信道模型,进而研制了信道仿真器,并与线极化天线分集情况进行比较。实验与仿真结果表明,同等条件下圆极化分集的等增益合并功率电平比线极化...
  • 关于信道极化及极化码的定义最初是在Arikan教授的原创性论文中提出,本节内容也是基于他的论文所写的。通过阅读本篇文章,大家可以掌握信道极化的原理,极化码如何定义以及如何度量信道可靠性。有问题欢迎留言交流啊...

    目录

    (如要找其他内容,欢迎访问我的主页寻找)
    #前言
    #极化码概述
    #极化码定义
    #极化码编码
    #极化码译码
    #5G标准中极化码的编译码概述
    #5G标准中极化码的编码
    #5G标准中极化码的译码
    #总结

    极化码定义

    关于信道极化及极化码的定义最初是在Arikan教授的原创性论文中提出,本节内容也是基于他的论文所写的。通过阅读本篇文章,大家可以掌握信道极化的原理,极化码如何定义以及如何度量信道可靠性。有问题欢迎留言交流啊!

    记号表示

    W:X→Y 表示一个通用二进制输入离散无记忆信道B-DMC(Binary-Discrete Memoryless Channel),其中数组X表示输入向量,数组Y表示输出向量;
    W(y | x) 表示信道转移概率,其中x∈X,y∈Y。数组X的元素在{0,1}中取值,数组Y以及转移概率的取值则是任意的。
    WNW^N 表示由N个彼此独立但相同的W信道所组成的DMC信道,对应: WNW^N:XNX^NYNY^N,该信道转移概率表示为:
    在这里插入图片描述

    信道度量参数

    这里有两个十分重要的参数需要学习和掌握:
    1、对称容量(信道容量):在这里插入图片描述
    该参数表示当信道进行可靠传输时可达到的最大传输速率;当I(W)值越大,表示信道传输效果越好,信道越可靠;反之,信道越不可靠。
    2、巴氏参数(Bhattacharyya parameter):在这里插入图片描述
    该参数表示信道的信息接受错误概率的上界,也即错误概率的最大值。很容易理解,当Z(W)值越小的时候,代表信道传输效果越好,信道越可靠;反之,信道越不可靠。

    生成矩阵

    生成矩阵是极化码编码很重要的组成部分。极化码的数学计算基于一个核矩阵的极化效应,极化效应通过克罗内克积(Kronecker)来产生(如果对Kronecker不了解的话,可百度查询,这里不对其进行介绍)。不同的核矩阵会有不同的极化速率和极化效果,在Arikan的原创论文中,他选择了矩阵 G2G_2=[1011]\begin{bmatrix} 1&0\\ 1&1\end{bmatrix} 作为核矩阵。对于一个长度为 N=2n2^n的极化码来说,其对应的生成矩阵表示为
    在这里插入图片描述
    该式子右边表示n个G2G_2矩阵依次进行Kronecker积之后再进行奇偶置换操作,BNB_N表示一个排列矩阵,通过将下标的二进制表示进行位翻转操作实现奇偶置换操作,下节会进行介绍。

    信道极化现象

    信道极化现象说的就是当我们输入的信息比特码长趋于无穷大的时候,信道产生极化现象,使得一部分信道,其信道容量趋于“1”,达到“无噪信道”,可进行可靠传输;一部分信道其信道容量趋于“0”,变成“全噪信道”,不能进行可靠传输。我们选择这些“无噪信道”传输我们发送的信息比特,用“全噪信道”发送一些收发双方都已知的冻结比特或者辅助信息比特,以此高效地利用信道传输我们的信息,提高性能。
    信道极化现象分为信道合并和信道分裂两步。下面对这两个过程进行详细描述
    一、信道合并
    信道合并过程就是通过递归方法,将N个相互独立且相同的信道W合并为信道WNW_N的过程。已知极化码的长度为N=2n2^n,下面是递归过程(下列图中和算式中一个圆里面有个加号,该符号表示模2加法运算):
    1、n=0时,N=1,此时W1W_1=W;
    2、n=1时,N=2,此时将两个B-DMC合并,合并过程如下图所示:
    在这里插入图片描述
    合并后得到矢量信道 W2W_2X2X^2Y2Y^2,对应转移概率为在这里插入图片描述
    上式又可以表示为在这里插入图片描述
    3、n=2时,N=4,此时将两个信道W2W_2合并,合并过程如下图所示
    在这里插入图片描述
    上图中的R4R_4表示奇偶置换操作,例如当输入序列为(s1s_1,s2s_2,s3s_3,s4s_4)时,通过奇偶置换得到序列(s1s_1,s3s_3,s2s_2,s4s_4)。
    合并后得到信道矢量W4W_4X4X^4Y4Y^4,对应的信道转移概率为在这里插入图片描述
    上式又可以写为在这里插入图片描述
    其中,G4G_4就表示长度为4的极化码的生成矩阵在这里插入图片描述

    4、如此递归合并,直到极化码的长度为N时,此时合并两个矢量信道WN/2W_ {N/2},合并过程如下图所示
    在这里插入图片描述
    合并后得到矢量信道WNW_NXNX^NYNY^N,其信道转移概率表示为在这里插入图片描述
    生成矩阵如前面定义计算得到。
    二、 信道分裂
    信道分裂的原理蕴含在极化码译码的算法原理当中,下面进行简要介绍,详细操作过程将会在译码算法那一章进行介绍。
    当通过上一节信道合并以后得到矢量信道WNW_N,之后对该矢量信道进行分裂,得到N个相互独立的二进制输入位信道,这些信道是并列的,同时传输比特信息。该信道表示为WNiW_N^i:X→YNY^Nx Xi1X^{i-1},1≤ i ≤N,其转移概率表示为在这里插入图片描述
    其中(y1Ny_1^N,u1i1u_1^{i-1})表示位信道WNiW_N^i的输出,uiu_i表示它的输入。
    为了对位通道有更加直观的理解,引入一个被称为精灵辅助的连续相消译码器,其译码原理是:当我们要判决元素uiu_i时,需要结合得到的接收信号值y1Ny_1^N和前面 i-1 个位信道的输入u1i1u_1^{i-1}(在这里我们假设前面的输入u1i1u_1^{i-1}都是判决正确的)。

    总结

    在本章中,我已经尽可能用比较通俗易懂的表达方式去为大家介绍极化码的相关定义和原理,我用一种我在学习这一节知识点时的理解顺序进行了排版,希望也能让大家更好的理解。相信通过这一节,大家已经学懂了极化码是怎么一回事,在下一节,我将会为大家介绍极化码的构造方式和算法原理,极化码的编码过程。如果有不懂或者错误的地方,欢迎大家批评指正。

    最后,新人博主写帖子不易,如果你觉得对你有帮助,多多点赞分享关注打赏,给我更多创作动力。祝大家都能有所学,有所获,加油!

    展开全文
  • Polar Code是通过引入信道极化的概念而建立的。信道极化分两个阶段,分别是信道联合和信道分裂。通过信道的联合和分裂,各个子信道的对称容量将呈现两极分化的趋势:随着码长NNN的增加,一部分子信道的容量趋于1,而...
  • x+y=zx+y=zx+y=z 重大时间节点 2016年11月18日,在美国内华达州里诺召开的3GPP RAN1...2009年在“IEEE Transaction on Information Theory”期刊上发表了一篇长达23页的论文更加详细地阐述了信道极化,并基于信道极化
  • 极化码的小白之路

    2020-07-19 15:23:11
    信道极化:信道在一系列的组合和分裂后一部分的信道的信道容量趋于1,另一部分的信道容量趋于0。这种现象就叫信道极化。 信道数量N越大,信道极化就越充分,且信道容量趋于1的比例是可求的。这里不做细节讨论。 极化...
  • 天线极化对LOS / OOS室内无线电信道中功率和RMS延迟扩展的影响
  • 极化码小结

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

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

    千次阅读 2017-09-16 18:06:12
    其中高可靠性的前提条件为“码长较长时”,在短码领域,由于信道极化的不充分,极化码并不能很好的逼近香农限。低复杂度也有前提条件,就是它是基于BEC(二元删除信道)提出的,在BEC信道下,极化码的编码和译码都...
  • 华为近日宣布继今年4月份率先完成中国IMT-2020(5G)推进组第一阶段的5G空口关键技术验证和测试后,在5G信道编码领域的极化码(Polar Code)技术上再次取得最新突破。 静止和移动场景、短包和长包场景的外场测试增益...
  • 实验室的极化码编码译码仿真程序,在BSC、BEC、AWGN信道条件下都有。使用密度进化法和巴氏参数估计信道,仿真性能非常好。 在Matlab下应用非常方便,支持多组仿真。配有应用说明,非常好用。希望能给大家带来帮助。
  • 信道化处理

    千次阅读 2010-12-02 21:19:00
    本章是重点 Ø 基带传输/频带传输 Ø 调制方式:BPSK/QPSK/QQPSK/8PSK/MSK/GMSK Ø 相干与非相干解调 Ø 极化分集 Ø 空间分集 Ø 角度分集 Ø 路径分集 Ø 
  • BEC信道极化现象 以消除概率=0.5 的二进制消除信道 BEC 为例,信道的错误概率上限巴氏参数可通过以下确定的递归计算得到: Python实现程序如下: import os import numpy as np import matplotlib.pyplot as plt ...
  • 作为第一种达到信道容量的高性能编码,极化码是未来6G数据传输的重要候选方案。为此提出了面向6G的极化处理框架。在此框架下,设计高性能的级联极化编码方案,可以逼近有限码长信道容量极限,符合6G超高可靠传输要求...
  • 信道编码方案中的极化码是5G通信领域中的研究热点。极化码在串行抵消译码下容易受到差错传播的影响,在中短码长上的性能并不理想。针对这些问题,在不同仿真情况下对系统极化码和非系统极化码的性能差异性进行了研究...
  • 雷德(Rader)算法:假如使用A[I]存的是顺序位序,而B[J]存的是倒位序。I&lt;J的时候需要变序,I&gt;J的时候就不用。注意:倒位排序-对二进制而言。倒位序 顺序 二进制表示 倒位序顺序0 0 000 0004 1 100 ...
  • 5G NR信道编码简述

    千次阅读 2019-11-26 11:51:32
    基于信道极化理论创造。关键是将消息承载在经过多次信道合成和分裂得到的高可靠子信道上。 上行传输中,对UCI进行编码,在PUCCH、PUSCH上传输;下行传输中,对DCI进行编码,在PDCCH上传输,也对广播信息进行编码,在...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 178
精华内容 71
关键字:

信道极化