🔢 mathematics

Construction of MRD Codes Based on Circular-Shift Operations

This paper presents a novel construction of maximum rank distance (MRD) codes based on circular-shift operations over $\mathbb{F}_q$ that avoids complex field arithmetic, offers efficient encoding, and establishes both equivalence to and distinction from Gabidulin and twisted Gabidulin codes under various parameter settings.

Original authors: Zhe Zhai, Sheng Jin, Qifu Tyler Sun, Zongpeng Li

Published 2026-02-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhe Zhai, Sheng Jin, Qifu Tyler Sun, Zongpeng Li

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

The Big Picture: Building Better Digital Locks

Imagine you are trying to send a secret message across a noisy, chaotic highway. Sometimes, parts of your message get scrambled, lost, or mixed up with other cars (data). To fix this, engineers use Error-Correcting Codes. Think of these codes as a special "padding" or "redundancy" you add to your message so that even if the highway is terrible, the receiver can still reconstruct the original message.

For a long time, the best way to build these "super-locks" (called MRD Codes) was like trying to solve a complex puzzle using a language only a few experts speak (advanced math involving huge, complex number systems). It worked, but it was slow, expensive, and hard to scale up.

This paper introduces a new way to build these locks. Instead of using the complex, foreign language, the authors built a system using simple, everyday tools (basic binary math and "shuffling" operations). It's faster, cheaper, and just as secure.

The Problem: The "Foreign Language" Barrier

To understand the breakthrough, let's look at the old method (called Gabidulin codes).

The Old Way: Imagine you are building a house. The old method requires you to use a specific, rare type of brick that only exists in a distant, hard-to-reach country (a mathematical concept called an extension field). To get these bricks, you have to import them, translate them, and then assemble them. As your house gets bigger (more data), the number of these rare bricks explodes, making the construction incredibly slow and complicated.
The Bottleneck: The math required to handle these "rare bricks" gets exponentially harder as the data size grows. It's like trying to do advanced calculus in your head while running a marathon.

The Solution: The "Circular Shuffle"

The authors of this paper said, "Why import rare bricks when we can just rearrange the ones we already have?"

They introduced a new construction based on Circular-Shift Operations.

The Analogy: Imagine you have a row of people holding hands in a circle.
- Old Method: To move the group, you have to calculate the exact mathematical coordinates of every single person in a 3D space.
- New Method: You just tell everyone to take one step to the right. The person at the end wraps around and stands at the beginning. This is a circular shift.
Why it's great: This "shuffling" is incredibly fast. In computer terms, it's just a simple "XOR" operation (a basic logic switch). It doesn't require complex calculations. It's like doing a dance step instead of solving a physics equation.

The Key Discoveries

The paper makes three major points, which we can visualize as follows:

1. The "Local vs. Global" Shop

The Old Shop: You had to go to a global warehouse (the complex math field) to buy your materials.
The New Shop: You can build the entire code using materials found right in your local neighborhood (basic math).
The Result: You can build much larger codes (handle more data) without the construction time slowing down to a crawl.

2. Are They the Same Thing? (The Identity Crisis)

The researchers asked: "Is this new 'shuffling' dance just a fancy way of doing the old 'rare brick' math?"

Sometimes, Yes: In specific, rare scenarios, the new dance moves end up looking exactly like the old math.
Usually, No: In most cases, the new dance is fundamentally different. It creates a new family of codes that the old math couldn't even reach. It's like discovering a new species of bird that looks a bit like a pigeon but has a completely different way of flying.

3. The Speed Boost (The Race)

The paper ran a race between the old method and the new method.

The Old Method: To generate a single message, it had to perform roughly $L^2$ steps (like walking up a staircase with $L$ steps, then doing it again for every step).
The New Method: It only takes $L$ steps (like walking up the staircase once).
The Impact: If $L$ is 100, the old method takes 10,000 steps. The new method takes 100. That's a 100x speedup. In the world of data centers and cryptography, this is a massive deal.

