CS Paper Radar

Exact Joint MAP Decoding for Unknown Load and Message Counts in Orthogonal Unsourced Random Access

Mohammad Kazemi, Mert Ozates

cs.IT ·submitted 2026-10-14 15:53 UTC · v1

Abstract

We study joint recovery of the load (the number of active users) and message-count vector in type-based unsourced random access with very short messages. Each user's $k$-bit message activates one of $M=2^k$ orthogonal resources; coherent collisions therefore produce a noisy, unnormalized histogram of the transmitted messages. For arbitrary load and message priors, we propose an exact joint maximum-a-posteriori (MAP) decoder. Known-load allocation is separable and convex; our contribution is to show that the solutions for all candidate loads are nested prefixes of one greedy chain. Scoring these prefixes with the Bayesian posterior terms jointly estimates the load and message-count vector in $O(M+K_{\max}\log M)$ time. We compare the proposed joint MAP decoder with marginal MAP, three scalar-count two-stage receivers, oracle-load MAP, a sum-only receiver, and a soft-pilot receiver. For $K\sim\operatorname{Unif}\{0{:}60\}$ at 2 dB, the proposed decoder cuts the no-activity false-alarm probability from $25.9\%$ to $3.5\%$ relative to the Bayesian-count two-stage receiver and, conditioned on $K\ge1$, reduces normalized count error by $21.4\%$. The advantage concentrates under idle or sparse uncertain activity, whereas support-count processing approaches joint MAP when the possible loads are well separated. We also prove that the sum-only statistic is insufficient and quantify prior and amplitude mismatch. The model targets synchronized, power-controlled, very-short payloads rather than general URA.

Closest papers

Nearest neighbours by meaning across the whole index.

Deterministic Smoothed MAP Detection for High-Dimensional MIMO Systems

cs.IT eess.SP ·2026-09-21 ·Vitor Tucci Ramos, Stephane Senecal, Sheng Yang
similarity 0.59
Abstract · 12 pages

We propose a deterministic smoothed maximum a posteriori (SMAP) framework for high-dimensional multiple-input multiple-output (MIMO) detection. The discrete constellation prior is approximated by an i.i.d. Gaussian mixture, yielding a differentiable MAP objective that retains the constellation structure while enabling continuous optimization. Unlike sampling-based approaches, SMAP formulates detection as a deterministic optimization problem and can be initialized by the output of an arbitrary detector, allowing it to operate either as a standalone detector or as a refinement stage. For hard detection, we introduce SMAP-KR, which complements the continuous solution with a local $K_R$-neighbor search evaluated according to the original maximum-likelihood metric. Annealed continuation improves robustness for higher-order constellations, while a two-neighbor approximation reduces the cost of evaluating the mixture prior. We further develop a soft-output SMAP method in which a local Gaussian approximation based on the curvature of the smoothed posterior provides symbol probabilities and bit log-likelihood ratios without posterior sampling or explicit counterhypothesis lists. Numerical results for critically loaded MU-MIMO systems show that SMAP-KR provides an increasingly favorable performance-complexity tradeoff as the system dimension grows and can also effectively refine the output of existing detectors. For coded transmission, soft SMAP provides substantial block-error-rate gains over both LMMSE- and K-best-based soft detection.

0.30

Joint Channel Estimation, Detection, and Resource Allocation for OTFS-RSMA

eess.SP ·2026-09-21 ·Chaedam Son, Si-Hyeon Lee
similarity 0.58
Abstract · This work has been submitted to the IEEE for possible publication

Orthogonal time frequency space (OTFS) modulation is well suited for high-mobility communications, but channel estimation and efficient multi-user transmission remain challenging. In this paper, we develop an OTFS-rate splitting multiple access (RSMA) framework that jointly considers pilot transmission, channel estimation, message detection, and resource allocation under imperfect channel state information (CSI). We consider guard-based and superimposed transmission for the common and private messages to account for the tradeoff between channel-estimation reliability and spectral efficiency (SE). We derive a linear minimum mean square error (LMMSE) channel estimator, error-aware message-passing detectors, and tractable surrogate rate expressions that account for channel-estimation errors. Based on these expressions, we formulate a joint resource-allocation problem and develop an SCA-based two-dimensional search algorithm together with a low-complexity alternative that exploits the analytical structure of the resource allocation. Numerical results demonstrate reliable channel-estimation and BER performance and show that configurations with guard-based common-message transmission achieve favorable sum-SE performance, while the preferred private-message structure depends on the operating regime. The low-complexity algorithm achieves near-SCA performance with substantially reduced computation time, and OTFS-RSMA remains competitive with OTFS-NOMA while requiring only a single SIC stage.

