로컬 테스트 가능 코드

로컬로 테스트할 수 있는 코드는 문자열의 비트 수가 적은(흔히 일정한) 비트를 보고 해당 코드에서 문자열이 단어인지 여부를 판단할 수 있는 오류 수정 코드의 한 유형이다. 경우에 따라서는 데이터를 모두 해독하지 않고 손상시켜 대응하여 적절한 조치를 취할 수 있도록 하는 것이 유용하다. 예를 들어, 통신에서, 수신자가 손상된 코드를 발견하면, 데이터를 재전송하도록 요청할 수 있으며, 이는 해당 데이터의 정확도를 높일 수 있다. 마찬가지로, 데이터 저장소의 경우, 이러한 코드는 손상된 데이터를 적절히 복구하고 다시 작성할 수 있다.

대조적으로, 로컬로 해독 가능한 코드는 원본 정보를 확률적으로 복구하기 위해 적은 수의 코드 비트를 사용한다. 오류의 분율은 디코더가 원래 비트를 올바르게 복구할 가능성을 결정한다. 그러나 모든 로컬 디코딩 가능한 코드가 로컬에서 테스트 가능한 것은 아니다.^[1]

분명히 어떤 유효한 암호도 암호로 받아들여야 하지만, 암호어가 아닌 문자열은 단 한 비트만 끌 수 있으므로, 많은 (확실히 일정한 숫자보다 더 많은) 탐색이 필요할 것이다. 이를 설명하기 위해, 테스트 실패는 문자열이 비트의 적어도 설정된 부분만큼 꺼진 경우에만 정의된다. 이것은 코드 단어가 일부 중복성을 추가하여 입력 문자열보다 길어야 함을 의미한다.

정의

두 문자열 사이의 거리를 측정하기 위해 해밍 거리를 사용한다.

${\displaystyle \Delta (x,y)= \{i:x_{i}\neq y_{i}\}}}$

