# Decoding a class of maximum Hermitian rank metric codes

Wrya K. Kadir  Informatics Department, University of Bergen Chunlei Li
Informatics Department, University of Bergen Ferdinando Zullo The research of
the last author was supported by the project “VALERE: VAnviteLli pEr la
RicErca” of the University of Campania “Luigi Vanvitelli” and by the Italian
National Group for Algebraic and Geometric Structures and their Applications
(GNSAGA - INdAM). Dipartimento di Matematica e Fisica, Università degli Studi
della Campania “Luigi Vanvitelli”

###### Abstract

Maximum Hermitian rank metric codes were introduced by Schmidt in 2018 and in
this paper we propose both interpolation-based encoding and decoding
algorithms for this family of codes when the length and the minimum distance
of the code are both odd.

##  1 Introduction

Let $\mathbb{F}_{q}^{n\times n}$ be the set of the square matrices of order
$n$ defined over $\mathbb{F}_{q}$, which is the finite field of $q$ elements.
We can equip $\mathbb{F}_{q}^{n\times n}$ with the following metric

$d(A,B)=\mathrm{rk}(A-B),$

where $\mathrm{rk}(A-B)$ is the rank of the difference matrix $A-B$. If
$\mathcal{C}$ is a subset of $\mathbb{F}_{q}^{n\times n}$ with the property
that for each $A,B\in\mathcal{C}$ then $d(A,B)\geq d$ with $1\leq d\leq n$,
then $\mathcal{C}$ is called a _rank metric code with minimum distance_ $d$,
or that $\mathcal{C}$ is a $d$-_code_ [9]. Furthermore, we say that
$\mathcal{C}$ is $\mathbb{F}_{q}$-_linear_ if $\mathcal{C}$ is an
$\mathbb{F}_{q}$-subspace of $(\mathbb{F}_{q}^{n\times n},+,\cdot)$, where $+$
is the classical matrix addition and $\cdot$ is the scalar multiplication by
an element of $\mathbb{F}_{q}$.

Examples are rank metric codes whose codewords are alternating matrices [4],
symmetric matrices [6, 8, 13] and Hermitian matrices [9, 11]. In this paper we
deal with the latter case.

Consider the conjugation map $\overline{\cdot}$ from $\mathbb{F}_{q^{2}}$ to
itself: $x\mapsto\overline{x}=x^{q}$. Let $A\in\mathbb{F}_{q^{2}}^{n\times n}$
and denote by $A^{*}$ its conjugate transpose, that is $A^{*}$ is obtained by
the transposition of the matrix $A$ in which the conjugate map is applied to
all of its entries. A matrix $A\in\mathbb{F}_{q^{2}}^{n\times n}$ is said to
be _Hermitian_ if $A^{*}=A$. Denote by ${\rm H}_{n}(q^{2})$ the set of all
Hermitian matrices of order $n$ over $\mathbb{F}_{q^{2}}$. In [9, Theorem 1],
Schmidt proved that if $\mathcal{C}$ is an $\mathbb{F}_{q}$-linear rank metric
code with minimum distance $d$ contained in ${\rm H}_{n}(q^{2})$, then

$|\mathcal{C}|\leq q^{n(n-d+1)}.$

When the equality is achieved, we say that $\mathcal{C}$ is a _maximum
Hermitian $d$-code_ or a _maximum Hermitian rank metric code_.

Each rank metric code can be described equivalently in terms of
$q$-polynomials. Let $\mathcal{L}_{n,q}$ denote the quotient
$\mathbb{F}_{q}$-algebra of the algebra of linearized polynomials over
$\mathbb{F}_{q^{n}}$ with respect to $(x-x^{q^{n}})$, i.e.

$\mathcal{L}_{n,q}=\left\\{\sum_{i=0}^{n-1}a_{i}x^{q^{i}}\colon
a_{i}\in\mathbb{F}_{q^{n}}\right\\}.$

