Achievability Bounds on Unequal Error Protection Codes

Liuquan Yao, Shuai Yuan, Yuan Li, Huazi Zhang, Jun Wang, Guiying Yan, Zhi-Ming Ma

Abstract: Unequal error protection (UEP) codes can facilitate the transmission of messages with different protection levels. In this paper, we study the achievability bounds on UEP by the generalization of Gilbert-Varshamov (GV) bound. For the first time, we show that under certain conditions, UEP enhances the code rate comparing with time-sharing (TS) strategies asymptotically.

Introduction

In modern communication systems like 5G, there is an increasing need to transmit diverse data types with varying reliability requirements simultaneously. For example, Ultra-Reliable Low-Latency Communication (URLLC) requires extreme protection against errors, while Enhanced Mobile Broadband (eMBB) prioritizes high data rates.

The standard approach to this problem is Time-Sharing (TS), where transmission time is split and each data type is encoded separately. However, information theory suggests that joint encoding via Unequal Error Protection (UEP) could be more efficient. While UEP has been studied for decades, proving its strict superiority over time-sharing in terms of asymptotic code rate has remained a challenge. This paper addresses this gap by providing new mathematical bounds that prove UEP's superiority under specific conditions.

Methodology: Generalizing the Gilbert-Varshamov Bound

The authors build upon the Gilbert-Varshamov (GV) bound, a fundamental tool in coding theory used to prove the existence of codes with specific minimum distances. Their approach involves three levels of refinement:

  1. Generalized GV Bound: Extending the standard greedy selection strategy to multi-level protection requirements using a union bound to estimate codeword space.
  2. Intersection Bound: Accounting for the fact that "Hamming balls" (the space around a codeword where errors are corrected) often overlap. By calculating the volume of these intersections, the authors derive tighter, more efficient bounds.
  3. Enlargement Bound: For two-level protection, they introduce a "nesting" strategy that packs high-protection codewords into larger connected sets within the space, utilizing available signal space more effectively than spatial segmentation.
Geometric representation of overlapping Hamming balls used to calculate the Intersection Bound.

Key Theoretical Insights

  • UEP > Time-Sharing: The paper provides the first proof that UEP offers a "non-vanishing rate improvement" over time-sharing, meaning the efficiency gain persists even as messages become infinitely long.
  • The "Nesting" Advantage: Unlike TS, which segments the code space, UEP allows messages to share space. By strategically placing high-protection codewords, UEP can "fill the gaps" with low-protection codewords more densely than TS ever could, especially when protection requirements differ significantly ($d_B \ll d_A$).

Numerical Results and Validation

The authors validated their findings through numerical simulations for code lengths ranging from $n=32$ to $n=512$. For short codes, the UEP bounds were compared against optimal practical codes from Codetables.de, showing that the new bounds are remarkably tight and useful for real-world engineering.

Rate region comparison ($R_A$ vs $R_B$) for $n=512$, demonstrating that UEP achievability bounds strictly outperform time-sharing (TS) strategies.

As shown in the rate region analysis, the UEP achievability bounds consistently outperform the TS baseline. Furthermore, the Enlargement Bound demonstrates that code size can grow exponentially faster than simpler union-bound-based estimates as the block length increases.

Conclusion and Future Work

This research establishes a rigorous theoretical foundation for the superiority of UEP codes. While the current proofs focus on binary codes, the logic is extensible to $q$-ary alphabets. Future work will involve moving from achievability (proving existence) to construction—designing specific low-complexity algorithms, such as UEP-optimized Polar or LDPC codes, that can practically reach these theoretical limits.

Summary updated

Abstract

Unequal error protection (UEP) codes can facilitate the transmission of messages with different protection levels. In this paper, we study the achievability bounds on UEP by the generalization of Gilbert-Varshamov (GV) bound. For the first time, we show that under certain conditions, UEP enhances the code rate comparing with time-sharing (TS) strategies asymptotically.
BibTeX
@misc{yao2024achievability,
  author = {Liuquan Yao and Shuai Yuan and Yuan Li and Huazi Zhang and Jun Wang and Guiying Yan and Zhi-Ming Ma},
  title = {{Achievability Bounds on Unequal Error Protection Codes}},
  year = {2024},
  eprint = {2405.03288},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.03288},
}
Figure