Maximal Spectral Efficiency of OFDM with Index Modulation under Polynomial Space Complexity

Edmundo Monteiro; Jo\~ao P. Vilela; Saulo Queiroz; Wesley Silva

REVIEW 2 major objections 4 minor 10 references

Maximal Spectral Efficiency of OFDM with Index Modulation under Polynomial Space Complexity

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves all OFDM-IM waveforms can be mapped at OFDM speed using a Pascal-triangle table of quadratic size.

desk verdict The Pascal-triangle mapper is a sound, useful result that deserves peer review; the 'maximal spectral efficiency' framing is contestable and should be corrected. read the letter →

arxiv 1908.02860 v3 pith:YH3PKMTU submitted 2019-08-07 eess.SP cs.CC

Saulo Queiroz , Wesley Silva , João P. Vilela , Edmundo Monteiro This is my paper · ORCID

classification eess.SPcs.CC

keywords OFDMwithindexmodulationspectralefficiencyPascal'strianglecomputationalcomplexityselectorlook-uptablesubblockpartitioning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

OFDM with Index Modulation (OFDM-IM) sends extra data by selecting which k of N subcarriers are active, and the index selector that makes that choice has been viewed as the scheme's computational bottleneck. The paper claims the bottleneck is removable: the binomial coefficients needed by the selector are exactly the entries of Pascal's triangle, so a precomputed table of $\Theta(N^2)$ entries turns each $O(i)$ coefficient calculation into a single lookup. With that assist, the index selector runs in $O(N)$ time and the whole mapper runs at the same asymptotic speed as a plain OFDM mapper while enabling all $2^{p_1}$ waveforms. This would mean the maximal spectral-efficiency gain over OFDM can be obtained without subblock partitioning and without the exponential-size lookup table that the literature assumed was necessary.

What carries the argument

The load-bearing object is the Pascal-triangle table, an $N\times(N/2)$ matrix whose entry in row $c$ and column $i$ is the binomial coefficient $C(c,i)$, the number of ways to choose $i$ items from $c$. The combinatorial number system behind the index selector guarantees that decoding a $p_1$-bit input reduces to a greedy sequence of comparisons between the input remainder and such coefficients, and the table answers each comparison in $O(1)$ instead of $O(i)$ multiplications. This is what collapses the index-selector complexity from $O(N^2)$ to $O(N)$ while keeping the selected active-subcarrier set identical to the original algorithm's.

What would settle it

For $M=2$, evaluate $\text{gain}_N(k)=\lfloor\log_2 C(N,k)\rfloor-(N-k)$ over all $k$ for a large even $N$, say $N=1000$; if the maximizing $k$ is clearly not $N/2$, the 'ideal setup' premise behind the maximal-SE framing is wrong, and the comparison with OFDM would need to be re-based, even though the Pascal-triangle mapper's complexity results hold for every $k$.

Watch

Extended reading notes

Core claim

The paper's central claim, Theorem 1, is that all $2^{p_1}$ OFDM-IM waveforms can be mapped at the same asymptotic time as an OFDM mapper using polynomial space. Under the 'ideal setup' $M=2$ and $k=N/2$, $p_1=\lfloor\log_2 C(N,N/2)\rfloor$ approaches $N-\log_2\sqrt{N}$, so a conventional LUT needs $\Theta(2^N/\sqrt{N})$ entries, while the Pascal-triangle table stores only $\Theta(N^2)$ binomial coefficients. Replacing the $O(i)$ computation of each $C(c_i,i)$ in the greedy index selector with an $O(1)$ table lookup drops the index selector from $O(N^2)$ to $O(N)$ steps. The active-subcarrier sets produced are the same as the original mapper's, so the maximal spectral-efficiency gain is preserved while throughput scales rather than vanishing.

Load-bearing premise

The argument assumes, on the strength of a citation, that $M=2$ and $k=N/2$ is the configuration with the largest spectral-efficiency gain over OFDM, and the asymptotic claims are stated for that configuration.

Editorial extensions

If this is right