It is well known that $\mathcal{L}_{n,q}$ is isomorphic to the
$\mathbb{F}_{q}$-algebra of square matrices over $\mathbb{F}_{q}$. Using this
fact and following [6], the set ${\rm H}_{n}(q^{2})$ of Hermitian matrices of
order $n$ over $\mathbb{F}_{q^{2}}$ can be identified as the following set of
linearized polynomials

${\mathcal{H}}_{n}(q^{2})=\left\\{\sum_{i=0}^{n-1}c_{i}x^{q^{2i}}\colon
c_{n-i+1}=c_{i}^{q^{2n-2i+1}}\,\text{ for
}\,i\in\\{0,\ldots,n-1\\}\right\\}\subseteq\mathcal{L}_{n,q^{2}},$

where the indices are taken modulo $n$. Note that if $n$ is odd then
$c_{(n+1)/2}$ belongs to $\mathbb{F}_{q^{n}}$.

There are some examples of maximum Hermitian $d$-codes, see [9, 11]. The first
two examples were given in [9, Theorems 4 and 5]. In this abstract, we
consider the decoding of the following class of codes.

###### Theorem 1.1

[9, Theorem 5] Let $n$ and $d$ be odd integers satisfying $1\leq d\leq n$. The
Hermitian forms
$H:\mathbb{F}_{q^{2n}}\times\mathbb{F}_{q^{2n}}\rightarrow\mathbb{F}_{q^{2}}$
given by $H(x,y)=\mathrm{Tr}\left(y^{q}L(x)\right)$ with

$L(x)=(b_{0}x)^{q^{(n+1)}}+\sum_{j=1}^{\frac{n-d}{2}}\left((b_{j}x)^{q^{(n+2j+1)}}+b_{j}^{q}x^{q^{(n-2j+1)}}\right),$
(1)

as $b_{0}$ ranges over $\mathbb{F}_{q^{n}}$ and
$b_{1},\ldots,b_{\frac{n-d}{2}}$ range over $\mathbb{F}_{q^{2n}}$, form an
additive $d$-code in $\mathrm{H}_{n}(q^{2})$, the set of $n\times n$ Hermitian
matrices over $\mathbb{F}_{q^{2}}$, and for $z\in\mathbb{F}_{q^{2n}}$ we
define $\mathrm{Tr}(z)=z+z^{q}+\ldots+z^{q^{n-1}}$ which stands for the trace
function $\mathrm{Tr}:\mathbb{F}_{q^{2n}}\rightarrow\mathbb{F}_{q^{2}}$.

The above statement also holds when one extends the $q^{2}$-polynomials to
$q^{2s}$-polynomials with the integer $s$ satisfying $\gcd(s,2n)=1$.

Our work in this abstract is also motivated by the recent work of De La Cruz,
Evilla and Özbudak [3], where in Section 6 they suggested studying decoding
algorithm for Hermitian rank metric codes. A summary of the existing
interpolation-based decoding algorithms of rank metric codes is given in [5,
Section V.].

##  2 Encoding and Decoding of Hermitian MRD codes

###  2.1 Encoding

Assume that $\\{\alpha_{1},\ldots,\alpha_{n}\\}$ is an
$\mathbb{F}_{q^{2}}$-basis of $\mathbb{F}_{q^{2n}}$ such that
$\mathrm{Tr}(\alpha_{i}^{q}\alpha_{j})$ is zero if $i\neq j$ and $1$ if $i=j$.
The property we require on the basis $\\{\alpha_{1},\ldots,\alpha_{n}\\}$
naturally extends the notion of _self-dual basis_ in this setting, for this
reason we will call it a _Hermitian self-dual basis_ and such a basis always
exists, see e.g. [1, Theorem 4.1]. Throughout what follows, we denote
$x^{[i]}=x^{q^{2i}}$ for the simplicity of presentation.

Let $L(x)$ as in Theorem 1.1. For the Hermitian form in Theorem 1.1, we have

