Title: Polar codes with a stepped boundary,
Abstract: We consider explicit polar constructions of blocklength $n\rightarrow\infty$
for the two extreme cases of code rates $R\rightarrow1$ and $R\rightarrow0.$
For code rates $R\rightarrow1,$ we design codes with complexity order of $n\log
n$ in code construction, encoding, and decoding. These codes achieve the
vanishing output bit error rates on the binary symmetric channels with any
transition error probability $p\rightarrow 0$ and perform this task with a
substantially smaller redundancy $(1-R)n$ than do other known high-rate codes,
such as BCH codes or Reed-Muller (RM). We then extend our design to the
low-rate codes that achieve the vanishing output error rates with the same
complexity order of $n\log n$ and an asymptotically optimal code rate
$R\rightarrow0$ for the case of $p\rightarrow1/2.$