Information theory meets circuit design: Why capacity-approaching codes require more chip area and power

摘要

It is generally thought that good codes, i.e. codes that operate at rates close to capacity and attain low error probabilities, are sophisticated constructions that require high encoding and decoding circuit power. In this paper, we rigorously show that this intuition is correct by deriving an information-theoretic lower bound on power consumption for encoding circuits using communication-complexity techniques. We first lower bound the “VLSI complexity” — measured as the product Awiresl2 where Awires is the wire-area and l is the number of clock cycles in implementation — for encoding. Using the lower bound on VLSI complexity, we derive a lower bound on power consumption of any fully-parallel encoding implementation for any code, and show that the consumed power must diverge to infinity as the error probability approaches zero. Further, the speed of this divergence increases as the rate approaches channel capacity. We also provide a refinement of an earlier result on VLSI complexity by El Gamal, Greene and Pang, which derives a lower bound on Achipl2, where Achip is the entire chip area required for encoding.