Recursive descriptions of polar codes

Noam Presman; Simon Litsyn

doi:10.3934/amc.2017001

Article Contents

2017, Volume 11, Issue 1: 1-65. Doi: 10.3934/amc.2017001

This issue Previous Article Next Article New almost perfect, odd perfect, and perfect sequences from difference balanced functions with d-form property

Recursive descriptions of polar codes

Noam Presman and
Simon Litsyn

School of Electrical Engineering, Tel Aviv University, Ramat Aviv 69978 Israel

Received: January 31, 2015

Revised: May 31, 2016

Published: May 2017

Abstract Full Text(HTML) Figure(23) / Table(1) Related Papers Cited by

Abstract

Polar codes are recursive general concatenated codes. This property motivates a recursive formalization of the known decoding algorithms: Successive Cancellation, Successive Cancellation with Lists and Belief Propagation. Using such description allows an easy development of these algorithms for arbitrary polarizing kernels. Hardware architectures for these decoding algorithms are also described in a recursive way, both for Arıkan's standard polar codes and for arbitrary polarizing kernels.

Keywords:

Mathematics Subject Classification: Primary: 94B05, 94B60; Secondary: 94B35.

Citation:

Full Text(HTML)

Figure 1. A GCC representation of a polar code of length $\ell^n$ symbols constructed by a homogenous kernel according to Definition 1

Download: Full-size image PowerPoint slide

Figure 2. Example 1's GCC representation (Arıkan's construction)

Download: Full-size image PowerPoint slide

Figure 3. Representation of a polar code with kernel of $\ell = 2$ dimensions as a layered factor graph

Download: Full-size image PowerPoint slide

Figure 4. Representation of a polar code with kernel of $\ell = 2$ dimensions as a layered factor graph (detailed version of Figure 3-recursion unfolded)

Download: Full-size image PowerPoint slide

Figure 5. Normal factor graph representation of the $g(\cdot)$ block from Figures 3 and 4 for Arikan's $(u+v, v)$ construction

Download: Full-size image PowerPoint slide

Figure 6. A GCC representation of the length $N=4^n$ bits mixed-kernels polar code $g^{(n)}(\cdot)$ described in Example 3

Download: Full-size image PowerPoint slide

Figure 7. Decoding tree for $(u+v, v)$ polar code illustrating the decision space of the SC and SCL algorithms

Download: Full-size image PowerPoint slide

Figure 8. Representation of SC as a sequential walk on a decoding tree

Download: Full-size image PowerPoint slide

Figure 9. SCL ($L=4$) algorithm example of $(u+v, v)$ with $N=8$ bits (see Figure 7) illustrated on the right a decoding tree on the outer-codes of the structure ($\mathcal{C}_{0}, \mathcal{C}_{1}$). The left decoding tree expands each edge of the right tree into decoding-paths on the outer-codes of $\mathcal{C}_{0}$ and $\mathcal{C}_{1}$. The labels of the edges are the values of the outer-codes.

Download: Full-size image PowerPoint slide

Figure 10. Normal factor graphs representations of polar codes kernels

Download: Full-size image PowerPoint slide

Figure 11. Messages of BP algorithm

Download: Full-size image PowerPoint slide

Figure 12. Normal factor graph representation for the first kernel of Example 4. This kernel is constructed by gluing inputs $u_{1}, u_2$ of the mapping defined by the generating matrix $\bf G$

Download: Full-size image PowerPoint slide

Figure 13. $(u+v, v)$ polar code PE block

Download: Full-size image PowerPoint slide

Figure 14. Blocks of the $(u+v, v)$ polar code decoders of length $N$ bits

Download: Full-size image PowerPoint slide

Figure 15. Block diagram for the SC pipeline decoder

Download: Full-size image PowerPoint slide

Figure 16. Block diagram for the SC line decoder

Download: Full-size image PowerPoint slide

Figure 17. Block diagram for the limited parallelism line decoder

Download: Full-size image PowerPoint slide

Figure 18. BP line decoder components definitions

Download: Full-size image PowerPoint slide

Figure 19. Block diagram for the BP line decoder. Details of figure appear in Figures 20, 21 and 22 corresponding to sub-figures A, B and C respectively.

