CN115001510A - Code word construction method for accelerating Polar code to implement FSCL decoding - Google Patents
Code word construction method for accelerating Polar code to implement FSCL decoding Download PDFInfo
- Publication number
- CN115001510A CN115001510A CN202210535003.XA CN202210535003A CN115001510A CN 115001510 A CN115001510 A CN 115001510A CN 202210535003 A CN202210535003 A CN 202210535003A CN 115001510 A CN115001510 A CN 115001510A
- Authority
- CN
- China
- Prior art keywords
- node
- rep
- nodes
- spc
- bit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Signal Processing For Digital Recording And Reproducing (AREA)
- Error Detection And Correction (AREA)
Abstract
Description
技术领域technical field
本发明属于通信技术领域,具体是指一种能够加速Polar码实施FSCL译码的码字构造方法。The invention belongs to the technical field of communication, and specifically relates to a codeword construction method capable of accelerating the implementation of FSCL decoding of Polar codes.
背景技术Background technique
极化(Polar)码是2009年由E.提出的一种新型信道编码。Polar码基于信道极化(Channel Polarization)进行设计,用性能较好的子信道承载信息比特,性能较差的子信道承载冻结比特,在低复杂度的串行消去(SC)译码算法下,被证明可以达到信道容量。在实际解码过程中SC译码存在错误传播,在解码中短码字、高码率码字时,有严重的性能损失。Vardy等人引入了SC列表(SCL)解码(参考文献[1]I.Tal and A.Vardy,“List decodingof polar codes,”IEEE Trans.Inf.Theory,vol.61,no.5,pp.2213–2226,March 2015.),通过在SC译码过程的每个信息节点中保留候选信息列表来提高SC解码的纠错性能,然而,此外,基于SCL的译码器由于需要遍历完整的二叉树而具有较高的译码延迟。一些学者提出了快速SCL(FSCL)译码算法,通过将特殊组成的子码进行分类,在其父节点直接进行译码,从而减少了树遍历带来的解码延迟,FSCL算法目前已经广泛应用于各类Polar码译码器。FSCL译码算法中特殊节点包括四类,分别为R0节点(全冻结比特)、R1节点(全信息比特)、Rep节点(末位为信息比特,其余冻结比特)和SPC节点(首位为冻结比特,其余信息比特),不同节点对应不同的处理方式,具有不同的译码复杂度。其中推导证明了R1节点至少需要进行min(Nv,L-1)次分裂,SPC节点至少需要进行min(Nv-1,L-1)次分裂,能够相比于SCL译码,没有性能损失,其中Nv表示该节点的大小,L表示列表大小。Hashemi等人研究了针对R1节点和SPC节点进行了降低复杂度的研究(参考文献[2]Hashemi S A,Condo C,Gross W J.Fastand flexible successive-cancellation list decoders for polar codes[J].IEEETransactions on Signal Processing,2017,65(21):5756-5769.),结果表明,R1节点进行2次分裂的效果与进行min(Nv,L-1)次分裂效果相似,SPC节点则需要至少3次的分裂达到与min(Nv-1,L-1)次分裂相似的效果,这进一步降低了译码复杂度。Polar codes were introduced in 2009 by E. A new type of channel coding proposed. Polar codes are designed based on Channel Polarization. Subchannels with better performance are used to carry information bits, and subchannels with poor performance are used to carry frozen bits. Under the low-complexity Serial Elimination (SC) decoding algorithm, Proven to reach channel capacity. In the actual decoding process, there is error propagation in SC decoding, and there is a serious performance loss when decoding medium-short codewords and high-bit-rate codewords. SC List (SCL) decoding was introduced by Vardy et al. (Ref. [1] I. Tal and A. Vardy, "List decoding of polar codes," IEEE Trans.Inf.Theory, vol.61, no.5, pp.2213 –2226, March 2015.), to improve the error correction performance of SC decoding by keeping a list of candidate information in each information node of the SC decoding process, however, in addition, SCL-based decoders suffer from Has a higher decoding delay. Some scholars have proposed the fast SCL (FSCL) decoding algorithm, which can reduce the decoding delay caused by tree traversal by classifying specially composed subcodes and decoding them directly at their parent nodes. The FSCL algorithm has been widely used at present. Various Polar code decoders. There are four types of special nodes in the FSCL decoding algorithm, namely R0 node (full frozen bits), R1 node (full information bits), Rep node (the last bit is the information bit, the rest are frozen bits) and SPC node (the first bit is the frozen bit) , the rest of the information bits), different nodes correspond to different processing methods and have different decoding complexity. The derivation proves that the R1 node needs at least min(N v , L-1) splits, and the SPC node needs at least min(N v -1, L-1) splits, which can be compared to SCL decoding, without performance loss, where N v is the size of this node and L is the list size. Hashemi et al. studied the complexity reduction for R1 nodes and SPC nodes (References [2] Hashemi SA, Condo C, Gross W J. Fastand flexible successive-cancellation list decoders for polar codes [J]. IEEE Transactions on Signal Processing, 2017, 65(21): 5756-5769.), the results show that the effect of two splits on the R1 node is similar to that of min(N v , L-1) splits, while the SPC node needs at least three splits The split achieves a similar effect to min(N v -1, L-1) splits, which further reduces the decoding complexity.
相关专家和研究人员还提出了的一些改进的基于特殊节点FSCL的补充结构化方案,即在原有的四种特殊节点基础上引入了更多种类特殊节点,可以将原有的小节点合并为更大的节点,减少了总的节点数量。但是实际译码器中,过多类型的特殊节点数量引入了更大的硬件设计复杂度,不利于提升译码器面效。此外,虽然总的节点数量减少,但是每个节点的维度变大,节点内部译码涉及到排序操作,更大维度的节点需要更长时间的排序操作,在一些码字下不利于降低时延。Relevant experts and researchers have also proposed some improved supplementary structuring schemes based on special node FSCL, that is, more types of special nodes are introduced on the basis of the original four special nodes, and the original small nodes can be merged into more special nodes. Larger nodes reduce the total number of nodes. However, in an actual decoder, too many types of special nodes introduce greater hardware design complexity, which is not conducive to improving the surface efficiency of the decoder. In addition, although the total number of nodes is reduced, the dimension of each node becomes larger, and the internal decoding of nodes involves sorting operations. Nodes with larger dimensions require a longer sorting operation, which is not conducive to reducing latency under some codewords. .
在实际通信系统中,往往追求更高的面效比和吞吐量,四类特殊节点中,译码复杂度由低到高为:R0节点均为冻结比特无需分裂,复杂度最低;Rep节点只需分裂一次;R1节点通过2次分裂保证性能损失极小;SPC需要分裂3次保证性能,并需要满足奇偶校验关系,复杂度最高。因此希望基于FSCL的译码在划分特殊节点时,能够尽量划分出复杂度低的特殊节点。在进行FSCL译码过程中,需要提前通过子信道可靠性的序列得到信息比特图样,然后根据信息比特图样进行特殊节点划分,因此,子信道的可靠性序列影响特殊节点划分的结果,通过调整子信道的可靠性序列,在构造方式上进一步优化FSCL的节点划分方式,从而降低FSCL译码时延和复杂度,目前尚未有相关的构造算法的研究。In actual communication systems, higher surface-efficiency ratio and throughput are often pursued. Among the four types of special nodes, the decoding complexity is from low to high: R0 nodes are frozen bits without splitting, and the complexity is the lowest; Rep nodes only have the lowest complexity. It needs to be split once; the R1 node needs to split 2 times to ensure that the performance loss is minimal; SPC needs to be split 3 times to ensure performance, and needs to meet the parity relationship, which is the most complex. Therefore, it is hoped that the FSCL-based decoding can try to divide special nodes with low complexity when dividing special nodes. In the process of FSCL decoding, it is necessary to obtain the information bit pattern through the sub-channel reliability sequence in advance, and then divide the special node according to the information bit pattern. Therefore, the reliability sequence of the sub-channel affects the result of the special node division. By adjusting the sub-channel reliability sequence The reliability sequence of the channel further optimizes the node division method of the FSCL in the construction method, thereby reducing the delay and complexity of the FSCL decoding. There is no research on the relevant construction algorithm yet.
发明内容SUMMARY OF THE INVENTION
本发明提出一种能够加速Polar码实施FSCL译码的构造方法,通过在Polar码构造层面划分出更多低复杂度特殊节点,从而在进行FSCL译码过程中,降低译码复杂度,减少译码延迟。包括具体步骤如下:The present invention proposes a construction method that can accelerate the implementation of FSCL decoding of Polar codes. By dividing more low-complexity special nodes at the construction level of Polar codes, in the process of FSCL decoding, the complexity of decoding is reduced, and the code delay. The specific steps are as follows:
步骤1:对给定的(E,K)Polar码,采用缩短或打孔算法进行速率匹配。Step 1: For a given (E, K) Polar code, use a shortening or puncturing algorithm to perform rate matching.
其中,E表示Polar码码块有效长度,K表示Polar码信息位长度,用n表示译码阶段数量,n为正整数。当E为2的n次幂时,令N=E,N表示Polar码码块速率匹配后的长度,不进行速率匹配;当E不等于2的n次幂时,令n=ceil(log2E),N=2n,ceil(*)表示向上取整。当码率R=K/N≥9/16时,采用缩短算法,当码率R=K/N<9/16时,采用打孔算法。P=N-E表示打孔或缩短删掉的比特长度。Among them, E represents the effective length of the code block of the Polar code, K represents the length of the information bits of the Polar code, and n represents the number of decoding stages, where n is a positive integer. When E is the nth power of 2, let N=E, N represents the length of the Polar code block after rate matching, and no rate matching is performed; when E is not equal to the nth power of 2, let n=ceil(log 2 E), N=2 n , ceil(*) means round up. When the code rate R=K/N≥9/16, the shortening algorithm is used, and when the code rate R=K/N<9/16, the puncturing algorithm is used. P=NE means puncturing or shortening the deleted bit length.
步骤2:计算Polar码子信道可靠性,得到可靠性序列。Step 2: Calculate the reliability of the Polar code sub-channel to obtain a reliability sequence.
通过固定序列或高斯近似对Polar码进行子信道可靠性计算,得到长度为N的Polar码子信道可靠性序列,序列中元素指示了相应子信道的位置,元素按照可靠性由高到低排序。最后P个元素指示了打孔或缩短删掉的比特位置。The sub-channel reliability of the Polar code is calculated by a fixed sequence or Gaussian approximation, and the sub-channel reliability sequence of the Polar code with length N is obtained. The elements in the sequence indicate the position of the corresponding sub-channel, and the elements are sorted according to reliability. The last P elements indicate the bit positions for puncturing or shortening.
步骤3:根据可靠性序列计算信息比特图样。Step 3: Calculate the information bit pattern according to the reliability sequence.
信息比特图样用于指示Polar码译码,由“0”和“1”组成,长度为N,分别对应Polar信息端的每个比特,“1”代表信息比特,“0”代表冻结比特。选择可靠性序列中前K个元素所指示的比特位置用于承载信息比特,将信息比特图样中这K个元素所指示的比特位置置“1”,其余位置置“0”。The information bit pattern is used to indicate the decoding of the Polar code, consisting of "0" and "1", with a length of N, corresponding to each bit of the Polar information end, "1" represents the information bit, and "0" represents the frozen bit. The bit positions indicated by the first K elements in the reliability sequence are selected to carry information bits, and the bit positions indicated by the K elements in the information bit pattern are set to "1", and the remaining positions are set to "0".
步骤4:根据信息比特图样进行特殊节点划分,得到特殊节点划分图样。Step 4: Perform special node division according to the information bit pattern to obtain a special node division pattern.
对信息比特图样进行划分,形成特殊节点划分图样。特殊节点划分图样中的每个元素包括三部分,特殊节点起始位置S、特殊节点长度Nv和特殊节点类型T,起始位置S表示该节点在整个码块长度N中的位置,特殊节点长度Nv≥1,特殊节点类型T共有四种,T=0表示该节点为R0节点,T=1表示该节点为Rep节点,T=2表示该节点为R1节点,T=3表示该节点为SPC节点。The information bit pattern is divided to form a special node division pattern. Each element in the special node division pattern includes three parts, the special node starting position S, the special node length N v and the special node type T, the starting position S represents the position of the node in the entire code block length N, the special node The length N v ≥ 1, and there are four types of special node types T. T=0 indicates that the node is an R0 node, T=1 indicates that the node is a Rep node, T=2 indicates that the node is an R1 node, and T=3 indicates that the node is the SPC node.
所述的对比特图样进行划分方法为:共分为n个阶段循环进行划分,其中n=log2 N。节点划分长度Nv=2n,对与第(2k)×2n个比特,定义为左子节点的初始位置,第(2k+1)×2n个比特定义为右子节点初始位置,k为正整数,每个阶段的划分要记录每个节点的起始位置S、长度Nv、特殊节点类型。当节点长度Nv为1时,类型只能分为R0或R1节点。当节点长度Nv大于2时,分为6种情况:(1)左子节点为R0、右子节点为R1,并且满足当前节点长度Nv=2,节点归为Rep-SPC节点,Rep-SPC节点为一种临时划分类型,长度为2;(2)当左子节点为R1、右子节点为R1,当前节点归为R1节点;(3)左子节点为R0、右子节点为R0,当前节点归为R0节点;(4)左子节点为R0、右子节点为Rep或Rep-SPC,当前节点归为Rep节点;(5)左子节点为SPC或Rep-SPC、右子节点为R1,当前节点归为SPC节点;(6)以上均不符合,标识为None节点,表示不属于任何一类节点,None节点为一种临时划分类型。n个阶段循环划分后,得到n组节点划分类型,然后再回溯n个阶段的节点划分,如果该阶段存在None节点,则用其子节点对该None节点进行替换,直至没有None节点,停止回溯,得到最终的特殊节点划分图样。The described method for dividing the bit pattern is as follows: dividing into n stages and cyclically dividing, wherein n=log 2 N . The node division length Nv=2 n , and the (2k)×2 n bits are defined as the initial position of the left child node, the (2k+1)×2 n bits are defined as the initial position of the right child node, and k is A positive integer, the division of each stage should record the starting position S, length N v , and special node type of each node. When the node length Nv is 1, the type can only be divided into R0 or R1 nodes. When the node length Nv is greater than 2, it is divided into 6 cases: (1) The left child node is R0, the right child node is R1, and the current node length Nv=2, the node is classified as Rep-SPC node, Rep-SPC node is a temporary division type with a length of 2; (2) when the left child node is R1 and the right child node is R1, the current node is classified as R1 node; (3) the left child node is R0 and the right child node is R0, the current The node is classified as an R0 node; (4) the left child node is R0, the right child node is Rep or Rep-SPC, and the current node is classified as a Rep node; (5) The left child node is SPC or Rep-SPC, and the right child node is R1 , the current node is classified as an SPC node; (6) If none of the above is met, it is marked as a None node, indicating that it does not belong to any kind of node, and the None node is a temporary division type. After n stages of cyclic division, n groups of node division types are obtained, and then the node division of n stages is backtracked. If there is a None node in this stage, the None node is replaced with its child nodes until there is no None node, and the backtracking is stopped. , to get the final special node partition pattern.
步骤5:定位特殊节点中Rep节点与SPC节点位置。Step 5: Locate the positions of the Rep node and the SPC node in the special node.
根据特殊节点划分图样中元素标识的特殊类型,记录Rep节点与SPC节点的起始位置和节点长度,从而可以得到所有Rep节点与SPC节点中每个比特的具体位置,记录所有Rep节点的最后一个比特位置的集合QRep,记录所有SPC节点第一个比特位置集合QSPC;According to the special type of element identification in the special node division pattern, record the starting position and node length of the Rep node and the SPC node, so that the specific position of each bit in all Rep nodes and SPC nodes can be obtained, and record the last of all Rep nodes. A set of bit positions Q Rep , recording the first set of bit positions Q SPC of all SPC nodes;
步骤6:将Rep节点中信息比特位置与SPC节点中冻结比特位置交换。Step 6: Swap the information bit position in the Rep node with the frozen bit position in the SPC node.
Rep与R0节点的区别在于最后一位是否为信息比特,SPC与R1节点的区别在于是否第一位为冻结比特,因此将Rep最后一位信息比特与SPC第一位冻结比特位置互换,可以分别将Rep节点、SPC节点变换为R0节点、R1节点。在可靠性序列获取集合QRep以及集合QSPC每个比特的可靠性大小,比特位置对应的可靠性序列元素越靠前,代表该比特位置越可靠;将Rep节点集合QRep中m个最可靠的比特对应的可靠序列元素与SPC节点集合QRep中m个最不可靠的比特对应的可靠序列元素互换,得到新的可靠性序列,令mNv表示SPC节点数量与Rep节点数量的最小值,m可以根据实际需要灵活调整,m的调整范围为0~mNv,m=0退化为常规的FSCL构造,m=mNv将会在构造时消除其中的全部的SPC节点或Rep节点,m的个数一般取ceil(mNv/2)。最后按照步骤3方式形成新的信息比特图样。The difference between Rep and R0 nodes is whether the last bit is an information bit, and the difference between SPC and R1 nodes is whether the first bit is a frozen bit. Transform the Rep node and the SPC node into the R0 node and the R1 node respectively. Obtain the reliability size of each bit of the set Q Rep and the set Q SPC in the reliability sequence. The higher the reliability sequence element corresponding to the bit position is, the more reliable the bit position is; the m most reliable Rep node sets Q Rep The reliable sequence elements corresponding to the bits of the SPC nodes are exchanged with the reliable sequence elements corresponding to the m least reliable bits in the SPC node set Q Rep to obtain a new reliability sequence. Let mN v represent the minimum value of the number of SPC nodes and the number of Rep nodes , m can be flexibly adjusted according to actual needs, the adjustment range of m is 0~mN v , m=0 degenerates into a conventional FSCL structure, m=mN v will eliminate all SPC nodes or Rep nodes in it during construction, m The number of is generally taken as ceil (mN v /2). Finally, a new information bit pattern is formed according to the method of
步骤7:根据新的信息比特图样按照步骤4进行特殊节点划分,完成加速FSCL译码的码字构造。Step 7: According to the new information bit pattern, perform special node division according to
本发明所述的构造方法的优点与积极效果在于:本发明通过在码字构造阶段进一步优化了特殊节点的划分方式,在不增加任何译码器资源开销的情况下,提高了低复杂度特殊节点在整体中所占比例,降低了整体译码复杂度,减少译码时延。相比于其他降低FSCL译码器复杂度的方法,本发明在构造阶段进行优化,不在译码阶段增加额外开销,不需要对现有译码器进行大幅度修改,可以达到降低译码器时延的效果。The advantages and positive effects of the construction method of the present invention are: the present invention further optimizes the division mode of special nodes in the codeword construction stage, and improves the low-complexity special node without increasing any decoder resource overhead. The proportion of nodes in the whole reduces the overall decoding complexity and reduces the decoding delay. Compared with other methods for reducing the complexity of the FSCL decoder, the present invention optimizes in the construction stage, does not increase extra overhead in the decoding stage, does not need to significantly modify the existing decoder, and can reduce the time required for the decoder. delayed effect.
本发明所述的构造方法充分利用Polar码不同特殊节点之间的关系,有效降低了译码器译码复杂度和时延,适用于各类Polar码译码器,包括使用缩短算法进行速率匹配的(690,460)Polar码译码器。The construction method of the present invention makes full use of the relationship between different special nodes of the Polar code, effectively reduces the decoding complexity and time delay of the decoder, and is suitable for various Polar code decoders, including the use of shortening algorithms for rate matching. (690, 460) Polar code decoder.
附图说明Description of drawings
图1为本发明所述的码字构造的流程示意图;Fig. 1 is the schematic flow chart of the codeword structure of the present invention;
图2为本发明所述的特殊节点划分示意图;2 is a schematic diagram of the division of special nodes according to the present invention;
图3为本发明所述的特殊节点转换关系示意图;3 is a schematic diagram of a special node conversion relationship according to the present invention;
图4为本发明所述的SPC节点与Rep节点部分比特互换示意图;FIG. 4 is a schematic diagram of partial bit exchange between the SPC node and the Rep node according to the present invention;
具体实施方式Detailed ways
下面结合附图和实施示例对本发明进行详细说明。The present invention will be described in detail below with reference to the accompanying drawings and implementation examples.
步骤1:对给定的(E,K)Polar码,采用缩短或打孔算法进行速率匹配。Step 1: For a given (E, K) Polar code, use a shortening or puncturing algorithm to perform rate matching.
其中,E表示Polar码码块有效长度,K表示Polar码信息位长度,用n表示译码阶段数量,n为正整数。例如,当E=690,K=460,n=ceil(log2E)=10,N=2n=1024,R=K/N≥9/16,采用缩短算法,P=N-E=334表示缩短删掉的比特长度。Among them, E represents the effective length of the code block of the Polar code, K represents the length of the information bits of the Polar code, and n represents the number of decoding stages, where n is a positive integer. For example, when E=690, K=460, n=ceil(log 2 E)=10, N=2 n =1024, R=K/N≥9/16, the shortening algorithm is used, and P=NE=334 means shortening Length of bits to delete.
步骤2:计算Polar码子信道可靠性,得到可靠性序列。Step 2: Calculate the reliability of the Polar code sub-channel to obtain a reliability sequence.
通过固定序列或高斯近似对Polar码进行子信道可靠性计算,得到长度为N的Polar码子信道可靠性序列,序列中元素指示了相应子信道的位置,元素按照可靠性由高到低排序。最后P个元素指示了打孔或缩短删掉的比特位置。The sub-channel reliability of the Polar code is calculated by a fixed sequence or Gaussian approximation, and the sub-channel reliability sequence of the Polar code with length N is obtained. The elements in the sequence indicate the position of the corresponding sub-channel, and the elements are sorted according to reliability. The last P elements indicate the bit positions for puncturing or shortening.
例如,对于(690,460)的Polar码,通过固定序列或高斯近似算法得到长度为1024的可靠性序列,前面的690个元素,可靠性高的比特位置如689、688、687等排在前面,可靠性低的比特位置如0、1、2等排在后面,整个序列需要严格按照计算的比特可靠性大小由高到低排序,不同的计算方式可能得到不同的可靠性序列,满足可靠性大小由高到低排序即可。最后334个元素依次为690~1023,代表了缩短删掉的比特位置,For example, for the Polar code of (690,460), a reliability sequence with a length of 1024 is obtained by a fixed sequence or Gaussian approximation algorithm. The first 690 elements, the high reliability bit positions such as 689, 688, 687, etc. Bit positions with low reliability, such as 0, 1, 2, etc., are ranked at the back. The entire sequence needs to be sorted in strict accordance with the calculated bit reliability from high to low. Different calculation methods may obtain different reliability sequences. Sort from high to low. The last 334 elements are 690 to 1023 in order, which represent the bit positions that are shortened and deleted.
步骤3:根据可靠性序列计算信息比特图样。Step 3: Calculate the information bit pattern according to the reliability sequence.
信息比特图样用于指示Polar码译码,由“0”和“1”组成,长度为N,分别对应Polar信息端的每个比特,“1”代表信息比特,“0”代表冻结比特。选择可靠性序列中前K个元素所指示的比特位置用于承载信息比特,将信息比特图样中这K个元素所指示的比特位置置“1”,其余位置置“0”。The information bit pattern is used to indicate the decoding of the Polar code, consisting of "0" and "1", with a length of N, corresponding to each bit of the Polar information end, "1" represents the information bit, and "0" represents the frozen bit. The bit positions indicated by the first K elements in the reliability sequence are selected to carry information bits, and the bit positions indicated by the K elements in the information bit pattern are set to "1", and the remaining positions are set to "0".
例如,对于N=32,K=16的Polar码,若其可靠性序列为{31,30,29,27,23,15,28,26,25,22,21,14,19,13,11,24,7,20,18,12,17,10,9,6,5,3,16,8,4,2,1,0},信息比特图样中的第{31,30,29,27,23,15,28,26,25,22,21,14,19,13,11,24}位为“1”,其余位置为“0”,信息比特图样为{0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1}。For example, for a Polar code with N=32 and K=16, if its reliability sequence is {31, 30, 29, 27, 23, 15, 28, 26, 25, 22, 21, 14, 19, 13, 11 ,24,7,20,18,12,17,10,9,6,5,3,16,8,4,2,1,0}, {31,30,29,27th in the information bit pattern ,23,15,28,26,25,22,21,14,19,13,11,24} bits are "1", the rest are "0", and the information bit pattern is {0,0,0,0 ,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,1,0,1,1,1,1,1,1,1,1 ,1,1,1}.
步骤4:根据信息比特图样进行特殊节点划分,得到特殊节点划分图样。Step 4: Perform special node division according to the information bit pattern to obtain a special node division pattern.
对信息比特图样进行划分,形成特殊节点划分图样。特殊节点划分图样中的每个元素包括三部分,特殊节点起始位置S、特殊节点长度Nv和特殊节点类型T,起始位置S表示该节点在整个码块长度N中的位置,特殊节点长度Nv≥1,特殊节点类型T共有四种,T=0表示该节点为R0节点,T=1表示该节点为Rep节点,T=2表示该节点为R1节点,T=3表示该节点为SPC节点。The information bit pattern is divided to form a special node division pattern. Each element in the special node division pattern includes three parts, the special node starting position S, the special node length N v and the special node type T, the starting position S represents the position of the node in the entire code block length N, the special node The length N v ≥ 1, and there are four types of special node types T. T=0 indicates that the node is an R0 node, T=1 indicates that the node is a Rep node, T=2 indicates that the node is an R1 node, and T=3 indicates that the node is the SPC node.
所述的对比特图样进行划分方法为:共分为n个阶段循环进行划分,其中n=log2 N。节点划分长度Nv=2n,对与第(2k)×2n个比特,定义为左子节点的初始位置,第(2k+1)×2n个比特定义为右子节点初始位置,k为正整数,每个阶段的划分要记录每个节点的起始位置S、长度Nv、特殊节点类型。当节点长度Nv为1时,类型只能分为R0或R1节点。当节点长度Nv大于2时,分为6种情况:(1)左子节点为R0、右子节点为R1,并且满足当前节点长度Nv=2,节点归为Rep-SPC节点,Rep-SPC节点为一种临时划分类型,长度为2;(2)当左子节点为R1、右子节点为R1,当前节点归为R1节点;(3)左子节点为R0、右子节点为R0,当前节点归为R0节点;(4)左子节点为R0、右子节点为Rep或Rep-SPC,当前节点归为Rep节点;(5)左子节点为SPC或Rep-SPC、右子节点为R1,当前节点归为SPC节点;6)以上均不符合,标识为None节点,表示不属于任何一类节点,None节点为一种临时划分类型。n个阶段循环划分后,得到n组节点划分类型,然后再回溯n个阶段的节点划分,如果该阶段存在None节点,则用其子节点对该None节点进行替换,直至没有None节点,停止回溯,得到最终的特殊节点划分图样。The described method for dividing the bit pattern is as follows: dividing into n stages and cyclically dividing, wherein n=log 2 N . The node division length Nv=2 n , and the (2k)×2 n bits are defined as the initial position of the left child node, the (2k+1)×2 n bits are defined as the initial position of the right child node, and k is A positive integer. The division of each stage should record the starting position S, length N v , and special node type of each node. When the node length Nv is 1, the type can only be divided into R0 or R1 nodes. When the node length Nv is greater than 2, it is divided into 6 cases: (1) The left child node is R0, the right child node is R1, and the current node length Nv=2, the node is classified as Rep-SPC node, Rep-SPC node is a temporary division type with a length of 2; (2) when the left child node is R1 and the right child node is R1, the current node is classified as R1 node; (3) the left child node is R0 and the right child node is R0, the current The node is classified as an R0 node; (4) the left child node is R0, the right child node is Rep or Rep-SPC, and the current node is classified as a Rep node; (5) The left child node is SPC or Rep-SPC, and the right child node is R1 , the current node is classified as an SPC node; 6) If none of the above is met, it is marked as a None node, indicating that it does not belong to any kind of node, and the None node is a temporary division type. After n stages of cyclic division, n groups of node division types are obtained, and then the node division of n stages is backtracked. If there is a None node in this stage, the None node is replaced with its child nodes until there is no None node, and the backtracking is stopped. , to get the final special node partition pattern.
例如,如图2所示,对于步骤3中(32,16)的Polar码,信息比特图样为{0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1}。分为n=5个阶段循环进行划分,第0阶段,节点长度Nv为1,左子节点的初始位置为{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30},右子节点的初始位置为{1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31},节点类型依次为{R0,R0,R0,R0,R0,R0,R0,R0,R0,R0,R0,R1,R0,R1,R1,R1,R0,R0,R0,R1,R0,R1,R1,R1,R1,R1,R1,R1,R1,R1,R1,R1};第1阶段,节点长度Nv为2,左子节点的初始位置为{0,4,8,12,16,20,24,28},右子节点的初始位置为{2,6,10,14,18,22,26,30},节点类型依次为{R0,R0,R0,R0,R0,Rep-SPC,Rep-SPC,R1,R0,Rep-SPC,Rep-SPC,R1,R1,R1,R1,R1};第2阶段,节点长度Nv为4,左子节点的初始位置为{0,8,16,24},右子节点的初始位置为{4,12,20,28},节点类型依次为{R0,R0,Rep,SPC,Rep,SPC,R1,R1,R1,R1};第3阶段,节点长度Nv为8,左子节点的初始位置为{0,16},右子节点的初始位置为{8,24},节点类型依次为{R0,None,None,R1};第4阶段,节点长度Nv为16,左子节点的初始位置为{0},右子节点的初始位置为{16},节点类型依次为{None,None}。然后将每个阶段从高到低进行树搜索,当父节点为None时,到其子节点取相应的信息,第4阶段节点类型依次为{None,None},初始位置为{0,16},节点长度为{16,16};存在None,到第3阶段子节点搜索,节点类型更新为{R0,None,None,R1},初始位置为{0,8,16,24},节点长度为{8,8,8,8};存在None,到第2阶段子节点搜索,节点类型更新为{R0,Rep,SPC,Rep,SPC,R1},初始位置为{0,8,12,16,20,24},节点长度为{8,4,4,4,4,8};不存在None,更新结束,得到特殊节点节点划分图样。For example, as shown in Figure 2, for the Polar code of (32, 16) in
步骤5:定位特殊节点中Rep节点与SPC节点位置。Step 5: Locate the positions of the Rep node and the SPC node in the special node.
根据特殊节点划分图样中元素标识的特殊类型,记录Rep节点与SPC节点的起始位置和节点长度,从而可以得到所有Rep节点与SPC节点中每个比特的具体位置,记录所有Rep节点的最后一个比特位置的集合QRep,记录所有SPC节点第一个比特位置集合QSPC;According to the special type of element identification in the special node division pattern, record the starting position and node length of the Rep node and the SPC node, so that the specific position of each bit in all Rep nodes and SPC nodes can be obtained, and record the last of all Rep nodes. A set of bit positions Q Rep , recording the first set of bit positions Q SPC of all SPC nodes;
例如,步骤4中的节点类型更新为{R0,Rep,SPC,Rep,SPC,R1},初始位置为{0,8,12,16,20,24},节点长度为{8,4,4,4,4,8},QRep={8+(4-1),16+(4-1)}={11,19},QSPC={12+(4-1),20+(4-1)}={15,23}。For example, the node type in
步骤6:将Rep节点中信息比特位置与SPC节点中冻结比特位置交换。Step 6: Swap the information bit position in the Rep node with the frozen bit position in the SPC node.
Rep与R0节点的区别在于最后一位是否为信息比特,SPC与R1节点的区别在于是否第一位为冻结比特,因此将Rep最后一位信息比特与SPC第一位冻结比特位置互换,可以分别将Rep节点、SPC节点变换为R0节点、R1节点,如图3所示,展示了不同类型特殊节点的转换关系。在可靠性序列获取集合QRep以及集合QSPC每个比特的可靠性大小,比特位置对应的可靠性序列元素越靠前,代表该比特位置越可靠;将Rep节点集合QRep中m个最可靠的比特对应的可靠序列元素与SPC节点集合QRep中m个最不可靠的比特对应的可靠序列元素互换,得到新的可靠性序列,令mNv表示SPC节点数量与Rep节点数量的最小值,m可以根据实际需要灵活调整,m的调整范围为0~mNv,m=0退化为常规的FSCL构造,m=mNv将会在构造时消除其中的全部的SPC节点或Rep节点,m的个数一般取ceil(mNv/2)。最后按照步骤3方式形成新的信息比特图样。The difference between Rep and R0 nodes is whether the last bit is an information bit, and the difference between SPC and R1 nodes is whether the first bit is a frozen bit. Transform the Rep node and SPC node into R0 node and R1 node respectively, as shown in Figure 3, showing the transformation relationship of different types of special nodes. Obtain the reliability size of each bit of the set Q Rep and the set Q SPC in the reliability sequence. The higher the reliability sequence element corresponding to the bit position is, the more reliable the bit position is; the m most reliable Rep node sets Q Rep The reliable sequence elements corresponding to the bits of the SPC nodes are exchanged with the reliable sequence elements corresponding to the m least reliable bits in the SPC node set Q Rep to obtain a new reliability sequence. Let mN v represent the minimum value of the number of SPC nodes and the number of Rep nodes , m can be flexibly adjusted according to actual needs, the adjustment range of m is 0~mN v , m=0 degenerates into a conventional FSCL structure, m=mN v will eliminate all SPC nodes or Rep nodes in it during construction, m The number of is generally taken as ceil (mN v /2). Finally, a new information bit pattern is formed according to the method of
例如,对于步骤4中的QRep和QSPC,根据步骤3中的可靠性序列可知,QRep中可靠位置由高到低依次为{19,11},QSPC中可靠位置由高到低依次为{23,15},如图4所示,将Rep节点集合QRep中前2个最可靠的比特对应的可靠序列元素与SPC节点集合QRep中2个最不可靠的比特对应的可靠序列元素互换,即,将可靠性序列中{19,11}与{23,15}位置互换,形成新的可靠性序列{31,30,29,27,19,11,28,26,25,22,21,14,23,13,15,24,7,20,18,12,17,10,9,6,5,3,16,8,4,2,1,0},得到新的信息比特图样{0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1}。For example, for Q Rep and Q SPC in step 4, according to the reliability sequence in step 3, it can be known that the reliable positions in Q Rep are {19, 11} in order from high to low, and the reliable positions in Q SPC are in order from high to low. is {23,15}, as shown in Figure 4, the reliable sequence elements corresponding to the first two most reliable bits in the Rep node set Q Rep and the reliable sequence corresponding to the two least reliable bits in the SPC node set Q Rep Element swapping, that is, swap the positions of {19,11} and {23,15} in the reliability sequence to form a new reliability sequence {31,30,29,27,19,11,28,26,25 ,22,21,14,23,13,15,24,7,20,18,12,17,10,9,6,5,3,16,8,4,2,1,0}, get new The information bit pattern of {0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1 ,1,1,1,1,1,1,1,1,1}.
步骤7:根据新的信息比特图样按照步骤4进行特殊节点划分,完成加速FSCL译码的码字构造。Step 7: According to the new information bit pattern, perform special node division according to
例如,将步骤6中的新的信息比特图样{0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1},按照步骤4进行特殊节点划分,得到特殊节点类型为{R0,R0,R1,R0,R1,R1},初始位置为{0,8,12,16,20,24},节点长度为{8,4,4,4,4,8}。从而减少了SPC、Rep的节点数量,分别对应增加了R1节点和R0节点数量,更有助于减少FSCL译码复杂度和译码时延。For example, the new information bit pattern in step 6 is {0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0 ,0,1,1,1,1,1,1,1,1,1,1,1,1}, divide the special nodes according to
Claims (10)
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202210535003.XA CN115001510B (en) | 2022-05-17 | 2022-05-17 | A codeword construction method for accelerating FSCL decoding of Polar codes |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202210535003.XA CN115001510B (en) | 2022-05-17 | 2022-05-17 | A codeword construction method for accelerating FSCL decoding of Polar codes |
Publications (2)
Publication Number | Publication Date |
---|---|
CN115001510A true CN115001510A (en) | 2022-09-02 |
CN115001510B CN115001510B (en) | 2024-05-28 |
Family
ID=83027972
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN202210535003.XA Active CN115001510B (en) | 2022-05-17 | 2022-05-17 | A codeword construction method for accelerating FSCL decoding of Polar codes |
Country Status (1)
Country | Link |
---|---|
CN (1) | CN115001510B (en) |
Citations (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US5799311A (en) * | 1996-05-08 | 1998-08-25 | International Business Machines Corporation | Method and system for generating a decision-tree classifier independent of system memory size |
US6055539A (en) * | 1997-06-27 | 2000-04-25 | International Business Machines Corporation | Method to reduce I/O for hierarchical data partitioning methods |
CN107342843A (en) * | 2017-01-05 | 2017-11-10 | 华为技术有限公司 | Speed matching method, code device and communicator |
CN110061745A (en) * | 2017-06-16 | 2019-07-26 | 华为技术有限公司 | The method and device of rate-matched reconciliation rate-matched |
CN110690941A (en) * | 2017-04-28 | 2020-01-14 | 华为技术有限公司 | Polar code rate matching method and device |
CN113556134A (en) * | 2021-06-28 | 2021-10-26 | 杭州电子科技大学 | Polar code puncturing encoder and encoding method suitable for simplifying serial offset decoding |
-
2022
- 2022-05-17 CN CN202210535003.XA patent/CN115001510B/en active Active
Patent Citations (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US5799311A (en) * | 1996-05-08 | 1998-08-25 | International Business Machines Corporation | Method and system for generating a decision-tree classifier independent of system memory size |
US6055539A (en) * | 1997-06-27 | 2000-04-25 | International Business Machines Corporation | Method to reduce I/O for hierarchical data partitioning methods |
CN107342843A (en) * | 2017-01-05 | 2017-11-10 | 华为技术有限公司 | Speed matching method, code device and communicator |
CN110690941A (en) * | 2017-04-28 | 2020-01-14 | 华为技术有限公司 | Polar code rate matching method and device |
CN110061745A (en) * | 2017-06-16 | 2019-07-26 | 华为技术有限公司 | The method and device of rate-matched reconciliation rate-matched |
CN113556134A (en) * | 2021-06-28 | 2021-10-26 | 杭州电子科技大学 | Polar code puncturing encoder and encoding method suitable for simplifying serial offset decoding |
Non-Patent Citations (1)
Title |
---|
张蔚等: "使用区间路径处理XML查询", 信息技术, no. 06, 25 June 2011 (2011-06-25), pages 105 - 108 * |
Also Published As
Publication number | Publication date |
---|---|
CN115001510B (en) | 2024-05-28 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
CN109660264B (en) | High performance polar code decoding algorithm | |
CN106656212A (en) | Self-adaptive continuous erasure decoding method and architecture based on polarization code | |
CN108833052B (en) | Channel polarization decoding path metric value sorting method | |
CN114785357B (en) | A BPL decoding algorithm based on CRC-LDPC-Polar cascade system | |
CN116683919B (en) | OSD decoding method based on ordering TEPs of LDPC code | |
CN110661533B (en) | Method for optimizing decoding performance of decoder for storing polarization code | |
CN114598331B (en) | Polar code encoding method, encoding and decoding method and device | |
WO2021073338A1 (en) | Decoding method and decoder | |
CN110233628A (en) | The adaptive belief propagation list decoding method of polarization code | |
CN116760425A (en) | A CRC-assisted OSD decoding method for LDPC codes | |
CN109831216A (en) | Polarization code SBP decoder based on G-Matrix verification | |
CN113852443B (en) | Low-complexity multi-user detection method in SCMA system | |
CN115001510B (en) | A codeword construction method for accelerating FSCL decoding of Polar codes | |
CN112534724A (en) | Decoder and method for decoding polarization code and product code | |
JP7251615B2 (en) | ALIGNMENT PROCESSING DEVICE, ALIGNMENT PROCESSING METHOD, AND PROGRAM | |
CN115037315B (en) | A multi-level flexible adaptive SCL pruning method based on Polar codes | |
CN114598334A (en) | Segmented CRC (cyclic redundancy check) assisted convolutional polarization code coding and decoding scheme | |
CN113992211A (en) | Base station rapid decoding method based on polarization code SCL algorithm | |
CN111010196B (en) | Decoding method for BP List of polarization code | |
Zheng et al. | Locally constrained guessing codeword decoding of short block codes | |
Wang et al. | Improved reduced latency soft-cancellation algorithm for polar decoding | |
CN113285722A (en) | Multi-deviation segmented redundancy check auxiliary statistical decoding method for short polarization code | |
Timokhin et al. | Fast Polar Decoding With Successive Cancellation List Creeper Algorithm | |
CN113114274A (en) | Simplified polar code continuous elimination list decoder based on segmented key set | |
Simsek et al. | Hardware optimization for belief propagation polar code decoder with early stopping criteria using high-speed parallel-prefix ling adder |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
PB01 | Publication | ||
PB01 | Publication | ||
SE01 | Entry into force of request for substantive examination | ||
SE01 | Entry into force of request for substantive examination | ||
GR01 | Patent grant | ||
GR01 | Patent grant |