-
极化码信道极化仿真
2019-01-18 15:30:40根据Arikan的论文自己编写的信道极化的仿真matlab程序。。 -
信道极化编码
2014-08-19 18:28:43对于对称二进制无记忆信道,通过信道极化可以构造趋于信道容量的编码。 -
信道极化:一种用于构造对称二进制输入无记忆信道的容量实现码的方法
2020-04-17 23:42:18作者为: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)的对称容量的码序列。对称容量是使用具有相等概率的信道的输入字符可以达到的最高速率。信道极化是指可以从给定B-DMC 的个独立副本中合成第二组个二进制输入信道,使得当变大时,接近1的索引的分数接近,接近0的索引的分数接近。极化信道对于信道编码是条件良好的:只需要通过容量接近1的通道以速率1发送数据,其余通道以速率0发送数据。基于此思想构造的代码称为极性代码。本文证明了,给定任意的B-DMCW和任意目标码率,存在一个极化码序列{CN;n≥1},使得Cn的块长,码率,在与码速率无关的情况下,逐次抵消译码下块差错概率有界为。这种性能可以通过编码器和解码器来实现,每个编码器和解码器的复杂度分别为。
I.引言与概述
香农关于有噪的信道编码定理的一个令人着迷的证明是,他使用随机编码方法来显示容量实现代码序列的存在,而不给出任何特定的这种序列[1]。从那时起,构造具有低编码和解码复杂度的可证明容量的代码序列成为了一个遥不可及的目标。 本文是针对B-DMC类的这一目标的尝试。
在这一部分中,我们将对本文的主要观点和结果进行说明。 首先,我们给出了一些定义,并陈述了通篇使用的一些基本事实。A.前期工作
一个二进制输入离散无记忆信道(B-DMC)可表示为表示为具有输入字母X,输出字母Y和转移概率W(y | x),x∈X,y∈Y。由于信道是二进制输入,集合;和是任意值。我们用表示次使用时对应的信道。因此,的转移概率为。
在给定B-DMCW的情况下,本文主要关注两个信道参数:对称容量
和巴氏指标参数
这些参数分别被用作速率和可靠性的度量。是信道在等概率输入下的进行可靠传输的最高速率,是当W仅使用一次发送0或1时最大似然(ML)判决错误概率的上界。
很容易看到取值于。 自始至终,我们将使用以2为底的对数;因此,也将取值于。 码率和信道容量的单位将是比特。
且仅当时,;当且仅当时,。附录中证明的以下界限可以使这一点更加精确。
命题1:对于任何B-DMCW,我们都有
当W是对称信道时,对称容量I(W)等于香农容量,即存在输出字母的置换的信道,使得(I)和(ii)对于所有y∈Y。二进制对称信道(Binary Symmetric Channel,BSC)和二进制删除信道(Binary Erasure Channel,BEC)都是满足对称性的B-DMC。具体地说,对于,满足且的B-DMC是为BSC。对于,满足或的B-DMC是为BEC。对于BEC,符号称为删除符号(Erasure Symbol)所有删除符号上的总和称为BEC的删除概率。我们用大写字母(如)表示随机变量(RVs),用相应的小写字母(如)表示它们的实现(样本值)。对于 是RV,表示X上的概率分配,对于的联合集合,表示联合概率分配,我们用标准记号,分别表示互信息及其条件形式。
行向量在这里简写为。对于给定的行向量,其子向量表示为,,且。如果,被视为无效。对于给定的和,记表示子向量。记表示奇数索引的子向量
,记表示偶数索引的子向量。例如,对于向量,有,。全零向量则记为。本文中的码构造将在二进制域GF(2)上的向量空间中进行。 除非另有说明,否则所有的向量、矩阵和对它们的运算都将是GF(2)上的。
特别地,对于GF(2)上的,向量,我们写表示它们的分量mod-2和。矩阵和矩阵的Kronecker乘积定义为
这是一个mr-by-ns矩阵。 对于所有n≥1,克罗内克积被定义为。 并定义的约定。
我们用来表示集合中元素的数目,我们用来表示集合的指示函数;因此,如果,则等于1,否则为0。B.信道极化
通道极化是一种操作,通过该操作,从给定B-DMC 的个独立副本中制造第二组N个信道,其显示极化效应的意义是,对称容量项对于除索引的消失部分之外的所有项都趋向于0或1。 该操作由信道合并阶段和信道分裂阶段组成。
1)信道合并:
此阶段以递归方式合并给定B-DMC W的副本,以产生向量通道,其中可以是2的任意幂,。 递归从第0级()开始,只有一个W副本,并且我们设置。 递归的第一级()组合了的两个独立副本,如图1所示,并获得了具有转移概率的通道
第2级(n=2)递归如图2所示,联合信道的2个独立副本得到信道,其转移概率为
在图2中,是完成从到的置换操作(排序)。从信道的输入的输入的映射可用公式表示为.
因此和的转移概率有关系式。图3所示为递归结构的一般形式。的2个独立副本联合产生信道。输入向量进入信道,首先被转换为:。是一个排列,称为反向洗牌运算,输入为,输出为。则成为2个独立副本的输入。
映射是二元域GF(2)上的线性变换。 通过归纳法得出,从合成通道的输入到基础原始通道的输入的总体映射也是线性的,可以用矩阵表示,即。
我们称大小为的生成器矩阵
两个信道和的转移概率由下式关联
其中.我们将在第VII节中证明,对于任何,,等于,其中是称为比特反转的置换矩阵,F=。 请注意,信道合并操作由矩阵完全指定。另请注意,和具有相同的行集,但顺序不同(位反转);我们将在第VII节中更详细地讨论此主题。2) 信道分裂
从合成矢量通道之后,信道极化的下一步是将拆分为由转移概率定义的一组个二进制输入坐标信道,已定义 由转移概率
其中表示的输出,表示其输入。
为了直观理解信道,考虑一个genie辅助的逐次消除解码器,其中第i个判决单元在观察到和过去的信道输入(由genie正确地提供,而不考虑早期的任何判决错误)之后估计。如果在上是先验一致的,则是第个判决单元在该场景中看到的有效信道。3)信道极化
定理1:对于任何B-DMC W信道,信道在某种意义上是极化的,对于任意的,当通过2的幂变为无穷大时,索引,其中满足的信道数占总信道数N的比例趋于,而满足的信道所占的比例趋于。
该定理在第IV节中得到了证明。对于具有擦除概率的BEC的情况,极化效应在图4中示出。 已经使用递归关系计算了数字
其中。 这种递推只对BEC有效,第III节证明了这一点。对于一般的B-DMC W,目前还没有有效的算法来计算。图4显示对于小的i趋向于接近0,对于大的i趋向于接近1.然而,在的中间范围内表现出不稳定的行为.对于一般的B-DMC,确定高于给定阈值的索引的子集是一个重要的计算问题,将在第IX节中讨论.
4)极化率
为了证明编码定理,极化效应随N的变化而保持极化速度是很重要的。我们在这方面的主要结果是根据参数给出的
定理2:对于任何且任意的B-DMC 信道W,都存在一个序列集,例如对于所有并且
该定理在IV-B节中得到了证明。
我们用而不是来表示定理2中的极化结果,因为这种形式更适合我们将要开发的编码结果。 在定理1的帮助下,从定理2可以得到以表示的偏振率结果。C. Polar coding
我们利用极化效应来构造实现对称信道容量的码,我们称之为极性编码。
极化编码的基本思想是建立一种编码系统,在该编码系统中,人们可以单独访问每个坐标信道,并且只通过接近0的那些信道发送数据。
1)-coset codes 陪集编码
首先,作为特殊情况,我们描述一类包含极性代码(主要关注的代码)的分组代码。 此类的块长度N被限制为2的幂,对于。 对于给定的N,该类中的每个代码都以相同的方式编码,即
其中是上面定义的N阶生成矩阵。
对于{1,…,N}的任意子集A,我们可以将(8)写为
其中表示由中具有索引的行组成的的子矩阵。如果现在固定和,并且将保留为自由变量,则将获得从源块到代码字块的映射。该映射是陪集编码:它是线性块码与生成器矩阵的陪集,该陪集由固定向量确定。 我们将此类代码统称为-coset代码。(陪集代码)
我们将这类码统称为-陪集码,单个-陪集码将由一个参数向量来标识,其中K是码的维数,指定A的大小。 比率称为编码率。我们将(我们将冗余参数K包括在参数集中,因为我们通常考虑K固定而A自由的码集。)设为信息集,将称为冻结位或向量。
例如,(4,2,{2,4},(1,0))代码具有编码映射
对于源块,编码块是。
不久将通过给出选择信息集合的特定规则来指定极性码。2)A successive cancellation decoder 连续消除解码器
考虑带有参数的陪集代码。 令被编码为码字,使通过信道被发送,并且使信道输出被接收。 在已知的情况下,解码器的任务是生成的估计值。
由于解码器可以通过设置来避免冻结部分中的错误,因此真正的解码任务是生成的估计。
除非提到其他解码器,否则本文将针对特定的连续消除(SC)解码器给出编码结果。 给定任何GN陪集码,我们将使用SC解码器,该解码器通过计算生成其决策
以从的顺序,其中是定义为
对于所有,。 我们将说如果或等效地如果则发生解码器块错误。
上面定义的决策函数与ML(最大似然)决策函数相似,但并不完全一样,因为它们将冻结的未来比特视为RV(随机向量),而不是已知比特。 作为这种次优的交换,可以使用递归公式有效地计算{hi},如我们在第II节中所示。 除算法效率外,决策函数的递归结构非常重要,因为它会使解码器的性能分析变得易处理。幸运的是,由于不使用真正的ML决策函数而导致的性能损失可忽略不计:仍可实现。3) Code performance代码性能
符号将表示码的块差错概率,假设每个数据向量以概率发送,并且解码由上述SC解码器完成。 更准确地说,
的所有选择的的平均值将由表示:
SC解码下的块错误概率的关键范围如下。命题2:对于任何B-DMC W和参数的任何选择,
因此,对于每个,都有一个冻结的向量
V-B节证明了这一点。 这一结果建议从{1,…,N}的所有K个子集中选择A以便最小化(13)的RHS。这个想法导致了极坐标的定义。在这里直接写为uAc
4) Polar codes
在给定B-DMC W的情况下,如果选择信息集A作为{1,…, N}的K元素子集,则具有参数(N,K,A,uAc)的GN陪集代码将被称为W的极化码。 对于所有
极化码是信道特定的设计:一个信道的极化码可能不是另一个信道的极化码。 本文的主要结果是证明了极性编码可以达到任意给定B-DMCW的对称容量。
极化码定义的另一种规则是将A指定为的K个元素子集,使得对于所有, 。 此替代规则也将达到。 但是,基于Bhattacharyya参数的规则具有与块错误概率的显式界限相联系的优点。
极性代码定义未指定如何选择冻结向量uAc; 可以随意选择。 uAc选择的这种自由度通过允许对总体进行平均,从而简化了极性代码的性能分析。 但是,我们并没有为选择uAc指定精确的规则,不仅仅是为了分析方便,还因为代码性能似乎对该选择相对不敏感。 实际上,我们在VI-B节中证明,对于对称通道,任何选择的foruAcis都与其他方法一样好。5)编码定理:
对于一个固定的B-DMC W,编号R≥0。 设定义为,根据W的极性编码规则选择A.因此,是针对W上具有块长度N和速率R的极性编码的SC解码下的块差错概率,在冻结位uAc的所有选择上取平均值。 本文的主要编码结果如下:
定理3:对于任何给定的B-DMCW和固定的R <I(W),连续消除解码下极性编码的块错误概率都满足
这个定理是定理2和界(13)的一个简单推论,如我们在V-B节中所示。 对于对称通道,我们有以下定理3的增强版本。
定理4:对于任何对称的B-DMC W和任何固定的,考虑GN陪集码的任何序列,其中N递增到无穷大,,根据W的极性编码规则选择,并且uAc取任意值。 连续消除解码后的块错误概率满足
第VI-B节证明了这一点。 注意,对于对称信道,等于W的香农容量6)复杂度:
极化码的一个重要问题是编码、译码和码构造的复杂性,信道极化构造的递归结构使得GN陪集码,特别是极化码的编译码算法复杂度较低。
定理5:对于GN陪集码的类别,编码的复杂度和连续消除解码的复杂度均为作为代码块长度N的函数。
这一定理在第VII节和第VIII节中得到了证明。注意,定理5中的复杂性界限与码率和冻结向量的选择方式无关。 即使在I(W)以上的利率下,这个界限仍然存在,但显然这没有实际意义。对于码构造,我们没有发现用于构造极性代码的低复杂度算法。 一个例外是BEC,对于该BEC,我们有一个极性代码构造算法,其复杂度为O(N)。 我们将在第九节中进一步讨论代码构造问题,并提出一种用于近似精确极性代码构造的低复杂度统计算法。
D.与以前工作的关系
本文是文献[2]工作的推广,文中用通道合并和分裂的方法证明了某些特定DMC的总截止率可以得到改善。 然而,没有任何递归方法被建议达到这种改进的极限。
随着当前工作的进展,很明显极性编码与Reed-Muller(RM)编码有很多共同之处[3],[4]。 实际上,递归代码构造和SC解码是极性编码的两个基本要素,似乎已经被RM代码引入了编码理论。
根据RM代码的一种构造,对于任何,和,将块长度为,尺寸为的RM代码(表示为)定义为线性代码,其生成器矩阵是通过删除行的获得的,因此删除的行中的汉明权重(该行中的1的个数)都不比其余K行中的汉明权重大 。
例如
这种构造体现了RM码和极性码之间的相似性。 由于对于任意,和具有相同的行集(只是顺序不同),显然RM码属于GN-陪集码的类,例如,是参数为的G4-陪集码。 因此,RM编码和极化码可以被认为是用于选择给定大小的GN陪集码的信息集合A的两个可选规则。 与极化编码不同,RM编码以与信道无关的方式选择信息集;它不像极性编码那样对信道极化现象进行微调。 我们将在X节中证明,至少对于这类BEC,信息集选择的RM规则在SC译码下导致渐近不可靠的码。 因此,通过更密切地关注信道极化,极性编码以非平凡的方式超越了RM编码。通过注意极化码是多级码,它是源于Plotkin码组合方法的一类码[5],可以建立到现有工作的另一种联系。
鉴于RM码也是多级码[6,pp.。 114-125]。
然而,与典型的多级码构造不同的是,在典型的多级码构造中,人们从特定的小码位开始以构建较大的码位,在极性编码中,多级码是通过相对于信道特定的准则清除全阶生成矩阵GN的行来获得的。 GN的特殊结构确保了无论如何删除,结果代码都是多级代码。 本质上,极性编码享有从这种编码的集合中选择多级编码的自由,以便适合手头的信道,而传统的多级编码方法没有这种程度的灵活性。最后,我们希望提及极化码的“频谱”解释,类似于Blahut对BCH代码的处理[7,Ch。 9]; 这种相似性已经被Forney 证明[8,Ch。 11]与RM代码有关。 从频谱观点来看,编码操作(8)被视为“频率”域信息矢量uN1到“时间”域码字矢量的变换。 变换是可逆的,其中。 解码操作被视为一种频谱估计问题,其中给了一个时域观测值,它是的嘈杂版本,并被要求估计。 为了帮助进行估算,允许冻结一定数量的uN1光谱分量。 极性编码的这种频谱解释表明,有可能在统一框架中处理极性代码和BCH代码。 频谱解释也为在极性编码中使用各种信号处理技术打开了大门。 确实,在第七节中,我们在设计极坐标编码器时采用了一些快速的变换技术。
E.论文大纲
论文的其余部分组织如下。 第二节探讨了信道分割的递归性质。 在第三节中,我们重点介绍了I(W)和Z(W)是如何通过信道合并和分离的单一步骤进行变换的。 我们将其推广到第四节的渐近分析,完成了定理1和定理2的证明,从而完成了本文关于信道极化的部分,其余部分主要是关于极性编码的。 第五节给出了SC译码下极化编码误块率的一个上界,并证明了定理3。第六节考虑了对称B-DMCS的极性编码,证明了定理4。第七节分析了编码器映射GN,从而得到了有效的编码器实现。 在第八节中,我们给出了一种复杂度为的SC译码的实现。 在第九节中,我们讨论了码构造的复杂度,并提出了一种统计近似码构造算法。 在十节中,我们解释了为什么RM码在SC译码下具有较差的渐近性能。 在第十一节中,我们指出了对目前工作的一些概括,给出了一些补充意见,并说明了一些有待解决的问题。
II.递归通道变换
我们通过(4)和(5)定义了逐块通道合并和拆分操作,该操作将W的N个独立副本转换为。 本节的目的是表明可以将该块状通道转换递归分解为单步通道转换。
我们说一对二进制输入通道和是通过二进制输入通道的两个独立副本的单步变换获得的,并且 写
当且仅当存在一对一的映射使得
据此,我们可以为任何给定的B-DMCW写
以为单位映射,其形式为(17)和(18)。事实证明,更广泛地说,我们可以写,
这是对以下内容的推论:
命题3:
该建议在附录中得到了证明。 现在可以通过以下方式证明(21)和(23)在形式上分别与(17)和(18)相同,从而证明变换关系(21)是合理的:
图5.N=8个信道的信道转换过程。因此,我们已经表明,从到的块状通道转换在局部级别上分解为形式为(21)的单步通道转换。 对于,全套这样的变换形成如图5所示的结构。从右向左读取,该图从变换的四个副本开始并以蝶形模式继续,每个蝶形模式表示形式为 。 蝶形阀的右端点处的两个通道始终相同且独立。 在最右侧,有W的8个独立副本;在左边的下一个级别有4个独立的和副本;依此类推。 向左的每一步都会使通道类型的数量加倍,但会使独立副本的数量减半。
III. 速率与可靠性转换
现在我们研究速率和可靠性参数和是如何通过局部(单步)变换(21)改变的。 通过了解局部行为,我们将能够得出从到的整体转换的结论。 附录中给出了本节结果的证明。
A.速率和可靠性的局部转换
命题4:假设对于某些二进制输入信道集合,。 那么,
当且仅当等于0或1。
等式(24)表示单步通道变换保持了对称容量。 不等式(25)与(24)表明,在单步变换下,对称容量保持不变,当且仅当是理想信道或完全噪声信道,。如果既不是完全噪声也不是完全噪声,则单步变换会在的情况上使对称容量偏离中心,从而有助于极化。命题5:假设对于某些二进制输入信道集合,。 那么,
当且仅当W是 BEC,等式成立于(27)。 当且仅当 Z(W)等于0或1,我们有,或等效地,当且仅当等于1或0。
这一结果表明,只有在单步信道变换下,可靠性才能在以下意义上提高
由于BEC在可靠性的w.r.t.极值行为中起着特殊的作用,因此它值得特别关注。命题6:考虑信道变换。 如果W是具有一定擦除概率的BEC,则信道和分别是具有擦除概率为的BEC。 相反,如果W’或W’'是BEC,则W是BEC。
B.速率和可靠性
现在我们回到第二节末尾的上下文。
命题7:对于任何B-DMC W,,变换在以下意义上是保持速率和提高可靠性的
在等式(31)中,如果W是BEC。 信道分裂使速率和可靠性偏离中心,这意味着
(32)和(33)中的等式(如果I(W)等于0或1)。可靠性项进一步满足
当W是BEC时,在(34)中有等式。累积率和可靠性满足
当W是BEC时,与(37)中的等式相等。
这一结果是从命题4和命题5作为特例得出的,不需要单独证明。 累积关系(36)和(37)分别分别重复使用(30)和(31)。命题4中的相等条件是用公式而不是表示的;这是可能的,因为:(i)命题4,当且仅当;(ii)是BEC当且仅当是BEC,这是从命题6归纳而来的。对于是擦除概率为的BEC的特殊情况,从命题4和命题6推导出参数可以通过递归计算
其中。 参数等于信道的擦除概率。递推关系(6)遵循(38)的事实,对于W信道一个BEC 。IV.信道极化
我们在本节中证明了有关信道极化的主要结果。 该分析基于图5中所示的递归关系。 但是,将图5重新绘制为如图6所示的二叉树会更加方便。树的根节点与通道W相关联。根W产生上通道和下通道,这两个通道与级别1的两个节点相关联。通道依次产生通道和,依此类推。 通道位于树的级别n处,节点号i,从顶部开始计数。
在图6中,按位序列对树的节点进行自然索引。根节点使用空序列进行索引。级别1的上部节点使用0进行索引,下部节点使用1进行索引。给定具有索引的n级节点,从其发出的上节点具有标签和下节点。根据该标记,信道位于节点处,。我们将位于节点处的信道表示为。
图6递归通道构建的树过程结合图6,我们定义了一个随机树过程,表示为。该过程从树的根部开始,。对于任意,给定,都等于或,概率各为1/2。因此,通过信道树所采取的路径可以被认为是由i.i.d.伯努利RVs,其中以相等的概率等于0或1。 假定已经采用样本值,则随机信道过程采用值。 为了跟踪信道随机序列的速率和可靠性参数,我们定义了随机过程。
为了更精确地描述这个问题,我们考虑了概率空间,其中Ω是所有二进制序列的空间是由圆柱集生成的Borel场(BF),,P是定义在F上的概率测度,使得。对于每个n≥1,我们将定义为cylinder 组生成的BF。我们将定义为仅由空集和Ω组成的无关BF。显然,。
现在可以如下正式定义上述随机过程。
后面的以后再写吧
-
转载-极化码系列(4)-编码之极化信道可靠性估计
2020-12-09 16:58:48Arikan在讨论信道极化时,采用的是B-DMC(二进制离散无记忆信道),然而在构造极化码时需要使用的计算巴氏参数Z(W)Z(W)Z(W)方法的适用范围是BEC信道。又因为BEC是B-DMC的子集。因此在Polar Code编码时只能回落到BEC...前言
由Arikan发明的Polar Code的经典编码算法已经在第二节基本阐述完毕,第三节则是对前文的举例。在编码实例中,有两个前提假设:
1.假设采用二进制删除信道
2.假设采用巴氏参数来评估各分裂子信道的可靠性。
Arikan在讨论信道极化时,采用的是B-DMC(二进制离散无记忆信道),然而在构造极化码时需要使用的计算巴氏参数方法的适用范围是BEC信道。又因为BEC是B-DMC的子集。因此在Polar Code编码时只能回落到BEC上来构造。
注意:当信道不是BEC信道时,比如二进制对称信道(BSC)信道或二进制高斯白噪声信道(BAWGNC),则超出了的适用范围,原因是各个分裂信道的的数值无法精确得到。
为了更精确的估计信道极化中各分裂子信道的可靠性,Mori等人提出了密度进化(Density Evolution,DE)的构造方法。该方法使用与所有类型的B-DMC。
定义错误概率:
对信道的个独立时隙上进行信道极化以后,得到极化信道,其中。令事件表示序号为的极化信道所承载的比特经过传输后发生错误,即
则极化信道的错误概率为。
注解:关于事件的定义,后续会有文章专门作解释。密度进化(DE)
类似于LDPC码等信道编码,信道极化也可以使用Tanner图的结构来表示。下图给了一个的例子,图中圆圈表示表示变量节点,每一个变量节点代表一个比特,同时也存储了该比特取值为0或1时的概率;而方框则表示校验节点,表示与之相连的各变量节点比特值的校验和为0。
由于变量节点的比特值仅可能有0或1两种取值,因此,存储与变量节点的消息往往用对数似然比(LLR)值来表示。
根据《Polar Code(2)编码原理》中的递归式与式,Tanner图中各个变量节点的LLR值可以递归地计算得到:
若最终得到的;否则,则判决为。
将某一个变量节点的LLR视为一个随机变量,用来表示该随机变量的概率密度函数(PDF)。由于信道满足对称性,可以假设发送的比特为全0,从而该变量节点的比特判决值错误的概率为:
在对第个信道进行可靠性估计时,如上图中加粗线条所示,以比特对应的节点为根节点,逐层扩散,直至最右侧一列变量节点,构成译码树。
用表示信道输入到最右侧一列变量节点的LLR值的PDF;用表示值的PDF。根据密度进化理论以及式(2)和式(3),假设发送的是全零比特序列,在值已知条件下,序号为的极化信道LLR值可以递归的计算如下:
其中,运算符,分别表示校验节点与变量节点上的卷积操作。通过概率密度函数与式(4)可以得到各个极化信道的可靠性度量值。高斯近似(GA)
通过密度进化,对极化信道的可靠度度量进行计算,可以适用于任意类型的B-DMC信道。然而,在实际算法实现时,需要维护一个高维的向量以存储量化过后的概率密度函数。为保证计算结果的精确,该向量的维度常取到,对如此高维的向量进行式(5)和式(6)的卷积操作,计算复杂度非常高。
大多数研究场景下,信道编码的传输信道模型均为BAWGNC信道。在BAWGNC信道下,可以将密度进化中的LLR值的概率密度函数用一族方差为均值2倍的高斯分布来近似,从而简化成了对一维均值的计算,大大降低计算量,这种对DE的简化计算即为高斯近似(Gaussian Approximation,GA)。
对噪声方差为的BAWGNC信道,调制方式为BPSK,若从信道获取的接收信号为。
注解:这里存在疑问,个人理解BPSK应该是。
其中发送比特,。
假设发送比特为全零序列,则对应的LLR值为:
其中。因此,式(9)中的LLR值符合均值为,方差为的高斯分布。根据已有的高斯近似理论,若输入的消息服从独立的高斯分布,对式(6)所示的变量节点上操作,则其输出也服从高斯分布;对式(5)所示的变量节点上的操作,其输出也非常接近高斯分布。由于高斯分布可以由其均值和方差决定,因此在概率密度函数的计算过程中值需要考虑均值和方差,但必须满足密度进化的对称条件。
如果用表示LLR的概率密度,则对称条件表示为。对于均值为,方差为的高斯分布,该对称条件可以简化为。因此,在高斯近似中仅需要考虑一维的变量,即均值。设可以用表示,则式(5)、式(6)和式(7)中所示的LLR计算过程可以用高斯近似成为
其中函数
在上连续单调递减,,,其反函数用表示。一般情况下,函数可以用如下的近似计算
在得到后,各极化信道在发送全零时对应的接收信号LLR值服从分布,于是可靠度量即可计算如下总结
巴氏参数、密度进化和高斯近似法都是计算各分裂子信道错误概率的方法,不同的方法有各自的适用范围。巴氏参数仅适用于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维去极化信道可以被认为是一个完全正的迹保持映射
,它取决于一个参数
,将量子态
映射为自身与最大混合态的线性组合上:
完全正性的条件为
满足:
经典容量
HSW定理说明了量子信道的经典容量
可以描述为正则化的Holevo信息:
这个量很难计算,这反映了我们在量子信道方面知识的匮乏。但是,如果Holevo信息是信道
的附加信息,即
然后通过计算信道的Holevo信息,得到其经典容量。
Holevo信息对所有信道的可加性是量子信息论中一个著名的开放猜想,但现在我们知道这个猜想并不适用于一般情况。通过证明所有信道的最小输出熵的可加性不成立来证明这一点,这是一个等价的猜想。
尽管如此,Holevo信息的可加性被证明对量子去极化通道是成立的,并且下面给出了证明的概要。因此,跨信道的多种用途的纠缠不能增加经典容量。从这个意义上说,信道的表现类似于经典通道。为了达到最佳的通信速率,只需选择一个标准正交基来编码消息,并在接收端执行投射到相同基上的测量。
探讨
该证明中使用的主要技术,即将interest(不知道在这里怎么翻译)的信道重写为其他更简单信道的凸组合,是前面用于证明单位量子比特信道的类似结果的方法的推广。
去极化信道的经典容量等于信道的Holevo信息,这意味着我们不能真正利用纠缠等量子效应来提高经典信息的传输速率。 在这个意义上,去极化通道可以被视为经典通道。
然而,Holevo信息的可加性一般不成立的事实,提出了一些未来的工作领域,即寻找违反可加性的信道,换句话说,可以利用量子效应来改善超出其Holevo信息之外的经典容量的信道。
-
论文研究 - 基于OFDM的UWB信道的极化码性能
2020-05-29 12:34:03多用户超宽带(UWB)信道严重地遭受了实际的损害。 其中,多径衰落和干扰(例如多路访问干扰(MAI)和符号间干扰(ISI))会严重降低系统性能。 本文提出了一种由Arikan最初开发的极性编码技术,旨在提高基于室内UWB... -
论文研究-一种V2V多天线几何去极化信道建模.pdf
2019-07-22 22:19:07该模型可通过已知的多天线配置、极化场辐射模式及散射体的空间分布,建立去极化效应模型,从而将信道的去极化效应由交叉极化鉴别度——XPD(cross polarization discrimination)的值表示,以拓展极化调制在V2V系统... -
采用可穿戴圆极化天线的离体信道特性建模与分集接收方法
2021-01-20 05:55:59在5.8 GHz频段上设计了天线实物,然后测量体域传播特性并建立离体分集信道模型,进而研制了信道仿真器,并与线极化天线分集情况进行比较。实验与仿真结果表明,同等条件下圆极化分集的等增益合并功率电平比线极化... -
极化码理论及算法研究(3)-极化码定义
2020-05-27 04:03:30关于信道极化及极化码的定义最初是在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以及转移概率的取值则是任意的。
表示由N个彼此独立但相同的W信道所组成的DMC信道,对应: :→,该信道转移概率表示为:
信道度量参数
这里有两个十分重要的参数需要学习和掌握:
1、对称容量(信道容量):
该参数表示当信道进行可靠传输时可达到的最大传输速率;当I(W)值越大,表示信道传输效果越好,信道越可靠;反之,信道越不可靠。
2、巴氏参数(Bhattacharyya parameter):
该参数表示信道的信息接受错误概率的上界,也即错误概率的最大值。很容易理解,当Z(W)值越小的时候,代表信道传输效果越好,信道越可靠;反之,信道越不可靠。生成矩阵
生成矩阵是极化码编码很重要的组成部分。极化码的数学计算基于一个核矩阵的极化效应,极化效应通过克罗内克积(Kronecker)来产生(如果对Kronecker不了解的话,可百度查询,这里不对其进行介绍)。不同的核矩阵会有不同的极化速率和极化效果,在Arikan的原创论文中,他选择了矩阵 = 作为核矩阵。对于一个长度为 N=的极化码来说,其对应的生成矩阵表示为
该式子右边表示n个矩阵依次进行Kronecker积之后再进行奇偶置换操作,表示一个排列矩阵,通过将下标的二进制表示进行位翻转操作实现奇偶置换操作,下节会进行介绍。信道极化现象
信道极化现象说的就是当我们输入的信息比特码长趋于无穷大的时候,信道产生极化现象,使得一部分信道,其信道容量趋于“1”,达到“无噪信道”,可进行可靠传输;一部分信道其信道容量趋于“0”,变成“全噪信道”,不能进行可靠传输。我们选择这些“无噪信道”传输我们发送的信息比特,用“全噪信道”发送一些收发双方都已知的冻结比特或者辅助信息比特,以此高效地利用信道传输我们的信息,提高性能。
信道极化现象分为信道合并和信道分裂两步。下面对这两个过程进行详细描述
一、信道合并
信道合并过程就是通过递归方法,将N个相互独立且相同的信道W合并为信道的过程。已知极化码的长度为N=,下面是递归过程(下列图中和算式中一个圆里面有个加号,该符号表示模2加法运算):
1、n=0时,N=1,此时=W;
2、n=1时,N=2,此时将两个B-DMC合并,合并过程如下图所示:
合并后得到矢量信道 :→,对应转移概率为
上式又可以表示为
3、n=2时,N=4,此时将两个信道合并,合并过程如下图所示
上图中的表示奇偶置换操作,例如当输入序列为(,,,)时,通过奇偶置换得到序列(,,,)。
合并后得到信道矢量:→,对应的信道转移概率为
上式又可以写为
其中,就表示长度为4的极化码的生成矩阵
…
4、如此递归合并,直到极化码的长度为N时,此时合并两个矢量信道,合并过程如下图所示
合并后得到矢量信道:→,其信道转移概率表示为
生成矩阵如前面定义计算得到。
二、 信道分裂
信道分裂的原理蕴含在极化码译码的算法原理当中,下面进行简要介绍,详细操作过程将会在译码算法那一章进行介绍。
当通过上一节信道合并以后得到矢量信道,之后对该矢量信道进行分裂,得到N个相互独立的二进制输入位信道,这些信道是并列的,同时传输比特信息。该信道表示为:X→x ,1≤ i ≤N,其转移概率表示为
其中(,)表示位信道的输出,表示它的输入。
为了对位通道有更加直观的理解,引入一个被称为精灵辅助的连续相消译码器,其译码原理是:当我们要判决元素时,需要结合得到的接收信号值和前面 i-1 个位信道的输入(在这里我们假设前面的输入都是判决正确的)。总结
在本章中,我已经尽可能用比较通俗易懂的表达方式去为大家介绍极化码的相关定义和原理,我用一种我在学习这一节知识点时的理解顺序进行了排版,希望也能让大家更好的理解。相信通过这一节,大家已经学懂了极化码是怎么一回事,在下一节,我将会为大家介绍极化码的构造方式和算法原理,极化码的编码过程。如果有不懂或者错误的地方,欢迎大家批评指正。
最后,新人博主写帖子不易,如果你觉得对你有帮助,多多点赞分享关注打赏,给我更多创作动力。祝大家都能有所学,有所获,加油!
-
转载-极化码系列(2)-极化码的编码原理
2020-12-01 17:33:58Polar Code是通过引入信道极化的概念而建立的。信道极化分两个阶段,分别是信道联合和信道分裂。通过信道的联合和分裂,各个子信道的对称容量将呈现两极分化的趋势:随着码长NNN的增加,一部分子信道的容量趋于1,而... -
转载-极化码系列(1)-极化码的起源和概述
2020-12-01 09:35:05x+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延迟扩展的影响
2021-02-24 22:40:59天线极化对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信道下,极化码的编码和译码都... -
5G信道编码技术取得新突破,极化码同时满足ITU三大应用需求
2017-08-01 13:42:00华为近日宣布继今年4月份率先完成中国IMT-2020(5G)推进组第一阶段的5G空口关键技术验证和测试后,在5G信道编码领域的极化码(Polar Code)技术上再次取得最新突破。 静止和移动场景、短包和长包场景的外场测试增益... -
实验室的极化码编码译码仿真程序,在BSC、BEC、AWGN信道条件下都有仿真
2017-10-28 16:36:29实验室的极化码编码译码仿真程序,在BSC、BEC、AWGN信道条件下都有。使用密度进化法和巴氏参数估计信道,仿真性能非常好。 在Matlab下应用非常方便,支持多组仿真。配有应用说明,非常好用。希望能给大家带来帮助。 -
信道化处理
2010-12-02 21:19:00本章是重点 Ø 基带传输/频带传输 Ø 调制方式:BPSK/QPSK/QQPSK/8PSK/MSK/GMSK Ø 相干与非相干解调 Ø 极化分集 Ø 空间分集 Ø 角度分集 Ø 路径分集 Ø -
python实现 Polar码极化过程
2020-06-02 11:27:45BEC信道极化现象 以消除概率=0.5 的二进制消除信道 BEC 为例,信道的错误概率上限巴氏参数可通过以下确定的递归计算得到: Python实现程序如下: import os import numpy as np import matplotlib.pyplot as plt ... -
面向6G的极化码与极化处理
2021-01-13 21:51:07作为第一种达到信道容量的高性能编码,极化码是未来6G数据传输的重要候选方案。为此提出了面向6G的极化处理框架。在此框架下,设计高性能的级联极化编码方案,可以逼近有限码长信道容量极限,符合6G超高可靠传输要求... -
系统极化码和非系统极化码的性能比较
2021-01-14 01:32:44信道编码方案中的极化码是5G通信领域中的研究热点。极化码在串行抵消译码下容易受到差错传播的影响,在中短码长上的性能并不理想。针对这些问题,在不同仿真情况下对系统极化码和非系统极化码的性能差异性进行了研究... -
极化码信道组合与分裂-倒位排序-对二进制而言-Rader算法
2018-04-13 10:11:33雷德(Rader)算法:假如使用A[I]存的是顺序位序,而B[J]存的是倒位序。I<J的时候需要变序,I>J的时候就不用。注意:倒位排序-对二进制而言。倒位序 顺序 二进制表示 倒位序顺序0 0 000 0004 1 100 ... -
5G NR信道编码简述
2019-11-26 11:51:32基于信道极化理论创造。关键是将消息承载在经过多次信道合成和分裂得到的高可靠子信道上。 上行传输中,对UCI进行编码,在PUCCH、PUSCH上传输;下行传输中,对DCI进行编码,在PDCCH上传输,也对广播信息进行编码,在...
-
(单细胞-SingleCell)单细胞标准流程(简化版)
-
UL 859:2017 Household Electric Personal Grooming Appliances(个人护理)-完整英文版(192页)
-
通过成形InGaN / GaN纳米棒来修改远场辐射图
-
FyreString:FyreString是PHP的免费开源字符串实用程序库-源码
-
Linux下jar包后台运行
-
Glasterfs 分布式网络文件系统
-
C笔记-源码
-
Vue中的动画封装(5-7)
-
2009年上半年 信息系统监理师 上午试卷 综合知识 软考真题【含答案和答案解析】
-
【阿里巴巴】22届春招-免笔试
-
辅助驾驶的哈密顿量对绝热演化是否总是有用?
-
Android数据库案例
-
C++代码规范和Doxygen根据注释自动生成手册
-
利用qt对数据库进行操作
-
2009年下半年 网络工程师 上午试卷 综合知识 软考真题【含答案和答案解析】
-
阿里集团八年容器化演进之路
-
Linux基础入门系列课程
-
使用Jenkins搭建iOS/Android持续集成打包平台
-
Python----图像数据增强 翻转变换 规则修剪 高斯模糊 随机旋转 直方图均值化
-
电影记录-源码