Counter braids: Asymptotic optimality of the message passing decoding algorithm

Yi Lu, Andrea Montanari, Balaji Prabhakar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 ℝ n + 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 1 minimization, while keeping the overall complexity linear in n.

Original languageEnglish (US)
Title of host publication46th Annual Allerton Conference on Communication, Control, and Computing
Pages209-216
Number of pages8
DOIs
StatePublished - Dec 1 2008
Externally publishedYes
Event46th Annual Allerton Conference on Communication, Control, and Computing - Monticello, IL, United States
Duration: Sep 24 2008Sep 26 2008

Publication series

Name46th Annual Allerton Conference on Communication, Control, and Computing

Other

Other46th Annual Allerton Conference on Communication, Control, and Computing
CountryUnited States
CityMonticello, IL
Period9/24/089/26/08

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software
  • Control and Systems Engineering
  • Communication

Fingerprint Dive into the research topics of 'Counter braids: Asymptotic optimality of the message passing decoding algorithm'. Together they form a unique fingerprint.

Cite this