1 Introduction
Rank metric codes were introduced first by Delsarte in [2], and independently by Gabidulin in [12] and Roth in [27]. They have been extensively investigated because of their applications in crisscross error correction [27], cryptography [6] and network coding [35]. The coding-theoretic properties of these codes have been studied in detail, and constructions of optimal codes with respect to a Singleton-like bound, known as MRD codes, have been found. An interested reader may refer to [8, 32] for more details.
Known decoding algorithms for MRD codes can be generally classified in two different approaches: syndrome-based decoding as in [5, 7, 25, 27] and interpolation-based decoding as in [9, 10, 13, 14, 16, 24]. Gabidulin in [5] solves the key equation in the decoding process by employing the linearized version of extended Euclidean (LEE) algorithm, while in [25], the key equation was solved by a linearized version of Berlekamp-Massey (BM) algorithm. The error values in both decoding algorithms in [5] and [25] are computed by an algorithm called Gabidulin algorithm. Loidreau in [16] proposed the first interpolation-based decoding approach for MRD codes and considered the analogue of Welch-Berlekamp (WB) algorithm, which was originally used to decode Reed-Solomon codes [38]. The algorithm directly gives the code’s interpolation polynomial and computing the error vector is not required in the decoding process.
Anzeige
In [31], Sheekey proposed the first family of MRD codes over \(\mathbb {F}_{q^{n}}\) which is linear over \(\mathbb {F}_{q}\) (instead of \({\mathbb {F}_{q^{n}}}\) as the well-known Gabidulin codes) and his idea were used later to introduce new MRD codes that are linear over a sub-field of \({\mathbb {F}_{q^{n}}}\) [18, 20‐22, 36]. When the rank of the error vector reaches the maximum unique decoding radius, the syndrome-based decoding approach works only for MRD codes that are linear over the main extension field. Randrianarisoa in [24, 26], gave an interpolation based decoding algorithm for twisted Gabidulin codes. Later this idea was adopted to decode additive generalized twisted Gabidulin codes and Trombetti-Zhou rank metric codes [10, 11]. Again BM algorithm is involved in the process of solving the key equations in [10] and [11] and it reduces the decoding problem to the problem of solving the projective polynomial equation \(x^{q^{v}+1}+ax+b=0\) and quadratic polynomial equation x2 + cx + d = 0 over \({\mathbb {F}_{q^{n}}}\), respectively. A similar idea is also used in [9] to decode Gabidulin codes beyond half the minimum distance. All the decoding algorithms described above have polynomial-time complexities. The result in [34] shows that when low-complexity normal basis are used, the complexity can be reduced even further. Solving the key equations carried out by BM or LEE algorithm are the most expensive steps in the above decoding algorithms.
Besides the aforementioned new MRD codes, there are also some restricted rank metric codes that are linear over a subfield of \({\mathbb {F}_{q^{n}}}\) which are not defined based on Sheekeys’ idea. The study of subsets of restricted matrices equipped with rank metric was started in 1975 by Delsarte and Goethals in [3], in which they considered sets of alternating bilinear forms. The theory developed in [2] and [3] found applications also in the classical coding theory. Indeed, the evaluations of the forms found in [3] give rise to subcodes of the second-order Reed-Muller codes, including the Kerdock code and the chain of Delsarte–Goethals codes; see also [28].
Using the theory of association schemes, bounds, constructions and structural properties of restricted rank metric codes have been investigated in symmetric matrices [17, 29, 39], alternating matrices [3] and Hermitian matrices [30, 37].
In this paper we will present both encoding and decoding algorithms for several optimal symmetric, alternating and Hermitian rank metric codes. Since the targeted codes are not linear over the extension field, syndrome-based decoding algorithms in [5] is not applicable. We choose interpolation-based decoding approach which is able to decode errors up to half of the minimum distance in polynomial time for all the aforementioned codes. A part of our work in this paper responds to a suggestion in [1], where the authors suggested studying the decoding of Hermitian rank metric codes.
Anzeige
2 Preliminaries
Let \(\mathbb {F}_{{\varrho }}\) denote a finite field of ϱ elements and \(\mathbb {F}_{{\varrho }}^{n\times n}\) be the set of the square matrices of order n defined over \(\mathbb {F}_{{\varrho }}\). We can equip \(\mathbb {F}_{{{\varrho }}}^{n\times n}\) with the following metric
where rk(A − B) is the rank of the difference matrix A − B. If \(\mathcal {C}\) is a subset of \(\mathbb {F}_{{{\varrho }}}^{n\times n}\) with the property that
then \(\mathcal {C}\) is called a rank metric code with minimum distance d, or that \(\mathcal {C}\) is a d-code, see e.g. [28]. A rank metric code \(\mathcal {C}\) is said to be additive if it is closed under the classical matrix addition + and said to be linear over a subfield \(\mathbb {E}\) of \(\mathbb {F}_{{{\varrho }}}\) if it is closed under both matrix addition and scalar multiplication by any element in \(\mathbb {E}\).
$$d_{r}(A,B)=\text{rk} (A-B),$$
$$d=\min\{\text{rk} (A-B) \colon A,B \in \mathcal{C}, A \ne B\},$$
Let \({\mathcal{L}}_{n, {\varrho }}\) denote the quotient \(\mathbb {F}_{{\varrho }}\)-algebra of all ϱ-polynomials over \({\mathbb {F}}_{{{\varrho }}^{n}}\) with degree smaller than n , namely,
It is well known that the \(\mathbb {F}_{{{\varrho }}}\)-algebra \({\mathcal{L}}_{n, {{\varrho }}}\) is actually isomorphic to the \(\mathbb {F}_{{{\varrho }}}\)-algebra \(\mathbb {F}_{{{\varrho }}}^{n\times n}\). Hence many rank metric codes \(\mathcal {C} \subseteq \mathbb {F}_{{{\varrho }}}^{n\times n}\) are expressed in terms of ϱ-polynomials in \({\mathcal{L}}_{n, {{\varrho }}}\). If ϱ is fixed or the context is clear, we can use the term linearized polynomials instead of ϱ-polynomials.
$$\mathcal{L}_{n,{\varrho}}=\left\{ \sum\limits_{i=0}^{n-1} a_{i} x^{{\varrho}^{i}} \colon a_{i} \in \mathbb{F}_{{\varrho}^{n}} \right\}.$$
Here we recall one important property of the Dickson matrix associated with ϱ-polynomials which is critical for the decoding in this paper.
Proposition 1
Let \(L(x)=\sum \limits _{i=0}^{n-1}a_{i}x^{{\varrho }^{i}}\) over \(\mathbb {F}_{{\varrho }^{n}}\) be a ϱ-polynomial with rank t. Then its associated Dickson matrix
has rank t over \(\mathbb {F}_{{\varrho }^{n}}\) and any t × t submatrix formed by t consecutive rows and t consecutive columns in D is non-singular.
$$D=\left( \begin{array}{l} a_{{i-j(\text{mod} n)}}^{{\varrho}^{i}} \end{array}\right)_{n\times n}=\left( \begin{array}{llll} a_{0}& a_{n-1}^{{\varrho}}& \cdots& a_{1}^{{\varrho}^{n-1}}\\ a_{1}& a_{0}^{{{\varrho}}}&\cdots& a_{2}^{{{\varrho}}^{n-1}}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n-1}& a_{n-2}^{{\varrho}}&\cdots& a_{0}^{{\varrho}^{n-1}} \end{array}\right),$$
(1)
Below we shall introduce three families of rank metric codes whose codewords have restrictive forms. The first two consist of symmetric and alternating matrices over \({\mathbb {F}}_{q}\), respectively, and the third one consists of Hermitian matrices defined over \({\mathbb {F}}_{q^{2}}\), where q is a prime power.
Recall that a matrix \(A\in \mathbb {F}_{q}^{n\times n}\) is said to be symmetric if AT = A and is said to be alternating if AT = −A, where AT is the transpose matrix of A. Let Sn(q) and An(q) be the set of all symmetric matrices and alternating matrices of order n over \(\mathbb {F}_{q}\), respectively. Following the connection given in [17], the set Sn(q) can be identified as
The set An(q) can be identified as
$${\mathcal{S}}_{n}(q)=\left\{ \sum\limits_{i=0}^{n-1} c_{i} x^{q^{i}} \colon c_{n-i}=c_{i}^{q^{n-i}} \text{ for } i \in \{0,\ldots,n-1\} \right\}\subseteq \mathcal{L}_{n,q}.$$
$${\mathcal{A}}_{n}(q)=\left\{ \sum\limits_{i=0}^{n-1} c_{i} x^{q^{i}} \colon c_{n-i}=-c_{i}^{q^{n-i}} \text{ for } i \in \{0,\ldots,n-1\} \right\}\subseteq \mathcal{L}_{n,q}.$$
Consider the conjugation map \(\overline {\cdot }\) from \(\mathbb {F}_{q^{2}}\) to itself: \(x \mapsto \overline {x} = x^{q}\). For a matrix \(A\in \mathbb {F}_{q^{2}}^{n\times n}\), we denote by A∗ the conjugate transpose of A, which is obtained by applying the conjugate map to all entries of AT. Recall that a matrix \(A\in \mathbb {F}_{q^{2}}^{n\times n}\) is said to be Hermitian if A = A∗. Let Hn(q2) be the set of all Hermitian matrices of order n over \(\mathbb {F}_{q^{2}}\). Similarly, it can be identified as
where the indices are taken modulo n. Note that if n is odd then c(n+ 1)/2 belongs to \(\mathbb {F}_{q^{n}}\).
$${\mathcal{H}}_{n}(q^{2})=\left\{ \sum\limits_{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}},$$
It can be easily verified that these three sets, together with the classical sum of matrices and the scalar multiplication by elements in \({\mathbb {F}_{q}}\), are \({\mathbb {F}_{q}}\)-vector spaces with dimensions
A subset of Sn(q), An(q) or Hn(q2) endowed with the rank distance will be termed a symmetric, alternating or Hermitian rank metric code, respectively, or symmetric, alternating or Hermitian d-code if d is the minimum distance of the considered code. With the isomorphism between \(\mathbb {F}_{{{\varrho }}}^{n\times n}\) and \({\mathcal{L}}_{n, {{\varrho }}}\), ϱ ∈{q,q2}, the codewords in these restricted rank metric codes will be represented in polynomials throughout this paper. For simplicity, we will denote by \(x^{[i]}:=x^{q^{i}}\) and \(x^{[{\kern -1.2pt}[ i]{\kern -1.2pt}]} := x^{q^{2i}}\) for any non-negative integer i.
$$\dim_{{\mathbb{F}_{q}}}(\mathrm{S}_{n}(q))=\frac{n(n+1)}{2}, \dim_{{\mathbb{F}_{q}}}(\mathrm{A}_{n}(q))=\frac{n(n-1)}{2}, \dim_{{\mathbb{F}_{q}}}(\mathrm{H}_{n}(q^{2}))=n^{2}.$$
2.1 Optimal symmetric and alternating d-codes
For symmetric and alternating rank metric codes, the following bounds on their size have been established [3, 29].
Theorem 2
[29, Theorem 3.3] Let \(\mathcal {C}\) be a symmetric d-code in \(\mathbb {F}_{q}^{n\times n}\). If d is even, suppose also that \(\mathcal {C}\) is additive. Then
$$\#\mathcal{C} \leq \left\{ \begin{array}{ll} q^{n(n-d+2)/2} & \text{if} n-d \text{is even},\\ q^{(n+1)(n-d+2)/2} & \text{if} n-d \text{is odd}. \end{array}\right.$$
Theorem 3
[3, Theorem 4] Let \(m=\lfloor \frac {n}2 \rfloor\). Let \(\mathcal {C}\) be an alternating 2e-code in \(\mathbb {F}_{q}^{n\times n}\). Then
$$\#\mathcal{C} \leq q^{\frac{n(n-1)}{2m}(m-e+1)}.$$
A symmetric (resp. alternating) d-code is said to be optimal if its parameters satisfy the equality in Theorem 2 (resp. Theorem 3). The following theorems present some instances of optimal symmetric (resp. alternating) d-codes, where \(\mathrm {Tr }_{q^{n}/q}(x)=x+x^{q}+\cdots +x^{q^{n-1}}\) is the trace function from \({\mathbb {F}}_{q^{n}}\) to \({\mathbb {F}_{q}}\).
Theorem 4
[29, Theorem 4.4] Let n and d be two positive integers such that 1 ≤ d ≤ n and n − d is even. The symmetric forms \(S:\mathbb {F}_{q^{n}}\times \mathbb {F}_{q^{n}}\rightarrow \mathbb {F}_{q}\) given by \(S(x,y)=\mathrm {Tr }_{q^{n}/q}\left (yL(x)\right )\) with
as \(b_{0},\ldots ,b_{\frac {n-d}{2}}\) range over \(\mathbb {F}_{q^{n}}\), form an additive optimal d-code in Sn(q).
$$L(x)= b_{0}x + \sum\limits_{j=1}^{\frac{n-d}{2}} \left( b_{j}x^{q^{j}}+(b_{j}x)^{q^{n-j}} \right),$$
(2)
In [29, Theorem 4.1] it has been shown that constructions of optimal symmetric d-codes with n − d odd in Sn(d) can be obtained by puncturing the examples of optimal symmetric d-codes found in [29, Theorem 4.4].
Theorem 5
[3, Theorem 7] Let n and e be two positive integers such that n is odd and 1 ≤ 2e ≤ n − 1, and let d = 2e. The alternating forms \(A:\mathbb {F}_{q^{n}}\times \mathbb {F}_{q^{n}}\rightarrow \mathbb {F}_{q}\) given by \(A(x,y)=\mathrm {Tr }_{q^{n}/q}\left (yL(x)\right )\) with
as \(b_{e},\ldots ,b_{\frac {n-1}{2}}\) range over \(\mathbb {F}_{q^{n}}\), form an additive optimal d-code in An(q).
$$L(x)= \sum\limits_{j=e}^{\frac{n-1}{2}} \left( b_{j}x^{q^{j}}-(b_{j}x)^{q^{n-j}} \right),$$
(3)
2.2 Optimal Hermitian d-codes
Schmidt characterized the upper bound on the size of Hermitian d-codes as follows [30, Theorem 1].
Theorem 6
[30, Theorem 1] An additive Hermitian d-code \(\mathcal {C}\) in \(\mathbb {F}_{q^{2}}^{n\times n}\) satisfies
Moreover, when d is odd, this upper bound holds also for non-additive Hermitian d-codes.
$$\#\mathcal{C} \leq q^{n(n-d+1)}.$$
A Hermitian d-code is called a optimal Hermitian d-code if it attains the above bound. Schmidt in [30] also gave constructions for optimal Hermitian d-codes for all possible value of n and d, except if n and d are both even and 3 < d < n. There are some examples of optimal Hermitian d-codes, see [30, 37]. We recall two examples given in [30, Theorems 4 and 5], where \(\mathrm {Tr }_{q^{2n}/q^{2}}\) is the trace function from \({\mathbb {F}}_{q^{2n}}\) to \({\mathbb {F}}_{q^{2}}\).
Theorem 7
[30, Theorem 4] Let n and d be integers of opposite parity satisfying 1 ≤ d ≤ 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 }_{q^{2n}/q^{2}}\left (y^{q}L(x)\right )\) with
as \(b_{1},\ldots ,b_{\frac {n-d+1}{2}}\) range over \(\mathbb {F}_{q^{2n}}\), form an additive optimal d-code in Hn(q2).
$$L(x)= \sum\limits_{j=1}^{\frac{n-d+1}{2}} \left( (b_{j}x)^{q^{(2n-2j+2)}}+{b_{j}^{q}} x^{q^{(2j)}} \right),$$
(4)
Theorem 8
[30, Theorem 5] Let n and d be odd integers satisfying 1 ≤ d ≤ 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 }_{q^{2n}/q^{2}}\left (y^{q}L(x)\right )\) with
as b0 ranges over \(\mathbb {F}_{q^{n}}\) and \(b_{1},\ldots ,b_{\frac {n-d}{2}}\) range over \(\mathbb {F}_{q^{2n}}\), form an additive optimal d-code in Hn(q2).
$$L(x)= (b_{0}x)^{q^{(n+1)}}+ \sum\limits_{j=1}^{\frac{n-d}{2}} \left( (b_{j}x)^{q^{(n+2j+1)}}+{b_{j}^{q}} x^{q^{(n-2j+1)}} \right),$$
(5)
3 Encoding
In the literature, no encoding method has been given for symmetric, alternating and Hermitian d-codes. This section is dedicated to the encoding of these three types of restricted d-codes. As a matter of fact, the encoding of an optimal d-code \(\mathcal {C}\) is mainly concerned with setting up a one-to-one correspondence between a message space of size \(\#\mathcal {C}\) and the code \(\mathcal {C}\) in an efficient way, which ideally also allows for an efficient decoding algorithm.
3.1 Encoding of symmetric d-codes
We start with the encoding of the optimal symmetric d-codes of size qn(n−d+ 2)/2 in Theorem 4, where n − d is even. The family of codes is linear over \(\mathbb {F}_{q}\) and the message space is naturally a vector space over \(\mathbb {F}_{q}\) with dimension n(n − d + 2)/2. But we can represent each message in the form of a k-dimensional vector over \(\mathbb {F}_{q^{n}}\) where k = (n − d + 2)/2 and the set of all the message vectors are closed under \(\mathbb {F}_{q}\)-linear operations.
In order to present a polynomial-time decoding algorithm for the optimal symmetric d-codes in Theorem 4, we shall express their codewords as evaluations of certain polynomials at linearly independent points over \({\mathbb {F}}_{q}\). For this reason, we need to employ a pair of dual bases in \({\mathbb {F}}_{q^{n}}\) over \({\mathbb {F}}_{q}\). Recall that given an ordered \({\mathbb {F}}_{q}\)-basis (α1,…,αn) of \({\mathbb {F}}_{q^{n}}\), its dual basis is defined as the ordered \({\mathbb {F}}_{q}\)-basis (β1,…,βn) of \({\mathbb {F}}_{q^{n}}\) such that
where δij denotes the Kronecker delta function. Note that a dual basis always exists for a given order basis (α1,…,αn) of \({\mathbb {F}}_{q^{n}}\) [15, Definition 2.30].
$$\text{Tr}_{q^{n}/q}(\alpha_{i}\beta_{j}) = \delta_{ij} \text{ for } i = 1, 2, \dots, n,$$
Let (α1,…,αn), (β1,…,βn) be a pair of dual bases of \(\mathbb {F}_{q^{n}}\) over \({\mathbb {F}_{q}}\). We will write \(\text {Tr}_{q^{n}/q}(x)\) as Tr(x) for simplicity when the context is clear. Let L(x) be a linearized polynomial as in Theorem 4. For the symmetric form we have
$$S(x,y)=\text{Tr}(x L(y)).$$
Now, we denote the associated matrix of S with respect to the ordered \(\mathbb {F}_{q}\)-basis (α1,…,αn) by \(\mathcal {S}\), of which the (i,j)-th entry \(\mathcal {S}(i,j)\) is given by
$$\mathcal{S}(i,j)=S(\alpha_{i}, \alpha_{j})=\text{Tr}(\alpha_{j} L(\alpha_{i})) .$$
Furthermore, the codewords of the additive d-code in Theorem 4 can be expressed in the symmetric matrix form as follows: let \(x, y \in {\mathbb {F}}_{q^{n}}\), then \(x=\sum \limits _{i=1}^{n} x_{i}\alpha _{i}\) and \(y=\sum \limits _{j=1}^{n} y_{j}\alpha _{j}\) for some \(x_{i},y_{j} \in {\mathbb {F}}_{q}\) and
$$\begin{array}{@{}rcl@{}} S(x,y)&=&\text{Tr}\left( \left( \sum\limits_{j}y_{j}\alpha_{j}\right)\sum\limits_{i}x_{i}L(\alpha_{i})\right) =\text{Tr}\left( \sum\limits_{i,j}x_{i}y_{j}\alpha_{j}L(\alpha_{i})\right)\\ &=&\sum\limits_{i,j}x_{i}y_{j}\text{Tr}\left( \alpha_{j}L(\alpha_{i})\right) = \sum\limits_{i,j}x_{i}\mathcal{S}(i,j)y_{j} =(x_{1},\ldots,x_{n})\cdot \mathcal{S}\cdot \left( \begin{array}{c} y_{1} \\ y_{2}\\ \vdots\\ y_{n} \end{array}\right), \end{array}$$
where \(\mathcal {S}(i,j)\) is the (i,j)-th entry in \(\mathcal {S}\).
In the following we show that the evaluation of the corresponding linearized polynomial at linearly independent elements α1,…,αn is a proper encoding method.
Define an n-dimensional vector over \(\mathbb {F}_{q}\) as
Since the i-th row of \(\mathcal {S}\) is given by (Tr(α1L(αi)),…,Tr(αnL(αi))) and since each L(αi) can be written as \({\sum }_{t} c_{t} \beta _{t}\) for some \(c_{t} \in {\mathbb {F}}_{q}\), we can write si as
$$s=(s_{1},\ldots,s_{n})=(\beta_{1},\ldots,\beta_{n})\cdot \mathcal{S}^{T}.$$
$$\begin{array}{@{}rcl@{}} s_{i} &=&\sum\limits_{j}\beta_{j} S(i,j) =\sum\limits_{j}\beta_{j} \text{Tr}(\alpha_{j}L(\alpha_{i})) \\ & =&\sum\limits_{j}\beta_{j}\text{Tr}\left( \alpha_{j}\sum\limits_{t}c_{t}\beta_{t}\right) =\sum\limits_{j}\beta_{j}\sum\limits_{t}c_{t}\text{Tr}(\alpha_{j}\beta_{t}) \\& =&\sum\limits_{j}\beta_{j}c_{j}=L(\alpha_{i}) \end{array}$$
since Tr(x) is linear over \(\mathbb {F}_{q}\) and (β1,…,βn) is the dual basis of (α1,…,αn). From the equality si = L(αi), we see that the encoding of symmetric d-codes given by Tr(yL(x)), as in Theorems 4 and 5, can be seen as the evaluation of L(x) at the basis (α1,…,αn) of \(\mathbb {F}_{q^{n}}\).
With the above preparation, we are now ready to look at the encoding of the optimal symmetric d-codes in Theorem 4 more explicitly.
Let (ω0,…,ωn− 1) be a basis of \(\mathbb {F}_{q^{n}}\) over \(\mathbb {F}_{q}\). For optimal symmetric d-codes in Theorem 4, the linearized polynomial can be expressed as
where k = (n − d + 2)/2. Then the encoding of a message \(f=(f_{0},\ldots , f_{k-1}) \in {\mathbb {F}}_{q^{n}}^{k}\) for the symmetric codes in Theorem 4 can be expressed as the evaluation of the following linearized polynomial at points ω0,…,ωn− 1:
where
$$L(x) = b_{0}x+\sum\limits_{j=1}^{k-1} \left( b_{j}x^{[j]}+(b_{j}x)^{[n-j]} \right),$$
$$L(x) = f_{0}x+\left( \sum\limits_{j=1}^{k-1} f_{j} x^{[j]} + (f_{j}x)^{{[n-j]}}\right) = \sum\limits_{i=0}^{n-1}\tilde{f}_{i}x^{[i]},$$
$$\begin{array}{@{}rcl@{}} \tilde{f}&=&\left( \tilde{f}_{0}, \dots,\tilde{f}_{k-1},0,\ldots,0 ,\tilde{f}_{n-k+1},\ldots,\tilde{f}_{n-1}\right) \\&=& \left( f_{0}, \dots, f_{k-1}, 0, \dots, 0, f^{[n-k+1]}_{k-1}, \dots, f^{[n-1]}_{1}\right). \end{array}$$
(6)
Let \(N= \left (\begin {array}{c} \omega _{i}^{[j]} \end {array}\right )_{n\times n}\) be the n × n Moore matrix generated by ωi’s. So the encoding of optimal symmetric and optimal alternating d-codes can be expressed as
where \(\tilde {f}=\left (\tilde {f}_{0}, \ldots , \tilde {f}_{n-1}\right )\) and NT is the transpose of the matrix N. Note that the first k and the last k − 1 elements of \(\tilde {f}\) are nonzero. This means at most n − d + 1 columns of the matrix NT are involved in the encoding process.
$$(f_{0},\ldots,f_{k-1})\mapsto (L(\omega_{0}),\ldots,L(\omega_{n-1}))=\tilde{f}\cdot N^{T},$$
(7)
3.2 Encoding of alternating d-codes
The encoding of alternating d-codes in Theorem 5 can be done similarly since the codewords in A(x,y) has the same form Tr(yL(x)) as in Theorem 4.
For alternating d-codes in Theorem 5, the linearized polynomial can be expressed as
Note that in Theorem 5, the parameters n is odd and d = 2e. The optimal alternating codes are \(\mathbb {F}_{q}\)-linear with dimension n(n − d + 1)/2. For simplicity, we again consider the message vectors in the form of vectors over \(\mathbb {F}_{q^{n}}\).
$$L(x) = \sum\limits_{j=e}^{\frac{n-1}{2}} \left( b_{j}x^{[j]}-(b_{j}x)^{[n-j]} \right).$$
Let (ω0,…,ωn− 1) be a basis of \(\mathbb {F}_{q^{n}}\) over \(\mathbb {F}_{q}\). 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 ω0,…,ωn− 1:
where
$$L(x)=\left( \sum\limits_{j=e}^{\frac{n-1}{2}} f_{j-e} x^{[j]} - (f_{j-e}x)^{{[n-j]}}\right)=\sum\limits_{i=0}^{n-1}\tilde{f}_{i}x^{[i]},$$
$$\begin{array}{@{}rcl@{}} \tilde{f}&=&\left( 0, \dots,0,\tilde{f}_{e},\ldots,\tilde{f}_{\frac{n-1}{2}},\tilde{f}_{\frac{n+1}{2}},{\ldots} ,\tilde{f}_{n-e},0,\ldots,0\right) \\&=& \left( 0,\dots,0, f_{0}, \dots, f_{k-1}, -f^{[\frac{n+1}{2}]}_{k-1}, \dots, -f^{[n-e]}_{0},0,\ldots,0\right). \end{array}$$
(8)
Similarly, the encoding of optimal alternating d-code can be expressed as
where \(\tilde {f}=\left (\tilde {f}_{0}, \ldots , \tilde {f}_{n-1}\right )\) and NT is the transpose of the matrix N. As shown in (8), at most n − d + 1 columns of the matrix N are involved in computation.
$$(f_{0},\ldots,f_{k-1})\mapsto (L(\omega_{0}),\ldots,L(\omega_{n-1}))=\tilde{f}\cdot N^{T},$$
(9)
3.3 Encoding of Hermitian d-codes
This section is dedicated to the encoding of the optimal Hermitian d-codes of size qn(n−d+ 1) explained in Theorems 7 and 8. Given positive integers d,n with 1 ≤ d ≤ n, for encoding of optimal Hermitian d-codes we are going to set up a one-to-one correspondence between a message space of size qn(n−d+ 1), and a Hermitian optimal d-code, which later permits us to decode efficiently. Therefore, for a message space of size qn(n−d+ 1), we may assume its elements as vectors over \({\mathbb {F}}_{q^{n}}\) of dimension k = n − d + 1.
For the optimal Hermitian d-codes in Theorems 7 and 8, we shall express their codewords as evaluations of certain polynomials at linearly independent points over \({\mathbb {F}}_{q^{2}}\). For this reason, we need to introduce the Hermitian variant of a basis in \({\mathbb {F}}_{q^{2n}}\) over \({\mathbb {F}}_{q^{2}}\). Given an ordered \({\mathbb {F}}_{q^{2}}\)-basis (α1,…,αn) of \({\mathbb {F}}_{q^{2n}}\), its Hermitian dual basis is defined as the ordered \({\mathbb {F}}_{q^{2}}\)-basis (β1,…,βn) of \({\mathbb {F}}_{q^{2n}}\) such that
where \(\text {Tr}_{q^{2n}/q^{2}}\) is the relative trace function from \(\mathbb {F}_{q^{2n}}\) to \(\mathbb {F}_{q^{2}}\), namely, \(\text {Tr}_{q^{2n}/q^{2}}(x)=\sum \limits _{i=0}^{n-1}x^{q^{2i}}\) and δij denotes the Kronecker delta function. Note that such a Hermitian dual basis always exists for a given order basis (α1,…,αn). Indeed, since there exist a dual basis (γ1,…,γn) for (α1,…,αn) satisfying \(\text {Tr}_{q^{2n}/q^{2}}(\alpha _{i}\gamma _{j})=\delta _{ij}\), one can simply takes \(\beta _{j} = \gamma _{j}^{q^{2n-1}}\) for \(j=1,2,\dots , n\) and then the above Hermitian dual property follows. We shall also write \(\text {Tr}_{q^{2n}/q^{2}}()\) as Tr() for simplicity whenever there is no ambiguity.
$$\text{Tr}_{q^{2n}/q^{2}}\left( {\alpha_{i}^{q}}\beta_{j}\right) = \delta_{ij} \text{ for } i = 1, 2, \dots, n,$$
Let (α1,…,αn) be an \(\mathbb {F}_{q^{2}}\)-basis of \(\mathbb {F}_{q^{2n}}\) and (β1,…,βn) be its Hermitian dual as described above. Let \(x,y \in {\mathbb {F}}_{q^{2n}}\), then \(x=\sum \limits _{i=1}^{n} x_{i} \alpha _{i}\) and \(y=\sum \limits _{i=1}^{n} y_{i} \beta _{i}\), for some \(x_{i},y_{i} \in {\mathbb {F}}_{q^{2}}\). It is clear that \(\text {Tr}(x^{q}y)=\sum \limits _{i,j=1}^{n}{x_{i}^{q}}y_{j}\text {Tr}({\alpha _{i}^{q}}\beta _{j})=\sum \limits _{i=1}^{n}{x_{i}^{q}}y_{i}=\langle ({x_{1}^{q}},\ldots ,{x_{n}^{q}}),(y_{1},\ldots ,y_{n})\rangle\).
Note that the Hermitian forms in Theorems 7 and 8 are of the form H(x,y) = Tr(xqL(y)). Now, we denote the associated matrix of H with respect to the ordered \(\mathbb {F}_{q^{2}}\)-basis (α1,…,αn) by \({\mathcal{H}}\), of which the (i,j)-th entry \({\mathcal{H}}(i,j)\) is given by
$$\mathcal{H}(i,j)=H(\alpha_{i}, \alpha_{j})=\text{Tr}\left( {\alpha_{j}^{q}} L(\alpha_{i})\right) .$$
Furthermore, the codewords of the additive d-code in Theorem 8 can be expressed in the Hermitian matrix form as follows
$$\begin{array}{@{}rcl@{}} H(x,y)&=&\text{Tr}\left( \left( \sum\limits_{j}y_{j}\alpha_{j}\right)^{q}\sum\limits_{i}x_{i}L(\alpha_{i})\right) =\text{Tr}\left( \sum\limits_{i,j}x_{i}{y_{j}^{q}}{\alpha_{j}^{q}}L(\alpha_{i})\right)\\ &=&\sum\limits_{i,j}x_{i}{y_{j}^{q}}\text{Tr}\left( {\alpha_{j}^{q}}L(\alpha_{i})\right) = \sum\limits_{i,j}x_{i}\mathcal{H}(i,j){y_{j}^{q}} =(x_{1},\ldots,x_{n})\cdot \mathcal{H}\cdot \left( \begin{array}{c} {y_{1}^{q}} \\ {y_{2}^{q}}\\ \vdots\\ {y_{n}^{q}} \end{array}\right), \end{array}$$
where \({\mathcal{H}}(i,j)\) is an element in \({\mathcal{H}}\). In the following we show that the evaluation of the corresponding linearized polynomial at linearly independent elements α1,…,αn is a proper encoding method. Define an n-dimensional vector over \({\mathbb {F}}_{q^{2}}\) as
Since the i-th row of \({\mathcal{H}}\) is given by \((\text {Tr}({\alpha _{1}^{q}}L(\alpha _{i})), \ldots , \text {Tr}({\alpha _{n}^{q}}L(\alpha _{i})))\) and since each L(αi) can be written as \({\sum }_{t} c_{t}\beta _{t}\) for some \(c_{t} \in {\mathbb {F}}_{q^{2}}\), we can write hi as
$$h=(h_{1},\ldots,h_{n})=(\beta_{1},\dots,\beta_{n})\cdot \mathcal{H}^{T}.$$
$$\begin{array}{@{}rcl@{}} h_{i} &=&\sum\limits_{j}\beta_{j} H(i,j) =\sum\limits_{j}\beta_{j} \text{Tr}\left( {\alpha_{j}^{q}}L(\alpha_{i})\right) \\ & =&\sum\limits_{j}\beta_{j}\text{Tr}\left( {\alpha_{j}^{q}}\sum\limits_{t}c_{t}\beta_{t}\right) =\sum\limits_{j}\beta_{j}\sum\limits_{t}c_{t}\text{Tr}\left( {\alpha_{j}^{q}}\beta_{t}\right) \\& = & \sum\limits_{t}\beta_{t}c_{t}=L(\alpha_{i}), \end{array}$$
where the fourth and fifth equality signs hold because Tr(x) is linear over \(\mathbb {F}_{q^{2}}\) and (β1,…,βn) is the Hermitian dual basis of (α1,…,αn). From the equality hi = L(αi), we see that the encoding of Hermitian d-codes given by Tr(yqL(x)), as in Theorems 7 and 8, can be seen as the evaluation of L(x) at the basis (α1,…,αn) of \(\mathbb {F}_{q^{2n}}\).
With the above preparation, we are now ready to look at the encoding of the Hermitian d-codes in Theorems 7 and 8 more explicitly.
Let \(\kappa =\lceil \frac {n-d}{2}\rceil\) and H be the Hermitian form given in Theorem 7. The linearized polynomial in (4) can be written as
and assuming \(m=\frac {n+1}{2}\), similarly one can write the linearized polynomial in (5) as
$$L(x) = \sum\limits_{j=1}^{\kappa} \left( (b_{j}x)^{[{\kern-1.2pt}[ n+1-j]{\kern-1.2pt}]}+{b_{j}^{q}} x^{[{\kern-1.2pt}[ j]{\kern-1.2pt}] } \right),$$
$$L(x) = (b_{0}x)^{[{\kern-1.2pt}[ m]{\kern-1.2pt}] } + \sum\limits_{j=1}^{\kappa} \left( (b_{j}x)^{[{\kern-1.2pt}[ m+j]{\kern-1.2pt}] }+{b_{j}^{q}} x^{[{\kern-1.2pt}[ m-j{]{\kern-1.2pt}]}} \right).$$
Let {1,η} be an \(\mathbb {F}_{q^{n}}\)-basis of \(\mathbb {F}_{q^{2n}}\). Let α0,α1,…,αn− 1 be a basis of \({\mathbb {F}}_{q^{2n}}\) over \(\mathbb {F}_{q^{2}}\). Raising all the basis elements αi to the q2-th power will still give a linearly independent set of elements in \(\mathbb {F}_{q^{2n}}\). We use \(\alpha _{0}^{q^{2}},\alpha _{1}^{q^{2}}, \ldots , \alpha _{n-1}^{q^{2}}\) as the evaluation points for optimal Hermitian d-codes in Theorem 7. The reason for this is to keep the consistent form \(L(x)=l_{0}x^{{[{\kern -1.2pt}[} 0 {]{\kern -1.2pt}]}}+l_{1}x^{{[{\kern -1.2pt}[} 1 {]{\kern -1.2pt}]}}+\cdots +l_{n-1}x^{{[{\kern -1.2pt}[} n-1 {]{\kern -1.2pt}]}}\) for the linearized polynomial representation (employing α0,…,αn− 1 as the evaluation points for this codes will obligate us to use the linearized polynomial of the form \(L(x)=l_{0}x^{{[{\kern -1.2pt}[} 1 {]{\kern -1.2pt}]}}+l_{1}x^{{[{\kern -1.2pt}[} 2 {]{\kern -1.2pt}]}}+\cdots +l_{n-1}x^{{[{\kern -1.2pt}[} n {]{\kern -1.2pt}]}}\)).
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}^{q^{2}},\alpha _{1}^{q^{2}}, \ldots , \alpha _{n-1}^{q^{2}}\):
where
and k = 2κ. For the optimal Hermitian d-code in Theorem 8 and the evaluation points α0,α1,…,α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 α0,α1,…,αn− 1:
where
and k = 2κ + 1. The first \(\frac {d+1}{2}\) and the last \(\frac {d-3}{2}\) coefficients of \(\tilde {f}\) are zero.
$$L(x) = \left( \sum\limits_{j=0}^{\kappa-1} (f_{j}+\eta f_{\kappa+j})^{q}x^{[{\kern-1.2pt}[ n-1-j ]{\kern-1.2pt}]} + (f_{j}+\eta f_{\kappa+j}x)^{[{\kern-1.2pt}[ j]{\kern-1.2pt}] }\right) =\sum\limits_{i=0}^{n-1}\tilde{f}_{i}x^{[{\kern-1.2pt}[ i ]{\kern-1.2pt}]},$$
(10)
$$\begin{array}{@{}rcl@{}} \tilde{f}&=&\left( \tilde{f}_{0}, \dots,\tilde{f}_{\kappa-1},0,\ldots,0,\tilde{f}_{n-\kappa},\ldots, \tilde{f}_{n-1}\right) = ((f_{0}+\eta f_{\kappa})^{[{\kern-1.2pt}[ 0]{\kern-1.2pt}]},\dots,\\&&(f_{\kappa-1}+ \eta f_{2\kappa-1})^{[{\kern-1.2pt}[ \kappa-1]{\kern-1.2pt}]},0, \dots, 0, (f_{\kappa-1}+ \eta f_{2\kappa-1})^{q},\ldots,(f_{0}+ \eta f_{\kappa})^{q}), \end{array}$$
(11)
$$\begin{array}{@{}rcl@{}} L(x)&=& (f_{0}x)^{[{\kern-1.2pt}[ m ]{\kern-1.2pt}]} + \left( \sum\limits_{j=1}^{\kappa} \left( f_{j}+\eta f_{\kappa+j}\right)^{q}x^{[{\kern-1.2pt}[ m-j]{\kern-1.2pt}]} +\left( (f_{j}+ \eta f_{\kappa+j})x\right)^{{[{\kern-1.2pt}[} m+j{]{\kern-1.2pt}]}}\right) \\&=&\sum\limits_{i=0}^{n-1}\tilde{f}_{i}x^{[{\kern-1.2pt}[ i]{\kern-1.2pt}]}, \end{array}$$
(12)
$$\begin{array}{@{}rcl@{}} \tilde{f}&=&\left( 0, \dots,0,\tilde{f}_{m-\kappa},\ldots,\tilde{f}_{m-1},\tilde{f}_{m},\tilde{f}_{m+1},\ldots,\tilde{f}_{m+\kappa},0,\ldots, 0\right)\\&=& (0,\dots,0,(f_{\kappa}+\eta f_{2\kappa})^{q},\ldots,(f_{1}+\eta f_{\kappa+1})^{q},f_{0}^{[{\kern-1.2pt}[ m ]{\kern-1.2pt}]},\\&&(f_{1}+\eta f_{\kappa+1})^{{[{\kern-1.2pt}[} m+1]{\kern-1.2pt}]},\ldots,(f_{\kappa}+\eta f_{2\kappa})^{{[{\kern-1.2pt}[} m+\kappa]{\kern-1.2pt}]},0,\ldots,0 ), \end{array}$$
(13)
Let \(M_{l}= \left (\begin {array}{c} \alpha _{i}^{[{\kern -1.2pt}[ j+l]{\kern -1.2pt}] } \end {array}\right )_{n\times n}\) be the n × n Moore matrix generated by \(\alpha _{0}^{q^{2l}},\alpha _{1}^{q^{2l}}, \ldots , \alpha _{n-1}^{q^{2l}}\) where l ∈{0,1}. We take l = 1 when we consider \(\alpha _{0}^{q^{2}},\alpha _{1}^{q^{2}}, \ldots , \alpha _{n-1}^{q^{2}}\) as the evaluation points which is used in (10) and l = 0 when α0,α1,…,αn− 1 are the evaluation points in (12).
So the encoding of the optimal Hermitian rank metric codes can be expressed as
where \(\tilde {f}=\left (\tilde {f}_{0},\ldots ,\tilde {f}_{n-1}\right )\) and \({M_{l}^{T}}\) is the transpose of the matrix Ml.
$$(f_{0},\ldots,f_{k-1})\mapsto \left( L\left( \alpha_{0}^{q^{2l}}\right),\ldots,L\left( \alpha_{n-1}^{q^{2l}}\right)\right)=\tilde{f}\cdot {M_{l}^{T}},$$
(14)
When n,d are integers with opposite parities as shown in (10), only the first κ and the last κ elements of \(\tilde {f}\) are nonzero. Also in the case when n,d are both odd integers, as can be seen in (12), the first m − κ and the last m − κ − 2 elements of \(\tilde {f}\) are zero. So we only use n − d + 1 columns of the Moore matrix in the encoding process.
In summary, the encoding of the optimal symmetric, alternating and Hermitian d-codes relies on converting the codewords of those codes to simplified linearized polynomials L(x) under carefully-chosen base of the extension fields, which enables us to treat encoding of those codes as evaluations of L(x) at linearly independent points.
4 Decoding
In Section 3 the encodings of symmetric, alternating and Hermitian d-codes are in the form of polynomial evaluation. In this section we will present interpolation-based decoding of those codes, which make use of some nice properties of Dickson matrices in Proposition 1.
4.1 Key equations for error interpolation polynomials
We start with the optimal symmetric and alternating d-codes in Theorems 4 and 5. Note that their codewords are in the form Tr(yL(x)) and can be deemed as n-dimensional vectors \((L(\omega _{0}), \dots , L(\omega _{n-1}))\) over \({\mathbb {F}}_{q^{n}}\). We assume errors that occur in transmission or storage medium are also vectors in \({\mathbb {F}}_{q^{n}}^{n}\).
Given a message \(f=(f_{0},\dots , f_{k-1})\in \mathbb {F}_{q^{n}}^{k}\), its corresponding codeword \(c=\tilde {f}\cdot N^{T}\), where \(\tilde {f}\) and NT are as given in Section 3. Let \(r=(r_{0}, \dots , r_{n-1})\) over \({\mathbb {F}}_{q^{n}}\) be a received word when the codeword \(c\in {\mathbb {F}}_{q^{n}}^{n}\) is transmitted, namely, r = c + e for certain error vector \(e \in {\mathbb {F}}_{q^{n}}^{n}\). Suppose \(g(x)=\sum \limits _{i=0}^{n-1}g_{i}x^{[i]}\) is the error interpolation polynomial such that
Clearly the error vector e is uniquely determined by the error interpolation polynomial g(x), and vice versa. Denote \(\tilde {g}=(g_{0},\ldots , g_{n-1})\). Then it follows that
$$g(\omega_{i})=e_{i}=r_{i}-c_{i}, \quad i=0, \ldots, n-1.$$
(15)
$$r = c+e = (\tilde{f}+\tilde{g}) N^{T}.$$
(16)
Denote by G the associated Dickson matrix of the q-polynomial g(x), i.e.,
where the subscripts are taken modulo n. Suppose the error e has rank t, by Proposition 1 we know that G has rank t and any t × t submatrix formed by t consecutive rows and columns in G has rank t. Furthermore, the first column of G can be expressed as a linear combination of \(G_{1}, \dots , G_{t}\) as
where \(G_{1},\dots , G_{t}\) are linearly independent over \(\mathbb {F}_{q^{n}}\).
$$G=\left( \begin{array}{ll}g^{[ j] }_{i-j~(\text{mod~}n)} \end{array}\right)_{n\times n} = \left( G_{0} G_{1} {\ldots} G_{n-1}\right) =\left[\begin{array}{cccc} g_{0} & g_{n-1}^{[1]}& {\ldots} & g_{1}^{[n-1]}\\ g_{1} & g_{0}^{[1]} & {\ldots} & g_{2}^{[n-1]}\\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ g_{n-1} & g_{n-2}^{[1]} & {\ldots} & g_{0}^{[n-1]} \end{array}\right],$$
$$G_{0} = \lambda_{1}G_{1}+{\cdots} + \lambda_{t}G_{t},$$
(17)
In the following we will make use of the pattern of L(x) in Theorems 4 and 5, which have consecutive d − 1 zero coefficients (up to a cyclic shift on the coefficients), and the properties of G in recovering the vector \(\tilde {g}\).
4.1.1 Optimal symmetric d-codes in Theorem 4
For optimal symmetric d-codes, by (6) we can rewrite (16) as
$$\begin{array}{@{}rcl@{}} r \cdot \left( N^{T}\right)^{-1}&=&\left( \tilde{f}_{0},\ldots,\tilde{f}_{k-1},0, \ldots,0,\tilde{f}_{n-k+1},\ldots,\tilde{f}_{n-1}\right) \\&&+ \left( g_{0}, \ldots,g_{k-1}, g_{k},\ldots, g_{n-k},g_{n-k+1}, \ldots, g_{n-1}\right). \end{array}$$
where \(\tilde {f}_{0}=f_{0}^{[0]}\), \(\tilde {f}_{j} = f_{j}\) and \(\tilde {f}_{j}=\tilde {f}_{n-j}^{[n-j]}\) for j = 1,…,k − 1. Recall that k = (n − d + 2)/2 for symmetric d-codes in Theorem 4. Letting \(\beta =(\beta _{0}, \ldots , \beta _{n-1})=r \cdot \left (N^{T}\right )^{-1}\), we obtain
where the subscripts are taken modulo n. Since the elements gk,…,gn−k are known, from (17) we can have the following system of linear equations:
which contains t unknowns λ1,…,λt in d − 1 − t linear equations.
$$g_{i} = \begin{cases} \beta_{i} &\text{ for } i= k, \dots, k+d-2,\\ \beta_{i} - \tilde{f}_{i} & \text{ for } i=n-k+1, \dots, n-2k+1, \end{cases}$$
(18)
$$g_{i} = \lambda_{1} g^{[1]}_{i-1} + \lambda_{2} g^{[2]}_{i-2} + {\cdots} + \lambda_{t} g^{[t]}_{i-t}, k+t \leq i\leq n-k,$$
(19)
4.1.2 Optimal alternating d-codes in Theorem 5
From (8) it follows that (16) is equivalent to
$$\begin{array}{@{}rcl@{}} r \cdot \left( N^{T}\right)^{-1}&=&\left( 0,\ldots,0,\tilde{f}_{e},\ldots,\tilde{f}_{n-e},0,\ldots,0 \right) \\&&+ (g_{0}, \ldots,g_{e-1}, g_{e},\ldots, g_{n-e},g_{n-e+1}, \ldots, g_{n-1}). \end{array}$$
where \(\tilde {f}_{j+e}=f_{j}\) and \(\tilde {f}_{n-e+j}=-f_{j}^{[n-e-j]}\) for j = 0,…,k. Suppose we have \(\beta =(\beta _{0}, \ldots , \beta _{n-1})=r \cdot \left (N^{T}\right )^{-1}\), similarly we obtain
where the subscripts are taken modulo n. Based on (20), we obtain the following linear system of equations
with t unknowns λ1.…,λt in 2e − 1 − t = d − 1 − t linear equations.
$$g_{i} = \left\{\begin{array}{ll} \beta_{i} &\text{ for } i =n-e+1, \dots, n+e-1,\\ \beta_{i} - \tilde{f}_{i} & \text{ for } i=e,\ldots, n-e, \end{array}\right.$$
(20)
$$g_{i} = \lambda_{1} g^{[1]}_{i-1} + \lambda_{2} g^{[2]}_{i-2} + {\cdots} + \lambda_{t} g^{[t]}_{i-t}, n-e+1+t \leq i<n+e \mod n$$
(21)
4.1.3 Optimal Hermitian d-codes
The approach of establishing the key equations in decoding Hermitian d-codes is similar to that for symmetric and alternating d-codes. Because Hermitian d-codes are defined over \(\mathbb {F}_{q^{2}}\) instead of \(\mathbb {F}_{q}\), we briefly describe the process in the sequel.
Suppose a Hermitian codeword \(c \in \mathbb {F}_{q^{2n}}^{n}\) is transmitted and a word r = c + e, with an error e with rank t added to the codeword c, is received. Suppose \(g(x)=\sum \limits _{i=0}^{n-1}g_{i}x^{{[{\kern -1.2pt}[} i{]{\kern -1.2pt}]}}\) is an error interpolation polynomial with rank t such that
where we use l = 1 for the Hermitian d-codes in Theorem 7 and l = 0 for the codes in Theorem 8. It is clear that the error vector e = (e0,…,en− 1) is uniquely determined by the polynomial g(x). Denote by
the Dickson matrix associated with g(x), then G has rank t and we can express
with unknown λi’s in \(\mathbb {F}_{q^{2n}}\).
$$g\left( \alpha_{i}^{[{\kern-1.2pt}[ l ]{\kern-1.2pt}]}\right)=e_{i}=r_{i}-c_{i}, \quad i=0, \ldots, n-1 \text{ and }l\in \{0,1\},$$
(22)
$$G=(G_{0}, \dots, G_{n-1}) = \left( \begin{array}{ll} g^{[{\kern-1.2pt}[ j ]{\kern-1.2pt}] }_{i-j~(\text{mod~}n)} \end{array}\right),$$
$$G_{0} = \lambda_{1}G_{1}+{\cdots} + \lambda_{t}G_{t},$$
(23)
Denote \(\tilde {g}=(g_{0},\ldots , g_{n-1})\). From (14) and (22) it follows that
$$r = c+e = (\tilde{f}+\tilde{g}) {M_{l}^{T}}.$$
(24)
Case 1. This case considers the optimal Hermitian d-codes in Theorem 7. Recall that in Theorem 7 the Hermitian d-codes have parameters n,d with opposite parities and the message space was represented in k-dimensional vectors over \(\mathbb {F}_{q^{n}}\) which are closed under \(\mathbb {F}_{q}\)-linear operations. Denoting \(\kappa = \lceil \frac {n-d}{2}\rceil\), we can rewrite (24) as
$$\begin{array}{@{}rcl@{}} r \cdot \left( {M_{1}^{T}}\right)^{-1}&=&\left( \tilde{f}_{0},\ldots,\tilde{f}_{\kappa-1},0, \ldots,0,\tilde{f}_{n-\kappa},\ldots,\tilde{f}_{n-1}\right) \\&& + (g_{0}, \ldots,g_{\kappa-1}, g_{\kappa},\ldots, g_{n-\kappa-1},g_{n-\kappa}, \ldots, g_{n-1}), \end{array}$$
where for j = 0,1,…,κ − 1, \(\tilde {f}_{n-j-1} = (f_{j}+\eta f_{\kappa +j})^{q} \text { and } \tilde {f}_{j} = \tilde {f}_{n-j-1}^{q^{2j+1}}\), and {1,η} is an \(\mathbb {F}_{q^{n}}\)-basis of \(\mathbb {F}_{q^{2n}}\).
Let \(\beta =(\beta _{0}, \ldots , \beta _{n-1})=r \cdot ({M_{1}^{T}})^{-1}\). Since 2κ = n − d + 1, we have n − κ − 1 = κ + d − 2 and
This together with (23) gives a system of d − 1 − t linear equations over \(\mathbb {F}_{q^{2n}}\) with t unknowns λi’s in \({\mathbb {F}}_{q^{2n}}\).
$$g_{i} = \left\{\begin{array}{ll} \beta_{i} &\text{ for } i =\kappa, \dots, \kappa+d-2\\ \beta_{i} - \tilde{f}_{i} & \text{ for } i=n-\kappa, \dots, n+\kappa-1. \end{array}\right.$$
(25)
Case 2. This case considers the optimal Hermitian d-codes in Theorem 8. In this case n,d are both odd integers. Denote m = (n + 1)/2 and κ = (n − d)/2. Note that (24) is equivalent to
$$\begin{array}{@{}rcl@{}} r \cdot \left( {M_{0}^{T}}\right)^{-1}&=&\left( 0,\ldots,0,\tilde{f}_{m-\kappa}, \ldots,\tilde{f}_{m+\kappa}, 0,\ldots,0\right) \\& &+ (g_{0}, \ldots,g_{m-\kappa-1}, g_{m-\kappa},\ldots, g_{m+\kappa},g_{m+\kappa+1}, \ldots, g_{n-1}). \end{array}$$
where \(\tilde {f}_{m} = f_{0}^{[{\kern -1.2pt}[ m]{\kern -1.2pt}]}\) and for j = 1,2,⋯ ,κ, \(\tilde {f}_{m-j} = (f_{j}+\eta f_{\kappa +j})^{q} \text { and } \tilde {f}_{m+j} = \tilde {f}_{m-j}^{q^{n+2j}}\). Denote \(\beta =(\beta _{0}, \ldots , \beta _{n-1})=r \cdot ({M_{0}^{T}})^{-1}\). Since κ = (n − d)/2, we have n − 1 − (m + κ + 1) + 1 + (m − κ) = n − 2κ − 1 = d − 1 known gi’s and we can obtain
where the subscripts are taken modulo n. Similarly, this together with (23) gives a system of d − 1 − t linear equations over \({\mathbb {F}}_{q^{2n}}\) with t unknowns λi’s in \({\mathbb {F}}_{q^{2n}}\).
$$g_{i} = \left\{\begin{array}{ll} \beta_{i} &\text{ for } i =m+\kappa+1, \dots, m+\kappa+d-1\\ \beta_{i} - \tilde{f}_{i} & \text{ for } i=m-\kappa, \dots, m+\kappa, \end{array}\right.$$
(26)
4.2 Reconstruction of the error polynomial
Recall that the error polynomials g(x) for symmetric and alternating d-codes are q-polynomials over \({\mathbb {F}}_{q^{n}}\) and the one for Hermitian d-codes are q2-polynomials over \({\mathbb {F}}_{q^{2n}}\). Despite the difference in representation, the approach used for recovering the coefficients will be the same for those error polynomials. This observation allows us to present the common procedure of reconstructing g(x)’s in a unified manner.
Let ϱ ∈{q,q2}. Given an error polynomial \(g(x)=\sum \limits _{i=0}^{n-1} \in \mathbb {F}_{{\varrho }^{n}}[x]\) with rank t, its associate Dickson matrix given by
also has rank t and G0 = λ1G1 + ⋯ + λtGt for t unknown λi’s in \(\mathbb {F}_{{\varrho }^{n}}\), which gives rise to a linearized recurrence as
where the subscripts of gi’s are taken modulo n. For the optimal symmetric, alternating and Hermitian d-codes in Section 2, Section 4.1 has established a system of d − 1 − t linear equations over \({\mathbb {F}}_{{{\varrho }}^{n}}\) in t unknowns \(\lambda _{i} \in {\mathbb {F}}_{{{\varrho }}^{n}}\) for each of them.
$$G=(G_{0}, G_{1},\dots, G_{n-1}) = \left( \begin{array}{ll} g_{i-j({\text{mod }n})}^{{\varrho}^{i}} \end{array}\right)_{n\times n}$$
$$g_{L} = \lambda_{1} g_{L-1}^{{\varrho}} + \lambda_{2} g_{L-2}^{{\varrho}^{2}} + {\cdots} + \lambda_{t} g_{L-t}^{{\varrho}^{t}} \text{ for } L=0, 1, \dots,n-1$$
(27)
According to the pattern in G, we have the following major steps for recovering the coefficients gi’s:
-
Step 1. derive the unknowns λ1,…,λt from the d − 1 − t linear equations given in Section 4.1 for each optimal d-code;
-
Step 2. use λ1,…,λt to recursively compute unknown gi’s in G.
Step 1 is the critical step in the decoding process. In Step 1 one has a system of d − 1 − t linear equations for each optimal d-codes with t unknowns. There are two options for solving the unknowns. The first option is simply applying Gaussian elimination algorithm on the equations; and the second option is to apply the modified Berlekamp-Massey algorithm in [33]. As a matter of fact, with the linearized recurrence in (27), the task of Step 1 becomes finding the coefficients of modified version of a linear shift register as in [33] for given d − 1 consecutive inputs gi’s for each optimal d-codes.
For Step 2, with the recursive relation in (27), one can calculate the remaining unknown coefficients gi’s in a sequential order.
4.3 Reconstruction of the original message
Recall that for each optimal d-code, it is assumed that a codeword c is transmitted and a word r = c + e is received. With the error polynomials g(x) obtained in Section 4.2, we are directly able to derive the codeword c = r − e. With the codeword c, we can obtain the coefficient vector \(\tilde {f}\) of the interpolation polynomial \(f(x)=\sum \limits _{i=0}^{n-1}\tilde {f}_{i}x^{q^{ui}}\) where u ∈{1,2}. One can compute \(\tilde {f}=(\tilde {f}_{0},\ldots ,\tilde {f}_{n-1})=c\cdot (\mathcal {A}^{T})^{-1}\) where \(\mathcal {A}\) is the Moore matrix associated with the linearly independent evaluation points. When the \(\tilde {f}\) is obtained, we can further reconstruct the original message f = (f0,…,fk− 1) according to the encoding for each optimal d-code as follows:
-
Symmetricd-codes.$$f=(f_{0},\ldots,f_{k-1})=\left( \tilde{f}_{0},\ldots,\tilde{f}_{k-1}\right).$$
-
Alternatingd-codes.$$f=(f_{0},\ldots,f_{k-1})=\left( \tilde{f}_{e},\ldots,\tilde{f}_{\frac{n-1}{2}}\right).$$
-
Hermitian d-codes.
-
Case 1. When n,d have different parities: for j ∈{0,…,κ − 1} where k = 2κ we have the following equationsThe unknown coefficients \(f_{j},f_{k+j}\in \mathbb {F}_{q^{n}}\) for j ∈{0,…,κ − 1} can be seen as the unique coordinate vector of \(\tilde {f}_{j}^{q^{-2j}}\) (or \(\tilde {f}_{n-j-1}^{q^{-1}}\)) expressed with respect to the basis {1,η} of \(\mathbb {F}_{q^{2n}}\) over \(\mathbb {F}_{q^{n}}\) and can be computed directly.$$\left\{\begin{array}{ll} \tilde{f}_{j}&=(f_{j}+\eta f_{\kappa+j})^{q^{2j}} \\ \tilde{f}_{n-j-1}&=(f_{j}+\eta f_{\kappa+j})^{q} . \end{array}\right.$$(28)
-
Case 2. When n,d are both odd: for j ∈ 1,…,κ − 1 where k = 2κ + 1 we have the following linear system of equations$$\left\{\begin{array}{ll} \tilde{f}_{m}&=f_{0}^{q^{2m}}\\ \tilde{f}_{m+j}&=(f_{j}+\eta f_{\kappa+j})^{q^{2(m+j)}} \\ \tilde{f}_{m-j}&=(f_{j}+\eta f_{\kappa+j})^{q} . \end{array}\right.$$(29)The coefficient f0 can be computed from the first equation as \(f_{0}=\tilde {f}_{m}^{q^{-2m}}\). Similar to the Case 1, the unknown coefficients fj,fj+κ can be seen as coordinate vector of \(\tilde {f}_{m-j}^{q^{-1}}\) (or \(\tilde {f}_{m+j}^{q^{-2(m+j)}}\)) written with respect to the basis {1,η}. So we can compute all the unknown coefficients \(f_{0},\ldots , f_{k-1}\in \mathbb {F}_{q^{n}}\) and recover the message.
-
4.4 Summary
The decoding algorithms in Section 4 share some similarities and one can summarize the decoding algorithms for all the restricted codes as follows:
-
Input: a received word r = (r0,…,rn− 1) with errors of \(t\leq \frac {d-1}{2}\) rank and linearly independent points 𝜃0,…,𝜃n− 1 in \(\mathbb {F}_{q^{un}}\) where u ∈{1,2}.
-
Idea: Reconstructing the code’s interpolation polynomial \(f(x)=\sum \limits _{i=0}^{n-1}\tilde {f}_{i}x^{q^{ui}}\) via the error interpolation polynomial \(g(x)=\sum \limits _{i=0}^{n-1}g_{i}x^{q^{ui}}\) where f(𝜃i) + g(𝜃i) = ci + ei = ri.
-
Output: The codeword c = r − e.
(1)
Compute the coefficients βi of the polynomial \(\beta (x)=\sum \limits _{i=0}^{n-1}\beta _{i}x^{q^{ui}}\) where ri = β(𝜃i). This is equivalent to \(r\cdot ({\mathcal{M}}^{T})^{-1}\), where \({\mathcal{M}}\) is the Moore matrix associated with 𝜃i’s.
(2)
Specify the known coefficients (gj,…,gj+d− 2) = (βj,…,βj+d− 2), where the subscripts are taken modulo n, based on the code.
(3)
Use the 2t known coefficients gi as the initial state in the BM algorithm and find the unique connection vector λ = (λ1,…,λt).
(4)
Let G be the Dickson matrix associated with g(x) with rank t. Write the first column G0 as the linear combination of the columns G1,…,Gt which can be written as the following recursive equations
$$g_{i} = \lambda_{1} g^{q^{u}}_{i-1} + \lambda_{2} g^{q^{2u} }_{i-2} + {\cdots} + \lambda_{t} g^{q^{tu}}_{i-t}, \quad 0\leq i < n.$$
(30)
(6)
Compute \(\tilde {f}=(\beta _{0},\ldots ,\beta _{n-1})-(g_{0},\ldots ,g_{n-1})\).
(7)
Compute the codeword \(c=\tilde {f}\cdot {\mathcal{M}}^{\mathcal {T}^{-1}}\).
The lines (1) and (7) in the above procedure need \(\mathcal {O}(n^{3})\) operations over \(\mathbb {F}_{q^{un}}\) which can be optimized if one applies the ideas in [23]. The line (2) needs linear complexity while the line (3) dominates the complexity of the whole process. The BM algorithm has complexity in the order of \(\mathcal {O}(n^{2})\) operations over \(\mathbb {F}_{q^{un}}\). The complexity of the the remaining steps can be neglected.
4.5 Examples
Example 1 (Symmetric d-Codes)
Let C be an optimal symmetric d-code with minimum distance d = 5 and length n = 7 defined over \(\mathbb {F}_{2^{7}}\). We consider a normal basis of \(\mathbb {F}_{2^{7}}\) over \(\mathbb {F}_{2}\) with normal element w = z95 as the evaluation points. Here z is a primitive element in \(\mathbb {F}_{2^{7}}^{*}\).
-
Encoding: Suppose Alice wants to transfer the message \(f=(f_{0},f_{1})=\left (z^{7}, z^{13}\right )\) to Bob via a noisy channel. The code’s evaluation polynomial would have the coefficient vector \(\tilde {f}=\left (f_{0},f_{1},0,0,0,0,f_{1}^{q^{6}}\right )=\left (z^{7}, z^{13}, 0, 0, 0, 0, z^{70}\right )\) which gives the codeword$$\begin{array}{@{}rcl@{}} c=\tilde{f}\left( \mathcal{M}^{T}\right)=\left( z^{108}, z^{36}, z^{11}, z^{12}, z^{57}, z^{24}, z\right)=\left( \begin{array}{lllllll} 1 &0& 1& 1& 1& 1& 0\\ 0& 0 &1 &0 &0 &1 &0\\ 1& 1& 0& 0& 1& 0& 1\\ 1& 0& 0& 0& 0& 0& 1\\ 1& 0& 1& 0& 1& 0& 1\\ 1 &1& 0& 0& 0& 0&0\\ 0& 0& 1& 1& 1& 0& 1 \end{array}\right), \end{array}$$in symmetric form.
-
Channel’s transmission: We assume that the noisy channel adds an error vector \(e=\left (z^{63}, z^{126}, z^{126}, z^{63}, z^{126}, z^{126}, z^{126}\right )\) with rank t = 2 to the codeword c and Bob receives the word$$r=c+e=\left( z^{4}, z^{45}, z^{124}, z^{52}, z^{37}, z^{104}, z^{13}\right).$$
-
Decoding: Now Bob received r and he wants to recover the message f. He first computes \(\beta =r\cdot ({\mathcal{M}}^{T})^{-1}=\left (z^{17}, z^{51}, z^{98}, z^{124}, z^{100}, z^{83}, z^{86} \right )\) and directly gets the coefficients (g2,g3,g4,g5) = (β2,β3,β4,β5) where \(g(x)=\sum \limits _{i=0}^{6}g_{i}x^{2^{i}}\) is the error interpolation polynomial and \(\tilde {g}=(g_{0},\ldots ,g_{6})\). Then he submits (g2,g3,g4,g5) in the BM algorithm and obtains the unique connection vector \((\lambda _{1},\lambda _{2})=\left (z^{25},z^{126}\right )\). Now he uses both (g2,g3,g4,g5) and (λ1,λ2) as inputs for modified version of LFSR described in [33] and get the vectorNow he can rearrange the components of a and gets \(\tilde {g}=\left (z^{115}, z^{71},z^{98}, z^{124}, z^{100}, z^{83}, z^{55}\right )\). Since he knows β and \(\tilde {g}\), he is able to compute \(\tilde {f}=\beta -\tilde {g}=\left (z^{7}, z^{13}, 0, 0, 0, 0, z^{70}\right )\) and finally \(f=\left (\tilde {f}_{0},\tilde {f}_{1}\right )=\left (z^{7},z^{13}\right )\).$$a=(g_{2},g_{3},g_{4},g_{5},g_{6},g_{0},g_{1})=\left( z^{98}, z^{124}, z^{100}, z^{83}, z^{55}, z^{115}, z^{71}\right).$$
Example 2 (Alternating d-Codes)
Suppose \(D\in \mathbb {F}_{2^{9}}\) be an alternating d-code with length n = 9 and minimum distance d = 6. Let w = z347 be the normal element for our normal basis which is used as the interpolation points. For the received word \(r=\left (z^{293}, z^{389}, z^{430}, z^{227}, z^{481}, z^{445}, z^{426}, z^{404}, z^{339}\right )\) containing error of t = ⌊(d − 1)/2⌋ = 2 rank, we can compute \(\beta , (\lambda _{1},\lambda _{2}),a, \tilde {g}, \tilde {f}, c\) and f similar to Example 1 as follows:
-
\(\beta =\left (z^{486}, z^{233}, z^{334}, z^{155}, z^{167}, z^{226}, z^{483}, z^{231}, z^{88}\right )\),
-
(β0,β1,β2,β7,β8) = (g0,g1,g2,g7,g8).
-
BM algorithm input (β7,β8,β0,β1,β2) gives \((\lambda _{1},\lambda _{2})=\left (z^{154}, z^{262}\right )\),
-
modified LFSR input (β7,β8,β0,β1,β2) and (λ1,λ2) gives$$\begin{array}{@{}rcl@{}} a&=&(\beta_{7},\beta_{8},\beta_{0},\beta_{1},\beta_{2}, g_{3},g_{4},g_{5},g_{6})\\&=&\left( z^{231}, z^{88},z^{486}, z^{233}, z^{334}, z^{505}, z^{113}, z^{265}, z^{425}\right), \end{array}$$
-
\(\tilde {g}=\left (z^{486}, z^{233}, z^{334}, z^{505}, z^{113}, z^{265}, z^{425},z^{231}, z^{88}\right )\),
-
\(\tilde {f}=\beta - \tilde {g}=\left (0, 0, 0, z^{77}, z^{397}, z^{440}, z^{329}, 0, 0\right )\),
-
\(c=\tilde {f}\cdot ({\mathcal{M}}^{T})=\left (z^{244}, z^{412}, z^{364}, z^{400}, z^{368}, z^{161}, z^{122}, z^{59}, z^{122}\right )\),
-
\(f=(f_{0},f_{1})=\left (\tilde {f}_{3},\tilde {f}_{4}\right )=\left (z^{77}, z^{397}\right )\).
Example 3 (Hermitian d-Codes)
Suppose \(\mathcal {C}\in \mathbb {F}_{2^{14}}^{7}\) be an optimal Hermitian d-code with length n = 7, minimum distance d = 5 and η = z. We use the normal basis W of \(\mathbb {F}_{2^{14}}\) over \(\mathbb {F}_{2^{2}}\) with normal element w = z8591 as the evaluation points, where z is the primitive element in \(\mathbb {F}_{2^{10}}^{*}\). Let \(r=\left (z^{3672}, z^{2957}, z^{1343}, z^{3039}, z^{10923}, z^{9913}, z^{1618}\right )\) be a received word with error of t = (d − 1)/2 = 2 rank. Then \(\beta =r\cdot ({\mathcal{M}}^{T})^{-1}= \left (z^{5036}, z^{5234}, z^{203}, z^{840}, z^{2939}, z^{13080}, z^{15830}\right )\). Let \(g(x)=\sum \limits _{i=0}^{6}g_{i}x^{2^{2i}}\) be the error interpolation polynomial. Due to the expected form of \(\tilde {f}\) in optimal Hermitian d-codes we have (β0,β1,β2,β6) = (g0,g1,g2,g6). Now we submit (β6,β0,β1,β2) in the BM algorithm and get the output \((\lambda _{1},\lambda _{2})=\left (z^{11141},z^{14283}\right )\). using both (β6,β0,β1,β2) and (λ1,λ2) as the input for the modified version of linear feedback shift register explained in [33], we get
So \(\tilde {g}=\left (z^{5036}, z^{5234}, z^{203}, z^{12223}, z^{9784}, z^{1048},z^{15830}\right )\) and the code’s evaluation polynomial has the coefficient vector \(\tilde {f}=\left (0,0,0,z^{4446},z^{11481},z^{15498},0\right )\). Then the codeword is
$$a=(\beta_{6},\beta_{0},\beta_{1},\beta_{2},g_{3},g_{4},g_{5})=\left( z^{15830}, z^{5036}, z^{5234}, z^{203}, z^{12223}, z^{9784}, z^{1048}\right).$$
$$\begin{array}{@{}rcl@{}} c&=&\tilde{f}\cdot \mathcal{M}^{T}=\left( z^{781}, z^{1313}, z^{4481}, z^{5130}, z^{1671}, z^{9656}, z^{1567}\right)\\ &=& \left( \begin{array}{lllllll} 1 &0& 0& 1& y& y^{2}& 1\\ 0& 1 &0 &y &y &y &1\\ 0& 0& 1& 0& y^{2}& 0& y^{2}\\ 1& y^{2}& 0& 0& y^{2}& y^{2}& 0\\ y^{2}& y^{2}& y& y& 1& y& y^{2}\\ y &y^{2}& 0& y& y^{2}& 1&1\\ 1& 1& y& 0& y& 1& 1 \end{array}\right), \end{array}$$
where y is the primitive element in \(\mathbb {F}_{2^{2}}^{*}\) and the message is f = (f0,…,fk− 1) = (l89,l97,l32) where l is the primitive element in \(\mathbb {F}_{2^{7}}^{*}\).
5 Conclusion
This work proposes the first encoding and decoding methods for three restricted families of rank metric codes including optimal symmetric, optimal alternating and optimal Hermitian rank metric codes. We showed that the evaluation encoding is a right choice for the aforementioned families and the proposed encoding methods are easily reversible and efficient. We also introduce three interpolation-based decoding algorithms that are based on the properties of Dickson matrix associated with linearized polynomials. In the decoding process we reduced the rank decoding problem to the problem of solving a system of linear equations which can be solved by Gaussian elimination method or Berlekamp-Massey algorithm in polynomial time.
Acknowledgements
The authors would like to thank the anonymous reviewers for their valuable suggestions and comments. The work of Chunlei Li was supported by the Research Council of Norway under Grants 247742 and 311646. The work of Ferdinando Zullo was supported by the project “VALERE: VAnviteLli pEr la RicErca” of the University of Campania “Luigi Vanvitelli” and was partially supported by the Italian National Group for Algebraic and Geometric Structures and their Applications (GNSAGA - INdAM).
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visithttp://creativecommons.org/licenses/by/4.0/.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.