Jump to content

Rank error-correcting code

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Alex.kshevetskiy (talk | contribs) at 17:46, 15 March 2012 (Created page with '{{infobox code | name = Rank codes | image = | image_caption = | namesake = Ernst M. Gabidulin | hierarchy = [[Linear blo...'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)
Rank codes
Named afterErnst M. Gabidulin
Classification
HierarchyLinear block code
Rank code
Block lengthn = q − 1
Message lengthk
Distancenk + 1
Alphabet sizeq = pm  (p prime)
Notation[n, k, nk + 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)

См. также

  1. ^ Codes for which each input symbol is from a set of size greater than 2.