리스트 디코딩

이 문서에는 참고 자료, 관련 읽기 또는 외부 링크가 포함되어 있지만 인라인 인용이 부족하여 출처가 불분명합니다. 좀 더 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다.(2011년 5월) (이 템플릿메시지 삭제 방법 및 삭제 타이밍에 대해 알아보기)

부호화 이론에서 목록 복호화는 큰 오류율을 위한 오류 수정 코드의 고유한 복호화 대안입니다.이 개념은 1950년대에 Elias에 의해 제안되었다.목록 디코딩의 주요 개념은 하나의 가능한 메시지를 출력하는 대신 디코딩 알고리즘이 하나의 가능한 가능성을 출력한다는 것입니다.이것에 의해, 일의의 디코딩에 의해서 허가된 수보다 많은 에러를 처리할 수 있습니다.

수신된 단어에서 하나의 유효한 코드 워드를 출력하도록 제약되는 코딩 이론의 고유한 디코딩 모델은 더 많은 양의 오류를 허용할 수 없습니다.이는 확률적 소음 모델(섀넌이 제안)과 적대적 소음 모델(리처드 해밍이 고려)에 대한 오류 수정 성능의 차이를 초래했다.90년대 중반 이후 부호화 이론 커뮤니티에 의한 상당한 알고리즘의 진보가 이 격차를 메워왔다.이 진행의 대부분은 리스트 디코딩이라고 불리는 완화된 오류 정정 모델에 기초하고 있으며, 여기서 디코더는 실제 전송된 코드워드가 출력 목록에 포함되는 최악의 병리학적 오류 패턴에 대한 코드워드 목록을 출력한다.다만, 일반적인 에러 패턴의 경우, 디코더는, 수신된 워드가 주어졌을 때에, 독자적인 단일의 코드 워드를 출력합니다.이것은 거의 항상 해당됩니다(다만, 이것은 모든 코드에 대해서 사실이라고는 알려져 있지 않습니다).여기서의 개선은 오류 수정 성능이 두 배로 향상된다는 점에서 중요합니다.이는 디코더가 최소 거리의 절반 배리어에 의해 제한되지 않기 때문입니다.이 모델은 코드워드 목록이 있는 것이 포기하는 것보다 확실히 더 낫기 때문에 매우 매력적입니다.리스트 디코딩의 개념은 복잡성 이론에서 많은 흥미로운 응용 분야를 가지고 있다.

채널 노이즈를 모델링하는 방법은 신뢰할 수 있는 통신이 가능한 속도를 제어한다는 점에서 중요한 역할을 합니다.채널 동작을 모델링하는 데는 크게 두 가지 생각이 있습니다.

• 채널의 확률적 거동이 잘 알려져 있고 너무 많거나 적은 오류 발생 확률이 낮다는 점에서 채널 소음이 정확하게 모델링되는 섀넌이 연구한 확률적 소음 모델
• 채널이 총 오류 수에 제한되는 코드워드를 임의로 손상시키는 대항마 역할을 하는 Hamming에 의해 고려된 최악의 경우 또는 적대적 소음 모델.

리스트 디코딩의 하이라이트는 적대적 소음 조건에서도 수정할 수 있는 비율과 오류 비율 사이의 정보 이론 최적 트레이드오프를 달성할 수 있다는 것이다.따라서 이는 어떤 의미에서 더 약한 확률적 소음 모델의 경우에 가능한 한 오류 수정 성능을 개선하는 것과 같다.

수학 공식화

