Computation-Limited Signals: A Channel Capacity Regime Constrained by Computational Complexity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916455405060096 |
|---|---|
| author | Queiroz, Saulo Vilela, João P. Monteiro, Edmundo |
| author_facet | Queiroz, Saulo Vilela, João P. Monteiro, Edmundo |
| contents | In this letter, we introduce the computational-limited (comp-limited) signals, a communication capacity regime in which the signal time computational complexity overhead is the key constraint -- rather than power or bandwidth -- to the overall communication capacity. We present the Spectro-Computational (SC) analysis, a novel mathematical framework that enhances classic concepts of information theory -- such as throughput, spectral efficiency and capacity -- to account for the signal processing computational complexity overhead. We consider a specific Shannon regime under which capacity is expected to get arbitrarily large as channel resources grow. Under that regime, we identify the conditions under which the time complexity overhead causes capacity to decrease rather than increasing, thereby creating the case for the comp-limited regime. We also provide examples of the SC analysis and show the OFDM waveform is comp-limited unless the lower-bound computational complexity of the $N$-point DFT problem verifies as $Ω(N)$, which remains an open challenge. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_05794 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Computation-Limited Signals: A Channel Capacity Regime Constrained by Computational Complexity Queiroz, Saulo Vilela, João P. Monteiro, Edmundo Information Theory Computational Complexity Signal Processing In this letter, we introduce the computational-limited (comp-limited) signals, a communication capacity regime in which the signal time computational complexity overhead is the key constraint -- rather than power or bandwidth -- to the overall communication capacity. We present the Spectro-Computational (SC) analysis, a novel mathematical framework that enhances classic concepts of information theory -- such as throughput, spectral efficiency and capacity -- to account for the signal processing computational complexity overhead. We consider a specific Shannon regime under which capacity is expected to get arbitrarily large as channel resources grow. Under that regime, we identify the conditions under which the time complexity overhead causes capacity to decrease rather than increasing, thereby creating the case for the comp-limited regime. We also provide examples of the SC analysis and show the OFDM waveform is comp-limited unless the lower-bound computational complexity of the $N$-point DFT problem verifies as $Ω(N)$, which remains an open challenge. |
| title | Computation-Limited Signals: A Channel Capacity Regime Constrained by Computational Complexity |
| topic | Information Theory Computational Complexity Signal Processing |
| url | https://arxiv.org/abs/2310.05794 |