英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料
基于码的有效短极化码的最大似然解码
摘要-极化码是已知第一个可执行的编码方式可实现任意对称二进制输入通道的香农容量。虽然存在极化码具有降低的复杂性的有效的次优解码器，但是最佳最大似然解码器的复杂性指数地增加。因此，最佳解码器对于极化编码的实际实现是不可行的。 在本文中，我们的动机是开发有效的最大似然解码器，降低复杂性。为此，提出了一种极化码基于球形解码算法，具有最佳性能。 另外，所提出的技术利用极化编码的两个属性来降低解码复杂度。 通过这种方式，降低的最佳解码的复杂度仅是立方的，而不是指数的。
关键词：最大似然估计，极化码，里德 - 穆勒码，球形译码
I.引言
极化码是第一类可证明的代码实现二元对称信道香农容量[1]。这可以通过编码器和解码器的复杂度O（N logN）而获得，即拟线性块长度N= 2^n，其中n是极化的阶数。尽管在极化码的编码器和解码器单元中的低复杂性，相应的解码器具有次优性能。在[1]和[2]中还报道了，对于使用准线性复杂度的任何beta;lt;0.5，串行抵消（SC）解码器执行块误差概率为Pele;2-Nbeta;。 在[3]中描述了极化码的SC解码器的一般化。在这种情况下，可以显示出性能受到用于短极化码的SC解码器的次最优性的影响。 另外，[4]介绍了极化码的另一个有效和次最佳解码器，置信传播（BP）解码器。[5]研究了极化码和里德 - 穆勒（RM）码的性能，并提出了极化码的BP解码器的有效实现。因此，在文献[6]中报道，在二进制擦除信道（BEC）上的BP的性能明显优于SC解码。然而，在二进制输入加性白高斯噪声信道（BAWGNC）上时性能不会增加[6]。 为了研究极化码在最大似然解码下的性能，在[7]中实现了基于Viterbi算法的用于短极化码的最大似然解码器。不幸的是，在极化编码中，解码复杂性指数地增加以获得最大似然性能[8]。 在这项工作中，首先，我们提出了一个效率树搜索算法在接收器单元中具有最大似然性能，其基于球解码的极化码深度第一搜索策略。其次，我们通过极化编码的编码属性的帮助简化了所提出的方法。 通过这种方式，搜索树可以被分割为具有减少的深度的两个独立的平行树。在[9]中已经表明，对于空时分组码的常规球解码将预期的复杂性从指数减少到多项式（大致为立方）。球面解码算法的思想首先由Fincke和Phost在[10]中作为一种格子中寻找最短向量问题的方法引入。 后来，它适用于[11]中的格子码的高效解码器和[12]和[13]中的多天线系统的空时分组码。我们专注于基于代码的快速球面解码算法，以减少不仅预期，而且最坏情况的解码复杂性[14] - [16]。 我们的动机是为各种块长度开发基于极化码结构的快速最优球解码算法。 在这项工作中，我们只考虑Nle;64的小块长度。此外，我们的方法也可以应用于相对较长的块长度。
极化码识别为P（N，K），其中K是维度，使得0le;Kle;N。注意GF（2）表示两个元素的伽罗瓦域，极化码的代数描述被给出为矩阵形式在GF（2）。
其中Fotimes;n是F的第n次克罗内克积。 这里，发送比特和对应的码字分别由d =（d0，...，dN-1）和x =（x0，...，xN-1）表示。 为了构造P（8,5），首先计算Fotimes;3为
并且在Bhattacharyya参数的帮助下，在极化码的构造中选择了高顺位的5行[1]。这里，我们可以注意到，大多选择第（N-1）行[1 0 ... 1 0]，并且它给我们提出的技术提供可以降低极化码的球解码复杂度的性质。生成矩阵给定为
通道极化规则的分析超出了本文的范围。 读者可以在[1]中找到详细的描述。另外，启发式建设性方法在[4]和[7]中给出。 有N -K = 3个输入位固定为零。 这些也称为冻结位，d0,2,4 = 0。 其他K = 5位drsquo;=（d1，d3，d5，d6，d7）是数据相关的。 以这种方式，极化码P（8,5）的编码器可以在GF（2）中被给出为x = d·G（8,5）。更明确地说，
其中x6 =（d6oplus;d7）（oplus;表示xor位操作）。 在BAWGNC上使用BPSK调制的接收信号可以表示为
其中V是具有零均值和方差sigma;2的加性白高斯噪声。 X是具有用于x，{“1”→ 1，“0”→ - 1}中的编码比特的BPSK调制信号的列向量。 用于BPSK调制的极化码的最大似然估计等效于获得最小欧几里德距离，并且其被给出为
其中 1 为长度为N的全1列向量。
II. 极化码的最佳解码器
作为众所周知的迭代接收过程，球解码算法是一种具有最佳误差性能的有效搜索方法。 简而言之，在算法的第一步中，球解码器假设中心点在1 /2（S 1）的球面，这取决于N维空间中接收的噪声矢量。 然后， 对所有可能的数据序列d#39; ，一个约束作为球体内的要求，以下给出其表达式。
其中r表示球体的半径。 为了阐明所提出的方法，可以给出该约束的开放形式为r 2ge;Sigma;P i，其中P（8,5）的情况的P i可以由下面的等式给出。
球体的半径被初始化为有限的r = inf，并且调制信号字母表在集合Omega;= {-1， 1}中给出。 为了更清楚，可以给出P（8,5）的伪码。
所提出的方法中所考虑的搜索树在图1中被描绘为搜索图。 存在能够在球体内产生至少一个子节点（黑色或灰色）的黑色节点。 相反，灰色节点是非生产性节点。 伪代码的软件实现在线可用[17]。 所提出的算法的解码复杂度是短极化码和RM码的多项式（大致为立方[9]）。
- 基于代码的复杂度减少为了获得更多的复杂性降低，我们认为可以利用极化编码的编码结构而不造成任何性能损失。 在这个目的中，我们注意到Fotimes;n的dN-1和相关的（N-1）行[1 0 ... 1 0]可以用于降低（13）中的所提出的搜索树的复杂度。 使用第（N-1）行的属性，我们可以应用并行两个分离的搜索过程。 通过这种方式，N维提出的搜索处理可以被拆分为两个独立的（N-1）维搜索处理，其可以并行实现而没有任何性能损失。 在并行处理-1中，假设对于P（8,5），d6 = 0，等式（4）可以写为
对于d6 = 0的条件估计可以通过下面的表达式给出
球约束可以给出为r2ge;Sigma;P0 i，其中
这里，我们可以给出并行进程-1的伪代码
通过这种方式，该方法产生解drsquo;。 其中d6 = 0和相应的度量r0。 独立地，在并行处理2中，我们假设d6 = 1，则在这种情况下等式（4）可以写为
对于d6 = 1的条件估计可以通过下面表达式给出
独立地，球约束可以给出为r2ge;Sigma;P1 i，其中
并行过程-2的伪代码可以表示为
独立地， 其中d6 = 1可以获得另一个解drsquo;度量r1。
有两个独立的和不同的解决方案和分别两个不同的度量。 最后，最优解可以通过使用两个不同度量的简单比较器来决定。 因此，N维搜索树可以被分割成2个并行（N-1）维搜索树。
III. 性能和复杂度结果
在本节中，我们给出一些模拟结果来评估期望的解码复杂度和所提出的用于短极化和RM码的方法的获得的最大似然误差性能。 首先，我们通过使用所提出的方法来研究RM和极化码的最大似然估计下的误差性能（64,57）。 在这种情况下，在图2中配置误码率（BER），在最佳性能下RM（64,57）比P（64,57）好。 这些结果也在文献[7]中报道，RM码由于其基于汉明距离的构造而具有更好的错误性能。此外，在图3中，RM（32,26）和P（32,26）实现了等效误差最大似然估计下的性能。 此外，帧错误率（FER）如图5-6所示。 本文提出的方法和文献[7]中基于Viterbi的方法执行相同的最大似然性能。幸运的是，我们可以证明所提出的方法的预期复杂度是立方的，而基于维特比的方法相对复杂度。在球解码算法中，期望的节点访问数可以用作期望的复杂度，而每个节点访问的复杂度增加节点的水平 。 此外，完整的试验集用于穷举搜索解码器。 我们假设所提出的算法和穷尽搜索解码器的预期复杂度可以被给出为目标BER = 10-2,10-3和10-4的平均节点访问数。 仿真结果在表1中给出，表明通过基于码的有效解码方法可以获得显著的复杂度降低，并且所提出的极化码的算法比RM码快2倍。 此外，P（64,57）和RM（64,57）的预期解码复杂度的显著减少在图4中示出，复杂度为EbN0的节点访问的数量。
IV. 结论
在这项工作中，我们介绍一种新的方法是球解码实现极化码的有效最大似然解码技术。 在这种情况下，球面解码基于提出的算法是具有最佳误差性能的极化码的首要选择。 此外，通过提出的方法获得显着的复杂性降低。 首先，示出了最佳解码器的复杂度仅是立方的，而不是指数的。 其次，观察到极化码的解码复杂度低于在所提出的算法下的RM码，同时保证了最佳性能。 因此，我们显示极化码具有快速可解码性质。 在极化编码中，对于解码复杂度有两个有用的属性，即生成矩阵中的零个数多，并行搜索树的编码方案特性。
使用极化码的无损源编码
摘要 - 在本文中考虑极化码的无损压缩。 开发极化编码算法和设计代码并计算平均压缩率的方法。 它表明，方程式渐近地达到最佳压缩率。 此外，所提出的方案在有限长度上具有非常好的性能。 编码和解码操作都可以用复杂度O（N log N）来实现，其中N表示代码的长度。
关键词 - 无损源编码，极化码，极化。
I.引言
误差校正码可以用于源的无损压缩[1]。 在其中在会产生错误的信道上发送压缩数据的设置中，这些方案通常更鲁棒。 已经引入了基于稀疏图形码的几种方案，其中编码和/或解码算法基于置信传播（BP）。 这些方案中的几个在实际设置中表现良好。 然而，最优性似乎难以证明这些方案。
由Arıkan[2]介绍的极性码是一组代码，它们使用低复杂度编码和解码算法实现多种信道的容量。 这些算法的复杂度缩放为O（N logN），其中N是代码的块长度。 最近[3]，[4]已经表明，除了用于信道编码的容量实现之外，极化码还对于有损和无损源编码以及多终端问题是最佳的，例如Slepian-Wolf ，Wyner-Ziv和Gelfand-Pinsker问题。
在[4]中，在无损设置中极化码是最佳的论证是基于将源编码问题映射到信道编码问题。 在[4]中提出的算法有时可能无法正确编码，当失败时，源向量被存储。 在本文中，我们更详细地研究极化码的无损压缩的使用，并表明我们可以修改算法来处理故障。 这就可以提出一种适于分析并且在实际有效长度设置中表现非常好的算法。
在信道编码设置中，极化码看起来与其他编码方案（例如仅对于非常大的块长度的低密度奇偶校验码）竞争。 其原因是解码算法的顺序性质和大量的错误传播。 然而，我们将显示在无损源编码设置中，几乎没有误差传播的问题，并且源编码性能接近适度块长度的理论极限。
大纲如下， 在第二部分中，我们介绍了整篇文章中使用的符号。 在第三节中，我们描述了编码和解码算法。 在第四节中，我们给出了我们的算法的最优性的证明。 在第五节中，我们讨论代码设计和分析。 此外，给出的模拟结果表明我们的方案在有限长度时有非常好的性能。
II. 定义和符号
我们用大写字母（例如U）表示随机变量，并使用相应的小写字母（例如u）来表示它们的实现。 令U表示随机向量（U0，...，UN-1）。 对于任何有限的整数集F，| F | 表示其基数。 此外，Fc表示关于集合{0，...，N-1}的F的补码。 UF表示（Ui1，...，Ui | F |），其中{ikisin;F：ikle;ik 1}。 以类似的方式，我们定义uF。 Uj i表示随机向量（Ui，...，Uj）。 二进制字段由F2表示。 令Ber（p）表示采用Pr（X = 1）= p在F2中取值的伯努利随机变量X. 我们用h2（p）来表示二进制熵函数。 具有概率p的二进制对称信道由BSC（p）表示。 我们用1（A）表示当语句A为真时为1的指示符函数，否则为0。 本文中的对数总是指log2。
在通道和源编码的极化的核心是偏振变换，并且在本文中，我们考虑基于以下矩阵的变换
变换本身被构造为
其中otimes;表示克罗内克积。 基于Gotimes;n的极坐标代码，其中G是l阶矩阵在[5]进行分析。 在这里，我们限制自己基于G2的代码。
定义1（极化码）：为任何Fsube;{0，...，N-1}和uFisin;F 定义的长度N = 2 ^n的极性码CN（F，uF） 2，是一个线性代码如下
换句话说，通过将具有F到uF中的索引固定并且在所有可能的值上改变Fc中的索引来构造代码CN（F，uF）。 让我们将集合F称为冻结集合并将属于它的索引称为冻结索引。
III.极坐标源编码和解码
考虑N = 2 n i.i.d的序列。 从Ber（p）源生成的源符号。 如在信道编码中，极化源编码的两个主要成分是顺序编码和极化。 而不是直接编码，我们考虑编码序列
由于变换是可逆的，我们有
此外，我们有熵的链式法则
熵的极化将意味着当我们增加N时，（1）右边的项变为接近1或接近0的值。现在，如果我们以从0到N -1的顺序方式对进行编码， 不需要对其H（Ui | Ui-1 0）接近于0的ui进行编码，因为它们可以从给定的源模型估计。 存储H（Ui | Ui-1 0）接近1的ui。 与用于信道编码设置的极坐标编码的主要区别在于，编码器可以执行估计并且与实现ui进行比较。 当估计结果是错误时，可以采取适当的行动。 从（1）得出，其条件熵逼近1的比特的分数是h 2（p），其导致h 2（p）的压缩率。
令chi;表示源序列的实现。 现在，我们考虑执行以下步骤的编码器。 首先，
全文共6467字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144162]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