The "Twisted" Twist

There is another famous type of code called "Twisted Gabidulin codes." The paper also checked if their new "shuffling" method was just a disguised version of these twisted codes.

The Verdict: In many settings, the new codes are unique. They are not just twisted versions of the old ones; they are a fresh, distinct invention that works even in situations where the old twisted codes fail (like when using the simplest computer language, binary).

Summary: Why Should You Care?

Think of data transmission as sending a fragile vase across a bumpy road.

Before: You wrapped the vase in a heavy, custom-made steel crate. It protected the vase, but the crate was so heavy and expensive to build that you could only send a few at a time.
Now: The authors invented a new wrapping technique using interlocking rubber bands (the circular shifts). It's just as strong, but it's lightweight, cheap to make, and you can wrap thousands of vases in the time it used to take to wrap one.

In short: This paper gives us a faster, cheaper, and more flexible way to protect our digital data, using simple "shuffling" tricks instead of complex math magic. It opens the door for more efficient storage systems, faster internet, and more secure communications.

1. Problem Statement

Maximum Rank Distance (MRD) codes are crucial for applications in cryptography, distributed storage, and subspace coding. The most well-known constructions, such as Gabidulin codes and twisted Gabidulin codes, rely on arithmetic over large extension fields ( $\mathbb{F}_{q^N}$ ).

Limitations of Existing Methods: As the code length $N$ $N$ increases, the required extension field $\mathbb{F}_{q^N}$ $F_{q^{N}}$ becomes significantly larger. This leads to:
- High computational complexity for encoding and decoding.
- Difficulty in selecting optimal parameters due to the rigidity of field arithmetic.
- Inefficient implementation, particularly when transforming vectors over $\mathbb{F}_{q^N}$ to matrices over $\mathbb{F}_q$ , which requires a carefully chosen basis that is not always easy to find or utilize efficiently.
Goal: The authors aim to construct MRD codes that operate entirely over the base field $\mathbb{F}_q$ using efficient operations (specifically circular shifts) to reduce computational complexity and improve parameter flexibility.

2. Methodology

The paper proposes a new construction of MRD codes based on circular-shift operations and Kronecker products, avoiding the arithmetic of extension fields.

Parameters:
- $q$ : A prime.
- $L$ : A positive integer such that $\gcd(q, L) = 1$ .
- $m_L$ : The multiplicative order of $q$ modulo $L$ (i.e., $q^{m_L} \equiv 1 \pmod L$ ).
- $J$ : Euler's totient function of $L$ (the number of integers in $[1, L-1]$ coprime to $L$ ).
- Code dimensions: $(J \times n, q^{Jk}, d)$ where $n \le m_L \le J$ .
Construction Steps:
1. Block Matrix $\Psi$ : A $k \times n$ block matrix is defined where each block is an $L \times L$ circulant matrix over $\mathbb{F}_q$ generated by powers of a cyclic permutation matrix $C_L$ .
2. Transformation Matrices ( $P, Q$ ): Two matrices $P \in \mathbb{F}_q^{J \times L}$ $P \in F_{q}^{J \times L}$ and $Q \in \mathbb{F}_q^{L \times J}$ $Q \in F_{q}^{L \times J}$ are constructed. The paper provides two methods:
  - Method 1: Using Vandermonde matrices and specific full-rank matrices $U, U'$ derived from roots of unity in $\mathbb{F}_{q^{m_L}}$ to ensure the MRD property.
  - Method 2: An alternative using a polynomial $\tau(x)$ (related to cyclotomic polynomials) to reduce encoding complexity further.
3. Codeword Generation: For a message vector $m \in \mathbb{F}_q^{Jk}$ , the codeword is generated via:
  $C = \{ \Delta(m(I_k \otimes P) \Psi_{k \times n} (I_n \otimes Q)) : m \in \mathbb{F}_q^{Jk} \}$
  where $\Delta$ maps a row vector to a $J \times n$ matrix.
