익스팬더 코드

이 기사는 위키피디아의 품질 기준을 충족시키기 위해 정리가 필요할 수 있다. 구체적인 문제는 정의가 누락되고, 문법에는 많은 양의 복사가 필요하다는 것이다. 맹목적으로 참고문헌을 가리키는 것이 기사의 요점이 되어서는 안 된다. 누락된 학술적 설명. 가능하다면 이 기사를 개선하는 것을 도와줘. (2012년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

익스팬더 코드
초당적 확장기 그래프
분류
유형	선형블록코드
블록 길이	${\displaystyle n}$
메시지 길이	$(\displaystyle n-m)$
등급	$1-m/n}$
거리	${\displaystyle 2(1-\epsilon )\cdot n}$
알파벳 크기	${\displaystyle 2}$
표기법	${\displaystyle [}$ ${\displaystyle n,}$ ${\displaystyle n}$- m${\displaystyle }$, ${\displaystyle 2}$( 1 -${\displaystyle ϵ}$) ${\displaystyle \gamma }$ ${\displaystyle n}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}$$-code$$
v t

코딩 이론에서, 익스팬더 코드는 초당적 익스팬더 그래프에서 생성되는 오류 수정 코드의 클래스를 형성한다. 저스틴 코드와 함께 익스팬더 코드는 일정한 양의 비율, 일정한 양의 상대적 거리, 일정한 알파벳 크기를 가지기 때문에 특히 관심이 많다. 실제로 알파벳에는 두 가지 요소만 들어 있어 확장자 코드는 이진 코드의 클래스에 속한다. 또한 확장기 코드는 코드의 블록 길이에 비례하여 인코딩 및 디코딩이 가능하다.

익스팬더 코드

