존슨 바운드

응용수학에서 존슨 바운드(Selmer Martin Johnson의 이름을 딴 이름)는 데이터 전송이나 통신을 위한 코딩 이론에서 사용되는 오류 수정 코드의 크기에 대한 제한이다.

정의

$C{\displaystyle }$ ${\displaystyle$ $C$$}$을(를) 길이 $n{\displaystyle }$ ${\displaystyle$ n$\},$ 즉 ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$의 부분 집합으로 한다$$$.$ $d{\displaystyle }$ ${\displaystyty$ $d}$을(를) 최소 거리$$$C$ ${\d$로 한다.

${\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}$ 사이의 해밍 거리입니다$.$

Let ${\displaystyle C_{q}(n,d)}$ be the set of all q-ary codes with length ${\displaystyle n}$ and minimum distance ${\displaystyle d}$ and let ${\displaystyle C_{q}(n,d,w)}$ denote the set of codes in ${\displaystyle C_{q}(n,d)}$ such that every element has$정확히$ w ${\displaystyle w}$ nonzero 항목.

$C{\displaystyle }$ $displaystyle C}$을(를) 기준으로 C ${\displaystyle C}$에 있는$$ 요소의 수를 가리킨다$.$ 그런 다음, ${\displaystyle {Aq}_{}n,}$ ${\displaystyle d}$)$${\$displaystyle A_{q}(n,d)}$을(를) $길이{\displaystyle }$ n$${\$displaystystyle n}$과 최소 $거리{\displaystyle }$ d$}$을(: ${\d$)로 정의한다$.$

${\displaystyle A_{q}(n,d)=\max_{C\in C_{q}(n,d)}C .}$

마찬가지로 $A{\displaystyle {}_{}}$ ${\displaystyle q_{}n}$ ,${\displaystyle }$d${\displaystyle }$, w${\displaystyle }$) ${\displaystyle A_{q}($${\displaystyle n}$$,d,w)}$을$($를) $C{\displaystyle {}_{}}$ ${\displaystyle q_{}n}$, ${\displaystyle d}$, w${\displaystyle }$) ${\displaystyle C_{q}(n,d,w)}$의 가장 큰 크기로 정의한다$$.

${\dplaystyle A_{q}(n,d,w)=\max_{C\in C_{q}(n,d,w)}C .}$

정리 1($A{\displaystyle {}_{}}$ ${\displaystyle q_{}}$(${\displaystyle n}$, d${\displaystyle }$) ${\displaystyle A_{q}(n,d)}$에 바인딩된 Johnson):$$

$d{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle t}$+ ${\displaystyle 1}$ ${\displaystyle d=2t+1}$인 경우$,$

${\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}-{d \choose t}A_{q}(n,d,d)}{A_{q}(n,d,t+1)}}}.}$

$d{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle t}$+ ${\displaystyle 2}$ ${\displaystyle d=2t+2}$인 경우$,$

${\displaystyle A_{q}(n,d)\leq {\frac{q^{n}{n}{\sum_{i-1)^{i}+{\frac {{n 선택 {{n 선택 t+1}(q-1)^{t+1}:{n {{n 선택{n}}}}}{{n 선택 t+}}}}}}}}}}}}}}}{{{{t+}}}}}}}}}{{{{{{{{{{{{{{{{{{{{{{{{{n 선택A_{q}(n,d,t+1)}}}.}$

정리 2 ($A{\displaystyle {}_{}}$ ${\displaystyle q_{}}$(${\displaystyle n}$, d${\displaystyle }$, w${\displaystyle }$) ${\displaystyle A_{q}(n,d,w)}$에 바인딩된 Johnson):$$

(i) > ${\displaystyle d>2w,}$

${\displaystyle A_{q}(n,d,w)=1.}$

(ii) $d{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle 2}$ ${\displaystyle w}$ ${\displaystyle d\leq 2w$인 경우 다음과 같이$$ $변수{\displaystyle }$ e ${\displaystyle e}$을(를) 정의하십시오.If ${\displaystyle d}$ is even, then define ${\displaystyle e}$ through the relation ${\displaystyle d=2e}$; if ${\displaystyle d}$ is odd, define ${\displaystyle e}$ through the relation ${\displaystyle d=2e-1}$. Let ${\displaystyle q^{*}=q-1}$. Then,

${\displaystyle A_{q}(n,d,w)\leq \left\lfloor {\frac {nq^{*}}{w}}\left\lfloor {\frac {(n-1)q^{*}}{w-1}}\left\lfloor \cdots \left\lfloor {\frac {(n-w+e)q^{*}}{e}}\right\rfloor \cdots \right\rfloor \right\rfloor \right\rfloor }$

여기서 ${\displaystyle \lfloor }$ ${{\displaystyle \lfloor ~~\floor }$는 플로어 기능이다.

비고: 정리 2의 경계를 정리 1의 바운드에 꽂으면 $A{\displaystyle {}_{}}$ ${\displaystyle q_{}}$(${\displaystyle n}$ ${\displaystyle ,d}$ ) ${\displaystyle A_{q}(n,d)}$에 숫자 상한이 생성된다$.$

참고 항목

• 싱글톤 바운드
• 해밍 바운드
• 플롯킨 바운드
• 엘리아스 바살리고 바운드
• 길버트-바르샤모프 바운드
• 게리머 바운드

참조

• Johnson, Selmer Martin (April 1962). "A new upper bound for error-correcting codes". IRE Transactions on Information Theory: 203–207.
• Huffman, William Cary; Pless, Vera S. (2003). Fundamentals of Error-Correcting Codes. Cambridge University Press. ISBN 978-0-521-78280-7.