Theoretical Characterization:
The authors characterize both the new codes and Gabidulin codes using $q$ -linearized polynomials over the row vector space $\mathbb{F}_q^N$ (instead of $\mathbb{F}_{q^N}$ ). This allows for a direct comparison of the polynomial evaluations used in both code families.

3. Key Contributions

New Construction over $\mathbb{F}_q$ :
The paper presents the first construction of MRD codes that avoids arithmetic over extension fields ( $\mathbb{F}_{q^J}$ ). The construction relies solely on $\mathbb{F}_q$ arithmetic and circular shifts, making it highly efficient for hardware implementation (e.g., XOR operations).
Characterization and Distinction from Gabidulin Codes:
- Case $J \neq m_L$ : The authors prove that under specific parameter settings (where the shift indices follow a specific arithmetic progression), the proposed codes are distinct from any Gabidulin code or twisted Gabidulin code. They are not equivalent to any known MRD code family.
- Case $J = m_L$ : The authors prove that the proposed codes coincide with Gabidulin codes. However, the circular-shift construction offers a new, efficient way to generate Gabidulin codes directly over $\mathbb{F}_q$ , bypassing the need for extension field arithmetic.
Generalization of Gabidulin Codes:
The paper demonstrates that the proposed codes are equivalent to a generalization of Gabidulin codes formed by summing and concatenating several smaller Gabidulin codes (of size $m_L \times n$ ). This generalization had not been previously explored in the literature.
Complexity Analysis:
- Proposed Codes: Generating a codeword requires $O(nkL)$ XOR operations (for $q=2$ ).
- Standard Gabidulin Codes: Generating a codeword requires $O(nkL^2)$ XOR operations due to multiplication in $\mathbb{F}_{2^L}$ .
- This represents a significant reduction in computational complexity, especially for large $L$ .

4. Key Results

Theorem 7 & 9: Proved that the constructed codes satisfy the Maximum Rank Distance (MRD) property ( $d = n - k + 1$ ) under specific conditions for matrices $P$ and $Q$ .
Theorem 12:
- If $J \neq m_L$ and parameters satisfy specific constraints, the new codes are not equivalent to any Gabidulin or twisted Gabidulin code.
- If $J = m_L$ , the new codes are equivalent to Gabidulin codes but constructed more efficiently.
Proposition 13: Under certain settings, the new codes are also distinct from twisted Gabidulin codes (specifically those with $h=0$ ).
Theorem 16: Established the equivalence between the proposed circular-shift codes and a generalized Gabidulin code structure (sum of concatenated Gabidulin codes) when $P$ and $Q$ are chosen in specific forms.
Example 4 & 5: Provided explicit numerical examples (e.g., $q=2, L=5, L=7$ ) verifying that the constructed codewords match theoretical predictions and, in the $J=m_L$ case, match standard Gabidulin codewords.

5. Significance and Impact

Practical Implementation: By eliminating the need for extension field arithmetic, the proposed codes are significantly easier to implement in software and hardware. The reliance on circular shifts and XOR operations makes them ideal for high-speed network coding and storage systems.
Parameter Flexibility: The construction allows for a wider range of parameter selections ( $J$ and $k$ ) without being constrained by the existence of specific extension field bases.
Theoretical Insight: The paper bridges the gap between linear network coding (which uses circular shifts) and rank metric coding. It clarifies the deep algebraic relationship between circular-shift operations and $q$ -linearized polynomials.
Efficiency: The reduction from $O(L^2)$ to $O(L)$ complexity for encoding is a major advancement for large-scale applications where $L$ (and thus the field size) is large.

In conclusion, this work provides a novel, efficient, and theoretically rigorous framework for constructing MRD codes that overcomes the implementation bottlenecks of traditional Gabidulin codes while maintaining optimal error-correction capabilities.