Fundamental bounds on the interconnect complexity of decoder implementations

Modern codes are often designed to attain the minimum possible error probability under a blocklength constraint. For instance, sparse-graph codes are often designed aiming for large girth in order to reduce the error-probability. In this paper, we show that such an improved performance comes at a fundamental cost: longer interconnects (wires) in the decoding circuit. Recent empirical results show why shorter interconnects are important: decoders with short interconnects can have significantly smaller power consumption because significant power is burned in wires, and this power is proportional to the length of the wire. We derive two bounds to demonstrate this cost: the first bound shows that for a belief-propagation decoder for a linear sparse-graph code, the wire-length must increase exponentially in the girth of the code. While this bound depends on the code construction, our second bound is fundamental: we derive lower bounds on the wire-length for decoding any code (even if it is nonlinear) and any message-passing decoding algorithm given the performance and the number of clock-cycles at the decoder. Under simplifying assumptions, we discuss novel small-girth code constructions that provide upper-bounds on the required interconnect-length.