2016/02/12 by Christopher Blake, Blake, Christopher G., Frank R. Kschischang +1
Computer Science · #Coding theory and cryptography #Cooperative Communication and Network Coding #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1602.04034
openalex publication_date 2016/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is shown that all polar encoding schemes of rate R>(1)/(2) of block length N implemented according to the Thompson VLSI model must take energy E≥Ω(N3/2). This lower bound is achievable up to polylogarithmic factors using a mesh network topology defined by Thompson and the encoding algorithm defined by Arikan. A general class of circuits that compute successive cancellation decoding adapted from Arikan's butterfly network algorithm is defined. It is shown that such decoders implemented on a rectangle grid for codes of rate R>2/3 must take energy E≥Ω(N3/2), and this can also be reached up to polylogarithmic factors using a mesh network. Capacity approaching sequences of energy optimal polar encoders and decoders, as a function of reciprocal gap to capacity χ= (1-R/C)-1, have energy that scales as Ω(χ5.325)≤ E ≤ O(χ7.05log4(χ)).