OFDM-IM can operate with all $N$ subcarriers in a single block, so subblock partitioning, which sacrifices spectral efficiency to reduce index-selector load, is no longer required.
The index selector ceases to be the most complex DSP block: mapper runtime is $O(N)$ and the throughput $m(N)/T(N)$ tends to a positive constant under the ideal setup.
The storage requirement drops from $\Theta(2^N/\sqrt{N})$ table entries to $\Theta(N^2)$, making the full-waveform mapper practical at substantially larger $N$.
The Pascal-triangle acceleration works for any activation ratio $k$, not only $k=N/2$, because every coefficient $C(c_i,i)$ lies in the table.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A direct comparison of the actual gain $\lfloor\log_2 C(N,k)\rfloor-(N-k)$ for $M=2$ suggests the maximum may occur near $k=2N/3$ rather than $N/2$; if so, the paper's 'maximal SE' label is inherited from the cited reference rather than re-derived, although the mapper itself would still work at the true optimal $k$.
The combinatorial-number-system lookup trick is general: any index-modulation or spatial-modulation system that maps bits to a $k$-subset by greedy binomial search can reuse the same Pascal-triangle table, so the speedup likely transfers beyond OFDM.
Because $C(c,i)=C(c,c-i)$ and the table is triangular, a hardware implementation could exploit symmetry to store roughly half the entries, extending the practical $N$ range while preserving the asymptotic $\Theta(N^2)$ bound.
The paper leaves open the question of whether the $\Theta(N^2)$ storage can be reduced to $O(N)$; if such a reduction exists, OFDM-IM would match OFDM's asymptotic space as well as its time.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things you should know. First, the algorithmic contribution is real: replacing the binomial-coefficient recomputation in the OFDM-IM index selector with a Pascal-triangle lookup gives O(N) time and Θ(N²) space for any k, which directly handles the long-standing 'LUT is exponential' objection in the OFDM-IM literature. As far as I can tell, that specific application is new. Second, the paper's headline claim about 'maximal spectral efficiency' does not match the paper's own bit accounting.

The complexity analysis is basically sound. With O(1) table lookups, each while-loop step is cheap, and the total number of while-loop attempts is bounded because `largestCandidate` only decreases across the outer loop. So the O(N) time conclusion holds, and the comparison with the Θ(2^N/√N) LUT is a fair way to show the space saving. The numerical case study is simple but honest, and the throughput separation follows from the complexity gap. The citation to the authors' earlier work for the O(N²) baseline is appropriate, not circular.

Soft spots, in order of severity. First, Lemma 4's proof is under-specified about the while-loop iteration count. It should explicitly argue that the total number of decrements is at most N-1+k, which makes the O(N) bound airtight. That is a minor fix, not a flaw in the result. Second, the premise that k=N/2 with M=2 maximizes the SE gain over OFDM is contestable. Using the paper's own bit counts, the gain for BPSK is floor(log2 C(N,k)) - (N-k). Stirling's approximation puts the large-N argmax near k=2N/3, not N/2. If reference [4] is maximizing a different objective (like the index-bit count p1 alone), the authors should say so explicitly. As written, the title and abstract rest on a premise the paper does not defend.

Who this is for: people working on OFDM-IM or index-modulation complexity. They will appreciate the Pascal-triangle trick and will also want the framing fixed. I would send this to a serious referee. With a corrected SE claim or a clear definition of 'gain', it is a solid letter publication; without that correction, the headline overstates.

Recommendation: engage with it, and ask the authors to tighten Lemma 4 and to either justify or drop the k=N/2 maximizing claim.

Referee Report

2 major / 4 minor

Summary. The paper studies the computational cost of the index selector (IxS) in OFDM with index modulation (OFDM-IM). The authors argue that under the setup M=2 and k=N/2 (called the ``ideal setup''), the original online IxS algorithm costs O(N^2) time, while a full 2^{p1}-entry lookup table would give O(N) time but Θ(2^N/√N) space. They propose replacing the online binomial-coefficient calculations with a Pascal-triangle table storing Θ(N^2) coefficients, and claim that this enables all 2^{p1} OFDM-IM waveforms in O(N) time with Θ(N^2) space. They also define a throughput scalability condition and show that the proposed mapper satisfies it.

Significance. The core algorithmic construction is clean, explicit, and parameter-free: if the missing loop-bound argument is supplied, the claimed O(N) time and Θ(N^2) space for the Pascal-triangle-assisted IxS is correct for any linear k, not just k=N/2. This is a valuable contribution because it removes the perceived need for subblock partitioning or exponential-size LUTs to enable all OFDM-IM waveforms, and it is independently verifiable from Algorithm 1 and Table I. However, the paper's identification of k=N/2 as the setup that maximizes the spectral-efficiency gain over OFDM is not derived and appears inconsistent with the paper's own bit-counting; this weakens the ``maximal spectral efficiency'' framing in the title and abstract, although it does not invalidate the mapper construction itself.

