커버링 코드

코딩 이론에서 커버 코드는 공간의 요소 집합(코드워즈라고 함)으로, 공간의 모든 요소가 어떤 코드 워드의 일정한 거리 내에 있다는 속성을 가지고 있다.

정의

$q{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 2}$ ${\displaystyle q\geq$2$\},$ $n{\displaystyle 1}$ 1$${\$displaystyle n\geq$1$\},$ $R{\displaystyle 0}$ 0 ${\displaystyle R\geq$ 0$}$을(를) 정수로 한다.A code ${\displaystyle C\subseteq Q^{n}}$ over an alphabet Q of size Q = q is called q-ary R-covering code of length n if for every word ${\displaystyle y\in Q^{n}}$ there is a codeword ${\displaystyle x\in C}$ such that the Hamming distance ${\displaystyle d_{H}(x,y)\leq$$R$ 즉, C의 암호어 주위에 있는 해밍 메트릭에 관한 R 반경의 구(또는 볼이나 루크돔)는 유한한 미터법 공간 ${\$ Q$^{n}}$를 소진해야 한다$.$코드 C의 커버 반경은 C가 R 커버링될 정도로 가장 작은 R이다.모든 완벽한 코드는 최소 크기의 커버 코드다.

예

C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341}은(는) 길이 4의 5arry 2커버 코드다.^[1]

커버링 문제

길이 n의 q-ary R-커버링 코드의 최소$$ 크기 ${\displaystyle {Kq}_{}}$ ${\displaystyle {}_{}n}$ ,${\displaystyle }$R$){\displaystyle K_{q}(n,R)}$의 결정은 매우 어려운 문제다.간격이 큰 상·하한만 알고 있는 경우가 많다.커버링 코드의 구성마다 K_q(n, R)에 대한 상한선을 부여한다.Lower bounds include the sphere covering bound and Rodemich's bounds ${\displaystyle K_{q}(n,1)\geq q^{n-1}/(n-1)}$ and ${\displaystyle K_{q}(n,n-2)\geq q^{2}/(n-1)}$.^[2]커버 문제는 ${\displaystyle {Qn}^{}}$ ${\$ Q$^{n},$즉 q-ary e-error code of length n의 최대 크기 결정과 밀접하게 관련되어 있다.

풋볼 풀 문제

특정 사례는 축구 풀 베팅에 근거한 축구 풀 문제인데, 축구 풀 베팅의 목적은 결과에 상관없이 최대 R '실수'가 있는 축구 경기에 대한 베팅 시스템을 마련하는 것이다.따라서, 최대 한 개의 'miss'와 일치하는 n개의 경우, 3번째 커버인₃ K(n,1)를 찾는다.

$n{\displaystyle }$= ${\displaystyle \frac{1}{}}$ ${\displaystyle 2^{}}$( ${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle \mathrm{k}{}^{}}$- 1${\displaystyle }$) ${\displaystyle$ n$={\tfrac {1}{$1}:{$2}}:(3^{k}-1)}}$ 3이$$^n-k 필요하므로 n = 4, k = 2, 9, n = 13, k = 3, 59049가 필요하다.^[3]2011년^[4] 현재 알려진 최고 한계는

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14
K3(n,1)	1	3	5	9	27	71-73	156-186	402-486	1060-1269	2854-3645	7832-9477	21531-27702	59049	166610-177147
K3(n,2)		1	3	3	8	15-17	26-34	54-81	130-219	323-555	729	1919-2187	5062-6561	12204-19683
K3(n,3)			1	3	3	6	11-12	14-27	27-54	57-105	117-243	282-657	612-1215	1553-2187

적용들

커버 코드에 관한 표준 작업에는^[5] 다음과 같은 용도가 열거되어 있다.

• 왜곡이 있는 압축
• 데이터 압축
• 오류 및 삭제 디코딩
• 상호접속망에서의 방송
• 풋볼 풀^[6]
• 한 번 쓴 추억
• 베를레캄프게일 게임
• 음성 부호화
• 셀룰러
• 부분 집합 및 Cayley 그래프

참조

외부 링크

• 커버 코드에 관한 문헌
• ${\displaystyle {Kq}_{}}$ ${\displaystyle {}_{}n}$, ${\displaystyle R}$) ${\displaystyle K_{q}(n,R)}$에 대한 경계