A Class of Optimal Structures for Node Computations in Message Passing Algorithms

Abstract

Consider the computations at a node in a message passing algorithm. Assume that the node has incoming and outgoing messages $\mathbf{x}=(x_1,x_2,\dots ,x_n)$ and $\mathbf{y}=(y_1,y_2,\dots ,y_n)$, respectively. In this paper, we investigate a class of structures that can be adopted by the node for computing $\mathbf{y}$ from $\mathbf{x}$, where each $y_j,j=1,2,\dots ,n$ is computed via a binary tree with leaves $\mathbf{x}$ excluding $x_j$. We make three main contributions regarding this class of structures. First, we prove that the minimum complexity of such a structure is $3n-6$, and if a structure has such complexity, its minimum latency is $\delta +\lceil \log (n-2^{\delta })\rceil$ with $\delta =\lfloor \log (n/2)\rfloor$, where the logarithm always takes base two. Second, we prove that the minimum latency of such a structure is $\lceil \log (n-1)\rceil$, and if a structure has such latency, its minimum complexity is $n\log (n-1)$ when $n-1$ is a power of two. Third, given $(n,\tau )$ with $\tau \ge \lceil \log (n-1)\rceil$, we propose a construction for a structure which we conjecture to have the minimum complexity among structures with latencies at most $\tau$. Our construction method runs in $O(n^3{\log }^2(n))$ time, and the obtained structure has complexity at most (generally much smaller than) $n\lceil \log (n)\rceil -2$.

Accepted for publication in IEEE Transactions on Information Theory

References in corpus (2)

• A 588 Gbps LDPC Decoder Based on Finite-Alphabet Message Passing
• Mutual Information-Maximizing Quantized Belief Propagation Decoding of Regular LDPC Codes