0.16

Soft-Output GRAND-Aided Macrosymbol

cs.IT ·2026-09-27 ·Sarah Khalifeh, Alexander Mariona, Ken R. Duffy, Muriel Medard
similarity 0.57
Abstract

Guessing Random Additive Noise Decoding-Aided Macrosymbol (GRAND-AM) provides a coding-based solution for non-orthogonal multiple access (NOMA) systems, enabling joint multiuser detection and error correction. GRAND-AM outperforms prior methods in symbol error rates while providing hard-detection output. We introduce soft-output GRAND-AM (SOGRAND-AM), a macrosymbol-level joint multiuser detection and decoding framework which generates calibrated bitwise a posteriori error probabilities. SOGRAND-AM extends GRAND-AM by enabling soft-decision outer forward error correction decoders, transparently integrating with existing decoders. SOGRAND-AM achieves approximately 2 dB improvement in bit error rate at the output of the outer soft-input decoder compared to hard input with GRAND-AM.

0.27

The Gaussian Multiuser Channel Capacity Region

cs.IT ·2026-09-15 ·John M. Cioffi
similarity 0.56
Abstract · 20 pages, 4 figures. Revised Gaussian specialization of the original preprint. Invited submission to IEEE Transactions on Communications

This work characterizes a Gaussian multiuser-channel capacity-region using receiver-subset message atoms, Gaussian single-user equivalents, and successive decoding. A memoryless multiuser-channel model specifies both the channel conditional distribution and the independent-use input distribution. For all linear Gaussian channels, independent Gaussian user signaling and receiver-local worst-case-noise/MMSE-GDFE transformations provide a single-user-equivalent basis for the complete capacity-region construction. Each user distributes its input autocorrelation among a finite set of receiver-subset atoms, whose rate sums satisfy the applicable receiver constraints. Minimum-energy and weighted-rate-sum designs optimize these allocations, while fixed-allocation linear programs determine feasible atomic rates and synchronized time-shared successive-decoding implementations. The resulting framework includes Gaussian multiple-access, broadcast, and interference channels, with numerical examples illustrating their rate regions and receiver designs.

0.28

Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation

cs.IT cs.DScs.LG ·2026-10-17 ·Krishnakumar Balasubramanian, Siddharth Bhandari, Shiva Prasad Kasiviswanathan
theory similarity 0.56
Abstract · 66 pages

We study quantization for inner-product estimation when storage and reading have separate budgets. In the static bit-probe model [Yao, 1981], an encoder stores $w$ bits about $x$ before seeing a query $y$, and a reader probes at most $r<w$ bits to estimate $x^\top y$. Both vectors lie in the $d$-dimensional Euclidean unit ball. Protocols may be randomized, and computation is unrestricted. Performance is measured by $d$ times the worst-case mean-squared error over $x,y$, averaged over protocol randomness. First, we show that query-independent reading cannot benefit from extra storage. Any such reader is equivalent to fully reading an $r$-bit message, even when later reads depend on previously returned bits. At fixed positive rates $W=w/d$ and $R=r/d$, the normalized minimax error converges to $1/(4^R-1)$, independent of $W$. The upper bound was already known [Ordentlich and Polyanskiy, 2025]. We prove the matching lower bound for arbitrary scalar decoders, extending the result for unbiased compressors [Safaryan et al., 2020]. Then, we show that query-dependent reading makes extra storage useful. We construct a two-batch protocol using Gaussian projections and random thresholds, with asymptotic normalized error at most $(π+o(1))/[4R\log(W/R)]$ as $W/R\to\infty$. At fixed $R$, this error vanishes as storage grows, giving an unbounded advantage over query-independent reading. We also prove a finite-dimensional lower bound for arbitrary encoders, decoders, and fully branching readers. In the doubly sparse regime $W/R\to\infty$ and $R\log(W/R)\to0$, it gives normalized error at least $(1-o(1))/[2R\log(W/R)]$. Thus, our protocol is optimal within a factor of $π/2$ in the leading constant.

