Rank-metric code[1]

Description

Also called a Delsarte code. Each codeword is a matrix over \(GF(q)\), with codewords forming a \(GF(q)\)-linear subspace, and with the metric being the rank of the difference of matrices. The distance \(d\) is the minimum rank of all nonzero matrices in the code. Rank-metric codes on \(n\times m\) matrices are denoted as \([n\times m,k,d]_q\).

The number of codewords satisfies \(k \leq \max(n, m) M\), where \(M\) is the maximum rank of all matrices in the code. Codes that achieve this bound with equality are called Delsarte optimal anticodes.

Protection

Protects against errors with rank \(\leq \lfloor \frac{d-1}2 \rfloor\).

The complexity of decoding rank-metric codes is unknown but expected to be harder than that of binary linear codes [2].

Decoding

Polynomial-reconstruction Berlekamp-Welch based decoder [3].Berlekamp-Massey based decoder [4].

Realizations

Identity-Based Encryption [5].Digital watermarking [6].Network coding and streaming media broadcasting [7].

Notes

See Ref. [8] for a discussion of MacWilliams identities and the relationship between rank metric and Gabidulin codes.

Parent

Children

References

[1]
P. Delsarte, “Bilinear forms over a finite field, with applications to coding theory”, Journal of Combinatorial Theory, Series A 25, 226 (1978). DOI
[2]
Gaborit Philippe and Zemor Gilles, “On the hardness of the decoding and the minimum distance problems for rank codes”. 1404.3482
[3]
P. Loidreau, “A Welch–Berlekamp Like Algorithm for Decoding Gabidulin Codes”, Coding and Cryptography 36 (2006). DOI
[4]
G. Richter and S. Plass, “Fast decoding of rank-codes with rank errors and column erasures”, International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings.. DOI
[5]
P. Gaborit et al., “Identity-Based Encryption from Codes with Rank Metric”, Advances in Cryptology – CRYPTO 2017 194 (2017). DOI
[6]
P. Lefèvre, P. Carré, and P. Gaborit, “Application of rank metric codes in digital image watermarking”, Signal Processing: Image Communication 74, 119 (2019). DOI
[7]
D. Silva and F. R. Kschischang, “Rank-Metric Codes for Priority Encoding Transmission with Network Coding”, 2007 10th Canadian Workshop on Information Theory (CWIT) (2007). DOI
[8]
Alberto Ravagnani, “Rank-metric codes and their duality theory”. 1410.1333
Page edit log

Zoo code information

Internal code ID: rank_metric

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: rank_metric

Cite as:
“Rank-metric code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/rank_metric
BibTeX:
@incollection{eczoo_rank_metric, title={Rank-metric code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/rank_metric} }
Share via:
Twitter |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/rank_metric

Cite as:

“Rank-metric code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/rank_metric

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/matrices/rank-metric/rank_metric.yml.