【《快速SC译码算法研究》6100字】

快速SC译码算法研究目录TOC\o"1-3"\h\u16446快速SC译码算法研究 [34]。Rate0码如果一个长为的极化码没有信息比特，只有冻结比特，则称为Rate0极化码。这种极化码由于不携带任何有效信息，在实际的通信系统中根本不会使用，但是却有可能作为一个子极化码出现，例如一个冻结比特就是一个长为1的Rate0极化码。将长为的极化码划分为多个子极化码后，可能某个子极化码只含有冻结比特。图3.3展示的是一个长为8的Rate0极化码，所有节点都是白色，代表所有的叶子节点都是冻结比特。长为的Rate0码译码如公式(3-2)所示，直接将所有码字译为0即可。 (3-2)Rate0极化码Rate1码如果一个长为的极化码没有冻结比特，只含有信息比特，也就是该极化码的码率为1，则称为Rate1码。图3.4展示的是个长为8的Rate1码，其中黑色节点表示所有的叶子节点都是信息比特。Rate1极化码假如长度为的Rate1码经过无记忆信道传输后，接收端的接收信号为。Rate1码的最大似然译码算法就是硬判决每一个接收信号，公式如(3-3)所示，可以得到硬判决序列。 (3-3)那么就是接收序列的最大似然译码结果。重复码若一个长为的极化码，信息比特存在于最后一个位置，前个位置都是冻结比特所在的位置，则称为Rep码，也称为重复码。图3.5展示的是一个长为8的Rep码，其中白色节点代表所有叶节点都是冻结比特，黑色节点代表所有叶节点都是信息比特，灰色节点代表其叶节点既包含冻结比特也包含信息比特。Rep极化码Rep码存在最大似然译码。若一个长为的Rep码经过无记忆信道传输，接收信号为，则其最大似然译码方法如下： (3-4)首先求出所有接收序列对数似然比的和S。如果S<0则译为全1序列，否则译码全0序列，Rep码只存在两种译码结果。单奇偶校验码如果一个长为的极化码只有第一个位置是信息比特，后个位置都是冻结比特，则称该极化码为单奇偶校验码，也称为SPC码。图3.6展示的是一个长为8的单奇偶校验码，节点颜色的含义与前文重复码节点颜色含义一致。SPC极化码定理3.1如果一个长为的极化码只有是冻结比特，其余都是信息比特，那么对于任意的该极化码的码字，所有码字的比特和为0。证明：对使用数学归纳法来证明。当时，信源为，经过极化码编码后为，显然无论取何值，码字的比特和为0。假设当时，只有是冻结比特，其余都是信息比特，并且所有码字的比特和为0。当时，信源序列可以写为，其中竖线表示把信源序列分为前一半和后一半，对于任意一个满足题设条件的码长为的码字x： (3-5)两个相同的部分模二和为0，剩下的根据归纳假设和也为0，因此对于满足题设条件的极化码，所有码字的比特和为0。证毕。对于单奇偶校验码的最大似然译码，首先还是硬判决每一个接收信号，得到硬判决序列： (3-6)如果，则译码结束，且是最大似然译码结果： (3-7)如果，则选取下标，将下标处的译码结果取反： (3-8)快速SC译码流程快速SC译码首先需要进行子极化码划分，也就是根据冻结比特的分布将长为的极化码划分为3.2节中描述的四种特殊的子极化码。译码主流程就是一个循环，遍历每一种特殊的子极化码，对每一种特殊的子极化码采用快速译码算法进行译码，一次译出一组码字。快速SC译码算法与标准SC译码算法流程一样，首先都需要进行对数似然比的运算，也就是填充矩阵。标准SC译码需要填充到所有列都有值时，才能译出一个码字。而快速SC译码算法填充到中间层时，如果发现是特殊的子极化码，就停止填充，直接估计多个码字。同理对于反向验证比特矩阵的填充过程，标准SC译码算法是每译出一个码字，都要计算一次，填充一次矩阵。而快速SC译码算法，每次译出多个码字，减少了一些标准SC译码算法中的矩阵的填充过程。下面对快速SC译码算法的两个主要流程：子极化码划分和译码主流程进行详细描述。子极化码划分子极化码划分流程如算法3-1所示，其中算法的输入为信道可靠性估计选出来的冻结比特索引位置组成的数组frozenbits，算法输出为划分出来的子极化码的信息矩阵nodearray。nodearray矩阵的行数是特殊子极化码的数量，列数为3。第一列表示特殊子极化码起始索引位置，第二列表示特殊子极化码的长度，第三列表示特殊子极化码对应的类型，用-1代表Rate0码，1代表Rate1码，2代表Rep码，3代表SPC码。可以很明显的观察到子极化码的划分方式不止一种，最极端的划分方式是每一个码元都当做一个子极化码，也就是只存在Rate0和Rate1两种子极化码，这种划分方式就与标准SC译码算法没有区别了。因此一个总的趋势是划分的子极化码长度越长，能够省略的中间计算过程就越多，对降低译码时延帮助就更大。因此本文采用递归方式，自顶向下进行子极化码的划分。子极化码划分流程图如图3.7所示。子极化码划分流程子极化码划分算法主体就是四个判断，每一个判断验证的是一个特殊的子极化码，如果该冻结比特数组不满足3.1节定义的四种特殊的子极化码，则将该冻结比特数组划分为两个长度减半的子数组，递归划分这两个特殊的子数组。当子码长度为2的时候，只存在Rate0，Rate1，Rep，SPC这四种特殊子码，因此不存在识别不了的子码。例如一个长为32的极化码，冻结位为16位，它的冻结比特数组frozenbits为[11111111111111001111100010000000]，其中1表示该位置的码元为冻结比特，0表示该位置的码元为信息比特。根据算法3-1生成出来的nodearray矩阵如公式(3-9)所示：算法3-1子极化码划分123456789101112131415161718input:frozenbitsoutput:nodearrayiffrozenbits[1:N-1]=1andfrozenbits[N]=0then识别出Rep码;elsetheniffrozenbits[1]=1andfrozenbits[2:N]=0then识别出SPC码;elsetheniffrozenbits[1:end]=0then识别出Rate1码;elsetheniffrozenbits[1:end]=1then识别出Rate0码;elsethen递归划分frozenbits[1:N/2];递归划分frozenbits[N/2+1:N];endendendend (3-9)该矩阵的含义为：从第1个码元开始是一个长度为8的Rate0码，从第9个码元开始是一个长为4的Rep码，，从第25个码元开始是一个长为8的Rate1码。图3.8展示的是该32位的极化码的树形结构，经过子码划分后结果为图3.9。其中白色节点表示冻结比特，黑色节点表示信息比特，灰色节点表示该节点既含有信息比特也含有冻结比特。N=32,K=16的极化码树形结构N=32,K=16的极化码子码划分快速SC译码流程快速SC译码算法如算法3-2所示。算法输入是接收信号的对数似然比数组LLR和子极化码划分算法计算出来的nodearray矩阵，输出是信息比特infobits。算法首先对一些中间变量进行初始化的工作，接下来就是循环遍历nodearray矩阵，矩阵的每一行都是一种特殊的子极化码。如果是第一次进入循环，就先用函数更新LLR中间变量，否则先执行函数再执行函数更新LLR。这里存在依赖关系，执行函数的时候需要依赖函数执行的结果。接着进入switch-case语句块，针对每一种特殊的子极化码采用不同的快速译码算法进行译码。每译出一个子极化码都需要进行部分和的更新，也就是更新反向验证比特。再译下一个子极化码时，会首先进行函数更新对数似然比的运算，需要使用到反向验证比特。与标准SC译码算法的对比前两个小节详细介绍了快速SC译码算法的子码划分与译码流程，下面以一个码长为8的极化码分别采用标准SC译码算法和快速SC译码算法进行译码，对比一下两种译码算法的区别。假设码长为8的极化码冻结比特分布为00010111，其中0代表该位置是冻结位，1代表该位是信息位。采用快速SC译码算法首先需要经过子码划分，通过调用子码划分程序可以将该极化码划分为码长为4的重复码和一个码长为4的单奇偶校验码，分别为前四个码元和后四个码元。下面以二叉树的形式来直观展示两种译码算法对数似然比更新的区别。图3.10和图3.11分别展示的是SC译码算法和快速SC译码的二叉树形式，译码过程可以抽算法3-2快速SC译码12345678910111213141516171819202122232425input:LLR,nodearrayoutput:infobits初始化中间变量;fori=0tolength(nodearray)doifi==0then用函数更新对数似然比中间变量;elsethen用函数更新对数似然比中间变量;用函数更新对数似然比中间变量;endswitch(nodearray[i])docaseRate0:do用Rate0快速译码;endcaseRate1:do用Rate1快速译码;endcaseSPC:do用SPC快速译码;endcaseRep:do用Rep快速译码;endend更新部分和end输出译码结果infobits;象为一个二叉树的遍历。其中遍历左节点，就是使用函数更新对数似然比；遍历右节点，就是使用函数更新对数似然比。图中的数字代表在第几个时钟周期进行计算。图3.10与表3.1的过程一一对应，经过3个时隙的对数似然比更新后，在第3个时隙将码字1译出来，但快速SC译码算法经过子码划分后，在第1个时隙可以译出前4个码字。这样的话，快速SC译码算法直接进入到标准译码过程的时隙8译第5个码字，没有经历标准SC译码算法的时隙4到时隙7的过程。同理在标准SC译码算法的第10个时隙，标准SC译码算法译第5个码字的时候，快速SC译码算法判断出这是一个单奇偶校验码，也可以在1个时隙内将最后的4个码字译出来，快速SC译码算法直接就结束了译码流程。使用二叉树的遍历来类比译码过程，可以直观看出快速SC译码算法减少了中间过程的计算步骤。在本例冻结比特的分布情况下，划分出来的这两种特殊的子极化码，如果每种特殊的子极化码都能在一个时隙译出的话，那么快速SC译码算法只使用了4个时隙，而标准SC译码过程使用了共14个时隙。在硬件实现上，时延的减少可以换来更大的译码吞吐率，因此快速SC译码算法在硬件实现上有更大的优势。当然随着码长增加，四种特殊的极化码都有发挥的空间。对于某个特定的码长N，时隙的减少与子极化码的划分相关。一个总的趋势是，划分的子极化码码长越长，能够减少的译码计算过程就越多，译码时延就越短。因此通过本文的子码划分程序，能都最大限度的减少译码时延。SC译码算法二叉树形式快速SC译码算法二叉树形式仿真结果与性能对比前面详细介绍了快速SC译码算法的译码流程，本节将使用Matlab软件仿真快速SC译码算法的各种性能，分析码长、码率对快速SC译码的性能影响。同时也对比分析标准SC译码算法、标准SCL译码算法和快速SC译码算法的之间的性能差距。FSC译码算法与标准SC译码算法对比为了分析极化码FSC与SC这两种译码算法之间的性能差距，采用码率为1/2，码长分别为64，256，1024的极化码，调制方式使用BPSK，信道选用AWGN信道，分别采用FSC和SC译码算法对接收信号进行译码。图3.12展示的是FSC译码算法与标准SC译码算法性能对比，3.12(a)展示的是误比特率的结果，3.12(b)展示的是误块率的结果。两种译码算法输入相同的数据，通过对比可以发现FSC与标准SC译码算法对比，并没有性能上的损失，两者性能基本一样。因为快速SC译码算法只是进行了一些中间剪枝操作，译码主流程基本一样，因此性能并没有损失。(a)BER (b)FERFSC与标准SC译码算法性能对比码长对极化码性能影响为了分析极化码在不同码长下的译码性能，采用码率为1/2，码长分别为64，128，256，512，1024，2048六种极化码，调制方式使用BPSK调制，信道选用AWGN信道，使用FSC译码算法进行译码。图3.13展示不同码长，极化码的译码性能。3.13(a)图是误比特率曲线，3.13(b)图是误块率曲线。Arikan的论文中指出，只有当码长趋近于无穷大的时候才能达到对称信道的信道容量，因此对于长码长的极化码，信道极化现象更明显，误码率也更低。从仿真结果可以看出，随着码长的增加，误比特率和误块率都减少，呈现一个负相关特性，与理论相符。(a)BER (b)FER极化码在不同码长下的译码性能码率对极化码性能影响码率对极化码性能有着重要影响，反映的是极化码携带有效信息的大小。为了研究码率对极化码性能影响，采用码长为512，码率分别为0.25，0.375，0.5，0.75的极化码，使用BPSK调制方式，信道使用AWGN信道，使用快速SC译码算法进行译码。仿真结果如图3.14所示，3.14(a)图是误比特率曲线，3.14(b)图是误块率曲线。随着码率增加，传输的有效信息增加，误比特率和误块率都会增加