0.19

Secure Multi-Access Coded Caching: A Lifting Approach

cs.IT ·2026-10-04 ·Han Fang, Qinyi Lu, Nan Liu, Wei Kang
theory similarity 0.55
Abstract · 48 pages, 2 figures. This paper was presented in part at the 2024 IEEE Information Theory Workshop(ITW)

We construct secure cyclic multi-access coded caching schemes by re-encoding the caches of a secure single-access scheme and reusing its multicast message unchanged. For a library of $N$ files, each of $K$ users reads $L<K$ consecutive shared caches and must recover its requested file while learning no information about the other files. Starting from a parent scheme with a cyclic representation of its cached symbols, the transformation lets each access window recover the corresponding parent-cache symbols and, conditioned on them, learn nothing about the remaining symbols. A deterministic Pascal-window encoder handles symbols whose consecutive appearances span at least $L$ users. A randomized complement-dual encoder handles shorter spans. Over a suitable finite field, these encoders attain the exact minimum per-block storage for every input length in the block-separable, parent-preserving class. Applying the transformation to two secure single-access schemes gives an achievable memory-rate family for $N,K\ge2$ and $1\le L<K$, including the exact rate-one cache size $(N-1)(K-1)/L$. Using converse bounds for arbitrary secure multi-access schemes, we prove approximation guarantees for the achievable family and give a proof of the exact $L=K-1$ tradeoff.

0.34

When Majority-Vote Fails: Sequence Reconstruction under Fixed-Weight Substitutions

cs.IT ·2026-10-21 ·Vivian Papadopoulou, Yonatan Yehezkeally, V. Arvind Rameshwar, Antonia Wachter-Zeh
theory similarity 0.55
Abstract

We consider the problem of binary sequence reconstruction where a sequence is transmitted multiple times over a channel, and each undergoes substitution errors by an arbitrary error vector of Hamming weight exactly $t$. We determine $N_{\mathrm{wc}}$, the minimum number of distinct channel output observations guaranteeing unique reconstruction by an optimal decoder, and show that the bit-wise majority-vote decoder, which was proved by Levenshtein (2001) to be optimal for channels corrupting up to $t$ bits, is in fact suboptimal here. Despite this suboptimality, we prove a condition that admits a practical early-termination rule, necessary for every decoder at any number of outputs $N$, and sufficient for bit-wise majority-vote even below $N_{\mathrm{wc}}$. We evaluate the number of outputs at which this condition is triggered, numerically, and show that it frequently occurs below $N_{\mathrm{wc}}$ when the block-length $k>2t+1$. Finally, we propose an alternative algorithm aimed at guaranteeing unique reconstruction with fewer observations than bit-wise majority-vote, and demonstrate through exhaustive enumeration that it successfully decodes channel output-sets where bit-wise majority-vote fails.

0.11

MacKay-Neal Codes Achieve Capacity under MAP Decoding

cs.IT ·2026-10-07 ·Kenta Kasai
theory similarity 0.55
Abstract · 22 pages

Statistical-mechanical analyses predict that MacKay-Neal codes can achieve channel capacity at fixed degrees. We prove this prediction for the uncoupled $(\ell,3,3)$ MN socket ensemble for every fixed integer $\ell\ge4$. For each binary-input memoryless symmetric channel of capacity strictly greater than $3/\ell$, the ensemble-average block error probability under maximum a posteriori (MAP) decoding is $O(\log N/N)$, where $N$ is the transmitted blocklength. The actual transmitted rate converges to $3/\ell$. The result includes both punctured and transmitted variables and does not condition the sparse square matrix on invertibility. The proof establishes an entropy inequality for six bits subject to even parity by an analytic argument that reduces the domain by symmetry, restricts its interior stationary points, where both partial derivatives vanish, to the diagonal, and controls the resulting scalar functions by explicit polynomial bounds. Exact configuration counts then bound the conditional entropy on the binary symmetric channel. A standard comparison by mutual information extends the entropy bound to general symmetric channels; independent output erasures and a minimum-distance estimate for the transmitted code yield the bit and block error bounds.

0.42