싱글톤 바운드

코딩 이론에서 리차드 콜롬 싱글턴의 이름을 딴 싱글턴 바운드는 블록 길이 $n{\displaystyle }$ ${\displaystyle$ $n$$\},$ 크기 $M{\displaystyle }$ ${\displaystyle$ M$},$ 최소$$ 거리 $d{\displaystyle }$ ${\displaysty d}$의 임의 블록 코드 $C{\displaystyle }$ ${\\displaysty C}$의 크기에 대해 비교적 조잡한 상한선이다$.$ 또한 조시바운드로 알려져 있다.^[1] 조시(1958년)가 증명했고, 그보다 앞서 코마미야(1953년)가 증명했다.

바운트 명세서

$길이{\displaystyle }$ n ${\displaystyle n}$의 코드$$ 워드 $집합{\displaystyle }$ C ${\displaystyle C}$의 최소 거리는 다음과 같이 정의된다$$.

${\displaystyle d=\min _{\x,y\in C:x\neq y\}d(x,y)}$

여기서 $d{\displaystyle }$( ${\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle d(x,y)}$은(는) $x{\displaystyle }$ ${\displaystyle x}$과($와{\displaystyle }$) y ${\displaysty y}$ 사이의 해밍 거리입니다$.$ $A{\displaystyle {}_{}}$ ${\displaystyle q_{}n}$, ${\displaystyle d}$) ${\displaystyle A_{q}(n,d)$ 식은 $길이{\displaystyle }$ $n{\displaystyle }$ ${\displaystyle q}$ -ary$$ 블록 코드에서$$ 가능한 코드 워드의 최대 개수를 나타내며$$, 최소 $거리{\displaystyle }$ d$${\$displaystyle d$

그러면 싱글톤 바운드는 다음과 같이 말하고 있다.

${\displaystyle A_{q}(n,d)\leq q^{n-d+1}.$

증명

이러한 단어의 각 문자는 나머지 문자와 독립적으로 $q{\displaystyle }$ ${\displaystyle q}$개의 서로 다른$$ 값 중 하나를 가질 수 있으므로 먼저$$$q{\displaystyle }$ ${\$$displaystyle q^{n}}$의 길이 $n{\displaystyle }$ ${\displaystyle$ q$}$ -ary$$ 단어 수가 ${\displaystyle q^{}}$ ${\$displaystysty q}개인지 관찰하십시오.

이제 $C{\displaystyle }$ ${\displaystyle C}$을(를) 임의의 $q{\displaystyle }$ ${\displaystyle q}$ -ary$$ 블록 코드인 최소 $거리{\displaystyle }$ d ${\displaystyle$ d$}$이(가) 되도록$$ 하라$.$ 분명히 모든 코드 워드 $c{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle C}$ ${\displaysty c\in$ C$}$는 구별된다$$. 각 코드 워드의 $처음{\displaystyle }$ ${\displaystyle \mathrm{d}}$- 1 ${\displaystyle d-1}$글자를$$ 삭제하여 코드를 펑크 낸다면 $C{\displaystyle }${\$displaystyle C}$의 모든 원본 코드 워드는 서로 최소 $d{\displaystyle }$ ${\displaystyle d}$의 해밍 거리를 가지므로$$ 결과 코드 워드는 여전히 쌍으로 달라야 한다. 따라서 변경된 코드의 크기는 원래 코드와 동일하다.

새로 얻은 암호는 각각 길이가 있다.

${\displaystyle n}$-${\displaystyle }$( ${\displaystyle \mathrm{d}}$- 1${\displaystyle }$)${\displaystyle }$= ${\displaystyle n}$- ${\displaystyle d}$+ ${\displaystyle 1}$ ${\디스플레이$ 스타일 $n-(d-1)=n-d+1$

따라서 최대 ${\displaystyle q^{}}$-${\displaystyle d^{}}$ + ${\displaystyle 1^{}}$ ${\$ q$^{n-d+1$}이$$(가) 있을 수 있다. $C{\displaystyle }$ ${\displaystyle C}$이(가) 임의였으므로 이 바운드는 이러한 매개 변수를 사용하여 가능한 가장 큰 코드에 대해 유지되어야 하므로, 다음과 같다.^[2]

${\displaystyle C \leq A_{q}(n,d)\leq q^{n-d+1}.$

선형코드

C ${\displaystyle C}$이(가$)$ $q{\displaystyle }$ ${\displaystyle$ $n$ $치수{\displaystyle }$ k ${\displaystyle k}$ 및 최소 거리 $d{\displaystyle }$ ${\displaysty d$$}$을(를) 가진 선형 코드인 경우, 최대 코드 워드는 ${\displaystyle q^{}}${\$displaystystyle q^{k}$이고 Singleton 바인딩 i는 q}이다.mplies:

${\displaystyle q^{}}$ ${\displaystyle q^{}{q}^{}}$ -${\displaystyle d^{}}$+ ${\displaystyle 1^{}}$ ${\$

하도록

${\displaystyle \mathrm{k}}$ ${\displaystyle \le n}$ -${\displaystyle d}$+ 1 ${\displaystyle k\leq n-d+1$

보통 다음과^[3] 같이 쓰여 있다.

${\displaystyle d}$ ${\displaystyle \le }$ ${\displaystyle n}$ -${\displaystyle \mathrm{k}}$+ 1 ${\displaystyle d\leq n-k+1$

선형 코드 사례에서 패리티 검사 매트릭스의 $순위$가 ${\displaystyle n}$- k ${\displaystyle n-k}$인 것을 관찰함으로써 Singleton 바운드의 다른 증거를 얻을 수 있다$.$^[4] 또 다른 간단한 증거는 표준 형태의 제너레이터 매트릭스 행이 $최대{\displaystyle }$ n${\displaystyle }$- ${\displaystyle k}$+ ${\displaystyle 1}$ ${\displaystyle n-k+1}$의 중량을 갖는다는 것을 관찰함으로써 얻는다$.$

역사

이 결과에 대해 통상적으로 주어지는 인용문은 싱글톤(1964년)이지만, 앞서 조시(1958년)에 의해 증명되었다. 웨일스어(1988, 페이지 72)에 따르면 그 결과는 1953년 코마미야 논문(1953)에서 찾을 수 있다.

MDS 코드

Singleton 바운드에서 동등성을 달성하는 선형 블록 코드를 MDS(최대 거리 분리 가능) 코드라고 한다. 그러한 코드의 예로는 코드 워드가 두 개뿐(따라서 최소 거리 n ${\displaystylen}$을(를) 갖는 전체 거리 $n{\displaystyle }$ {\displaystyle n}을(를) 갖는 코드$,$ (${\displaystyle {}_{}{}^{}}$)${\displaystyle n^{}}$ ${\$최소 거리 1)의 전체 사용 코드, 단일 패리티 기호(최소 거리 2) 및 d)가 있다.우랄 암호 이것들은 종종 사소한 MDS 코드라고 불린다.

2진수 알파벳의 경우 사소한 MDS 코드만 존재한다.^[5][6]

비경쟁 MDS 코드의 예로는 리드-솔로몬 코드와 확장 버전이 있다.^[7][8]

MDS 코드는 $고정{\displaystyle }$ n ${\displaystyle n}$ $및$ k ${\displaystyle k}$의$$경우 가장 큰 오류 수정 및 탐지 기능을 가지기 때문에 중요한 블록 코드 클래스다. MDS 코드를 특성화하는 몇 가지 방법이 있다.^[9]

정리: $C{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle C}$을(를) F ${\displaystyle {}_{}}$ ${\$ 위에 선형 [${\displaystyle ,}$ ${\displaystyle k,}$ ${\displaystyle d}$ ${\displaystyle n,k,d}$ $]$으로 두십시오$.$ 다음은 이에 해당한다.

• ${\displaystyle C}$ ${\displaystyle C}$은(는) MDS 코드다.
• $C{\displaystyle }$ ${\displaystyle C}$에 대한 제너레이터 행렬의 $k{\displaystyle }$ ${\displaystyle k}$ 열은$$ 선형 독립적이다.
• $C{\displaystyle }$ ${\displaystyle C}$에 대한 패리티 검사 매트릭스의 n${\displaystyle }$- ${\displaystyle k}$ ${\displaystyle n-k}$ 열은$$ 선형 독립적이다$$.
• $⊥{\$은(는) MDS 코드다.
• $G{\displaystyle }$=${\displaystyle }$( ${\displaystyle I}$ A${\displaystyle }$) ${\displaystyle G=(I A)}$이(가) $C{\displaystyle }$ ${\displaystyle C}$에 대한 제너레이터 $매트릭스$라면$$A {\$displaystyle$ A$}$의 모든 사각형 하위 파라미터는$$ 비경정형이다.
• $d{\displaystyle }$ ${\displaystyle d}$ 좌표$$ 위치를 지정하면 정확히 이러한 위치를 지원하는 (최소 중량) 코드 워드가 있다.

이러한 특성화 중 마지막은 MDS 코드의 전체 중량 분포를 위한 명시적 공식인 MacWilliams ID를 사용함으로써 허용된다.^[10]

정리: $C{\displaystyle }$ ${\displaystyle C}$을(를) $선형{\displaystyle {\mathbb{}}_{}}$ [${\displaystyle ,}$ ${\displaystyle k,}$ ${\displaystyle d}$, d ${\displaystyle n,k,d}$ $]$로 두십시오. F ${\displaystyle {}_{}}${\$displaystyle \mathb$ {$F$$}$ $_{q}.$ $만약{\displaystyle {}_{}}$ ${\displaystyle A_{}}$가 $무게{\displaystyle }$${\$$displaystystyleyle C}$에 있는 암호의 수를$$ 나타내면$$$,$ 그 다음,

${\displaystyle A_{w}={\binom {n}{w}}\sum _{j=0}^{w-d}(-1)^{j}{\binom {w}{j}}(q^{w-d+1-j}-1)={\binom {n}{w}}(q-1)\sum _{j=0}^{w-d}(-1)^{j}{\binom {w-1}{j}}q^{w-d-j}.}$

투영 기하학의 호

MDS 코드의 제너레이터 매트릭스 기둥의 선형 독립성은 유한 투영 기하학의 객체로부터 MDS 코드를 구성할 수 있다. Let ${\displaystyle PG(N,q)}$ be the finite projective space of (geometric) dimension ${\displaystyle N}$ over the finite field ${\displaystyle \mathbb {F} _{q}}$. Let ${\displaystyle K=\{P_{1},P_{2},\dots ,P_{m}\}}$ be a set of points in this projective space 균일한 좌표로 표시됨. 열이$$ 이 점의 균일한 좌표인${\displaystyle }$(${\displaystyle \mathrm{N}}$+ ${\displaystyle 1}$) ${\displaystyle \times }$ m ${\displaystyle (N+1)\time m}$ 행렬$$ $G{\displaystyle }$ ${\displaystyle G}$을(를) 형성하십시오. 그러면.^[11]

Theorem: ${\displaystyle K}$ is a (spatial) ${\displaystyle m}$-arc if and only if ${\displaystyle G}$ is the generator matrix of an ${\displaystyle [m,N+1,m-N]}$ MDS code over ${\displaystyle \mathbb {F} _{q}}$.

참고 항목

• 길버트-바르샤모프 바운드
• 플롯킨 바운드
• 해밍 바운드
• 존슨 바운드
• 게리머 바운드

메모들

참조

• Joshi, D.D (1958), "A Note on Upper Bounds for Minimum Distance Codes", Information and Control, 1 (3): 289–295, doi:10.1016/S0019-9958(58)80006-6
• Komamiya, Y. (1953), "Application of logical mathematics to information theory", Proc. 3rd Japan. Nat. Cong. Appl. Math.: 437
• Ling, San; Xing, Chaoping (2004), Coding Theory / A First Course, Cambridge University Press, ISBN 0-521-52923-9
• MacWilliams, F.J.; Sloane, N.J.A. (1977), The Theory of Error-Correcting Codes, North-Holland, pp. 33, 37, ISBN 0-444-85193-3
• Pless, Vera (1998), Introduction to the Theory of Error-Correcting Codes (3rd ed.), Wiley Interscience, ISBN 0-471-19047-0
• Roman, Steven (1992), Coding and Information Theory, GTM, 134, Springer-Verlag, ISBN 0-387-97812-7
• Singleton, R.C. (1964), "Maximum distance q-nary codes", IEEE Trans. Inf. Theory, 10 (2): 116–118, doi:10.1109/TIT.1964.1053661
• Vermani, L. R. (1996), Elements of algebraic coding theory, Chapman & Hall
• Welsh, Dominic (1988), Codes and Cryptography, Oxford University Press, ISBN 0-19-853287-3

추가 읽기

• J.H. van Lint (1992). Introduction to Coding Theory. GTM. 86 (2nd ed.). Springer-Verlag. p. 61. ISBN 3-540-54894-7.
• Niederreiter, Harald; Xing, Chaoping (2001). "6. Applications to algebraic coding theory". Rational points on curves over finite fields. Theory and Applications. London Mathematical Society Lecture Note Series. 285. Cambridge: Cambridge University Press. ISBN 0-521-66543-4. Zbl 0971.11033.