Filetype PDF | Posted on 03 Feb 2023 | 2 years ago
Authentication
digital resources
188x Filetype PDF File size 0.18 MB Source: iitp.ru
Rank-metric codes and applications
Ernst M. Gabidulin
Moscow Institute of Physics and Technology (State University)
Email: ernst.gabidulin@gmail.com
Abstract
The State of Art for rank codes is represented. The theory and applications are
considered.
1 Rank Codes
1.1 Definition
There exist two representations of Rank codes: matrix representation and vector represen-
tation.
In matrix representation, rank codes are defined as subsets of a normed space {FN×n, Rk}
q
of N × n matrices over a finite (base) field F , where the norm of a matrix M ∈ FN×n
q q
is defined to be the algebraic rank Rk(M) of this matrix over Fq. The rank distance be-
tween two matrices M1 and M2 is the rank of their difference Rk(M1 − M2). The rank
distance of a matrix rank code M ⊂ FN×n is defined as the minimal pairwise distance:
q
d(M)=d=min(Rk(M −M ):M,M ∈M, i6=j).
i j i j
In vector representation, rank codes are defined as subsets of a normed n-dimensional space
{Fn , Rk} of n-vectors over an extension field F N, where the norm of a vector v ∈ Fn is
qN q qN
defined to be the column rank Rk(v | Fq) of this vector over Fq, i.e., the maximal number
of coordinates of v which are linearly independent over the base field Fq. The rank distance
between two vectors v , v is the column rank of their difference Rk(v − v | F ). The
1 2 1 2 q
rank distance of a vector rank code V ⊂ Fn is defined as the minimal pairwise distance:
qN
d(V) = d = min(Rk(v −v ) : v ,v ∈ V, i 6= j).
i j i j
1.2 Background
Algebraic coding theory may be considered as the theory of subsets of a certain normed
finite-dimensional space Γ over the finite field equipped with a norm function N. The most
known norm in coding theory is the Hamming weight of a vector. It turns out that the
rank function Rk(A) of matrices A over fields can be considered as the norm function. In
particular, the well-known inequalities for sums of matrices |Rk(A)−Rk(B)| ≤ Rk(A+B) ≤
1
Rk(A)+Rk(B)define implicitly the rank distance relations on the space of all matrices of
identical size. Explicitly, the concept of the rank metric was introduced by Loo-Keng Hua
[1] as ”Arithmetic distance”. Philippe Delsarte [2] defined the rank distance (or, q-distance)
on the set of bilinear forms (equivalently, on the set of rectangular matrices) and proposed
the construction of optimal codes in bilinear form representation. Ernst M. Gabidulin [3]
introduced the rank distance for vector spaces over extension fields and found connections
between rank codes in the vector representation and in the matrix representation. Optimal
codes in vector representation were described. Fast coding and decoding algorithms were
proposed for optimal codes.
2 Theory
The normed spaces {FN×n, Rk} and {Fn , Rk} are isomorphic isometrically. Let a basis
q qN
Ω={ω ,ω ,...,ω } of F N over F be chosen. Then each vector v = v1 v2 ... vn ∈
1 2 N q q
Fn can be mapped into the N ×n matrix M ∈ FN×n by replacing each coordinate v with
qN q j
the N-column consisting of coefficients in representing vj by the basis Ω. This mapping is
bijective and isometric.
Given a rank code M in matrix representation one can construct a rank code V in vector
representation with the same size, code distance and pairwise distances, and vice versa.
The size |M| = |V| of related codes with code distance d satisfy the Singleton bound
|M| = |V| ≤ min(qN(n−d+1),qn(N−d+1). Codes reaching this bound are called maximum
rank distance codes, or, MRD codes.
Arank code M in matrix representation is called Fq-linear if M is a subspace of FN×n.
q
Arank code V in vector representation is called F N-linear if V is a subspace of Fn .
q qN
Mapping a FqN-linear code V in vector representation into related code M in matrix rep-
resentation results in a Fq-linear code.
Mapping a Fq-linear code M in matrix representation into related code V in vector repre-
sentation results in not necessary a FqN-linear code.
Constructions of Fq-linear rank codes in the matrix representation and FqN-linear rank
codes in the vector representation will be considered.
2.1 Delsarte’s optimal rank codes in matrix representation
Delsarte’s construction of rank codes in bilinear form representation is presented here in
matrix representation.
N−1
Assume that n ≤ N. Let Tr(x) = P xql, x ∈ FqN, be the Trace function from FqN
l=0
into Fq. Let d be an integer in {1,2,...,n}. Let u = u0 u1 ... un−d ∈ Fn−d+1. Let
qN
µ ,µ ,...,µ be linearly independent elements of F N. Let Ω = {ω ,ω ,...,ω } be a basis
1 2 n q 1 2 N
for FqN. n o
DefineacodeinmatrixrepresentationasthesetofN×nmatricesM = M(u) = [Mij(u)] : u ∈ Fn−d+1 ,
qN
2
where !
n−d
M (u)=Tr Xuωµqs .
ij s i j
s=0
ThenMisarankcodewithcodedistancedreachingtheSingletonbound|M| = qN(n−d+1).
Let Ai(n,d), i = 0,1,...,n, be the number of code matrices with rank i. The weight
distribution is as follows: A (n,d) = 1, i = 0
0
Ai(n,d) = 0, i = 1,...,d−1.
i−d
n X s i s(s−1) N(d−i+1−s)
Ai(n,d) = (−1) q 2 (q −1),
i s
s=0
i−1
if i = d,...,n, where n = Q qn−qj is the Gaussian binomial coefficient.
i qi−qj
j=0
2.2 Optimal rank codes in vector representation
A F N-linear vector code V is a subspace of the normed space {Fn , Rk}. Denote by
q qN
(n,k,d) a code V of dimension k ≤ n and rank distance d. Such a code can be described in
terms of a full rank generator matrix Gk over the extension field F N of size k × n. Code
q
vectors {v} are all linear combinations of this matrix. Thus the size of a code is equal to
|V| = qNk.
Equivalently, a rank code V can be described in terms of a full rank parity-check matrix
Hn−k over FqN of size (n−k)×n. It satisfies the condition GkH⊤ =O,whereOistheall
n−k
zero k×(n−k) matrix. Code vectors {v} are all solutions of the linear system of equation
vH⊤ =0.
n−k
For optimal (MRD) codes, it must be k = n−d+1, or, n−k = d−1.
General constructions of MRD codes in terms of parity-check matrices can be described
as follows. Let h ,h ,...,h be a set of elements from the extension field F n linearly
1 2 n q
independent over the base field F. Let s be a positive integer such that gcd(s,N) = 1.
Then a parity matrix of the form
h h . . . h
1 2 n
qs qs qs
h h . . . h
1 2 n
H = q2s q2s q2s .
d−1 h h . . . h
1 2 n
... . . . . . . . . .
q(d−2)s q(d−2)s q(d−2)s
h h . . . h
1 2 n
defines an MRD (n,k,d) code with code length n ≤ N, dimension k = n−d+1 and rank
distance d = n −k +1.
Equivalently, general constructions of MRD codes can be described in terms of gener-
ator matrices. Let g ,g ,...,g be a set of elements from the extension field F n linearly
1 2 n q
3
independent over the base field F. Then a generator matrix of the form
g g . . . g
1 2 n
gqs gqs . . . gqs
1 2 n
G = gq2s gq2s . . . gq2s .
k 1 2 n
... . . . . . . . . .
q(k−1)s q(k−1)s q(k−1)s
g g . . . g
1 2 n
defines an MRD (n,k,d) code with code length n ≤ N, dimension k = n −d+1 and
rank distance d = n−k+1. The weight distribution of vector MRD codes coincides for a
given d with the weight distribution of Delsarte’s codes above.
The case s = 1 is used mostly.
No other constructions of MRD codes are known (2009).
2.3 Correcting rank errors and rank erasures
Let a MRD (n,k,d = n − k + 1) code V be given. Let a transmitted signal be v and
received signal be y = v+etotal, where etotal is an error. The code V can correct in general
vector errors of the form
etotal =e+erow+ecol
=e u +e u +···+eu+
1 1 2 2 t t
+a r +a r +···+a r +
1 1 2 2 v v
+w c +w c +···+wc
1 1 2 2 l l
provided that 2t + v + l ≤ d − 1.
The part e = e u + e u + ··· + e u is called a random rank error of rank t under
1 1 2 2 t t
assumption that elements e ∈ F N are linearly independent over the base field F and
i q q
unknown to the decoder; n-vectors u ,u ,...,u have coordinates in the base field F , are
1 2 t q
linearly independent over the base field Fq and also unknown to the decoder. The rank t
is unknown to the decoder.
The part e = a r + a r + ··· + a r is called a vector rank row erasure with side
row 1 1 2 2 v v
information under assumption that elements a ∈ F N are linearly independent over the
i q
base field F and known to the decoder; n-vectors r ,r ,...,r have coordinates in the base
1 2 v
field Fq, are linearly independent over the base field Fq and unknown to the decoder.
The part e =wc +wc +···+wc iscalled a vector rank column erasure with side
col 1 1 2 2 l l
information under assumption that elements w ∈ F N are linearly independent over the
i q
base field F and are unknown to the decoder; n-vectors c ,c ,...,c have coordinates in
q 1 2 l
the base field Fq, are linearly independent over the base field Fq and known to the decoder.
First fast correcting random rank errors only was proposed in [3]. The algorithm is
based on the extended Euclidean division algorithm for linearized polynomials. There
exist several further modifications.
Algorithms for correcting random rank errors and rank erasures simultaneously are
proposed in [4], [5], [7].
4
no reviews yet
Please Login to review.