major comments (2)

[Section I and Lemma 1] The claim that M=2 and k=N/2 is the setup that maximizes the OFDM-IM spectral-efficiency gain over OFDM is not established and appears to be incorrect under the paper's own bit counts. With M=2, the OFDM-IM mapper sends m=⌊log2 C(N,k)⌋+k bits while OFDM sends N bits, so the gain is ⌊log2 C(N,k)⌋-(N-k). For large N, this behaves as N[H(α)-(1-α)] - 0.5 log2 N + O(1) with α=k/N, whose continuous maximum is at α=2/3, not α=1/2. Thus k=N/2 maximizes p1 (Lemma 1's title is correct) but not the SE gain over OFDM. Since the title, abstract, Lemma 1's proof, and Theorem 2 rely on the ``maximal SE gain'' premise, the authors must either derive the claim from a clearly stated metric or correct the framing. The Pascal-triangle mapper itself works for any k, so the algorithmic results can be maintained after the correction.
[Lemma 4 and Algorithm 1] The proof that the table-assisted IxS runs in O(N) time is under-specified. Replacing each binomial-coefficient calculation by an O(1) table lookup changes the per-evaluation cost, but Lemma 4 does not bound the number of while-loop iterations in Algorithm 1. The sentence ``the inner loop ... reduces from O(k)×O(i) to O(k)×O(1)'' assumes one lookup per i, whereas the while loop may decrement ci several times. The conclusion is nevertheless correct: the candidate value starts at N-1 and strictly decreases on each decrement, so the total number of while-loop body executions across all i is at most N-1, giving O(N) evaluations once table lookups are O(1). This telescoping argument should be stated explicitly; it is load-bearing for Theorem 1. The same argument is also needed to justify the O(N^2) bound for the original algorithm in Section II-A, since the count k(k+1)/2 there appears to count only one binomial evaluation per i.

minor comments (4)

[Lemma 4] The phrase ``computes O(N^2) distinct binomial coefficients'' is misleading: Algorithm 1 evaluates only O(N) coefficients per symbol, and the O(N^2) quantity is the number of entries in the Pascal-triangle table. Please rephrase to distinguish the table size from the number of queries.
[Table I] The table uses the convention C(n,i)=0 for n<i, as shown in the first rows. This convention should be stated explicitly in the text so that Algorithm 1's while loop termination is clear for small X.
[Footnote 2] The historical note on Pascal's triangle points to a Wikipedia URL; this is not appropriate for a published letter. Replace it with a standard reference on combinatorial number systems or Pascal's triangle.
[Section II-D, Definition 1] The sentence ``the throughput of the mapper is not scalable unless ineq. 1 does hold'' should read ``unless Inequality (1) holds''; the current wording is grammatically incomplete.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the Pascal-triangle mapper is an independent construction, and self-citations to [5] are non-load-bearing.

full rationale

The central claim (Theorem 1) is that assisting the IxS algorithm of Algorithm 1 with a Pascal-triangle table maps all 2^{p1} OFDM-IM waveforms in O(N) time with Θ(N^2) space. The proof chain is self-contained: Lemma 4 bounds the table by the Cartesian product of rows c_i ∈ {0,...,N−1} and columns i ∈ {1,...,N/2}, which is Θ(N^2) entries; with each binomial coefficient read in O(1), Algorithm 1's while-loop budget is bounded by N because the candidates c_i strictly decrease from N−1 to ≥0. The only inputs are the combinatorial number system stated in Section II-A and the definition p1 = floor(log2 C(N,k)). Lemma 1's asymptotic p1 ≈ N − log2(sqrt(N)) follows from the standard central-binomial-coefficient bound under k = N/2, so the citation to [5] there is superfluous rather than load-bearing. The O(N^2) baseline for the original IxS is also derived in Section II-A via k(k+1)/2 with k = N/2, so the self-citation to [5] for that baseline is not the source of the argument. The SCE metric in Definition 1 is a definition, not a fitted or predicted quantity; Theorem 2's limit calculation uses only Lemma 1 and Theorem 1. No parameter is fitted to any subset of data and no result is renamed from an input. The only caveat is the 'ideal setup' k = N/2 premise, which is imported from external reference [4]; whether or not that premise maximizes the paper's own SE-gain expression is a correctness/framing question, not circularity, and the mapper's complexity proofs hold for any k. Overall, the derivation does not reduce to its inputs, so the paper shows no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted. The central claim relies on standard combinatorial facts, the word-RAM model, and the contested premise that k=N/2 maximizes SE gain. No new entities are invented.

