On (Partial) unit memory codes based on Gabidulin codes

Antonia Wachter, Vladimir R. Sidorenko, Martin Bossert, Victor V. Zyablov

TL;DR

This paper introduces a novel construction for (Partial) Unit Memory (PUM) convolutional codes using Gabidulin codes, which are known for their strong error-correcting capabilities in rank-metric settings. The authors define a new "sum rank metric" and derive upper bounds for PUM codes under this metric, demonstrating that their construction achieves these bounds, particularly for free rank distance and half the optimal slope.

What Problem Does This Paper Address?

Convolutional codes are fundamental in error control, and their performance is often characterized by their free distance and slope. While constructions for PUM codes based on Hamming metric codes exist, there's a growing interest in rank metric codes, especially for applications like network coding where dependencies between transmitted blocks are crucial. Gabidulin codes are a prominent class of rank metric codes. This paper aims to bridge these areas by constructing PUM codes based on Gabidulin codes, adapting distance measures to a "sum rank metric" suitable for multi-shot network coding scenarios, and analyzing their performance.

Methods

The core of this paper lies in the construction and analysis of PUM codes derived from Gabidulin codes. Key methods include:

  • Sum Rank Metric: A new distance metric is defined, extending the concept of rank distance to sequences of vectors. This metric is crucial for analyzing codes in multi-shot network coding.
  • Gabidulin Code Foundation: The construction leverages the algebraic structure of Gabidulin codes, which are rank-metric analogues of Reed-Solomon codes.
  • PUM Code Construction: A specific construction method is proposed, using Gabidulin codes as building blocks for the parity-check matrices of PUM codes. This involves defining specific relationships between submatrices of the parity-check matrix.
  • Distance Analysis: The paper derives upper bounds for the free rank distance and the slope of these PUM codes under the sum rank metric. These bounds are connected to existing bounds for Hamming metric codes.
  • Explicit Construction and Performance Evaluation: An explicit construction is provided, and the free rank distance and slope are calculated for a specific case (dual memory $\tau_H = 1$).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Rank and Convolutional Codes: The paper successfully demonstrates how to combine the strengths of Gabidulin codes (rank-metric error correction) with the structure of convolutional codes (PUM codes) for enhanced performance.
  • Sum Rank Metric's Relevance: The introduction and use of the sum rank metric highlight its importance for analyzing codes in scenarios like multi-shot network coding, where the traditional rank metric might not fully capture the error-correcting potential.
  • Achieving Optimal Bounds: The proposed construction achieves the theoretical upper bound for the free rank distance and a significant portion (half) of the optimal slope, indicating high error-correcting capability.
  • Algebraic Construction: The use of Gabidulin codes allows for an algebraic and systematic construction of PUM codes, which is beneficial for both theoretical analysis and practical implementation.

Key Results

  • Upper Bounds: The paper derives upper bounds for the free rank distance ($d_{free} \leq 2n-k+1$ for UM codes, $d_{free} \leq n-k+v+1$ for PUM codes) and the slope ($\alpha \leq n-k$) under the sum rank metric.
  • Explicit Construction: A method for constructing PUM codes based on Gabidulin codes is presented, ensuring that the parity-check matrix satisfies specific properties.
  • Performance for $\tau_H=1$: For PUM codes with dual memory $\tau_H=1$, the construction achieves:
  • $d_{free} = 2(n-k)+1 = n-k+v+1$, which meets the upper bound.
  • $\alpha = \frac{n-k+1}{2}$, which is half the optimal slope.

Limitations and Future Work

  • Decoding Algorithm: The paper acknowledges that a decoding algorithm for these newly constructed codes is a significant area for future research, suggesting that algorithms similar to those for Hamming metric PUM codes might be applicable.
  • Generator Matrix Construction: The authors propose exploring PUM constructions where the generator matrices themselves define Gabidulin codes, as opposed to the current construction which uses Gabidulin codes for parity-check matrices.
  • Field Size Restriction: The explicit construction requires a certain minimal field size (e.g., $s \geq (\tau_H+1) \cdot \frac{n}{n-k} \cdot (n-k)$) to ensure linear independence of elements, which might be a practical consideration.

Summary updated

Abstract

Partial) unit memory ((P)UM) codes provide a powerful possibility to construct convolutional codes based on block codes in order to achieve a high decoding performance. In this contribution, a construction based on Gabidulin codes is considered. This construction requires a modified rank metric, the so-called sum rank metric. For the sum rank metric, the free rank distance, extended row rank distance, and its slope are defined analogous to the extended row distance in the Hamming metric. Upper bounds for the free rank distance and slope of (P)UM codes in the sum rank metric are derived, and an explicit construction of (P)UM codes based on Gabidulin codes is given.
BibTeX
@article{wachter2011partial,
  author = {Antonia Wachter and Vladimir R. Sidorenko and Martin Bossert and Victor V. Zyablov},
  title = {{On (Partial) unit memory codes based on Gabidulin codes}},
  journal = {Probl. Inf. Transm.},
  year = {2011},
  doi = {10.1134/s0032946011020049},
}
Figure