Back to Search
Start Over
Two Classes of Optimal Multi-Input Structures for Node Computations in Message Passing Algorithms
- Publication Year :
- 2024
-
Abstract
- In this paper, we delve into the computations performed at a node within a message-passing algorithm. We investigate low complexity/latency multi-input structures that can be adopted by the node for computing outgoing messages y = (y1, y2, . . . , yn) from incoming messages x = (x1, x2, . . . , xn), where each yj , j = 1, 2, . . . , n is computed via a multi-way tree with leaves x excluding xj . Specifically, we propose two classes of structures for different scenarios. For the scenario where complexity has a higher priority than latency, the star-tree-based structures are proposed. The complexity-optimal ones (as well as their lowest latency) of such structures are obtained, which have the near-lowest (and sometimes the lowest) complexity among all structures. For the scenario where latency has a higher priority than complexity, the isomorphic-directed-rooted-tree-based structures are proposed. The latency-optimal ones (as well as their lowest complexity) of such structures are obtained, which are proved to have the lowest latency among all structures.
- Subjects :
- Computer Science - Information Theory
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2407.08941
- Document Type :
- Working Paper