⚡ electrical engineering

Low-Complexity Sparse Superimposed Coding for Ultra Reliable Low Latency Communications

This paper proposes a low-complexity sparse superimposed coding scheme for ultra-reliable low-latency communications that utilizes a sparse codebook structure and multipath matching pursuit decoding to achieve a favorable trade-off between block error rate performance and computational complexity.

Original authors: Yanfeng Zhang, Xi'an Fan, Xu Zhu, Jinkai Zheng, Hui Liang, Weiwei Yang, Tom H. Luan

Published 2026-01-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yanfeng Zhang, Xi'an Fan, Xu Zhu, Jinkai Zheng, Hui Liang, Weiwei Yang, Tom H. Luan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a very short, urgent text message (like "Stop!" or "Fire!") over a noisy walkie-talkie. In the world of high-speed internet, this is called Ultra-Reliable Low-Latency Communication (URLLC). The goal is to get the message there instantly and perfectly, without any delays or mistakes.

The problem is that traditional ways of sending these short messages are like trying to carry a heavy, dense suitcase full of packing peanuts just to send a single note. It takes too much energy to pack and unpack (encoding and decoding), which slows everything down.

This paper proposes a new, lighter way to send these messages using something called Sparse Superimposed Coding (SSC). Here is how it works, explained through simple analogies:

1. The Old Way: The Dense Suitcase

Think of the old method as a codebook where every single slot is filled with a number. To send a message, you have to mix your data with all these numbers.

The Problem: It's like trying to find a specific needle in a haystack where every piece of hay is actually a needle. To decode the message, the receiver has to do a massive amount of math to sort through everything. This takes too much time and computer power, which is bad for battery-powered devices like IoT sensors.

2. The New Idea: The Sparse Map

The authors suggest a "Sparse" approach. Imagine instead of a full suitcase, you have a map with only a few marked spots.

The Concept: You only use a tiny fraction of the available "slots" to carry your message. Most of the slots are empty (zero).
The Innovation: They designed a special "codebook" (the rulebook for how to mix the message) that is mostly empty. It's like a grid where 90% of the squares are blank, and only a few have numbers in them.

3. How It Works: The "Sparse" Spreading

When you send the message:

Mapping: You take your short message and decide which few spots on the grid to use (like placing stickers on a specific few pages of a book).
Spreading: You then "spread" your message across the airwaves using these few spots. Because the grid is mostly empty, the math required to mix the signal is much simpler.
The "Sparsity Factor": The authors introduce a knob called the Sparsity Factor (R).
- If you turn the knob to 1.0, the grid is full (the old, heavy way).
- If you turn it down to 0.5, half the grid is empty.
- If you turn it down to 0.25, three-quarters of the grid is empty.

4. The Result: Less Work, Same Message

The paper claims that by turning this knob down (making the codebook sparser), you drastically reduce the work the computer has to do.

The Analogy: Imagine you are looking for a friend in a crowded stadium.
- Old Way: You have to check every single seat in the stadium.
- New Way: You know your friend is only sitting in 10% of the stadium. You only check those specific sections. You find them just as fast, but you didn't have to walk through the empty seats.

5. What the Tests Showed

The authors ran simulations to see if this "lazy" (sparse) way would mess up the message.

The Trade-off: If you make the grid too empty (below a certain point), the message gets garbled, and errors happen.
The Sweet Spot: They found a "Goldilocks" zone (around a sparsity factor of 0.3 to 0.5). In this zone:
- The computer work is cut by about 50%.
- The message reliability stays almost exactly the same as the old, heavy method.
- It works well even if the message size changes slightly.

Summary

The paper presents a clever trick for sending short, urgent data: Stop packing the whole suitcase. Instead, use a sparse map with mostly empty spaces. This allows devices to send and receive messages much faster and with less battery drain, without losing the reliability needed for critical tasks like autonomous driving or industrial control.

Key Takeaway: By making the "rulebook" for sending data mostly empty, we can save massive amounts of computing power while still getting the message across perfectly.

Technical Summary: Low-Complexity Sparse Superimposed Coding for Ultra Reliable Low Latency Communications