코딩 이론에서 확장자 코드는${\displaystyle }$[${\displaystyle {n\mathrm{}}_{}}$, ${\displaystyle n}$- ${\displaystyle m}$ ${\displaystyle {}_{}}$ 2 $displaystyle [n,n-m]_{2}\},$ 패리티 검사 매트릭스가 초당적 확장자 그래프의 인접 매트릭스인 선형$$ 블록 코드다. These codes have good relative distance ${\displaystyle 2(1-\varepsilon )\gamma \,}$, where ${\displaystyle \varepsilon \,}$ and ${\displaystyle \gamma \,}$ are properties of the expander graph as defined later), rate ${\displaystyle \left(1-{\tfrac {m}{n}}\right)\,}$, and decodability(running time $O{\displaystyle }$(${\displaystyle n}$) ${\$의 알고리즘이 존재함$$).

정의

Let ${\displaystyle B}$ be a ${\displaystyle (c,d)}$-regular graph between a set of ${\displaystyle n}$ nodes ${\displaystyle \{v_{1},\cdots ,v_{n}\}}$, called variables, and a set of ${\displaystyle cn/d}$ nodes ${\displaystyle \{$$C_{1},\cdots ,C_{cn/d$ 제약 조건이라고 함.

Let ${\displaystyle b(i,j)}$ be a function designed so that, for each constraint ${\displaystyle C_{i}}$, the variables neighboring ${\displaystyle C_{i}}$ are ${\displaystyle v_{b(i,1)},\cdots ,v_{b(i,d)}}$.

$S{\displaystyle \mathcal{}}$ ${\$을(를) 블록 길이 $d{\displaystyle }$ ${\displaystyle d}$의 오류 수정 코드가 되도록$$ 한다$.$ The expander code ${\displaystyle {\mathcal {C}}(B,{\mathcal {S}})}$ is the code of block length ${\displaystyle n}$ whose codewords are the words ${\displaystyle (x_{1},\cdots ,x_{n})}$ such that, for ${\displaystyle 1\leq i\leq cn/d}$, ${\displaystyle (x_{b(i,1)}}$${\displaystyle {}_{},}$ ${\displaystyle \cdots }$, ${\displaystyle {}_{}}$ ${\displaystyle b_{}}$( ${\displaystyle i_{}}$, d${\displaystyle {}_{}}$)${\displaystyle (x_{b(i,1)},\cdots ,x_{b(i$$,d)}}}$의 코드 워드 입니다$.$^[1]

비독점적 무손실 확장기 그래프가 존재하는 것으로 나타났다. 게다가 우리는 명시적으로 그것들을 구성할 수 있다.^[2]

등급

$C{\displaystyle }$ ${\$의 비율은 블록 길이로 나눈 치수다$$. 이 경우 패리티 검사 매트릭스의 크기는 ${\displaystyle m}$ ${\displaystyle \times }$ n ${\$$displaystyle$ $m\times n\,}$이고$,$ $따라서{\displaystyle }$ C ${\\\\\\\\}$은$({\displaystyle n}$ -${\displaystyle }$m${\displaystyle }$)${\displaystyle }$/ ${\displaystyle \mathrm{n}}$= 1 - ${\displaystyle m}$/$$ $displaystyle (n-m)/n=1-m/n$이다$.$

거리

Suppose ${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$. Then the distance of a ${\displaystyle (n,m,d,\gamma ,1-\varepsilon )\,}$ expander code ${\displaystyle C\,}$ is at least ${\displaystyle 2(1-\varepsilon )\gamma n\,}$.

증명

Note that we can consider every codeword ${\displaystyle c\,}$ in ${\displaystyle C\,}$ as a subset of vertices ${\displaystyle S\subset L\,}$, by saying that vertex ${\displaystyle v_{i}\in S\,}$ if and only if the ${\displaystyle i\,}$th index of the codeword is a 1. Then ${\displaystyle c\,}$ is a codeword iff every vertex ${\displaystyle v\in R\,}$ is adjacent to an even number of vertices in ${\displaystyle S\,}$. (In order to be a codeword, ${\displaystyle cP=0\,}$, where ${\displaystyle P\,}$ is the parity check matrix. 그러면 $R{\displaystyle }$ ${\$$displaystyle R\,}$의 각 꼭지점은 $P$의 각 열에 해당된다$.$GF에 ${\displaystyle \text{대한}}$ 행렬 곱하기(${\displaystyle 2}$)${\displaystyle }$=${\displaystyle }${ ${\displaystyle 0,}$ 1$}$ {\$displaystyle {\text}$$그러면$ GF$}(2)=\{0,1\}\,}$ 그런 다음 원하는 결과를 제공한다.) 따라서 $꼭지점{\displaystyle }$ v ${\displaystyle \in }$ ${\displaystyle R}$ ${\$ R$\}$이(가) $S{\displaystyle }$ ${\$ S$\,}$의 단일 꼭지점에 인접한$$ 경우 $c{\displaystyle }$ ${\$은(는) 코드 워드가 아님을 즉시 알 수 있다$.$ Let ${\displaystyle N(S)\,}$ denote the neighbors in ${\displaystyle R\,}$ of ${\displaystyle S\,}$, and ${\displaystyle U(S)\,}$ denote those neighbors of ${\displaystyle S\,}$ which are unique, i.e., adjacent to a single vertex of ${\displaystyle S\,}$.

보조정리1길

For every ${\displaystyle S\subset L\,}$ of size ${\displaystyle S \leq \gamma n\,}$, ${\displaystyle d S \geq N(S) \geq U(S) \geq d(1-2\varepsilon ) S \,}$.

증명

Trivially, ${\displaystyle N(S) \geq U(S) \,}$, since ${\displaystyle v\in U(S)\,}$ implies ${\displaystyle v\in N(S)\,}$. ${\displaystyle N(S) \leq d S \,}$ follows since the degree of every vertex in ${\displaystyle S\,}$$$ $d{\displaystyle }$ ${\$ 그래프의 확장 속성에 의해 $d{\displaystyle }$(${\displaystyle 1}$ -${\displaystyle \epsilon }$) ${\displaystyle S}$ $displaystyle$ d $(1-\varipsilon$) S$\,}$개의$$ 가장자리 집합이 있어야 하며, 이 모서리들은 구별되는 꼭지점으로 이동한다. The remaining ${\displaystyle d\varepsilon S \,}$ edges make at most ${\displaystyle d\varepsilon S \,}$ neighbors not unique, so ${\displaystyle U(S)\geq d(1-\varepsilon ) S -d\varepsilon S =d(1-2\varepsilon ) S \,}$.

코롤라리

충분히 작은 $모든{\displaystyle }$ S ${\$에는 독특한 이웃이 있다$$. 이는 < {\$displaystyle \varepsilon <{\tfrac {1}{2}}\,}$ 이후부터이다

보조정리2길

$T$< (1 -$ε$)가$$ 부분집합 ${\displaystyle T}$${\displaystyle \subset }$ L${\$$displaystyle$ $T\subset L\}$은(는) 고유한 $이웃$을 가지고 있다$.$

증명

Limma1T≤γ n{\displaystyle T\leq \gamma n\,},&T>γ n{\displaystyle 2(1-\varepsilon)\gamma n>&T>\gamma n\,}2(1− ε)γ n을 가정합니다. S⊂ T 같은{\displaystyle S\subset T\,}은 S)γ n{\displaystyle S=\gamma n\,}자. Limma1 보아 우리는 알고 있는 사건을 증명한다.U(${\displaystyle U(S) \geq d(1-2\varepsilon ) S \,}$. Then a vertex ${\displaystyle v\in U(S)\,}$ is in ${\displaystyle U(T)\,}$ iff ${\displaystyle v\notin N(T\setminus S)\,}$, and we know that ${\displaystyle T\setminus S\le 2(1-\epsilon )\gamma n-\gamma n=(1-2\epsilon )\gamma n}${\displaystyle T\setminus S\leq 2(1-\varepsilon)\gamma n-\gamma n=(1-2\varepsilon)\gamma n\,}, 그렇게 Limma1의 첫 부분에 의해, 우리는 N을 알고 있(T∖ S)≤ d(1− 2ε)γ n{\displaystyle N(T\setminus S)\leq d(1-2\varepsilon)\gamma n\,}. ε<12{\displaystyle \varepsilon<>{\tfrac{1}{2}}\,},. u${\displaystyle U(T) \geq U(S)\setminus N(T\setminus S) \geq U(S) - N(T\setminus S) >0\,}$, and hence ${\displaystyle U(T)\,}$ is not empty.

코롤라리

U(T)>일과 관계되는 것은 만약 T⊂ 나는{\displaystyle T\subset L\,}적어도 1독특한 이웃,;0{\displaystyle U(T)>0\,}, 해당 단어 c{\displaystyle c\,}T{\displaystyle T\,}에 해당하는은 될 수 없지만, 모두 0벡터에에 의해. 곱하지 않습니다. 확인 matrix. By the previous argument, ${\displaystyle c\in C\implies wt(c)\geq 2(1-\varepsilon )\gamma n\,}$. Since ${\displaystyle C\,}$ is linear, we conclude that ${\displaystyle C\,}$ has distance at least ${\displaystyle 2(1-\varepsilon )\gamma n\,}$.

인코딩

확장자 코드의 인코딩 시간은 일반 선형 코드 $O{\displaystyle }$( ${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\$의 인코딩 시간으로 매트릭스 곱셈으로$$ 상한 값을 지정한다. 스필먼에 의한 결과는 인코딩이 $O{\displaystyle }$(${\displaystyle n}$) ${\$시간$$ 내에 가능하다는 것을 보여준다.^[3]

디코딩

코드 디코딩은 다음 알고리즘을 사용하여 < 1 ( n) {\$displaystyle$$$\varepsilon <{\$tfrac${1}{4$}\}$에 O ($n{\displaystyle }$)\$displaystyle$ $\varepsilon$ ${\displaystyle <\{\backslash }$$tfrac$ {1$}{4}\}\}.$

Let ${\displaystyle v_{i}\,}$ be the vertex of ${\displaystyle L\,}$ that corresponds to the ${\displaystyle i\,}$th index in the codewords of ${\displaystyle C\,}$. Let ${\displaystyle y\in \{0,1\}^{n}\,}$ be a received word, and ${\displaystyle V(y)=\{v_i\mid \text{the}{i}^{\text{th}}\text{positi}}$${\displaystyle V(y)=\{v_{i}\mid {\text{the }}i^{\text{th}}{\text{ position of }}y{\text{ is a }}1\}\,}$. Let ${\displaystyle e(i)\,}$ be ${\displaystyle \{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is even}}\}$$\,}$, and ${\displaystyle o(i)\,}$ be ${\displaystyle \{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is odd}}\} \,}$. Then consider the greedy algorithm:

---

입력: $수신{\displaystyle }$ 단어 y ${\$ y$\backslash ,\}.$

o(i) > e(i)의 flip entry i in y'에 실패하는 i가 있는 경우 V(y')의 홀수 정점 수에 인접한 R에 v가 있는 동안 y'로 초기화한다. 

출력: 실패 또는 수정된 $코드{\displaystyle {}^{}}$ 워드 y ${\displaystyle {\prime }^{}}$ $displaystyle y$

---

증명

우리는 먼저 알고리즘의 정확성을 보여주고, 그 알고리즘의 실행 시간을 조사한다.

정확성

우리는 수신된 코드 워드가 원래 코드 워드의 절반 거리 내에 있을 때 알고리즘이 올바른 코드 워드로 종료된다는 것을 보여줘야 한다. 부패 변수의 집합을 $S{\displaystyle }$ ${\$${\displaystyle s}$= S $displaystyle$ s$=S$ $\backslash ,\},$ $그리고{\displaystyle }$ R ${\$ R$\,}$에서 불만족(정점 수의 홀수 수에 인접한) 정점 집합이 $c{\displaystyle }$ ${\$이 되도록 한다$.$ 다음 보조자는 유용하게 될 것이다.

보조정리3길

< < $<\$ n인 경우, $($) > ( ){\$displaystyle$ $v_{$$i}\,}$가 $있는{\displaystyle {}_{}}$ v${\displaystyle {}_{}}{\displaystyle i_{}}$가 있다

증명

Limma1으로써, 우리는 Us{\displaystyle U(S)\geq d(1-2\varepsilon)s\,}(1− 2ε)≥ d(S). 그래서 평균 꼭지점, d/2{\displaystyle d(1-2\varepsilon)>, d/2\,}독특한 이웃(기억하는 독특한 이웃들이며, 따라서 위에 깐다에 기여하(나는 불만을 느끼고 있){\displaystyle o(나는)\,}), 죄 적어도 d(1− 2ε)을 갖고 있다.ce< $displaystyle \varepsilon <{\tfrac${1$}{4$ 따라서 꼭지점${\displaystyle {}_{}}i{\displaystyle {}_{}}$ {\$displaystyle v_{i}\,$ ( )> > ${\$이 있다

그래서, 만약 우리가 아직 암호어에 도달하지 않았다면, 항상 뒤집어야 할 꼭지점이 있을 것이다. 다음으로, 우리는 오류의 수가 $\gamma {\displaystyle }$ ${\displaystyle n}$ ${\$ n$\,}$을(를) 넘어서 결코 증가할 수 없다는 것을 보여준다$.$

보조정리4길

< (- )$n$($1-2\$$varepsilon$)$n$로 시작하면 알고리즘의 어느 지점에서나$$ $s{\displaystyle }$ =${\displaystyle }$s = $=n$에 도달하지 않는다$.$

증명

When we flip a vertex ${\displaystyle v_{i}\,}$, ${\displaystyle o(i)\,}$ and ${\displaystyle e(i)\,}$ are interchanged, and since we had ${\displaystyle o(i)>e(i)\,}$, this means the number of unsatisfied vertices on the right decreases by at least one after each flip. Since ${\displaystyle s<\gamma (1-2\varepsilon )n\,}$, the initial number of unsatisfied vertices is at most ${\displaystyle d\gamma (1-2\varepsilon )n\,}$, by the graph's ${\displaystyle d\,}$-regularity. If we reached a string with ${\displaystyle \gamma n\,}$ errors, then by Lemma 1, there would be at least ${\displaystyle d\gamma (1-2\varepsilon )n\,}$ unique neighbors, which means there would be at least ${\displaystyle d\gamma (1-2\varepsilon )n\,}$ unsatisfied vertices, a contradi기계 장치를 달다

레마스 3과 4는 < ) $[\$$C{\displaystyle }$ ${\\$ C$\,}$의 절반 거리)$$로 시작하면, 우리는 언제나 뒤집기 위한$$ $꼭지점{\displaystyle {}_{}}$ v ${\displaystyle i_{}}$ $displaystytyleyle v_{i}$를 찾을 수 있다는 것을 보여준다. 각 플립은 $R{\displaystyle }$ ${\$에서 불만족 정점 수를 최소 1 이상$$ 감소시키고, 따라서 알고리즘은 $대부분$의 m ${\$단계에서$$ 종료되며, Lema 3에 의해 어떤 코드 워드에서 종료된다. (암호 워드에서가 아니라 플립할 정점이 있을 것이다.) Lemma 4는 ${\displaystyle \mathrm{우리}}$가 올바른 암호어로부터 $결코$ ben {\$displaystyle \gamma$ n$\,}$ 이후 코드를γ n을(1− ε),γ n{\displaystyle 2(1-\varepsilon)\gamma n>, \gamma n\,}(ε<>부터 12{\displaystyle \varepsilon<>{\tfrac{1}{2}}\,}), 그것에 종료하지만 반드시 정확한 부호 워드, 이후 비트, 대칭의 수 이하의 절반 거리(거리 2입니다. 그래서 우리는 여행할 수 없었다.멀리 en 이끄는다른 암호문에도 도달해야 한다.

복잡성

우리는 이제 알고리즘이 선형 시간 디코딩을 달성할 수 있다는 것을 보여준다. $n{\displaystyle \frac{}{}}$ ${\displaystyle \frac{m}{}}$ $displaystyle {\tfrac {n}{m}\,}$을(를$)$ 일정하게 하고$$ r {\$displaystyle$ r\,}을$($를) $R{\displaystyle }$ ${\$ $R$$\,}$의 정점 최대도로 한다$$$.$ $r{\displaystyle }$ ${\$ r$\,}$은 알려진 구성에도 일정하게 한다$$.

1. 전처리: $R{\displaystyle }$ ${\$ R$\,}$의 각 꼭지점에 홀수 또는 짝수 수의 이웃이 있는지$$ 계산하는 데 O(${\displaystyle mr}$) ${\$ $O$$(mr)\,}$시간이$$ 걸린다.
2. Pre-processing 2: We take ${\displaystyle O(dn)=O(dmr)\,}$ time to compute a list of vertices ${\displaystyle v_{i}\,}$ in ${\displaystyle L\,}$ which have ${\displaystyle o(i)>e(i)\,}$.
3. 각 반복: 우리는 단지 첫번째 목록 요소를 제거한다. $R{\displaystyle }$ ${\$의 홀수/ 짝수 정점 목록을 업데이트하려면 업데이트 $O{\displaystyle (d}$) ${\$ 항목만$$ 업데이트하면 되고 필요에 따라 삽입/제거하면 된다$.$ $그런{\displaystyle }$ 다음 L ${\$의 정점 목록에서 $O{\displaystyle }$(${\displaystyle \mathrm{dr})}$ ${\$개의$$ 항목을 인접 항목보다 더 이상하고$$ 필요에 따라 삽입/제거하는 방식으로 업데이트한다. 따라서 각 반복에는 $O{\displaystyle }$( ${\displaystyle d}$ ${\displaystyle r}$) ${\$시간이$$ 소요된다.
4. 위에서 주장했듯이, 총 반복 횟수는 최대 $m{\displaystyle }$ ${\$회 입니다$.$

이렇게 하면 총 $O{\displaystyle (m}$ ${\displaystyle d}$ ${\displaystyle r}$)${\displaystyle }$= ${\displaystyle O(n}$) ${\$ O$(mdr)=O(n)\,}$시간의$$ 런타임이 주어지며, $여기$서 d ${\$ 및$$ $r{\displaystyle }$ ${\$ r$\,}$은 상수인$$ 것이다.

참고 항목

• 익스팬더 그래프
• 저밀도 패리티 검사 코드
• 오류 수정 코드의 선형 시간 인코딩 및 디코딩
• ABNR 및 AEL 코드

메모들

이 글은 박사를 바탕으로 한 것이다. 벤카테산 구루스와미의 코스 ^[4]노트

참조