1. Polar Codes with Higher-Order Memory
- Author
-
Hüseyin Afşer and Hakan Delic
- Subjects
Combinatorics ,Computer Networks and Communications ,0202 electrical engineering, electronic engineering, information engineering ,Polar ,020206 networking & telecommunications ,02 engineering and technology ,Upper and lower bounds ,Decoding methods ,Computer Science Applications ,Information Systems ,Mathematics - Abstract
We introduce a construction of a set of code sequences {Cn(m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {Cn(m)} is a generalization of polar codes presented by Arikan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n − 1) and N(n − m), and {Cn(m)} coincides with the original polar codes when m = 1. We show that {Cn(m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error Pe of {Cn(m)} and show that $${P_e} = O({2^{ - {N^\beta }}})$$ is achievable for β < 1/[1+m(ϕ − 1)], where ϕ ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρm − ρm − 1 − 1. The encoding and decoding complexities of {Cn(m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Arikan’s construction.
- Published
- 2018