$H(x,y)=\mbox{Tr}(y^{q}L(x))=\mbox{Tr}(x^{q}L(y)).$

Let $x,y\in\mathbb{F}_{q^{2n}}$, then $x=\sum_{i=1}^{n}x_{i}\alpha_{i}$ and
$y=\sum_{i=1}^{n}y_{i}\alpha_{i}$, for some
$x_{i},y_{i}\in\mathbb{F}_{q^{2}}$. It is clear that
$\mathrm{Tr}(x^{q}y)=\langle(x_{1}^{q},\ldots,x_{n}^{q}),(y_{1},\ldots,y_{n})\rangle=\sum_{i=1}^{n}x_{i}^{q}y_{i}$.
Now, denote by $\mathcal{H}$ the associated matrix of $H$ with respect to the
ordered $\mathbb{F}_{q^{2}}$-basis $(\alpha_{1},\ldots,\alpha_{n})$ and denote
by $\mathcal{H}(i,j)$ its $(i,j)$-entry, namely,
$\mathcal{H}(i,j)=H(\alpha_{i},\alpha_{j})=\mbox{Tr}(\alpha_{j}^{q}L(\alpha_{i}))$.

In the following we show how the codewords of the additive $d$-code in Theorem
1.1 can be expressed in the Hermitian matrix form. Note that

$\displaystyle H(x,y)$
$\displaystyle=\text{Tr}\left(\left(\sum_{i}y_{i}\alpha_{i}\right)^{q}\sum_{j}x_{j}L(\alpha_{j})\right)=\mbox{Tr}\left(\sum_{i,j}y_{i}^{q}x_{j}\alpha_{i}^{q}L(\alpha_{j})\right)$
$\displaystyle=\sum_{i,j}y_{i}^{q}x_{j}\mbox{Tr}\left(\alpha_{i}^{q}L(\alpha_{j})\right)=\sum_{i,j}y_{i}^{q}x_{j}\mathcal{H}(i,j)=(y_{1},\ldots,y_{n})^{q}\cdot\mathcal{H}\cdot\left(\begin{array}[]{c}x_{1}\\\
\vdots\\\ x_{n}\end{array}\right).$

In the literature, no encoding method has been given for Hermitian $d$-codes.
In the following we show that the evaluation of the corresponding linearized
polynomial at linearly independent elements $\alpha_{1},\ldots,\alpha_{n}$ is
a proper encoding method.

Let $h=(h_{1},\ldots,h_{n})$ be the Hermitian vector corresponding to the
Hermitian matrix $\mathcal{H}$, that is

$h_{r}=\sum_{i}\alpha_{i}H(\alpha_{i},\alpha_{r}).$

Since $H(\alpha_{i},\alpha_{r})=\mathrm{Tr}(\alpha_{i}^{q}f(\alpha_{j}))$, we
can write $h_{r}$ as

$h_{r}=\sum_{i}\alpha_{i}\mbox{Tr}(\alpha_{i}^{q}L(\alpha_{r}))=\sum_{i}\alpha_{i}\mbox{Tr}\left(\alpha_{i}^{q}\sum_{j}c_{j}\alpha_{j}\right)=\sum_{i}\alpha_{i}\sum_{j}c_{j}\mbox{Tr}(\alpha_{i}^{q}\alpha_{j})=\sum_{i}c_{i}\alpha_{i},$

where $L(\alpha_{r})=\sum_{j}c_{j}\alpha_{j}$, by using the fact that $L(x)$
is linear over $\mathbb{F}_{q^{2}}$ and the fact that
$(\alpha_{1},\ldots,\alpha_{n})$ is a Hermitian self-dual basis. From the
above calculations we see that the evaluation encoding is the right way of
encoding Hermitian $d$-codes, since $h_{r}=L(\alpha_{r})$.

Let $m=(n+1)/2$, $\kappa=(n-d)/2$ and $H$ be the Hermitian form given in
Theorem 1.1. Then the linearized polynomial in (1) can be written as