C$(\$를${\displaystyle }$(${\displaystyle n,}$ ${\displaystyle k,}$ ${\displaystyle d{}_{}}$(\$displaystyle (n, k$, $d)_{q})$ 오류 수정$$ 코드라고 $합니다{\displaystyle \mathcal{}}$. 즉$,$ $C{\displaystyle \mathcal{}}$(\$displaystyle {C})$는 $길이{\displaystyle }$n(\$displaystyle$ n$),$ $치수{\displaystyle }$k(\$displaystyle$ k$)$ 및$$ 최소 $displaystyled$의 코드입니다$$.${\displaystyle }$$사이즈{\displaystyle }$$$$q의${\ \ $displaystyle$$$\$$Sigma$$$$。목록 디코딩 문제는 다음과 같이 공식화할 수 있습니다.

입력: $단어{\displaystyle }$ x $\\$ x$\in$ \$Sigma ^{n$ $오류{\displaystyle }$ 제한 e$\displaystyle$ e$}$를 받았습니다.

$출력$: x$${$C$$}$의 모든 $코드워드{\displaystyle {}_{}}$ x${\displaystyle {}_{}{}_{}}$, ${\displaystyle {x\mathrm{}}_{}}$2, ${\displaystyle ...,}$ ${\displaystyle x_{}}$ m ${\displaystyle {}_{}}$ {\$displaystyle x_{1$},$x_{2},\ldots,x_{m}\ in${\$displaystyle$ x$}$로부터의 해밍 거리가 $최대{\displaystyle }$e {\$displaystyle$ e$\}$인 목록.

리스트 디코딩 동기

$수신$된 $워드$ y\$displaystyle$ y$\backslash ($일부 전송된 $코드워드{\displaystyle }$ c$\displaystyle$ c$)$를 노이즈 버전으로 지정하면 디코더는 수신된 워드에 가장 가까운 코드워드에 베팅하여 전송된 코드워드를 출력하려고 합니다.두 코드워드 사이의 해밍 거리는 디코더에 의해 수신된 워드가 주어졌을 때 가장 가까운 코드워드를 찾기 위한 메트릭으로 사용됩니다.d$${\$displaystyle$d$$$\}$가$코드$ C의 최소 해밍 거리인 $경우{\displaystyle }$,$정확히$ d ${\$$displaystyle$$$c_${1$$}$와 c$$2 {\$displaystyle$ d$}$의 $위치$가 다른 $코드워드{\displaystyle {}_{}}$ ${\displaystyle {c1}_{}}$과$$${\displaystyle {c2\mathrm{}}_{}}$(\$displaystyle$ $c_{2})$가 존재합니다.여기서 $수신어{\displaystyle }$y(\$displaystyle$y)가$$ ${\displaystyle {코드워드\mathrm{}}_{}}$c1(\$displaystyle c_{1$}) $및{\displaystyle {}_{}}$ $(\$에서 등거리에 있는 경우 디코더는 $(\$${$$1$})과 $(\$ 중 $어느{\displaystyle {}_{}}$ 것을 결정할 수 없기 때문에 명확한 디코딩이 불가능합니다.원래의 송신 코드 워드로 출력합니다.그 결과, 최소 거리의 절반이 조합 장벽으로서 기능해, 그 이상의 명확한 에러 수정은 불가능하게 되어, 일의적인 디코딩만을 고집하고 있는 경우.그러나 위에서 설명한$y$와 $같은{\displaystyle }$ 단어는 최악의 경우에만 발생하며, Hamming ball이 고차원 공간에서 채워지는 방식을 보면 최소 거리의 절반을 넘는 에러 $e$라도 Hamming di 내에 하나의 $코드워드{\displaystyle }$c{$display$$$$style$$$c$}$밖에 없습니다.$e$를 선택합니다$$.이 주장은 자연 앙상블에서 선택한 랜덤 코드에 대해 높은 확률로 유지되며, 실제 응용 분야에서 잘 연구되고 있는 리드-솔로몬 코드의 경우 더욱 그러합니다.사실, 섀넌의 q-ary 대칭 채널에 대한 용량 정리의 증명은 랜덤 코드에 대한 위의 주장에 비추어 볼 수 있다.

list-decoding 명령에서는 최악의 경우 디코더는 코드워드의 작은 목록을 출력할 수 있습니다.일부 컨텍스트 고유의 정보 또는 사이드 정보를 사용하여 목록을 삭제하고 원래 전송된 코드 워드를 복구할 수 있습니다.따라서 일반적으로 이것은 고유한 디코딩보다 더 강력한 오류 복구 모델인 것으로 보입니다.

리스트 디코딩 가능성

다항식 시간 리스트 디코딩 알고리즘이 존재하기 $위해서$는 수신 $워드{\displaystyle }$r$\$$displaystyle$ r$\$displaystyle ${\displaystyle \mathrm{pn}}$$($서 p$\displaystyle$ p$)$ 주위에$$ 반경 p\$displaystyle$pn의$$ Hamming ball이 $블록{\displaystyle }$ 길이$$n\$displaystyle$n의 오차를 갖는다는 조합 보증서가 필요합니다.이는 목록 크기 자체가 알고리즘 실행 시간의 하한이기 때문입니다.따라서 리스트 사이즈는 코드의 블록 $길이{\displaystyle }$n(\$displaystyle$ n$)$의 다항식이어야 합니다.이 요건의 조합적 결과는 코드 레이트에 상한을 부과하는 것입니다.목록 디코딩 약속은 이 상한을 충족합니다.1${\displaystyle }$-$R$에 $근접$하는 오류의 극히 일부까지 나열할 수 있는 $비율{\displaystyle }$R의 $코드$(\$displaystyle$$$R$)$가 존재하는$$ 것으로 비건설적으로 나타났다. 1${\displaystyle }$-$R$의 $수량$을 목록 해독 용량이라고 한다.이는 고유한 디코딩 모델에 비해 상당히 많은 양의 오류를 수정할 수 있는 가능성이 있기 때문입니다.메시지를 복구하려면 전송된 기호 중 $일부{\displaystyle }$ R$(표시 스타일$ R$)$이 정확해야 합니다.이는 복호화에 필요한 올바른 기호 수에 대한 정보 이론 하한이며 목록 복호화를 통해 잠재적으로 이 정보 이론 한계를 달성할 수 있습니다.단, 이 가능성을 실현하기 위해서는 명시적 코드(다항 시간에 구축 가능한 코드)와 부호화 및 복호화를 수행하기 위한 효율적인 알고리즘이 필요합니다.

(p, L)-list-decodability

에러 $fraction{\displaystyle \mathrm{}}$ 0$$ p$$1 { $displaystyle$ 0 \$leqslant$ 1$$} 및$$ $정수{\displaystyle }$ L$$1 { $displaystyle L$ \$geqslant$$$1$$$\}$의 경우 $코드$ ${\displaystyle C^{}}$는$$디코딩 가능한$fraction$으로 $표시$됩니다.$le$ L$}$ 또는$$ $({\displaystyle p}$ ,${\displaystyle L}$) \ $displaystyle ( p$ , $L$) - list$$ - decodeable $if{\displaystyle }$ y$$\ $displaystyle$ y $\ in$ \ Sigma ^ { $n$$$} ${\displaystyle 、}$ ${\displaystyle y}$$$$display$ $style$$\$ $in$$$$$\ sigma ^ { n } {\ 、 hamming $distance{\displaystyle }$ $pn$$${\$${\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\${\displaystyle }${\ {\ {\ {\ {\ {\ {\ {\ {\ {\

목록 디코딩 조합

코드의 리스트 디코딩 가능성과 최소 거리 및 속도 등의 기타 기본 파라미터 간의 관계는 상당히 잘 연구되어 왔다.모든 코드는 최소 거리의 절반을 넘어 Johnson 반지름이라고 불리는 경계까지 작은 목록을 사용하여 리스트 디코딩할 수 있는 것으로 나타났습니다.이는 ${\displaystyle \frac{\mathrm{d2}}{}}$보다${\displaystyle }훨씬{\displaystyle \frac{}{}}$ 큰 목록 디코딩 반경을 가진 (${\displaystyle p,}$ $)$ {$displaystyle (p, L)}$ {$displaystyle {tfrac {d}$ {2$}}$의${\displaystyle }$좋은 속도의 목록 디코딩$$ 가능 코드가 존재함을 증명하기 때문에 매우 중요합니다$.$즉$$, Johnson bound는 $d2({$ {$d}{2}})$보다 약간 큰 반경의$$ $Hamming{\displaystyle \frac{}{}}$ ball에 다수의 코드워드가 존재할 가능성을 배제하고 있으며$,$ 이는 리스트 디코딩으로 훨씬 더 많은 오류를 수정할 수 있음을 의미합니다.

리스트 디코딩 용량

정리(리스트 디코딩 용량).q${\displaystyle 2}$ 2, ${\displaystyle 0p}$ p${\displaystyle 1}$1 - ${\displaystyle \frac{1}{}}$q { $display style q$ \ $geqslant$ 2, 0 \ $leqslant$ p \$leqslant$1 - { \ $tfrac$ {$$$}$ {$$}$$} ${\displaystyle \mathrm{and<img\; alt="\{\backslash displaystyle\; q\backslash geqslant\; 2,0\backslash leqslant\; p\backslash leqslant\; 1-\{\backslash tfrac\; \{1\}\{q\}\}\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/4850487ba02f7a21d472772c39b3a01ca73d8ada"\; style="vertical-align:\; -1.338ex;\; width:20.554ex;\; height:3.676ex;">}}$ 0 0 0 0 0 0$다음$ 2개의 문장은 블록 $n$이 충분히 크다$.$

i) R${\displaystyle 1}$1 - ${\displaystyle \mathrm{Hq}{}_{}}$( p${\displaystyle }$) -$display$\ $displaystyle$R \$leqslant 1-H_{q}(p)$ - \$epsilon$의 경우$,{\displaystyle }$($p{\displaystyle }$$$, $O$( ${\displaystyle 1}$/ ${\displaystyle )}$) \ $displaystyle ( p$ , $O$ ( 1 / \ $epsilon$)이 존재합니다.

ii) R${\displaystyle 1{}_{}}$ - ${\displaystyle H_{}}$q (${\displaystyle p}$) + ${\$ \ $displaystyle$ R $\ geqslant 1-H_{q }$ + \ $epsilon$의 경우$,{\displaystyle }$ 모든 (${\displaystyle p}$,$$L ) \ $displaystyle ( p$ , $L$) } - list$$ - ${\displaystyle {\mathrm{decodable}}^{}}$ code는 $= Q （$ n ） （ n { $L{\displaystyle }$ （ n ） （ ） （ ） { l l l l l l L $omega$ L { L { L （ ） （ l L ） （ （ ） ）

어디에

$({displaystyle H_{q}(p)=p\log _{q}(q-1)-p\log _{q}p-(1-p)\log _{q}(1-p)})$

q { $display style$ $q$$}$ - ary$$ 엔트로피 ${\displaystyle \mathrm{함수}}$입니다.${\displaystyle \mathrm{p}}$$$ $（$${\displaystyle }$$0$, $1$$）$ 。\ $displaystyle$ [ ${\displaystyle 0}$ , 1${\displaystyle }$]$$。{ displaystyle $[ 0$ ,$$$1$ ]${\displaystyle }$。$}$

즉, 채널 용량에 근접하는 속도의 경우 효율적인 디코딩 알고리즘을 가능하게 하는 다항식 크기의 리스트가 있는 리스트 디코딩 가능한 코드가 존재하는 반면, 채널 용량을 초과하는 속도의 경우 리스트 크기가 기하급수적으로 증가하여 효율적인 디코딩 알고리즘의 존재를 배제합니다.

리스트 디코딩 용량의 증명은 q$\displaystyle$q\ary$$ 대칭 ${\displaystyle \mathrm{채널q}}$ ${\displaystyle {}_{}}$ $\$의 용량과 정확히 일치한다는 점에서 중요합니다.실제로 "리스트 디코딩 용량"이라는 용어는 적대적 채널 언더리스트 디코딩의 용량으로 해석해야 합니다.또한 리스트 디코딩 용량의 증명은 코드 레이트와 리스트 디코딩에서 수정할 수 있는 에러 비율 사이의 최적의 트레이드오프를 핀이 나타내는 중요한 결과입니다.

입증의 스케치

이 검증의 배후에 있는 아이디어는 랜덤코드가 ${\displaystyle \mathrm{선택}}$되고 ($p{\displaystyle }$${\displaystyle }$,$$) \ $display$ $style$ ($p$ , L$$)\ $display$( p , L )\ display ( p , L $)\backslash {\displaystyle }$ list$$ - decodable with ${\displaystyle {high}_{}}$ rate R ${\displaystyle ⩽{}_{}-}$H - ${\displaystyle 1\frac{\mathrm{}}{}}$ (${\displaystyle }$)을 나타내는 바이너리 $대칭채널{\displaystyle }$ ${\displaystyle B}$ ${\displaystyle {}_{}}$capacity에 대한 Shannon의 검증과 유사합니다.$playstyle$ R$\leqslant 1-H_{q}(p)-{\tfrac {1}{L}}}$ 상기$$ 수량을 초과하면 목록 $크기{\displaystyle }$L(\$displaystyle$ L$)$이 초다항적으로 커지는 것을 알 수 있습니다.

"bad" 이벤트는 수신된 $단어{\displaystyle }$ y ${\displaystyle [}$ [${\displaystyle {}^{}}$q ]${\displaystyle n^{}}${ $displaystyle$ y$\in [q$]^{$n$$}$ $및$ L + ${\displaystyle 1}$ { $displaystyle$L +$1$${\displaystyle {}_{}{메시지\mathrm{}}_{}}$ m${\displaystyle ,}$ ${\displaystyle ...,}$ ${\displaystyle {}_{}}$ ${\displaystyle l_{}}$ [$]${ $displaystyle m_0},$ \$ldots, m_{L}\in [$q]^{k$}$이(k})에 $따라{\displaystyle \mathcal{}}$ C${\displaystyle )}$가 발생하는 이벤트로 정의됩니다.$i)\in$ B$(y,pn$in B(y,pn$)$0${\displaystyle l}$L${\displaystyle (\backslash }$$displaystyle$ 0$\leqslant$ i$\leqslant$ L$)$에 대해$$p(\$displaystyle$ p$)$는 수정해야 할 오류의 $비율$이고 $displaystyle$ B$(yle,pn)$는 $radius{\displaystyle }$ ${\displaystyle \mathrm{pndisplay}}$$$pn(\$display$ pn$)$가 $수신$된 pn$)$입니다.

여기서 고정 $메시지{\displaystyle {}_{}}$ ${\displaystyle {mi}_{}}$${\displaystyle {}_{}}$${\displaystyle [}$ [${\displaystyle {}^q}$ ]${\displaystyle k}$\ \ $displaystyle$$$m$_$ { i } \ $in$[$q$]^{ $k$} \ $displaystyle$ $（$ ${\displaystyle y}$ ,$pn$$$$） a$ a a a a now now now now now now now now now now now now now now now now now${\displaystyle }$（ m ${\displaystyle {\_}_{}}$ $m_{i$} ） word c c c c c c c c c c c c c c c c c c c c $c{\displaystyle \mathcal{}}$ c c c c c word c c c c c c c c c [ [ [ [ [ [ associ$$ associ [ now now now

${\displaystyle \Pr \left [C(m_{i})\in B(y,pn)\right]=frac {mathrm {Vol}(y,pn)}{q^{n}}\leqslant q^{-n(1-H_{q}(p)}}},$

${\displaystyle \mathrm{여기}}$서 V ${\displaystyle {}_{}}$ ${\displaystyle l_{}}$q (${\displaystyle y}$ , ${\displaystyle pn}$) { $displaystyle Vol$_ {$q$}(y$$,$pn )$는 수신 단어$y{\displaystyle }$ { \ $displaystyle$ y$$}를$$$$ 중심으로 한 $반지름{\displaystyle }$ ${\displaystyle \mathrm{pn}}$ { $displaystyle$pn $}$의 해밍 볼의 부피입니다.위의 관계에서 부등식은 해밍 공의 부피 상한을 따른다.${\displaystyle {q{}_{}}^{}}$ ${\displaystyle {H_{}}^{}}$q (${\displaystyle p^{}}$) { $display style$ q ^ { $H$_ {$q$（ p$$ ） }}} : [${\displaystyle {}^{}}$q ]$.\$ $display$$style$[$q$]^{$n}$의 단어를 중심으로 $p$의 해밍 볼의 부피를 매우 정확하게 추정할 수 있습니다.다른 표현으로 해밍 볼 수 있습니다.증명 스케치를 계속 진행하기 위해$,{\displaystyle }$ 우리는 확률론($y, m$ ${\displaystyle \dots ,}$ ${\displaystyle m_{}}$ L$)$에서 나쁜 사건이 발생할 확률이 수량${\displaystyle {}^{}}q{\displaystyle {}^{}}$ -${\displaystyle n^{}}$ (${\displaystyle L^{}}$ ${\displaystyle {+1}^{}}$) (${\displaystyle 1^{}}$- $p-style )$로 상한임을 알 수 있는 결합을 상상한다$.$$p$

위와 같이 "모든" 불량 이벤트가 발생할 확률은 1$({displaystyle$1)$$$미만$이라고 할 수 있습니다.이를 나타내기 위해 수신 가능한 모든 $단어{\displaystyle }$ y ${\displaystyle [}$ [${\displaystyle {}^{}}$q ]${\displaystyle n^{}}$ $\$ $displaystyle$ y$\in [$$q$]^{$n}$ 및$$ [${\displaystyle q}$ ${\displaystyle {}^{}}{\displaystyle k^{}}$. $display$$style$ L$in$ in in in of of of의 모든 가능한 서브셋을 조사합니다.$^{k}.}$

이제 파트 (ii)의 증명으로 넘어가면 속도가 목록 디코딩 용량을 초과할 때 모든 $y{\displaystyle }$ ${\displaystyle q}$ [${\displaystyle {}^q}$]n$$\ $display style$ y$\in [q$]^{$n}$ 주위에$$ 초다항적으로 많은 코드워드가 있다는 것을 보여줘야 한다.$레이트{\displaystyle }$ R${\displaystyle 1}$ ${\displaystyle 1_{}}$- ${\displaystyle \mathrm{Hq}}$( ${\displaystyle p}$) + ${\$ { \ $display$ style R \ $geqslant$ 1-H_${q$} ( p ) + \ $epilon$ $code{\displaystyle }$ $\}$일 경우 C${\displaystyle b}$B ( ${\displaystyle y}$, ${\displaystyle \mathrm{pn}}$){ $displaystyle$$$\ $mathcal${ $C$}\ $cap B$( y , pn$)$는 초다항식적으로 크다는 ${\displaystyle 것}$을 나타낼 필요가 있습니다.$y\in [q]^{n}:$ 랜덤으로$$ 뽑힌 다음

$\displaystyle \Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]$

해밍볼은 번역이 불변하기 때문입니다.해밍 볼의 부피의 정의와 y$(\displaystyle$ y$)$가 [$(\$ 중에서$$ 균일하게 선택된다는 $사실$로부터 우리는 또한

$\displaystyle \Pr[c\in B(y,pn)]=\Pr[y\in B(c,pn)]=parc frac {mathrm {Vol}(y,pn)}{q^{n}}\geqslant q^{-n(1-H_{q}(p)-o(n)}}}$

다음으로 지시 $변수{\displaystyle {}_{}}$ ${\displaystyle X_{}}$ c$\$를 정의하겠습니다.

$\displaystyle X_{c}=begin{cases}1&cin B(y,pn)\0&{\text{othery}}\end{cases}}$

해밍볼의 부피를 예상해서

$\displaystyle {begin{aligned}E[B(y,pn)]={c\in\mathcal {C}\[4pt]={c\in\mathcal {C}\Pr[X_{c}=1]\[4]\sum qsum}\\[4pt]&=\sum q^{n(R-1+H_{q}(p)+o(1)}\\[4pt]&\geqslant q^{\Omega (n)}\end {aligned}}$

따라서 확률론적 방법에 따라 속도가 목록 복호화 용량을 초과할 경우 목록 크기가 초다항적으로 커짐을 보여주었다.이것으로 리스트 디코딩 용량의 프루프 스케치가 완료됩니다.

리스트 디코딩 알고리즘

1995년부터 2007년까지의 기간 동안, 부호화 이론 커뮤니티는 점진적으로 더 효율적인 리스트 디코딩 알고리즘을 개발하였다.Reed-Solomon 코드 알고리즘은 Johnson $반지름{\displaystyle \mathrm{}}$(${\displaystyle \sqrt{1}}$ -${\displaystyle \sqrt{}}$1${\displaystyle }$-${\$ \ $display style$1 - { \ $sqrt${ 1 - \ $delta }$ ） up \ displaystyle \ $delta$ } ${\$ {\ $the{\displaystyle }$ algorith$$$$ algorith algorith algorith algorith algorith 、 \ $displaystyle$ \ delta$$。단, Reed-Solomon code의 경우$$$\delta {\displaystyle }$ ${\displaystyle =1}$ - ${\displaystyle R\sqrt{}}$$$(\$displaystyle$ \$displaystyle$$= 1$-${\displayrt$ {R$$$}}}$ 의$$ 오차를 $수정{\displaystyle \mathrm{}}$ 할 수 있습니다.대표적인 리스트 디코딩 알고리즘은 다음과 같습니다.

• 수단 '95 – Reed-Solomon 코드에 대해 알려진 최초의 단순하지 않은 목록 디코딩 알고리즘으로, Madhu 수단에 의해 개발된 $최대{\displaystyle \mathrm{}1-2\sqrt{\mathrm{}}}$ $(\$의 에러를 효율적으로 목록 디코딩할 수 있습니다.
• Guruswami-Sudan '98 – Madhu 수단과 그의 박사과정 학생 Venkatesan Guruswami에 의해 Reed-Solomon 코드를 $최대{\displaystyle \mathrm{}1개}$의 R$(\$ 오류까지$$ 목록 디코딩하기 위한 위의 알고리즘 개선.
• Parvaresh – Vardy '05 – 획기적인 논문에서 Farzad Parvaresh와 Alexander Vardy는 1${\displaystyle }$-$$R (\$display 1-{\sqrt {R}})$의 $반경{\displaystyle }$ 이상으로 디코딩할 수 있는 저환율 R$$(\$display style$ R$\})$의 코드를 제시했습니다$.$이 코드들은 ${\displaystyle 1}$에 $의해{\displaystyle }$ 평가된 바리안트입니다${\displaystyle .}$$t$ 일반 리드-솔로몬 코드의 경우처럼 $(\displaystyle$ 1)가$$아닌$$$$1개의$$ 상관 다항식.
• Guruswami–Rudra '06-또 하나의 획기적인 발전에서 Venkatesan Guruswami과 Atri 루드라는 list-decoding 용량을 달성하는 것을 노골적인 코드를 준다면, 그것은, 그들은 목록 − R어떤ϵ 을에 ϵ{1-R-\epsilon\displaystyle}−은 반경 1까지 디코딩, 즉 opti과 0{\displaystyle \epsilon>0}., 이것은 error-correction.mal 레듬성듬뿍 담았습니다.이것은 약 50년 동안 열려 있던 질문에 대한 해답이다.이 연구는 ACM의 커뮤니케이션(최근 컴퓨터 사이언스에 게재된 가장 중요한 연구결과에 전념)의 연구 하이라이트 섹션에 초대되어 사이언스지 2007년 9월 21일자 '코딩과 컴퓨팅의 힘 합치'라는 기사에서 언급되었습니다.그들에게 주어지는 코드들은 접힌 리드-솔로몬 코드라고 불리며, 단순한 리드-솔로몬 코드일 뿐이지만 코드워드 기호를 조심스럽게 묶음으로써 더 큰 알파벳 위에 있는 코드처럼 보인다.

리드-솔로몬 코드에 대한 리스트 디코딩 알고리즘은 보편성과 그들이 가지고 있는 훌륭한 대수적 특성 때문에 연구자들의 주된 관심사였다.Reed-Solomon 코드의 리스트 디코딩 문제는 다음과 같이 공식화할 수 있습니다.

입력:${\displaystyle }$[$,$ + $({$q$$}) 리드-Solomon 코드의 경우, ${\displaystyle 1†}$ ${\displaystyle i}$$(\$$displaystyle$$$1$\leq$i\$leq$ n$)$의 쌍$({\displaystyle {\alpha }_{}}$i,$$ $i)$이 주어집니다.$여기$서 ${\displaystyle y_{}}$$$_$style$ i$_$ style } 。$(\$ _${i$는 유한 $필드{\displaystyle {}_{}}$ $(\$와 $에러{\displaystyle }$ 파라미터 e${\displaystyle =n}$-$$t(\$displaystyle$ e$=n-t$의 구별된 포인트입니다.

출력: 목표는 p$($${\displaystyle {\alpha }_{}}$i) $=$ $(\$ p$(\alpha$ _${i$})의 $메시지$ $길이$인 최대 k(\$displaystyle$ $k$$$$)$의 모든 $다항식{\displaystyle P(}$X)$$ F${\displaystyle {}_{}}$q [$X$]를 $찾는$ 것이다.보다$$ 많은 오류를 허용할 수 있도록 $가능한$한 작게$하고$ 싶습니다.

위의 공식에서 Reed-Solomon 코드의 리스트 디코딩 알고리즘의 일반적인 구조는 다음과 같습니다.

${\displaystyle \mathrm{1단계}}$: (인터폴레이션) Q${\displaystyle ({\alpha }_{}}$ i${\displaystyle {}_{}}$ ${\displaystyle {}_{}{i}_{}}$) ${\displaystyle =}$$$(\$display style$ Q$(\alpha$ _${i,y_{i$}) $= 0$$display style$ 1$\qle$인 0이 아닌 이변량 $다항식{\displaystyle }$Q$(X,Y)$를 찾습니다$.$

순서 2: (루트 검색/인자화)$Y$${\displaystyle }$-${\displaystyle p}$${\displaystyle }$( ${\displaystyle X}$) { $displaystyle$Y - p ($X$ )$$} { displaystyle Y - ${\displaystyle p}$$$( $X$ )${\displaystyle }$} { $displaystyle$Q ($X$, ${\displaystyle Y}$)$$} { $displaystyle$ Q ( X , $Y$) } $。$${\displaystyle Q}$(${\displaystyle X}$,${\displaystyle p}$ )${\displaystyle =}$ ${\displaystyle 0}$ {$displaystyle$ Q ( $X$, $p$( X ) =$0$${\displaystyle <img\; alt="\{\backslash displaystyle\; Q(X,p(X))=0\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/3b40f5156045aff83fe4a9b676d637c086b6dd9f"\; style="vertical-align:\; -0.838ex;\; width:15.881ex;\; height:2.843ex;">}$} 。이러한 각 다항식에 대해 p${\displaystyle }$(${\displaystyle {\alpha }_{}}$i ) ${\displaystyle =}$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$( \ $displaystyle$ p ( \ $alpha$$$_ { i } =$y$_ {$i$ } 의${\displaystyle }$i${\displaystyle }$[ $displaystyle$ i$]$의 $최소{\displaystyle }$$$t$$$$} 의 $값$을 확인합니다.세인트.

이변량 다항식을 효율적으로 인수분해할 수 있다는 사실을 고려할 때, 위의 알고리즘은 다항 시간에 실행된다.

복잡성 이론 및 암호학 응용 프로그램

몇 가지 흥미로운 코드 패밀리의 리스트 디코딩을 위해 개발된 알고리즘은 계산 복잡성과 암호학 분야에서 흥미로운 응용 프로그램을 찾아냈다.다음으로 코딩 이론 이외의 어플리케이션의 샘플리스트를 나타냅니다.

• 단방향 순열에서 하드코어 술어 구성.
• NP 검색 문제의 목격자를 예측합니다.
• 부울 함수의 경도를 증폭합니다.
• 랜덤 행렬의 영구 평균 대소문자 경도입니다.
• 추출기 및 의사 난수 생성기.
• 효율적인 배신자 추적

외부 링크

• 마두 수단의 목록 해독에 관한 조사
• 마두 수단의 코스 노트
• Luca Trevisan이 가르친 코스의 노트
• 벤카테산 구루스와미가 가르치는 코스의 노트
• ATRI Rudra가 가르치는 코스의 노트
• P. Elias, "소음 채널에 대한 목록 디코딩", 기술 보고서 335, MIT, 전자공학 연구소, 1957.
• P. Elias, "리스트 디코딩을 위한 오류 수정 코드", IEEE Transactions on Information Theory, vol. 37, 페이지 5–12, 1991.
• J. M. Wozencraft, "목록 디코딩", 분기별 진척 보고서, MIT, vol. 48, 페이지 90-95, 1958.
• 벤카테산 구루스와미의 박사 논문
• 리스트 디코딩 알고리즘 결과
• 접힌 리드-솔로몬 코드