Rank error-correcting code
Rank codes | |
---|---|
Named after | Ernst M. Gabidulin |
Classification | |
Hierarchy | Linear block code Rank code |
Block length | n = q − 1 |
Message length | k |
Distance | n − k + 1 |
Alphabet size | q = pm (p prime) |
Notation | [n, k, n − k + 1]q-code |
Algorithms | |
Berlekamp–Massey Euclidean over Frobenius poynomials | |
Properties | |
Maximum-distance separable code | |
In coding theory, Rank codes are non-binary[1] linear error-correcting codes invented by Ernst M. Gabidulin. They described a systematic way of building codes that could detect and correct multiple random rank errors. By adding redundancy with coding k-symbol word to a n-symbol word, a rank code can detect any errors of rank ⌊n-k/2⌋. As an erasure code, it can correct up to n-k known erasures.
Rank code is an algebraic linear code over the finite field similar to Reed-Solomon code. Instead of using Hamming metric, the code is defined over rank metric.
The rank of the vector over is the maximum number of linearly independent components over . The rank distance between two vectors over is the rank of the difference of these vectors.
disstance is a rank of the distance используется новая ранговая метрика (ранговое расстояние), которое задаётся как ранг разности векторов над полем .
Ранговый код позволяет исправлять ошибки в передаваемой информационной матрице, если ранг ошибки не выше заданного.
Определения
Пусть задано — n-мерное векторное пространство над полем Галуа , где — степень простого числа, а — некоторый фиксированный базис этого поля, если его рассматривать как векторное пространство над полем .
Любой элемент можно однозначно представить как . Если обозначить совокупность всех матриц с элементами из как , то для любого вектора можно задать биекцию с помощью следующего правила:
Рангом вектора над полем будем называть ранг соответствующей матрицы и обозначать как . Данный ранг (точнее, отображение ) задаёт норму на . Данная норма задаёт на ранговую метрику:
Тогда произвольное множество {x1, x2, ..., xM} векторов из Xn назовём кодом (с кодовым расстоянием , а подпространство Xn размерности k — линейным или (n, k)-кодом.
Использование
На основе ранговых кодов были предложены некоторые новые криптосистемы (ГПТ). Также было показано, что ранговые коды можно использовать при сетевом кодировании, которое использует возможность кода исправлять ошибки с рангом не выше заданного.
Литература
- Габидулин Э.М. (1985). "Теория кодов с максимальным ранговым расстоянием" (in Russian). 21 (1) (Пробл. передачи информ ed.): 3–16.
{{cite journal}}
: Cite journal requires|journal=
(help)CS1 maint: date and year (link) - E.M. Gabidulin, N.I. Pilipchuk (June 29-July 4, 2003). "A new method of erasure correction by rank codes" (Proceedings of the 2003 IEEE International Symposium on Information Theory ed.). Yokohama, Japan: 423. ISBN 0-7803-7728-1.
{{cite journal}}
: Check date values in:|year=
and|date=
(help); Cite journal requires|journal=
(help)CS1 maint: date and year (link) CS1 maint: multiple names: authors list (link) CS1 maint: year (link) - Габидулин Э.М., Пилипчук Н.И. (2004). "Симметричные ранговые коды" (in Russian). 40 (2) (Пробл. передачи информ ed.): 3–18.
{{cite journal}}
: Cite journal requires|journal=
(help)CS1 maint: date and year (link) CS1 maint: multiple names: authors list (link) - Alexander Kshevetskiy, Ernst M. Gabidulin (4-9 Sept. 2005). "The new construction of rank codes" (Proceedings of IEEE International Symposium on Information Theory (ISIT) 2005 ed.). Adelaide, Australia: 2105–2108. ISBN 0-7803-9151-9.
{{cite journal}}
: Check date values in:|year=
and|date=
(help); Cite journal requires|journal=
(help)CS1 maint: date and year (link) CS1 maint: multiple names: authors list (link) CS1 maint: year (link)
См. также
- ^ Codes for which each input symbol is from a set of size greater than 2.