混合多核极化码的极化性

doi:10.16088/j.issn.1001-6600.2020082902

摘要/Abstract

摘要： Arikan于2009年提出的极化码是纠错编码理论领域的一大突破,也是近年来的研究热点,已广泛应用于5G通信等领域。本文主要研究作为极化码的推广的混合多核极化码的极化性。首先,利用随机切换信道概念,将以对称二元输入离散无记忆信道(BIDMC)为子信道构成的并行广播信道(PBC)的信道容量的一个重要下界推广到子信道中包含非对称BIDMC的情形;然后,放宽极化码构造中通用的信道组合与分裂策略(CAST)对基础信道对称性及等价性要求,并在基础信道是非对称BIDMC时,利用PBC信道容量的下界对CAST生成的各虚拟信道的最大对称容量进行估计;最后,通过分析混合多核极化码的编码矩阵与递归构造中使用的各CAST的关系,并利用CAST虚拟信道对称容量的估计,首次在基础信道为一般BIDMC的条件下,对混合多核极化码的极化性给出了严格证明。

关键词: 极化码, 对称容量, 逐次删除译码算法, 混合多核极化码, 组合与分裂策略

Abstract: The proposal of polar codes by Arikan in 2009 is a significant breakthrough in coding theory. It has been one of the hottest topics for researchers in the field of error-correcting codes in recent years, and has been widely applied in 5G communication systems, etc. This paper mainly deals with the polarization of hybrid multi-kernel polar codes which are generalizations of the conventional polar codes. Firstly, by introducing random switch channels, a lower bound for the symmetric capacities of parallel broadcast channels (PBCs) is generalized to the case that the constituent channels contain some asymmetric binary-input discrete memoryless channels (BIDMCs). Secondly, for the common tool of combining-and-splitting tactics (CAST) for the construction of polar codes, the restriction on symmetry and equivalence for the underlying channels are removed. Under the condition that the underlying channels are general BIDMCs, a lower bound for the largest symmetric capacity of the synthetic channels is generated by a CAST. Next, for any hybrid multi-kernel polar code, the exact relation between its coding matrix and the CASTs used in the iterative construction are determined. Finally, a rigorous proof for its polarization is demonstrated by using the lower bound on the symmetric capacity of synthetic channels generated by CASTs, when the underlying channel is a general BIDMC.

Key words: polar codes, symmetric capacity, successive cancellation decoding, hybrid multi-kernel polar code, combining and splitting tactics

中图分类号:

O236.2

宋睿, 徐铭, 唐元生. 混合多核极化码的极化性[J]. 广西师范大学学报（自然科学版）, 2021, 39(3): 69-82.

SONG Rui, XU Ming, TANG Yuansheng. The Polarization of Hybrid Multi-kernel Polar Codes[J]. Journal of Guangxi Normal University(Natural Science Edition), 2021, 39(3): 69-82.

参考文献

[1]ARlKAN 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.
[2]KORADA S B, ŞAŞOĞLU E, Urbanke R. Polar codes: Characterization of exponent, bounds, and constructions[J]. IEEE Transactions on Information Theory, 2010, 56(12): 6253-6264.
[3]MORI R. Properties and construction of polar codes[D]. Kyoto: Kyoto University, 2010.
[4]MORI R, TANAKA T. Channel polarization on q-ary discrete memoryless channels by arbitrary kernels[C]// Proceedings of 2010 IEEE International Symposium on Information Theory(ISIT). Piscataway NJ: IEEE Press, 2010: 894-898.
[5]ŞAŞOĞLU E. Polar coding theorems for discrete systems[D]. Lausanne, Switzerland: Swiss Federal Institute of Technology in Lausanne, 2011.
[6]TRIFONOV P. Efficient design and decoding of polar codes[J]. IEEE Transactions on Communications, 2012, 60(11): 3221-3227.
[7]TAL I, VARDY A. How to construct polar codes[J]. IEEE Transactions on Information Theory, 2013, 59(10): 6562-6582.
[8]MORI R, TANAKA T. Source and channel polarization over finite fields and Reed-Solomon matrices[J]. IEEE Transactions on Information Theory, 2014, 60(5): 2720-2736.
[9]LIN H P, LIN S, ABDEL-GHAFFAR K A S. Linear and nonlinear binary kernels of polar codes of small dimensions with maximum exponents[J]. IEEE Transactions on Information Theory, 2015, 61(10): 5253-5270.
[10]YE M, BARG A. Polar codes using dynamic kernels[C]// Proceedings of 2015 IEEE International Symposium on Information Theory(ISIT). Piscataway NJ: IEEE Press, 2015: 231-235.
[11]LEE M K, YANG K. The exponent of a polarizing matrix constructed from the Kronecker product[J]. Designs, Codes and Cryptography, 2014, 70(3): 313-322.
[12]GABRY F, BIOGLIO V, LAND I, et al. Multi-kernel construction of polar codes[C]// 2017 IEEE International Conference on Communications Workshops(ICC). Piscataway NJ: IEEE Press, 2017: 761-765.
[13]BIOGLIO V, GABRY F, LAND I, et al. Minimum-distance based construction of multi-kernel polar codes[C]// IEEE Global Communications Conference(GLOBECOM). Piscataway NJ: IEEE Press, 2017: 1-6.
[14]BENAMMAR M, BIOGLIO V, GABRY F, et al. Multi-kernel polar codes: Proof of polarization and error exponents[C]// 2017 IEEE Information Theory Workshop(ITW). Piscataway NJ: IEEE Press, 2017: 101-105.
[15]COPPOLINO G, CONDO C, MASERA G, et al. A multi-kernel multi-code polar decoder architecture[J]. IEEE Transactions on Circuits and Systems I: Regular Papers,2018, 65(12): 4413-4422.
[16]CHENG L, ZHOU W, ZHANG L. Hybrid multi-kernel construction of polar codes[C]// IEEE 89th Vehicular Technology Conference(VTC2019-Spring). Piscataway NJ: IEEE Press, 2019: 1-5.
[17]JAYRAM T S, ARlKAN E. A note on some inequalities used in channel polarization and polar coding[J]. IEEE Transactions on Information Theory, 2018, 64(8): 5767-5768.
[18]LIN J. Divergence measures based on the Shannon entropy[J]. IEEE Transactions on Information Theory, 1991, 37(1): 145-151.
[19]LAND I, HOEHER P A, HUBER J. Bounds on information combining for parity-check equations[C]// International Zurich Seminar on Communications. Piscataway NJ: IEEE Press, 2004: 68-71.
[20]LAND I, HUETTINGER S, HOEHER P A, et al. Bounds on information combining[J]. IEEE Transactions on Information Theory, 2005, 51(2): 612-619.
[21]SUTSKOVER I, SHAMAI S, ZIV J. Extremes of information combining[J]. IEEE Transactions on Information Theory, 2005, 51(4): 1313-1325.
[22]WYNER A D, ZIV J. A theorem on the entropy of certain binary sequences and applications: Part I[J]. IEEE Transactions on Information Theory,1973, 19(6): 772-777.
[23]CHUNG K L. A course in probability theory[M]. 2nd ed. New York: Academic Press, 1974.
[24]EL-KHAMY M, MAHDAVIFAR H, FEYGIN G, et al. Relaxed polar codes[J]. IEEE Transactions on Information Theory, 2017, 63(4): 1986-2000.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed