순위오류수정코드

순위 코드
분류
계층	선형블록코드 순위코드
블록 길이	n
메시지 길이	k
거리	n − k + 1
알파벳 크기	Q = qN (q prime)
표기법	[n, k, d]-코드
알고리즘
베를레캄프-마스시 유클리드 주 프로베니우스 다항식으로
v t

코딩 이론에서 랭크 코드(Gabidulin 코드라고도 함)는 해밍이 아닌 랭크 메트릭에 대한 비이진^[1] 선형 오류 수정 코드다.그들은 다수의 무작위 순위 오류를 감지하고 수정할 수 있는 체계적인 코드 구축 방법을 설명했다.n-심볼 워드에 k-심볼 워드를 코딩하는 중복성을 추가하면 순위 코드는 t = = (d - 1) / 2 ⌋까지의 모든 순위 오류를 수정할 수 있는데 여기서 d는 코드 거리다.삭제 코드로, d - 1까지 알려진 삭제를 수정할 수 있다.

순위 코드는 리드-솔로몬 코드와 유사한$$ 유한 필드 G ${\displaystyle F}$(${\displaystyle {}^{}}$ ${\displaystyle N^{}}$) ${\displaystyle GF(q^{N})$에 대한 대수 선형 코드다.

${\displaystyle \mathrm{GF}({}^{}}$ ${\displaystyle N^{}}$) ${\displaystyle GF(q^{N})$에 대한 벡터 순위는 ${\displaystyle \mathrm{GF}(q}$) ${\displaystyle GF(q)}$에 대한 선형 독립 구성 요소의 최대 수입니다$$$.$$G{\displaystyle }$ ${\displaystyle F({}^{}}$ ${\displaystyle N^{}}$) ${\displaystyle GF(q^{N})$에 대한 두 벡터 사이의 순위 거리는 이러한$$ 벡터 차이의 순위다.

순위 코드는 오류 벡터 등급이 t 이하인 모든 오류를 수정한다.

순위 메트릭

$X{\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$을(를) $유한장{\displaystyle }$ $){\$^{$N}\오른쪽)$ 위에 n차원 벡터 공간으로 두십시오$.$ 여기서 $q{\displaystyle }$ ${\displaysty q}$은 prim의 $힘$이고$$N {\$displaystysty N}$은 양의 정수입니다$$.Let ${\displaystyle \left(u_{1},u_{2},\dots ,u_{N}\right)}$, with ${\displaystyle u_{i}\in GF(q^{N})}$, be a base of ${\displaystyle GF\left({q^{N}}\right)}$ as a vector space over the field ${\displaystyle GF\left({q}\right)$$}$.

Every element ${\displaystyle x_{i}\in GF\left({q^{N}}\right)}$ can be represented as ${\displaystyle x_{i}=a_{1i}u_{1}+a_{2i}u_{2}+\dots +a_{Ni}u_{N}}$. Hence, every vector ${\di$$Splaystyle {\vec}=\좌측({x_{1},x_{2},\dots,x_{n}}\우측)$을 $통해$ ${\displaystyle \mathrm{GF}{}^{}{q}^{}}$ ) ${\$을 매트릭스로 작성할$$ 수 있다.

${\displaystyle {\vec {x}}=\left\ {\begin{array}{*{20}c}a_{1,1}&a_{1,2}&\ldots &a_{1,n}\\a_{2,1}&a_{2,2}&\ldots &a_{2,n}\\\ldots &\ldots &\ldots &\ldots \\a_{N,1}&a_{N,2}&\ldots &a_{N,n}\end{array}}\right\ }$

Rank of the vector ${\displaystyle {\vec {x}}}$ over the field ${\displaystyle GF\left({q^{N}}\right)}$ is a rank of the corresponding matrix ${\displaystyle A\left({\vec {x}}\right)}$ over the field ${\displaystyle GF\left({q}\right)}$ denoted by ${\displaystyle r(\stackrel{}{x}}$${\displaystyle \stackrel{}{\to }}$; ${\displaystyle q}$) ${\$.

모든 벡터 $x{\displaystyle \stackrel{}{}}$→ ${\$의 집합은 공간$$ $X{\displaystyle {}^{}}$ ${\displaystyle n^{}}$= ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ X$^{n}=$$A_{{N}^{n$ .맵 $x{\displaystyle \stackrel{}{}}$→${\displaystyle r}$(${\displaystyle x\stackrel{}{}}$→;${\displaystyle q}$) ${\$은 ${\displaystyle X^{}}$ n ${\$에 대한 표준과$$ 순위 메트릭을 정의한다.

${\displaystyle d\reftediation{\vec {x};{\vec {y}}\오른쪽)=r\re\reftiated{\vec}-{\vec {y};q}\right)$

순위코드

A set ${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}$ of vectors from ${\displaystyle X^{n}}$ is called a code with code distance ${\displaystyle d=\min d\left(x_{i},x_{j}\right)}$. If the set also forms a k-dimensional subspace of ${\dis$$Playstyle X^{n$ 그러면 $d{\displaystyle }$ {\$displaystyle d}$을(를) 가진 선형(n, k) 코드라고 부른다$.$ 이와 같은 선형 순위 메트릭 코드는 항상 Singleton $바운드{\displaystyle }$ d${\displaystyle }$≤ ${\displaystyle n}$ -${\displaystyle k}$+ ${\displaystyle 1}$ ${\displaystyled d\leq n-k+1}$을 만족한다$.$

행렬 생성 중

d = n - k + 1의 최대 순위 거리(또는 MRD) 코드인 몇 가지 알려진 순위 코드 구조가 있다.가장 쉽게 만들 수 있는 것은 (일반화된) 가비둘린 코드로 알려져 있는데, 처음에 델사르트(이 코드)에 의해 발견되었고, 후에 가비둘린(그리고 크셰베츠키)에 의해 발견되었다.

원소 $x{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle (q^{}}$ N ${\displaystyle {}^{}}$ ${\displaystyle$$[i]}$을(를) 프로베니우스 검정력$({\displaystyle }$$q^{N})$으로 정의하자.

${\displaystyle x^{[i]}=x^{q^{i\mod N}}}\,}$

Then, every vector ${\displaystyle {\vec {g}}=(g_{1},g_{2},\dots ,g_{n}),~g_{i}\in GF(q^{N}),~n\leq N}$, linearly independent over ${\displaystyle GF(q)}$, defines a generating matrix of the MRD (n, k, d = n − k + 1)-code.

${\displaystyle G=\left\ {\begin{array}{*{20}c}g_{1}&g_{2}&\dots &g_{n}\\g_{1}^{[m]}&g_{2}^{[m]}&\dots &g_{n}^{[m]}\\g_{1}^{[2m]}&g_{2}^{[2m]}&\dots &g_{n}^{[2m]}\\\dots &\dots &\dots &\dots \\g_{1}^{[(k-1)m]}&g_{2}^{[(k-1)m]}&\put &g_{n}^{[(k-1)m]}\end{array}}\right\ ,}$

여기서 ${\displaystyle gcd(m}$, ${\displaystyle N}$)${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle \gcd(m,N)=1$

적용들

순위 코드에 기초한 공개키 암호체계에 대한 제안이 몇 가지 있다.그러나 대부분 불안정한 것으로 판명되었다(예: 참조).2008년^[4] 4월, 암호학 저널 (Journal of Cryptology).

등급 코드는 네트워크 코딩의 오류 및 삭제 보정에 유용하다.

참고 항목

• 선형코드
• 리드-솔로몬 오차 보정
• Berlekamp-Massey 알고리즘
• 네트워크 코딩

메모들

참조

• Gabidulin, Ernst M. (1985), "Theory of codes with maximum rank distance", Problems of Information Transmission, 21 (1): 1–12
• Kshevetskiy, Alexander; Gabidulin, Ernst M. (4–9 September 2005), "The new construction of rank codes", Proceedings of IEEE International Symposium on Information Theory (ISIT) 2005: 2105–2108, doi:10.1109/ISIT.2005.1523717, ISBN 978-0-7803-9151-2
• Gabidulin, Ernst M.; Pilipchuk, Nina I. (June 29 – July 4, 2003), "A new method of erasure correction by rank codes", Proceedings of the 2003 IEEE International Symposium on Information Theory: 423, doi:10.1109/ISIT.2003.1228440, ISBN 978-0-7803-7728-8

외부 링크

• 순위-금속 코덱의 MATLAB 구현