assumptions (4)

standard math Combinatorial number system: every X in [0, C(N,k)-1] has a unique representation X=Σ C(ci,i) with ck>...>c1≥0.
Invoked in Section II-A as the basis of the IxS algorithm; unproved background.
standard math The central binomial coefficient C(N,N/2) = Θ(2^N N^{-0.5}) as N→∞.
Used in Lemma 1 to derive p1 ≈ N - log2√N; standard Stirling approximation.
domain assumption The setup M=2, k=N/2 maximizes the spectral efficiency gain of OFDM-IM over OFDM.
Section I asserts this with citation [4]; the paper does not derive it, and it is contestable.
domain assumption Random-access memory allows O(1) retrieval after reading the index.
Lemma 2 and the PT query argument assume O(1) table lookup once the address is formed; standard in complexity analysis.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Maximal Spectral Efficiency of OFDM with Index Modulation under Polynomial Space Complexity." pith.science (2026). https://pith.science/paper/YH3PKMTU

@misc{pith2026190802860,
  author       = {Pith},
  title        = {Pith review of: Maximal Spectral Efficiency of OFDM with Index Modulation under Polynomial Space Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YH3PKMTU}},
  note         = {Machine review of arXiv:1908.02860}
}

read the original abstract

In this letter, we demonstrate a mapper that enables all waveforms of OFDM with Index Modulation (OFDM-IM) while preserving polynomial time and space computational complexities. Enabling all OFDM-IM waveforms maximizes the spectral efficiency (SE) gain over the classic OFDM but, as far as we know, the computational overhead of the resulting mapper remains conjectured as prohibitive across the OFDM-IM literature. We show that the largest number of binomial coefficient calculations performed by the original OFDM-IM mapper is polynomial on the number of subcarriers, even under the setup that maximizes the SE gain over OFDM. Also, such coefficients match the entries of the so-called Pascal's triangle (PT). Thus, by assisting the OFDM-IM mapper with a PT table, we show that the maximum SE gain over OFDM can be achieved under polynomial (rather than exponential) time and space complexities.

Figures

Figures reproduced from arXiv: 1908.02860 by the authors.

