Fast-SSC-Flip Decoding Algorithm Based on Critical Flip Set for Polar Code
-
摘要: 为了降低极化码快速简化串行抵消翻转(Fast-SSC-Flip)译码算法的候选翻转比特集合大小，减小搜索复杂度，该文提出一种基于关键翻转集合的极化码Fast-SSC-Flip译码算法。基于快速简化串行抵消(Fast-SSC)译码过程中首位译码错误信息比特有极大的概率落于关键集合(CS)中，以及Fast-SSC-Flip译码算法的候选比特均为码字比特，所提算法利用极化码的生成矩阵得到与CS中信息比特相应的码字比特，并用这些码字比特构建关键翻转集合(CFS)作为候选翻转比特集合。实验结果表明，在使用相同候选比特可靠性度量准则的前提下，在码长$N = 1\;024$及码率$R = 0.5$时，该文所提基于关键翻转集合的Fast-SSC-Flip译码算法相较于传统Fast-SSC-Flip算法在不损失译码性能的情况下，候选翻转集合大小显著降低；相较于新的快速简化串行抵消翻转(N-Fast-SSC-Flip)算法有相近的译码性能，但候选翻转集合至少缩小了77.93%。
-
关键词:
- 极化码 /
- 快速简化串行抵消译码 /
- 比特翻转 /
- 关键翻转集合
Abstract: In order to reduce the candidate flip bit set size when using Fast Simplified Successive Cancellation Flip(Fast-SSC-Flip) decoding algorithm and decrease the search complexity, a kind of Fast-SSC-Flip decoding algorithm based on critical flip set for polar code is proposed. Based on the fact that the first decoding error information bit in the Fast Simplified Successive Cancellation (Fast-SSC) decoding process is highly likely to fall into the Critical Set (CS), and the candidate bits in the Fast-SSC-Flip decoding algorithm are all codeword bits, the proposed algorithm uses the polar code generator matrix to obtain the corresponding codeword bits of the information bits in the CS, and constructs a Critical Flip Set (CFS) as the candidate flip bit set. Experimental results show that, under the same candidate bit reliability measurement criteria, when the code length N = 1 024 and the code rate R = 0.5, the proposed Fast-SSC-Flip decoding algorithm based on critical flip set reduces significantly the candidate flip bit set size without sacrificing decoding performance compared to the traditional Fast-SSC-Flip algorithm; Compared to the New Fast Simplified Successive Cancellation Flip( N-Fast-SSC-Flip) algorithm, the candidate flip bit set decreased by at least 77.93% while maintaining similar decoding performance.-
Key words:
- Polar codes /
- Fast-SSC decode /
- Bit flip /
- Critical Flip Set(CFS)
-
算法1 关键集合CS构建 输入：信息比特索引集合${\boldsymbol{I}}$ 输出：关键集合CS (1) 根据集合${\boldsymbol{I}}$构建裁剪后的SSC译码树，并初始化CS为空集 (2) 将每个子块的首位比特放入到CS中 
下载: 导出CSV
表 1 ${\boldsymbol{N}} = {\boldsymbol{1\;024}}$, ${\boldsymbol{K}} = {\boldsymbol{512}}$, ${\boldsymbol{{T_{{\rm{sim}}}} = {10^6}}}$时CS的有效性验证
SNR (dB) 0.5 1.0 1.5 2.0 2.5 3.0 译码错误帧数 947 225 708 607 320 935 81 666 12 462 1 057 首错在CS中 942 203 707 058 320 717 81 652 12 462 1 057 准确性 0.994 7 0.997 8 0.999 3 0.999 8 1.0 1.0 CS的维度 107 110 111 116 124 129
下载: 导出CSV
算法2 CFS构造算法 输入：信息比特索引集合${\boldsymbol{I}}$，Fast-SSC译码树结构tree_struct，
码字决策LLR向量${\boldsymbol{\lambda}} _1^N$输出：关键翻转集合CFS (1) ${\text{CS}}$ $\leftarrow $ Construct Critical Set (${\boldsymbol{I}}$) (2) for $i = 1:|{\rm{CS}}|$ do (3) 根据tree_struct，找到CS($i$)相应的${\boldsymbol{\varOmega}}$ (4) 根据${\boldsymbol{\lambda}} _1^N$选择${\boldsymbol{\varOmega}}$中最不可靠的码字比特放入到CFS集合中 (5) end for
下载: 导出CSV
算法3 CFS-Fast-SSC-Flip译码算法 输入：信道接收序列$y$，信息比特索引集合${\boldsymbol{I}}$，最大可翻转次数
${T_{\max }}$输出：译码输出比特序列${\boldsymbol{u}}_1^N$ (1) $[\hat {\boldsymbol{u} }_1^N,{\boldsymbol{\lambda}} _1^N] \leftarrow$Fast-SSC$(y,{\boldsymbol{I}})$ (2) if 译码码字$\hat {\boldsymbol{u}}_1^N$未通过CRC校验，then (3) CFS$ \leftarrow $Construct CFS$(\lambda _1^N,{{{\rm{tree}}_{-}{\rm{struct}}} },{\boldsymbol{I} })$ (4) 根据度量准则对所有${x_i} \in {\text{CFS}}$进行升序排序 (5) for $i = {\text{1} }:{T_{{\rm{max}}} }$ do (6) $[\hat {\boldsymbol{u}}_1^N] \leftarrow$Fast-SSC-Flip$(y,{\boldsymbol{I}},{\text{CFS} }(i))$ (7) if 译码码字$\hat {\boldsymbol{u}}_1^N$通过CRC校验，then (8) return $\hat {\boldsymbol{u}}_1^N$ (9) end if (10) end for (11) end if (12) return $\hat {\boldsymbol{u}}_1^N$
下载: 导出CSV
表 2 各种译码算法的平均迭代次数
极化码参数 N = 512, R = 0.5 N = 1 024, R = 0.5 SNR (dB) 1.0 2.0 3.0 1.0 2.0 3.0 Fast-SSC-Flip 5.256 1.597 1.018 6.153 1.428 1.004 N-Fast-SSC-Flip 5.039 1.482 1.013 5.958 1.369 1.003 Fast-SSC-Flip-CS 6.118 5 1.625 1 1.095 9 6.263 7 1.887 3 1.013 8 CFS-Fast-SSC-Flip 5.041 1.486 1.013 5.963 1.370 1.003
下载: 导出CSV
表 3 CFS与传统Fast-SSC-Flip译码算法的候选翻转比特集合大小比较
极化码参数 N = 512, R = 0.5 N = 1 024, R = 0.5 SNR (dB) 1.0 2.0 3.0 1.0 2.0 3.0 CFS平均大小 52 58 62 87 96 113 传统翻转比特集合大小 256 512 缩小比例 (%) 79.69 77.34 75.78 83.01 81.25 77.93
下载: 导出CSV
-
[1] ARIKAN E. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE Transactions on Information Theory, 2009, 55(7): 3051–3073. doi: 10.1109/TIT.2009.2021379 [2] AFISIADIS O, BALATSOUKAS-STIMMING A, and BURG A. A low-complexity improved successive cancellation decoder for polar codes[C]. The 48th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, USA, 2014: 2116–2120. [3] CHANDESRIS L, SAVIN V, and DECLERCQ D. Dynamic-SCFlip decoding of polar codes[J]. IEEE Transactions on Communications, 2018, 66(6): 2333–2345. doi: 10.1109/TCOMM.2018.2793887 [4] ZHANG Xueting, LIU Yingzhuang, and CHEN Shaoping. BER evaluation based SCFlip algorithm for polar codes decoding[J]. IEEE Access, 2020, 8: 3042–3054. doi: 10.1109/ACCESS.2019.2962003 [5] QIAO Xinyuan, CUI Hangxuan, LIN Jun, et al. Reducing search complexity of dynamic SC-Flip decoding for polar codes[C]. The 7th International Conference on Computer and Communications (ICCC), Chengdu, China, 2021: 27–31. [6] ERCAN F and GROSS W J. Fast thresholded SC-flip decoding of polar codes[C]. 2020 IEEE International Conference on Communications, Dublin, Ireland, 2020: 1–7. [7] DAI Bin, GAO Chenyu, YAN Zhiyuan, et al. Parity check aided SC-flip decoding algorithms for polar codes[J]. IEEE Transactions on Vehicular Technology, 2021, 70(10): 10359–10368. doi: 10.1109/TVT.2021.3106349 [8] ALAMDAR-YAZDI A and KSCHISCHANG F R. A simplified successive-cancellation decoder for polar codes[J]. IEEE Communications Letters, 2011, 15(12): 1378–1380. doi: 10.1109/LCOMM.2011.101811.111480 [9] SARKIS G, GIARD P, VARDY A, et al. Fast polar decoders: Algorithm and implementation[J]. IEEE Journal on Selected Areas in Communications, 2014, 32(5): 946–957. doi: 10.1109/JSAC.2014.140514 [10] HANIF M and ARDAKANI M. Fast successive-cancellation decoding of polar codes: Identification and decoding of new nodes[J]. IEEE Communications Letters, 2017, 21(11): 2360–2363. doi: 10.1109/LCOMM.2017.2740305 [11] GIARD P and BURG A. Fast-SSC-flip decoding of polar codes[C]. IEEE Wireless Communications and Networking Conference Workshops (WCNCW), Barcelona, Spain, 2018: 73–77. [12] ZHOU Yangcan, LIN Jun, and WANG Zhongfeng. A new fast-SSC-flip decoding of polar codes[C]. IEEE International Conference on Communications (ICC), Shanghai, China, 2019: 1–6. [13] ZHOU Yangcan, LIN Jun, and WANG Zhongfeng. Improved fast-SSC-flip decoding of polar codes[J]. IEEE Communications Letters, 2019, 23(6): 950–953. doi: 10.1109/LCOMM.2019.2910059 [14] JAN Q, HUSSAIN S, LIU Zechen, et al. Improved partitioned fast-SSC-flip decoding for polar coded[C]. The 7th International Conference on Computer and Communication Systems (ICCCS), Wuhan, China, 2022: 382–386. [15] WANG Xiumin, WANG Ting, LI Jun, et al. Improved multiple bit-flipping fast-SSC decoding of polar codes[J]. IEEE Access, 2020, 8: 27851–27860. doi: 10.1109/ACCESS.2020.2964904 [16] JAN Q, HUSSAIN S, FURQAN M, et al. Parity-check-CRC concatenated polar codes SSCFlip decoder[J]. Electronics, 2022, 11(23): 3839. doi: 10.3390/electronics11233839 [17] GUO Rui, YANG Pei, YING Na, et al. Multiple node flip fast-SSC decoding algorithm for polar codes based on node reliability[J]. KSII Transactions on Internet and Information Systems, 2022, 16(2): 658–675. doi: 10.3837/TIIS.2022.02.015 [18] MONDELLI M, HASHEMI S A, CIOFFI J M, et al. Sublinear latency for simplified successive cancellation decoding of polar codes[J]. IEEE Transactions on Wireless Communications, 2021, 20(1): 18–27. doi: 10.1109/TWC.2020.3022922 -
下载:
图(6) / 表(6)
计量
- 文章访问数: 285
- HTML全文浏览量: 181
- PDF下载量: 29
- 被引次数: 0