$L(x)=(b_{0}x)^{[m]}+\sum_{j=1}^{\kappa}\left((b_{j}x)^{[m+j]}+b_{j}^{q}x^{[m-j]}\right).$

Let $\\{1,\eta\\}$ be an $\mathbb{F}_{q^{n}}$-basis of $\mathbb{F}_{q^{2n}}$.
Let $\alpha_{0},\alpha_{1},\ldots,\alpha_{n-1}$ be a Hermitian self-dual basis
of $\mathbb{F}_{q^{2n}}$. For the maximum Hermitian $d$-code in Theorem 1.1
and the evaluation points $\alpha_{0},\alpha_{1},\ldots,\alpha_{n-1}$, the
encoding of a message $f=(f_{0},\ldots,f_{k-1})\in\mathbb{F}_{q^{n}}^{k}$ can
be expressed as the evaluation of the following linearized polynomial at
points $\alpha_{0},\alpha_{1},\ldots,\alpha_{n-1}$:

$\begin{array}[]{rcl}L(x)&=&(f_{0}x)^{[m]}+\left(\sum\limits_{j=1}^{\kappa}(f_{j}+\eta
f_{\frac{k-1}{2}+j})^{q}x^{[m-j]}+(f_{j}+\eta
f_{\frac{k-1}{2}+j}x)^{[m+j]}\right)\\\
&=&\tilde{f}_{0}x+\tilde{f}_{1}x^{[1]}+\cdots+\tilde{f}_{n-1}x^{[n-1]}.\end{array}$
(2)

Let $M=\begin{pmatrix}\alpha_{i}^{[j]}\end{pmatrix}_{n\times n}$ be the
$n\times n$ Moore matrix generated by $\alpha_{i}$’s.

So the encoding of the maximum Hermitian rank metric code can be expressed as

$(f_{0},\ldots,f_{k-1})\mapsto(L(\alpha_{0}),\ldots,L(\alpha_{n-1}))=\tilde{f}\cdot
M^{T},$ (3)

where $\tilde{f}=(\tilde{f}_{0},\ldots,\tilde{f}_{n-1})$ and $M^{T}$ is the
transpose of the matrix $M$. As shown in (2), the first $m-\kappa$ and the
last $m-\kappa-2$ elements of $\tilde{f}$ are zero, we only employ $k$ columns
of the Moore matrix in the encoding process.

###  2.2 Interpolation Decoding

For a received word $r=c+e$ with an error $e$ added to the codeword $c$ during
transmission, when the error $e$ has rank $t\leq\lfloor\frac{d-1}{2}\rfloor$,
the unique decoding task is to recover the unique codeword $c$ such that
$d_{r}(c,r)\leq\lfloor\frac{d-1}{2}\rfloor$.

Suppose $g(x)=\sum_{i=0}^{n-1}g_{i}x^{[i]}$ is an error interpolation
polynomial such that

$g(\alpha_{i})=e_{i}=r_{i}-c_{i},\quad i=0,\ldots,n-1.$ (4)

It is clear that the error vector $e$ is uniquely determined by the polynomial
$g(x)$, and denote $\tilde{g}=(g_{0},\ldots,g_{n-1})$. From (3) and (4) it
follows that

$r=c+e=(\tilde{f}+\tilde{g})M^{T}.$

This is equivalent to

$\displaystyle r\cdot(M^{T})^{-1}=$
$\displaystyle(0,\ldots,0,\tilde{f}_{m-\kappa},\ldots,\tilde{f}_{m+\kappa},0,\ldots,0)$
$\displaystyle+(g_{0},\ldots,g_{m-\kappa-1},g_{m-\kappa},\ldots,g_{m+\kappa},g_{m+\kappa+1},\ldots,g_{n-1}).$

