Back to Search
Start Over
A Class of Optimal Structures for Node Computations in Message Passing Algorithms.
- Source :
-
IEEE Transactions on Information Theory . Jan2022, Vol. 68 Issue 1, p93-104. 12p. - Publication Year :
- 2022
-
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}, \ldots, x_{n})$ and $\mathbf {y} = (y_{1}, y_{2}, \ldots, 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, \ldots, 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 \geq \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$. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 68
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 154265885
- Full Text :
- https://doi.org/10.1109/TIT.2021.3119952