Generalized Pair Weights of Linear Codes and Linear Isomorphisms Preserving Pair Weights

Hongwei Liu, Xu PanIEEE Trans. Information Theory 2022 · DOI

TL;DR

This paper introduces and studies "generalized pair weights" for linear codes, extending the concept of generalized Hamming weights. The authors establish conditions for codes to be "pair equiweight" and characterize "pair r-equiweight" codes. Crucially, they provide a necessary and sufficient condition for linear isomorphisms to preserve these pair weights, offering a new perspective on code equivalence.

What Problem Does This Paper Address?

Modern coding theory relies heavily on various weight hierarchies, such as the generalized Hamming weight hierarchy, to understand code performance and cryptographic properties. While the Hamming weight and distance are well-established, the "pair weight" metric, introduced to handle symbol-pair errors in data storage, is newer. This paper aims to generalize the powerful tools developed for Hamming weights to this pair weight setting. Specifically, it seeks to understand the structure of codes based on their pair weight hierarchy and to characterize linear transformations that preserve these pair weights, analogous to the well-known MacWilliams extension theorem for Hamming weights.

Methods

The paper builds upon existing definitions of pair weights and generalized Hamming weights. Key methods include:

  • Definition of Generalized Pair Weights: Extending the concept of generalized Hamming weights to the pair weight setting, defining $d_r^{\text{pair}}(C)$ as the minimum pair weight of $r$-dimensional subspaces of a code $C$.
  • Characterization of Pair Equiweight Codes: Deriving necessary and sufficient conditions for a linear code to have all its non-zero codewords with the same pair weight.
  • Characterization of Pair r-Equiweight Codes: Defining and characterizing codes where all $r$-dimensional subspaces have the same minimum pair weight.
  • Linear Isomorphisms Preserving Pair Weights: Developing a necessary and sufficient condition for a linear isomorphism between two codes to preserve pair weights. This involves analyzing the behavior of the weight distribution under the isomorphism.
  • Algorithmic Approach: Proposing an algorithm to efficiently determine if a code is pair equiweight and if an isomorphism preserves pair weights, leveraging matrix properties and subspace counts.

Datasets

Not discussed in the paper. The paper focuses on theoretical aspects of linear codes over finite fields and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Generalization is Possible: The paper demonstrates that the rich theory surrounding generalized Hamming weights can be successfully extended to the realm of pair weights, opening up new avenues for research in this area.
  • Pair Equiweight Codes are Structured: The characterizations of pair equiweight and pair r-equiweight codes reveal specific structural properties that can be exploited for code design and analysis.
  • Isomorphisms are Tricky: Unlike Hamming weights, where monomial transformations are key, linear isomorphisms preserving pair weights are more nuanced. The paper provides a precise condition for this preservation, highlighting that simple permutation matrices might not suffice.
  • Computational Efficiency: The proposed algorithmic approach for checking pair equiweight properties and isomorphism preservation is significantly more efficient than brute-force checking of all codewords, especially for large codes.

Key Results

  • The paper derives necessary and sufficient conditions for a linear code to be a pair equiweight code.
  • It characterizes pair $r$-equiweight codes for $1 \le r \le k-1$.
  • A necessary and sufficient condition is established for a linear isomorphism to preserve pair weights between two linear codes.
  • Bounds related to the Singleton bound for generalized pair weights are presented.
  • An efficient algorithm is proposed for determining pair equiweight properties and pair-weight-preserving isomorphisms.

Limitations and Future Work

  • Focus on Finite Fields: The current work is primarily focused on linear codes over finite fields. Extending these results to codes over rings or other algebraic structures could be a future direction.
  • Specific Code Families: While the paper provides general conditions, exploring these concepts for specific families of codes (e.g., Reed-Muller, Goppa codes) and computing their generalized pair weight hierarchies would be valuable.
  • Applications: The authors mention potential applications in cryptography. Further research could explore how these generalized pair weights and isomorphism properties can be leveraged for cryptographic constructions or security analysis.
  • Algorithmic Refinements: While an efficient algorithm is proposed, further optimization or exploration of its practical performance on very large codes might be beneficial.

Summary updated

BibTeX
@article{liu2022generalized,
  author = {Hongwei Liu and Xu Pan},
  title = {{Generalized Pair Weights of Linear Codes and Linear Isomorphisms Preserving Pair Weights}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  doi = {10.1109/tit.2021.3120229},
}

Loading related content...

Figure