Polar codes with a stepped boundary

We consider explicit polar constructions of blocklength $n\to \mathrm{\infty }$ for the two extreme cases of code rates $R\to 1$ and $R\to 0.$ For code rates $R\to 1,$ 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\to 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\to 0$ for the case of $p\to 1\mathrm{/}2.$