On the Optimum Cyclic Subcode Chains of (2, m)* for Increasing Message Length

Xiaogang Liu, Yuan Luo, Kenneth W. ShumarXiv 2013 · OpenReview

Abstract

The distance profiles of linear block codes can be employed to design variational coding schemes for encoding messages with variational lengths, achieving lower decoding error probabilities through large minimum Hamming distances. This paper investigates optimum distance profiles with respect to cyclic subcode chains (DPCs) of punctured second-order Reed-Muller codes $RM(2,m)^*$ for increasing message lengths. Two standards for optimality are studied based on the rhythm of message length increase.

Introduction

In modern communication systems such as CDMA and 3GPP, data transmission rates are rarely static. Users may send short bursts of control information or long streams of payload data. This variability necessitates "variational coding," where a system must dynamically adjust the code used for error correction. The primary challenge is maintaining high performance—specifically, a large minimum Hamming distance—while ensuring the code remains "cyclic" to allow for efficient hardware implementation via shift registers.

The Challenge of Variational Coding

As the dimension of a code (the number of information bits) increases, the minimum Hamming distance typically decreases. For engineers, the goal is to find a sequence, or "chain," of nested subcodes where this degradation is minimized. While previous research has explored general linear codes, finding optimal chains that preserve the cyclic property is a significantly more complex combinatorial task.

Methodology: Algebraic Foundations

The researchers focused on the punctured second-order Reed-Muller code, $RM(2, m)^*$. To identify the optimal chains, they defined Distance Profiles (DP) and established two standards for comparison:

  • Standard I: Compares codes with the same dimension profile.
  • Standard II: A global comparison across all possible cyclic subcode chains.

To calculate minimum distances without exhaustive searching, the authors utilized sophisticated algebraic tools, including primitive idempotents and quadratic forms. These tools allow for the precise determination of weight distributions.

Weight distribution of the subcodes used to determine minimum Hamming distances.

By analyzing these weight distributions, the authors could mathematically prove the minimum distance of each subcode in a chain.

Weight distribution for complex cyclic subcode chains under Standard II.

Key Insights and Results

The study's most significant contribution is the derivation of the exact Optimum Distance Profile under Standard II (ODPC-II) for $RM(2, m)^*$ when $m$ is even. This provides a definitive "best-case" sequence for engineers to follow.

Theorem Highlights

  • Theorems 1 & 2: Establish optimum distance profiles for odd and even $m$ when starting from a specific subcode (the first-order Reed-Muller code).
  • Theorem 3: Identifies the global optimum cyclic subcode chain for $RM(2, m)^*$ when $m$ is even, providing a definitive blueprint for optimal code expansion.

For a practical example, consider a code with $m=6$ (length 63). The authors identified an optimum distance sequence of 15, 23, 27, 31, 63. This sequence provides engineers with a clear roadmap of how error-correction capability will evolve as the data rate increases.

Conclusion and Future Directions

This work proves that the cyclic property does not need to be sacrificed for performance. While currently focused on second-order Reed-Muller codes, the methodology holds promise for other code families. Specifically, the authors suggest that these distance profile techniques could be applied to Polar codes, which are critical for 5G communications. Extending "cyclic subcode chain" logic to Polar codes could lead to more flexible and efficient next-generation hardware.

Summary updated

Abstract

The distance profiles of linear block codes can be employed to design variational coding scheme for encoding message with variational length and getting lower decoding error probability by large minimum Hamming distance. %, e.g. the design of TFCI in CDMA and the researches on the second-order Reed-Muller code $\mathcal{RM}(2,m)$, etc. Considering convenience for encoding, we focus on the distance profiles with respect to cyclic subcode chains (DPCs) of cyclic codes over $GF(q)$ with length $n$ such that $\mbox{gcd}(n,q) = 1$. In this paper the optimum DPCs and the corresponding optimum cyclic subcode chains are investigated on the punctured second-order Reed-Muller code $\mathcal{RM}(2,m)^*$ for increasing message length, where two standards on the optimums are studied according to the rhythm of increase.
BibTeX
@misc{liu2013optimum,
  author = {Xiaogang Liu and Yuan Luo and Kenneth W. Shum},
  title = {{On the Optimum Cyclic Subcode Chains of (2, m)* for Increasing Message Length}},
  year = {2013},
  eprint = {1306.0710},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1306.0710},
}
Figure