[发明专利]一种连续消除极化堆解码器

摘要

本发明公开了一种连续消除极化堆解码器，将每一条解码路径的可能性值、路径长度和路径信息存放在一个大根堆中，堆的初始化由极化码的第一个信息位所产生的两条初始路径建立，进行解码，直到最终解码路径通过CRC校验为解码成功，或者最终解码路径不通过CRC校验Q次或者堆中元素个数为0为解码失败。本发明用堆来存储不同长度的解码路径，而在堆中插入操作的复杂度只需要O(logD)，小于栈解码器的O(D)，因此在连续消除极化堆解码中，插入操作的时间复杂度降低，进一步带来解码时间复杂度的降低。

主权项

一种连续消除极化堆解码器，其特征在于，包括如下步骤：步骤1：由第一个信息位产生两条初始路径的可能性值、路径长度和路径信息存放入最初的大根堆里，尾指针为2；步骤2：取出堆的根节点，若根节点的路径长度Lroot等于K，则跳至步骤3；否则若根节点的路径长度Lroot小于Lmax，则进行步骤2.1，否则跳至步骤2.2；其中，K为极化码的信息位长度，Lroot为根节点的路径长度，Lmax为堆中至少出现Q次的路径的最大长度，Q为堆中同一长度路径出现的最大上限次数；步骤2.1：尾指针从堆的末尾寻找第一个满足路径长度大于等于Lmax的路径替换到根节点，并且尾指针移动到该位置的前一个位置，表示该节点之后的路径已经删除，若尾指针为0，则宣告解码失败并结束，否则跳回步骤2；步骤2.2：将堆的根节点添加一位‘0’或者‘1’之后扩展成两条新的路径，比较这两条路径的可能性值大小，将可能性值大的路径定义好路径，另一条定义为差路径；用好路径替换原根节点，并作堆的下调操作，若当前堆中节点未满，则进行步骤2.2.1，否则跳至步骤2.2.2；步骤2.2.1：将差路径插入到堆的末尾，并做堆的上调操作，再跳回步骤2；步骤2.2.2：随机选择堆的一个叶子节点，将其与差路径比较可能性值大小，将可能性大的那条保留在堆中，并作堆的上调操作，跳回步骤2；步骤3：对根节点进行CRC校验，通过校验即为解码成功；否则，将堆中最后一个元素替换根节点并做下调操作，尾指针减1；如果尾指针为0，那么解码失败；否则不通过次数加1，如果不通过次数等于Q，则解码失败，否则跳回步骤2。