Counter braids: Asymptotic optimality of the message passing decoding algorithm

A novel counter architecture, called Counter Braids, has recently been proposed for per-flow counting on high-speed links. Counter Braids has a layered structure and compresses the flow sizes as it counts. It has been shown that with a Maximum Likelihood (ML) decoding algorithm, the number of bits needed to store the size of a flow matches the entropy lower bound. As ML decoding is too complex to implement, an efficient message passing decoding algorithm has been proposed for practical purposes. The layers of Counter Braids are decoded sequentially, from the most significant to the least significant bits. In each layer, the message passing decoder solves a sparse signal recovery problem. In this paper we analyze the threshold dimensionality reduction rate (d-rate) of the message passing algorithm, and prove that it is correctly predicted by density evolution. Given a signal in ℝ ⁿ ₊ with n∈ non-vanishing entries, we prove that one layer of Counter Braids can reduce its dimensionality by a factor 2.08 ∈log (1/∈) + O(∈). This essentially matches the rate for sparse signal recovery via L ₁ minimization, while keeping the overall complexity linear in n.