Download: Full-size image PowerPoint slide

Figure 20. Block diagram for the BP line decoder (Figure 19) -zoom-in: Sub-figure A

Download: Full-size image PowerPoint slide

Figure 21. Block diagram for the BP line decoder (Figure 19) -zoom-in: Sub-figure B

Download: Full-size image PowerPoint slide

Figure 22. Block diagram for the BP line decoder (Figure 19) -zoom-in: Sub-figure C

Download: Full-size image PowerPoint slide

Figure 23. Block definitions of SC line decoder for polar code of length $N$ based on a linear $\ell$ dimensions kernel with alphabet $F$

Download: Full-size image PowerPoint slide

Table 1. Routing tables for OP-MUX and OP-DEMUX in Figure 18

$c^{(opMux)}, c^{(opDeMux)}$	$c^{(BPPE)}$	$\mu^{(in)}_0$	$\mu^{(in)}_1$	$\mu^{(out)}$	Equation
$0$	$0$	$\mu^{(in)}_{x_1}$	$\mu^{(in)}_{u_1}$	$\mu_{e_1\rightarrow a_0}$	(45)
$1$	$1$	$\mu^{(in)}_{x_0}$	$\mu^{(in)}_{u_0}$	$\mu_{a_0 \rightarrow e_1}$	(46)
$2$	$1$	$\mu^{(in)}_{x_0}$	$\mu_{e_1\rightarrow a_0}$	$\mu_{u_0}^{(out)}$	(47)
$3$	$0$	$\mu^{(in)}_{x_1}$	$\mu_{a_0\rightarrow e_1}$	$\mu_{u_1}^{(out)}$	(48)
$4$	$1$	$\mu^{(in)}_{u_0}$	$\mu_{e_1\rightarrow a_0}$	$\mu_{x_0}^{(out)}$	(49)
$5$	$0$	$\mu^{(in)}_{u_1}$	$\mu_{a_0\rightarrow e_1}$	$\mu_{x_1}^{(out)}$	(50)
$6$	$0$ or $1$	$\mu^{(ext, in)}_0$	$\mu^{(ext, in)}_1$	$\mu^{(ext, out)}$	(80)

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	E. Arıkan, A performance comparison of polar codes and Reed-Muller codes, IEEE Commun. Lett., 12 (2008), 447-449.
[2]	E. Arıkan, Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels, IEEE Trans. Inf. Theory, 55 (2009), 3051-3073. doi: 10.1109/TIT.2009.2021379.
[3]	E. Arıkan, Systematic polar coding, IEEE Commun. Lett., 15 (2011), 860-862.
[4]	E. Arıkan and E. Telatar, On the rate of channel polarization, in 2009 IEEE Int. Symp. Inf. Theory (ISIT), 1493-1495.
[5]	A. Balatsoukas-Stimming, M. B. Parizi and A. Burg, LLR-based successive cancellation list decoding of polar codes, IEEE Trans. Signal Proc., 63 (2015), 5165-5179. doi: 10.1109/TSP.2015.2439211.
[6]	A. Balatsoukas-Stimming, M. B. Parizi and A. Burg, On metric sorting for successive cancellation list decoding of polar codes, in 2015 IEEE Int. Symp. Circ. Syst. (ISCAS), 1993-1996. doi: 10.1109/ISCAS.2015.7169066.
[7]	A. Balatsoukas-Stimming, A. J. Raymond, W. J. Gross and A. Burg, Hardware architecture for list successive cancellation decoding of polar codes, IEEE Trans. Circ. Syst. Ⅱ Express Briefs, 61 (2014), 609-613. doi: 10.1109/TCSII.2014.2327336.
[8]	G. Berhault, C. Leroux, C. Jego and D. Dallet, Partial sums computation in polar codes decoding, preprint, arXiv: 1310.1712 doi: 10.1109/ISCAS.2015.7168761.
[9]	E. Blokh and V. Zyabolov, Coding of generalized concatenated codes, Probl. Peredachi Inform., 10 (1974), 45-50.
[10]	G. Bonik, S. Goreinov and N. Zamarashkin, A variant of list plus CRC concatenated polar code, preprint, arXiv: 1207.4661
[11]	T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, The MIT Press, 2001.
[12]	I. Dumer, Concatenated codes and their multilevel generalizations, in Handbook of Coding Theory, Elsevier, The Netherlands, 1998.
[13]	I. Dumer, Soft-decision decoding of Reed-Muller codes: a simplified algorithm, IEEE Trans. Inf. Theory, 52 (2006), 954-963. doi: 10.1109/TIT.2005.864425.
[14]	I. Dumer and K. Shabunov, Soft-decision decoding of Reed-Muller codes: recursive lists, IEEE Trans. Inf. Theory, 52 (2006), 1260-1266. doi: 10.1109/TIT.2005.864443.
[15]	Y. Fan and C. Y. Tsui, An efficient partial-sum network architecture for semi-parallel polar codes decoder implementation, IEEE Trans. Signal Proc., 62 (2014), 3165-3179. doi: 10.1109/TSP.2014.2319773.
[16]	G. D. Forney, Concatenated Codes, MIT Press, Cambridge, 1966.
[17]	G. D. Forney, Codes on graphs: normal realizations, IEEE Trans. Inf. Theory, 47 (2001), 520-548. doi: 10.1109/18.910573.
[18]	N. Hussami, S. Korada and R. Urbanke, Performance of polar codes for channel and source coding, in 2009 IEEE Int. Symp. Inf. Theory (ISIT), 1488-1492. doi: 10.1109/ISIT.2009.5205860.
[19]	S. B. Korada, Polar Codes for Channel and Source Coding, Ph. D theis, EPFL, 2009.
[20]	S. B. Korada, E. Sasoglu and R. Urbanke, Polar codes: characterization of exponent, bounds, and constructions, IEEE Trans. Inf. Theory, 56 (2010), 6253-6264. doi: 10.1109/TIT.2010.2080990.
[21]	C. Leroux, I. Tal, A. Vardy and W. J. Gross, Hardware architectures for successive cancellation decoding of polar codes, preprint, arXiv: 1011.2919 doi: 10.1109/ICASSP.2011.5946819.
[22]	C. Leroux, A. Raymond, G. Sarkis, I. Tal, A. Vardy and W. Gross, Hardware implementation of successive-cancellation decoders for polar codes, J. Signal Proc. Syst., 69 (2012), 305-315. doi: 10.1007/s11265-012-0685-3.
[23]	C. Leroux, A. Raymond, G. Sarkis and W. Gross, A semi-parallel successive-cancellation decoder for polar codes, IEEE Trans. Signal Proc., 61 (2013), 289-299. doi: 10.1109/TSP.2012.2223693.
[24]	B. Li, H. Shen and D. Tse, An adaptive successive cancellation list decoder for polar codes with cyclic redundancy check, IEEE Commun. Lett., 16 (2012), 2044-2047. doi: 10.1109/LCOMM.2012.111612.121898.
[25]	J. Lin, C. Xiong and Z. Yan, A reduced latency list decoding algorithm for polar codes, in 2014 IEEE Workshop Signal Proc. Syst. (SiPS), 1-6. doi: 10.1109/SiPS.2014.6986062.
[26]	A. Mishra, A. Raymond, L. Amaru, G. Sarkis, C. Leroux, P. Meinerzhagen, A. Burg and W. Gross, A successive cancellation decoder ASIC for a 1024-bit polar code in 180nm CMOS, in 2012 IEEE Asian Solid State Circ. Conf. (A-SSCC), 205-208. doi: 10.1109/IPEC.2012.6522661.
[27]	R. Mori and T. Tanaka, Performance and construction of polar codes on symmetric binaryinput memoryless channels, in 2009 IEEE Int. Symp. Inf. Theory (ISIT), 1496-1500. doi: 10.1109/ISIT.2009.5205857.
[28]	R. Mori and T. Tanaka, Channel polarization on q-ary discrete memoryless channels by arbitrary kernels, in 2010 IEEE Int. Symp. Inf. Theory (ISIT), 894-898. doi: 10.1109/ISIT.2010.5513568.
[29]	R. Mori and T. Tanaka, Non-binary polar codes using Reed-Solomon codes and algebraic geometry codes, in 2010 IEEE Inf. Theory Workshop (ITW), 1-5. doi: 10.1109/CIG.2010.5592755.
[30]	A. Pamuk, An FPGA implementation architecture for decoding of polar codes, in 2011 Int. Symp. Wirel. Commun. Syst. (ISWCS), 437-441. doi: 10.1109/ISWCS.2011.6125398.
[31]	A. Pamuk and E. Arıkan, A two phase successive cancellation decoder architecture for polar codes, in 2013 IEEE Int. Symp. on Inf. Theory Proc. (ISIT), 957-961. doi: 10.1109/ISIT.2013.6620368.
[32]	Y. S. Park, Energy-Efficient Decoders of Near-Capacity Channel Codes, Ph. D thesis, Univ. Michigan, 2014.
[33]	Y. S. Park, Y. Tao, S. Sun and Z. Zhang, A 4. 68Gb/s belief propagation polar decoder with bit-splitting register file, in 2014 Symp. VLSI Circ. Digest Techn. Papers, 1-2.
[34]	N. Presman, O. Shapira and S. Litsyn, Binary polar code kernels from code decompositions, preprint, arXiv: 1101.0764 doi: 10.1109/TIT.2015.2409257.
[35]	N. Presman, O. Shapira and S. Litsyn, Polar codes with mixed-kernels, preprint, arXiv: 1107.0478 doi: 10.1109/ISIT.2011.6034223.
[36]	N. Presman, O. Shapira and S. Litsyn, Mixed-kernels constructions of polar codes, IEEE J. Selected Areas Commun., 34 (2016), 239-253. doi: 10.1109/JSAC.2015.2504278.
[37]	N. Presman, O. Shapira, S. Litsyn, T. Etzion and A. Vardy, Binary polarization kernels from code decompositions, IEEE Trans. Inf. Theory, 61 (2015), 2227-2239. doi: 10.1109/TIT.2015.2409257.
[38]	A. Raymond and W. Gross, A scalable successive-cancellation decoder for polar codes, IEEE Trans. Signal Proc., 62 (2014), 5339-5347. doi: 10.1109/TSP.2014.2347262.
[39]	G. Sarkis, P. Giard, A. Vardy, C. Thibeault and W. Gross, Fast polar decoders: algorithm and implementation, IEEE J. Sel. Areas Commun., 32 (2014), 946-957. doi: 10.1109/JSAC.2014.140514.
[40]	G. Sarkis, P. Giard, A. Vardy, C. Thibeault and W. Gross, Increasing the speed of polar list decoders, in 2014 IEEE Workshop Signal Proc. Syst. (SiPS), 1-6. doi: 10.1109/SiPS.2014.6986089.
[41]	E. Sharon, S. Litsyn and J. Goldberger, Efficient serial message-passing schedules for LDPC decoding, IEEE Trans. Inf. Theory, 53 (2007), 4076-4091. doi: 10.1109/TIT.2007.907507.
[42]	I. Tal and A. Vardy, List decoding of polar codes, in 2011 IEEE Int. Symp. Inf. Theory (ISIT), 1-5. doi: 10.1109/TIT.2015.2410251.
[43]	I. Tal and A. Vardy, List decoding of polar codes, IEEE Trans. Inf. Theory, 61 (2015), 2213-2226. doi: 10.1109/TIT.2015.2410251.
[44]	P. Trifonov, Efficient design and decoding of polar codes, IEEE Trans. Commun., 60 (2012), 3221-3227. doi: 10.1109/TCOMM.2012.081512.110872.
[45]	B. Yuan and K. Parhi, Architecture optimizations for BP polar decoders, in 2013 IEEE Int. Conf. Acoust. Speech Signal Proc. (ICASSP), 2654-2658. doi: 10.1109/ICASSP.2013.6638137.
[46]	B. Yuan and K. Parhi, Early stopping criteria for energy-efficient low-latency beliefpropagation polar code decoders, IEEE Trans. Signal Proc., 62 (2014), 6496-6506. doi: 10.1109/TSP.2014.2366712.
[47]	V. Zinoviev, Generalized concatenated codes, Probl. Peredachi Inform., 12 (1976), 5-15.