  A counter braid (CB) is a novel counter architecture introduced by Lu et al.
in 2007 for per-flow measurements on high-speed links which can be decoded with
low complexity using message passing (MP). CBs achieve an asymptotic
compression rate (under optimal decoding) that matches the entropy lower bound
of the flow size distribution. In this paper, we apply the concept of spatial
coupling to CBs to improve the performance of the original CBs and analyze the
performance of the resulting spatially-coupled CBs (SC-CBs). We introduce an
equivalent bipartite graph representation of CBs with identical
iteration-by-iteration finite-length and asymptotic performance. Based on this
equivalent representation, we then analyze the asymptotic performance of
single-layer CBs and SC-CBs under the MP decoding algorithm proposed by Lu et
al.. In particular, we derive the potential threshold of the uncoupled system
and show that it is equal to the area threshold. We also derive the Maxwell
decoder for CBs and prove that the potential threshold is an upper bound on the
Maxwell decoding threshold. We show that the area under the extended MP
extrinsic information transfer curve is equal to zero precisely at the area
threshold. This, combined with the analysis of the Maxwell decoder and
simulation results, leads us to the conjecture that the potential threshold is
equal to the Maxwell decoding threshold and hence a lower bound on the maximum
a posteriori decoding threshold. Interestingly, SC-CBs do not show the
well-known phenomenon of threshold saturation of the MP decoding threshold to
the potential threshold characteristic of spatially-coupled low-density
parity-check codes and other coupled systems. However, SC-CBs yield better MP
decoding thresholds than their uncoupled counterparts. Finally, we also
consider SC-CBs as a compressed sensing scheme and show that low undersampling
factors can be achieved.