코드 $C{\displaystyle :}${$$${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ k${\displaystyle {}^{}}$→ { $0,$${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$에 대한 $문자열$의 거리는 다음과 같이 계산된다$$.

${\displaystyle \Delta (w,C)=\min _{x}\{\Delta (w,C(x))\}}$

상대 거리는 비트 수의 일부로 계산된다.

${\displaystyle \delta (x,y)=\Delta (x,y)/n{\text{ 및 }}\delta (w,C)=\Delta (w,C)/n}$

A code ${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$ is called ${\displaystyle q}$-local ${\displaystyle \delta }$-testable if there exists a Turing machine M given random access to an input ${\displaystyle w}$ that makes at most ${\displaystyle q}$ non-adaptive queries of ${\displaystyle w}$ ${\displaystyle w}$을(를) 사용하고 다음 사항을 충족하십시오.^[2]

• For any ${\displaystyle x\in \{0,1\}^{k}}$ and ${\displaystyle w=C(x)}$, ${\displaystyle Pr[M^{w}(1^{k})=1]=1}$. In other words, M accepts given access to any codeword of C.
• For ${\displaystyle w\in \{0,1\}^{n}}$ such that ${\displaystyle \delta (w,C)>\delta }$, ${\displaystyle Pr[M^{w}(1^{k})=1]\leq 1/2}$. M must reject strings ${\displaystyle \delta }$-far from C at least half the time.

또한 코드의 비율은 메시지 길이와 코드 워드 길이의 비율이다.

${\displaystyle r={\frac { x }{ C(x)}}}$

한계

선형 크기의 로컬 테스트 가능한 코드가 있는지 여부는 여전히 의문이지만 "거의 선형"으로 간주되는 몇 가지 구조가 있다.^[3]

1. 다항식은 로 선형에 가까운 것으로, >0 ${\displaystyle \epsilon >0}$에$대해{\displaystyle ,}$ ${\displaystyle {}^{}}$ =${\displaystyle {k\mathrm{}}^{}}$ ${\displaystyle 1^{}}$ + $\$ {\$displaystyle n=k^{$1+\$epsilon$
2. $n{\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle {1\mathrm{}}^{}}$+ ${\displaystyle {ϵ}^{}}$( k$){\$ 형식의 함수, 여기서 $ϵ{\displaystyle }$($){\displaystyle \epsilon (k)}$은 0을 향해 가는 함수다$$. 이것은 k가 증가함에 따라 n이 선형에 가까워지게 한다. 예를 들면 다음과 같다.
   • $\displaystyle 1/\log \log k}$
   • ${\displaystyle 1}$${\displaystyle }$/${\displaystyle }$( ${\displaystyle \log }$ ${\displaystyle }$ k${\displaystyle {}^{}}$) ${\displaystyle c^{}}$ ${\$ 1$/(\log$ k$)^{c}$ 일부 $c{\displaystyle \in }$ (${\displaystyle 0,}$ 1${\displaystyle }$) ${\displaystyle c\in (0,1)}$
   • ${\displaystyle \exp }$ ${\displaystyle }$(${\displaystyle \log }$ ${\displaystyle }$ ${\displaystyle {log}^{}}$ ${\displaystyle }$ k${\displaystyle {}^{}}$) c${\displaystyle {}^{}}$)${\displaystyle }$/ ${\displaystyle c}$ ${\displaystyle \in }$ (0${\displaystyle }$, ${\displaystyle 1}$ ) {\$displaystyle \exp(\log \log k)^{c}/\log$ k$}$에 $대한{\displaystyle }$ c ∈${\displaystyle }$(${\displaystyle 0}$ , 1${\displaystyle }$) ${\displaysty c\in (0,1)}$

These have both been achieved, even with constant query complexity and a binary alphabet, such as with ${\displaystyle n=k^{1+1/(\log k)^{c}}}$ for any ${\displaystyle c\in (0,1)}$. The next nearly linear goal is linear up to a polylogarithmic factor; ${$$\displaystyle n={\text}}{polly}(\log$ k$)*k$ 이 제약을 충족하는 선형 테스트 가능한 코드를 아직 생각해내지 못한 사람은 없다.^[3]

2021년 11월에 두 개의 프리프린트가 "${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$ ${\$ $c$$^{3}}$ -LTCs$$"의 첫 번째 다항식 시간 구성을 보고했는데^[4][5][6][7], 즉 고정 $속도{\displaystyle }$ r ${\displaystyle$ r$\},$ 일정한 거리 $\Delta {\displaystyle }$ ${\displaystyle \delta},$ 일정한$$ 위치 $q{\displaystyle }$ ${\displaysty q}$이 있다$.$

확률적으로 확인할 수 있는 증거와의 연결

국지적으로 시험 가능한 코드는 확률적으로 검사 가능한 증명서(PCP)와 많은 공통점을 가지고 있다. 이것은 그들의 구성의 유사성으로부터 명백해야 한다. 두 가지 모두 $q{\displaystyle }$ ${\displaystyle q}$ 랜덤$$ 비적응 쿼리를 큰 문자열로 부여받으며, 수용하려면 확률 1로, 수용하지 않으면 절반 이하의 시간을 수용해야 한다. ${\displaystyle {주요}^{}}$ 차이점은 PCP가 w${\displaystyle {}^{}}$${\displaystyle w}$이(${\displaystyle 가)}$ 존재하여 $M{\displaystyle }$w$($ x ) = 1 {\displaystyle $M^{w}(x)=1$}이(가) 있는 $경우$ x {\displaystyle x$}$을$($를$)$ 수락하는 데 관심이 있다는 점이다$.$ 반면에 로컬 테스트 가능한 코드는 코드의 일부인 경우$$ w ${\displaysty w$를 수락한다. PCP 교정쇄가 로컬에서 테스트 가능한 코드를 인코딩한다고 가정할 때 많은 일이 잘못될 수 있다. 예를 들어, PCP 정의는 무효한 증명에 대해서는 아무 것도 말하지 않고, 무효한 입력에 대해서만 말한다.

이러한 차이에도 불구하고, 로컬 테스트 가능한 코드와 PCP는 유사하여 하나를 자주 구성하면 프로베러가 다른 하나를 구성하게 된다.^[8]

예

하다마드 코드

가장 유명한 오류 수정 코드 중 하나인 Hadamard 코드는 현지에서 테스트할 수 있는 코드다. 코드 워드 ${\displaystyle x}$는 선형 함수 $f{\displaystyle (}$ y${\displaystyle }$)${\displaystyle }$= ${\displaystyle \sum \underset{}{}}$ i ${\displaystyle \underset{}{x}}$ ${\displaystyle i_{}}$ i ${\$모드 2)가 되도록 Hadamard 코드에 암호화되어 있다. 이것은 입력보다 기하급수적으로 더 많은 비트를 필요로 하는 가능한 모든 y에 대해 이 기능의 결과를 나열할 것을 요구한다. sring w가 hadamard 코드의 코드 워드인지 테스트하기 위해, 우리는 그것이 인코딩하는 함수가 선형인지 테스트만 하면 된다. $즉{\displaystyle ,}$ ${\displaystyle x}$와 y의 임의 벡터에 대해 w$$ ( x${\displaystyle }$)$=$ ${\displaystyle w(}$ ${\displaystyle y}$)${\displaystyle }$= w${\displaystyle }$( $x$ y${\displaystyle }$) {\$displaystyle$ w$(x$)\$oplus w(y)=w(x$\oplus y$)}}$을( 여기서 } ${\displaysty \oplus }$은 비트 XOR을 의미하는지 단순히 확인하는 것이다.

유효한 인코딩 $w{\displaystyle }$ ${\displaystyle w}$에$$대해 선형 함수의 정의인 이 방정식이 참임을 쉽게 알 수 있다. 그러나 다소 어려운 점은$$ C에서 멀리 떨어진$\Delta {\displaystyle }$ {\$displaystyle$ \delta $}$인 $문자열$은$Δ$ {\$displaystyle$ \delta $}$의 오차 상한을 갖는다는 것을 보여준다$.$ 한 바운드는 세 개의 프로브 중 하나가 부정확한 결과를 낼 확률을 정확히 추정하는 직접적인 접근법에 의해 발견된다. A, B 및 C를 $w{\displaystyle }$( x${\displaystyle }$) ${\displaystyle w(x$ w${\displaystyle }$( ${\displaystyle y}$) ${\displaystyle w(y$ $w{\displaystyle }$( ${\displaystyle x}$ ${\displaystyle \oplus }$ y${\displaystyle }$) ${\displaysty w(x\oplus y)}$의 이벤트가 되도록 ${\displaystyle \mathrm{한다}}$. E가 정확히 일어나는 사건 중 하나가 되게 하라. 이렇게 되다

${\displaystyle {\begin{aligned}P(E)&\geq P(A\cup B\cup C)-3*P(A\cup B)\\&\geq 3*P(A)-3*P(A\cup B)-3*P(A\cup B)\\&\geq 3\delta -6\delta ^{2}\end{aligned}}}$

이는 < 5/ {\$delta \leq$516}에 대해 작동하지만, 에는 - 6 2 < {\$displaystyle$3\$delta -6\delta ^{$2} . 추가 작업으로 오류의 경계가 있음을 나타낼 수 있다

${\displaystyle f(x)={\case}3\reason -6\reason ^{2}&:0\leq \req \req 5/16\\req \req \req\\\reason &:45/reason\nd{case}}}}}}}$

주어진 $\Delta {\displaystyle }$ ${\displaystyle \delta }$에 대해$,$ 이것은 잘못된 긍정의 지속적인 가능성만 가지고 있기 때문에, 우리는 단지 1/2 이하로 확률을 얻기 위해 일정한 횟수를 체크할 수 있다.^[3]

롱코드

롱 코드는 로컬에서 테스트 가능한 코드에 가까운 매우 큰 블로업을 가진 또 다른 코드다. Given an input ${\displaystyle 0\leq i\leq 2^{k}}$ (note, this takes ${\displaystyle k}$ bits to represent), the function that returns the ${\displaystyle i^{th}}$ bit of the input, ${\displaystyle f_{i}(x)=x_{i}}$, is evaluated on all possible ${\displaystyle$$2^{k}}$ -비트$$ $입력{\displaystyle \mathrm{}}$ 0${\displaystyle }$≤ ${\displaystyle x}$ ${\displaystyle \le }$ ${\displaystyle {2{\mathrm{}}^{}}^{}}$ ${\displaystyle {\mathrm{}}^{}}$ ${\$ x$\leq 2^{2^{k$ 코드 워드는 이것들의 결합(길이 ${\displaystyle {n^{}}^{}}$= ${\displaystyle {2{\mathrm{}}^{}}^{}}$ k ${\$ 그 방법 국내 일부 오류가 발생한 이 테스트하고 y=-1{\displaystyle y=x}이 균일하게 임의로 입력){\displaystyle)} 따질 것이 있었는데, 각 비트의 앞면 작은 가능성을,μ>만약 f()))f(y){\displaystyle f())0{\displaystyle \mu>0}.{\displaystyle f} 부호 워드를 f 받아들인다.=f(y$)}}.$$f{\displaystyle }$ ${\displaystyle f}$이(가) 암호어라면$$, $확률{\displaystyle {}_{}}$ $1{\displaystyle \mathrm{}}$- ${\displaystyle x_$${i$$}$이(가) 변경되지 않은$$ $한{\displaystyle }$ f$${\$displaystyle f}$을(^[9]를) 받아들이게 된다$.$ 이는 암호어가 항상 허용되지만 일부 요구 사항에는 충분할 수 있다.

다른 로컬 테스트 가능 코드로는 리드-뮬러 코드(디코딩 알고리즘에 대한 로컬 디코딩 코드 참조), 리드-솔로몬 코드 및 단축 코드가 있다.

참고 항목

• 길버트-바르샤모프 바운드
• 해밍 코드
• 익스팬더 코드

참조

외부 링크

• "Breakthroughs — Locally Testable Codes with Constant Rate, Distance, and Locality Simons Institute for the Theory of Computing". simons.berkeley.edu. 6 October 2021.{{cite web}}: CS1 maint : url-status (링크)