where $\tilde{f}_{m}=f_{0}^{[m]}$ and for $j=1,2,\cdots,\kappa$,
$\tilde{f}_{m-j}=(f_{j}+\eta f_{\kappa+j})^{q}\text{ and
}\tilde{f}_{m+j}=\tilde{f}_{m-j}^{q^{n+2j}}$. Letting
$\beta=(\beta_{0},\ldots,\beta_{n-1})=r\cdot(M^{T})^{-1}$, we obtain

$\begin{cases}(g_{0},\ldots,g_{m-\kappa-1})=(\beta_{0},\ldots,\beta_{m-\kappa-1})\\\
(g_{m+\kappa+1},\ldots,g_{n-1})=(\beta_{m+\kappa+1},\ldots,\beta_{n-1})\end{cases}$
(5)

Equivalently, we have

$g_{m+\kappa+j}=\beta_{m+\kappa+j}\text{ for }j=1,2,\cdots,d-1,$ (6)

where the subscripts are taken modulo $n$. In addition, we have

$g_{m-\kappa+j}=\beta_{m-\kappa+j}-\tilde{f}_{m-\kappa+j}\text{ for
}j=1,\ldots,2\kappa.$ (7)

With the relation $\tilde{f}_{m+j}=\tilde{f}_{m-j}^{q^{n+2j}}$ for $1\leq
j\leq\kappa$, it is sufficient to recover the coefficients
$g_{m+\kappa+1},\ldots,g_{m}$.

Therefore, the task of correcting error $e$ is equivalent to reconstructing
$g(x)$ from the available information characterized in the above relations (6)
and then apply $g(x)$ to recover $\tilde{f}$. This reconstruction process
heavily depends on the property of the associated Dickson matrix of $g(x)$ and
will be discussed in next subsection.

###  2.3 Polynomial reconstruction

The Dickson matrix associated with $g(x)$ can be given by

$G=\begin{pmatrix}g^{[j]}_{i-j~{}({\rm mod~{}}n)}\end{pmatrix}_{n\times
n}=\left(G_{0}\,\,G_{1}\,\,\ldots\,\,G_{n-1}\right),$ (8)

where the indices $i,\,j$ run through $\\{0,1,\ldots,n-1\\}$ and $G_{j}$ is
the $j$-th column of $G$.

According to the properties of the Dickson matrix, when $D$ has rank $t$, any
$t\times t$ matrix formed by $t$ successive rows and columns in $G$ is
nonsingular, see e.g. [12] and [2]. Then $G_{0}$ can be expressed as a linear
combination of $G_{1},\ldots,G_{t}$, namely,
$G_{0}=\lambda_{1}G_{1}+\lambda_{2}G_{2}+\cdots+\lambda_{t}G_{t},$ where
$\lambda_{1},\ldots,\lambda_{t}$ are elements in $\mathbb{F}_{q^{2n}}$. This
yields the following recursive equations

$g_{i}=\lambda_{1}g^{[1]}_{i-1}+\lambda_{2}g^{[2]}_{i-2}+\cdots+\lambda_{t}g^{[t]}_{i-t},\quad
0\leq i<n,$ (9)

where the subscripts in $g_{i}$’s are taken modulo $n$. Recall that the
elements $g_{0},\ldots,g_{m-\kappa-1}$ and $g_{m+\kappa+1},\ldots,g_{n-1}$ are
known from (5). Hence, we obtain the following linear equations with known
coefficients and variables $\lambda_{1},\ldots,\lambda_{t}$:

$g_{i}=\lambda_{1}g^{[1]}_{i-1}+\lambda_{2}g^{[2]}_{i-2}+\cdots+\lambda_{t}g^{[t]}_{i-t},\,\,m+\kappa+t+1\leq
i<n+m-\kappa~{}(\mbox{mod }n).$ (10)