Problem Statement
Ultra-reliable low-latency communication (URLLC) is a critical requirement for next-generation wireless networks, supporting time-critical applications such as autonomous vehicles and industrial IoT. However, traditional transmission strategies relying on lengthy data packets are ill-suited for URLLC due to the high latency and spectral inefficiency caused by extensive control signaling and error correction procedures. While Sparse Vector Coding (SVC) and its variants, such as Sparse Superimposed Coding (SSC), have emerged as promising solutions for short-packet transmission, they face significant computational challenges. Conventional SSC schemes typically employ dense codebook matrices (e.g., Gaussian or Bernoulli) to ensure high decoding accuracy. This approach leads to an exponential increase in codebook size with the number of transmitted bits, resulting in prohibitive encoding and decoding complexity as well as substantial storage overhead. This complexity is particularly detrimental in resource-constrained IoT scenarios, creating a need for schemes that reduce computational load without sacrificing reliability.

Methodology
The paper proposes a low-complexity SSC scheme designed specifically for short-packet URLLC scenarios. The core innovation lies in the design of a sparse codebook structure where each codeword contains only a small number of non-zero elements.

Encoding Process: The information bits are partitioned into two segments. The first segment ( $b_I$ bits) is encoded into the non-zero block index of a sparse vector via sparse mapping. The second segment ( $b_S$ bits) is mapped to the values of $K$ non-zero elements using QAM modulation.
Sparse Codebook Construction: Instead of using a dense spreading matrix, the authors introduce a sparse Bernoulli codebook matrix. This is achieved by constructing a sampling matrix $G$ where each column contains only $D$ non-zero elements (with $D \ll M$ ). The original dense codebook is sampled using this matrix to generate a sparse codebook $\bar{A}$ . A sparsity factor $R = D/M$ controls the proportion of non-zero elements.
Decoding Algorithm: The receiver employs the traditional Multipath Matching Pursuit (MMP) algorithm to recover the sparse vector. The key to the complexity reduction is exploiting the sparsity of the measurement matrix $\Phi$ (derived from the sparse codebook and channel). The authors demonstrate that operations such as Gram matrix calculation and residual updates, which are typically $O(NM)$ or $O(K^3 + MK^2)$ in dense systems, can be performed element-wise over the non-zero indices. This reduces the residual update complexity to $O(RNM)$ and the least squares estimation to $O(K^3 + RMK^2)$ .

Key Contributions

Sparse Codebook Design: The paper introduces a sparse Bernoulli codebook matrix that substantially reduces the encoding and decoding complexity of SSC schemes.
Complexity-Performance Trade-off: The proposed scheme utilizes a sparsity factor $R$ to control the trade-off between computational complexity and decoding performance. The analysis shows an approximate $R$ -fold reduction in decoding complexity.
Algorithmic Adaptation: The decoding process is adapted to leverage the sparse structure of the measurement matrix, significantly lowering the computational cost of the MMP algorithm compared to dense matrix implementations.

Simulation Results
Extensive simulations were conducted to evaluate the Block Error Rate (BLER) performance against Signal-to-Noise Ratio (SNR) under Rayleigh fading channels, comparing the proposed scheme with conventional SVC and dense SSC schemes.

Performance vs. Sparsity: The results indicate that the BLER performance degrades gradually as the sparsity factor $R$ decreases. However, for $R \leq 0.25$ , the degradation is minimal compared to the conventional dense SSC scheme. When $R$ drops below this threshold, performance deteriorates rapidly.
Optimal Trade-off: At $R = 0.5$ , the proposed scheme achieves a BLER performance very close to the conventional SSC scheme, with an SNR gap of only approximately 0.2 dB at a BLER of $10^{-5}$ . This configuration offers a substantial reduction in complexity (approximately 50%) with only marginal performance sacrifice.
Robustness: The proposed scheme demonstrates strong robustness across different transmission block lengths ( $M$ ). While performance gaps widen at very low $R$ values (e.g., 0.25) as block lengths decrease, the scheme with $R = 0.5$ maintains performance comparable to conventional schemes across varying block lengths.
Comparison with SVC: The proposed scheme outperforms the conventional SVC scheme when $R > 0.375$ , demonstrating superior reliability across a wide range of sparsity configurations.

Significance and Claims
The paper claims that the proposed low-complexity SSC scheme effectively addresses the computational bottleneck of existing SVC/SSC methods in URLLC scenarios. By introducing a sparse codebook structure, the authors achieve a favorable trade-off between BLER performance and computational complexity. The work suggests that the scheme is a promising candidate for resource-constrained IoT applications, offering strong robustness across different transmission block lengths while maintaining reliability comparable to dense codebook implementations. The authors conclude that the scheme successfully balances the competing demands of ultra-reliability and low-latency processing without incurring the excessive overhead associated with dense matrix operations.