**Figure 2.** Proposed mapper vs. OFDM-IM index selector mapper under the maximal spectral efficiency: runtime (a), throughput (b) and number of table entries [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 9 canonical work pages

[4]

Generalization of orthogonal frequency division multiplexing with index modulation,

R. Fan, Y . J. Yu, and Y . L. Guan, “Generalization of orthogonal frequency division multiplexing with index modulation,” IEEE Trans. on Wireless Commun., vol. 14, no. 10, pp. 5350–5359, Oct. 2015

work page 2015
[1]

Novel index modulation techniques: A survey,

T. Mao, Q. Wang, Z. Wang, and S. Chen, “Novel index modulation techniques: A survey,” IEEE Commun. Surveys Tuts, vol. 21, no. 1, pp. 315–348, 1st Quart. 2018

work page 2018
[2]

Index modulation techniques for next-generation wireless networks,

E. Basar, M. Wen, R. Mesleh, M. D. Renzo, Y . Xiao, and H. Haas, “Index modulation techniques for next-generation wireless networks,” IEEE Access, vol. 5, pp. 16 693–16 746, Aug. 2017

work page 2017
[3]

Orthogonal frequency division multiplexing with index modulation,

E. Basar, U. Aygolu, E. Panayirci, and H. V . Poor, “Orthogonal frequency division multiplexing with index modulation,” IEEE Trans. Signal Process., vol. 61, no. 22, pp. 5536–5549, Nov. 2013

work page 2013
[5]

What is the cost of the index selector task for ofdm with index modulation?

S. Queiroz, J. Vilela, and E. Monteiro, “What is the cost of the index selector task for ofdm with index modulation?” in IFIP/IEEE Wireless Days (WD) 2019, Manchester, UK, Apr. 2019

work page 2019
[6]

Dual-mode index modulation aided OFDM,

T. Mao, Z. Wang, Q. Wang, S. Chen, and L. Hanzo, “Dual-mode index modulation aided OFDM,” IEEE Access, vol. 5, pp. 50–60, Aug. 2017

work page 2017
[7]

Multiple-mode orthogonal frequency division multiplexing with index modulation,

M. Wen, E. Basar, Q. Li, B. Zheng, and M. Zhang, “Multiple-mode orthogonal frequency division multiplexing with index modulation,” IEEE Trans. Commun., vol. 65, no. 9, pp. 3892–3906, Sep. 2017

work page 2017
[8]

Spectral efﬁciency enhancement based on sparsely indexed modulation for green radio communication,

M. Salah, O. A. Omer, and U. S. Mohammed, “Spectral efﬁciency enhancement based on sparsely indexed modulation for green radio communication,” IEEE Access, vol. 7, pp. 31 913–31 925, Mar. 2019

work page 2019

Show all 10 references

[9]

Equiprobable subcarrier activation method for OFDM with index modulation,

M. Wen, Y . Zhang, J. Li, E. Basar, and F. Chen, “Equiprobable subcarrier activation method for OFDM with index modulation,” IEEE Commun. Lett., vol. 20, no. 12, pp. 2386–2389, Dec. 2016

2016
[10]

A survey on spatial modulation in emerging wireless systems: research progresses and applications,

M. Wen, B. Zheng, K. J. Kim, M. Di Renzo, T. A. Tsiftsis, K. Chen, and N. Al-Dhahir, “A survey on spatial modulation in emerging wireless systems: research progresses and applications,” IEEE J. Sel. Areas Commun., vol. 37, no. 9, pp. 1949–1972, Sep. 2019. This is the author's ...

1949

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [4]

Generalization of orthogonal frequency division multiplexing with index modulation,

R. Fan, Y . J. Yu, and Y . L. Guan, “Generalization of orthogonal frequency division multiplexing with index modulation,” IEEE Trans. on Wireless Commun., vol. 14, no. 10, pp. 5350–5359, Oct. 2015

work page 2015

[2] [1]

Novel index modulation techniques: A survey,

T. Mao, Q. Wang, Z. Wang, and S. Chen, “Novel index modulation techniques: A survey,” IEEE Commun. Surveys Tuts, vol. 21, no. 1, pp. 315–348, 1st Quart. 2018

work page 2018

[3] [2]

Index modulation techniques for next-generation wireless networks,

E. Basar, M. Wen, R. Mesleh, M. D. Renzo, Y . Xiao, and H. Haas, “Index modulation techniques for next-generation wireless networks,” IEEE Access, vol. 5, pp. 16 693–16 746, Aug. 2017

work page 2017

[4] [3]

Orthogonal frequency division multiplexing with index modulation,

E. Basar, U. Aygolu, E. Panayirci, and H. V . Poor, “Orthogonal frequency division multiplexing with index modulation,” IEEE Trans. Signal Process., vol. 61, no. 22, pp. 5536–5549, Nov. 2013

work page 2013

[5] [5]

What is the cost of the index selector task for ofdm with index modulation?

S. Queiroz, J. Vilela, and E. Monteiro, “What is the cost of the index selector task for ofdm with index modulation?” in IFIP/IEEE Wireless Days (WD) 2019, Manchester, UK, Apr. 2019

work page 2019

[6] [6]

Dual-mode index modulation aided OFDM,

T. Mao, Z. Wang, Q. Wang, S. Chen, and L. Hanzo, “Dual-mode index modulation aided OFDM,” IEEE Access, vol. 5, pp. 50–60, Aug. 2017

work page 2017

[7] [7]

Multiple-mode orthogonal frequency division multiplexing with index modulation,

M. Wen, E. Basar, Q. Li, B. Zheng, and M. Zhang, “Multiple-mode orthogonal frequency division multiplexing with index modulation,” IEEE Trans. Commun., vol. 65, no. 9, pp. 3892–3906, Sep. 2017

work page 2017

[8] [8]

Spectral efﬁciency enhancement based on sparsely indexed modulation for green radio communication,

M. Salah, O. A. Omer, and U. S. Mohammed, “Spectral efﬁciency enhancement based on sparsely indexed modulation for green radio communication,” IEEE Access, vol. 7, pp. 31 913–31 925, Mar. 2019

work page 2019