The above recurrence gives a generalized version of $q$-linearized shift
register as described in [10], where $(\lambda_{1},\ldots,\lambda_{t})$ is the
connection vector of the shift register. It is the key equation for the
decoding algorithm in this paper, by which we shall reconstruct $g(x)$ in two
major steps:

  * Step 1. derive $\lambda_{1},\ldots,\lambda_{t}$ from (5) and (10);

  * Step 2. use $\lambda_{1},\ldots,\lambda_{t}$ to compute $g_{m-\kappa},\ldots,g_{m+\kappa}$ from (9).

Step 1 is the critical step in the decoding process, and Step 2 is simply a
recursive process that can be done in linear time in $\mathbb{F}_{q^{2n}}$.
The following discussion shows how the procedure of Step 1 works.

As discussed in the beginning of this section, for an error vector with
$\mbox{rk}(e)=t\leq\lfloor\frac{d-1}{2}\rfloor$, (10) contains a system of
$(n-k)-t=d-1-t\geq t$ affine linear equations in the variables
$\lambda_{1},\ldots,\lambda_{t}$, which has rank $t$. Hence the variables
$\lambda_{1},\ldots,\lambda_{t}$ can be uniquely determined. Here we assume
the code has high code rate, for which the Berlekamp-Massey algorithm is more
efficient. Although the recurrence equation (10) is a generalized version of
the ones in [7, 10], the modified Berlekamp-Massey algorithm can be applied
here to recover the coefficients $\lambda_{1},\ldots,\lambda_{t}$.

##  3 Conclusion

In this abstract we have proposed both interpolation-based encoding and
decoding algorithms for a family of maximum Hermitian rank metric codes when
the length and the minimum distance of the code are both odd. In the future we
will extend it to other classes of maximum rank distance codes with
restrictions.

## References

  * [1] R. C. Bose and I. Chakravarti.  Hermitian varieties in a finite projective space ${PG}(n,q^{2})$.  Canadian Journal of Mathematics, 18:1161–1182, 1966.
  * [2] B. Csajbók.  Scalar $q$-subresultants and Dickson matrices.  Journal of Algebra, 547:116–128, 2020.
  * [3] J. De La Cruz, J. R. Evilla, and F. Özbudak.  Hermitian rank metric codes and duality.  IEEE Access, 9:38479–38487, 2021.
  * [4] P. Delsarte and J.-M. Goethals.  Alternating bilinear forms over GF$(q)$.  Journal of Combinatorial Theory, Series A, 19(1):26–50, 1975.
  * [5] W. K. Kadir, C. Li, and F. Zullo.  On interpolation-based decoding of maximum rank distance codes.  Submitted to International Symposium on Information Theory (ISIT), 2021.
  * [6] G. Longobardi, G. Lunardon, R. Trombetti, and Y. Zhou.  Automorphism groups and new constructions of maximum additive rank metric codes with restrictions.  Discrete Mathematics, 343(7):111871, 2020.
  * [7] G. Richter and S. Plass.  Fast decoding of rank-codes with rank errors and column erasures.  In International Symposium on Information Theory (ISIT), pages 398–398, June 2004.
  * [8] K.-U. Schmidt.  Symmetric bilinear forms over finite fields with applications to coding theory.  Journal of Algebraic Combinatorics, 42(2):635–670, 2015.
  * [9] K.-U. Schmidt.  Hermitian rank distance codes.  Designs, Codes and Cryptography, 86(7):1469–1481, 2018.
  * [10] V. Sidorenko, G. Richter, and M. Bossert.  Linearized shift-register synthesis.  IEEE Transactions on Information Theory, 57(9):6025–6032, Sep. 2011.
  * [11] R. Trombetti and F. Zullo.  On maximum additive Hermitian rank-metric codes.  Journal of Algebraic Combinatorics, pages 1–21, 2020.
  * [12] B. Wu and Z. Liu.  Linearized polynomials over finite fields revisited.  Finite Fields and Their Applications, 22:79–100, 2013.
  * [13] Y. Zhou.  On equivalence of maximum additive symmetric rank-distance codes.  Designs, Codes and Cryptography, 88(5):841–850, 2020.