디코딩 방법

코딩 이론에서 디코딩은 수신된 메시지를 주어진 코드의 코드 워드로 변환하는 과정이다. 암호문자에 메시지를 매핑하는 많은 일반적인 방법이 있다. 이것들은 종종 이진 대칭 채널과 같이 노이즈가 많은 채널을 통해 전송된 메시지를 복구하는 데 사용된다.

표기법

$C\subset \mathbb {F} _{2}^{n}$ is considered a binary code with the length $n$ ; $x,y$ shall be elements of $\mathbb {F} _{2}^{n}$ ; and $d(x,y)$ is the distance between those elements.

이상적인 관찰자 디코딩

메시지 $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ ${\$ x $\in \mathb {F} _{2}^{n$ 그러면 이상적인 관찰자 해독은 코드 워드 $y\in C$ $y\in C$ C ${\displaysty y\in$ C $}$ 를 생성한다 $y\in C$ 이 프로세스를 통해 다음과 같은 해결책이 도출된다.

\mathb{P}(y{\mbox{resent}\mbox{recept}\mbox{recept})

예를 들어, 전송 후 $x$ $메시지$ x{\ $displaystyle$ x $}$ 로 수신될 가능성이 가장 높은 코드 $y$ 워드 $y$ $y$ 을(를) 선택할 수 있다.

디코딩 규칙

각 코드 워드는 예상 가능한 가능성이 없다. 수신된 메시지로 변이될 가능성이 동일한 두 개 이상의 코드 워드가 있을 수 있다. 이러한 경우 송신자와 수신자는 해독 규약에 대해 사전에 합의해야 한다. 인기 있는 관례는 다음과 같다.

코드 워드의 재전송 요청 - 자동 반복 요청.
가장 가능성이 높은 코드 워드 집합에서 그것에 가까운 임의의 코드 워드를 선택하십시오.
다른 코드가 뒤따를 경우 코드 워드의 모호한 부분을 지운 것으로 표시하고 외부 코드가 이를 모호하게 만들기를 희망한다.

최대우도 디코딩

수신된 벡터 $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ ${\$ 최대우도 $x\in {\mathbb {F}}_{2}^{n}$ 디코딩이 최대화된 $y\in C$ 코드 워드 $y\in C$ $y\in C$ C $y\in C$ 을(를) 선택하십시오.

\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})

\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})

y

\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})

)

{\displaystyle \mathb

{

P}(x{\mbox{ 수신}}\mid

y

{\mbox{ 전송

즉, $y$ $y$ 이(가) 전송된 $y$ 경우 $x$ $x$ 이(가) 수신될 $x$ 확률을 최대화하는 $y$ 워드 y ${\displaysty y}$ 이다. 만약 모든 암호어가 똑같이 전송될 가능성이 있다면, 이 계획은 이상적인 관찰자 해독과 같다. 사실, 베이즈 정리(Bayes Organy에 의해

{\displaystyle{\begin}\mbox{regated}\mathb {P}(x{\mbox{receed}}\mid y{\mbox{pass})(x{\mbox{receed},y{\mbox{}})}{\mbathb {P}(y\mbox{p}}}}}}}}}}}})}}\\\{}}=\matcb {P}(y{\mbox{pass}\mid x{\mbox{수신})\cdot {\frac {\matcb {P}(x{mbox{수신}}})}{\mbox{수신}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}"(y{{{{{{{{{{{{{{{{{{{{{{{{수신송}}}}\end{정렬}}}

$\mathbb {P} (x{\mbox{ received}})$ $\mathbb {P} (x{\mbox{ received}})$ $\mathb {P}(x{\mbox{수신})$ 을(를) 수정하면 $\mathbb {P} (x{\mbox{ received}})$ $x$ $x$ 을(를) 재구성하고 $x$ $\mathbb {P} (y{\mbox{ sent}})$ ${\displaystyle \mathb {P}(y{mbox{}})$ 을(보냄)는 모든 암호문이 동일하게 전송됨)할 가능성이 있으므로 일정하게 된다 $\mathbb {P} (y{\mbox{ sent}})$ . Therefore, $\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})$ is maximised as a function of the variable $y$ precisely when $\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})$ is maximised, and t그의 주장은 다음과 같다.

이상적인 관찰자 디코딩과 마찬가지로 비독점 디코딩에 대한 규약이 합의되어야 한다.

최대우도 디코딩 문제는 정수 프로그래밍 문제로도 모델링할 수 있다.^[1]

최대우도 디코딩 알고리즘은 일반화된 분배 법칙을 적용함으로써 해결되는 "제품 함수의 marginize a product function" 문제의 한 예다.^[2]

최소 거리 디코딩

수신된 코드 워드 $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ ${\$ 이 $x\in \mathbb {F} _{2}^{n}$ 가) 지정되면 최소 디코딩 거리 $y\in C$ $y\in C$ $y\in C$ ${\displaysty y\in C}$ 를 $y\in C$ 선택하여 해밍 거리를 최소화하십시오.

d(x,y)=\#\{i:x_{i}\not =y_{i}\}}

즉, 가능한 한 $x$ $x$ 에 가까운 $y$ 코드 $워드$ y $y$ 를 선택하십시오 $x$

이산 메모리 없는 채널 $p$ $p$ 의 오류 확률이 엄격히 1/2 미만인 $p$ 경우, 최소 거리 디코딩은 다음과 같은 경우 최대우도 디코딩과 동일하다는 점에 유의하십시오.

d(x,y)=d,\,}

{\begin{aigned}\mbox{p}}\mad x{\mbox{p}}}}&#{{n-d}\cdot p^{d}\&}=1-p^{n}}\cdot \{p}{p}{p}{p}}}}{p}}}}}}}}}}}}}}}오른쪽)^{d}\\\end{aigned}}

(p가 1/2 미만이기 때문에) d를 최소화하여 최대화한다.

최소 거리 디코딩은 가장 가까운 이웃 디코딩이라고도 한다. 표준 배열을 사용하여 보조하거나 자동화할 수 있다. 최소 거리 디코딩은 다음 조건이 충족될 때 합리적인 디코딩 방법이다.

오류가 발생할 $p$ 확률 $p$ $p$ 은(는) 기호의 위치와 무관하다.
오류는 독립적인 사건이다 – 메시지의 한 위치에서 발생한 오류는 다른 위치에 영향을 주지 않는다.

이러한 가정은 이항 대칭 채널을 통한 전송에 합리적일 수 있다. 디스크의 스크래치 하나 때문에 많은 이웃 기호나 코드 워드에 오류가 발생할 수 있는 DVD와 같은 다른 미디어에는 불합리할 수 있다.

다른 디코딩 방법과 마찬가지로, 고유하지 않은 디코딩에 대한 규약이 합의되어야 한다.

디코딩 증후군

신드롬 디코딩은 소음이 많은 채널, 즉 오류가 발생하는 채널에서 선형 코드를 디코딩하는 매우 효율적인 방법이다. 본질적으로 신드롬 디코딩은 축소된 룩업 테이블을 사용하여 디코딩하는 최소 거리다. 이것은 코드의 선형성에 의해 허용된다.^[3]

$C\subset \mathbb {F} _{2}^{n}$ $C\subset \mathbb {F} _{2}^{n}$ $C\subset \mathbb {F} _{2}^{n}$ $C\subset \mathbb {F} _{2}^{n}$ ${\$ 이(가 $d$ ) 패리티 $확인$ H {\ $displaystyle H}$ 의길이 n {\ $displaystyle$ d}의 선형 $C\subset \mathbb {F} _{2}^{n}$ 코드라고 가정해 보십시오 $H$ $그렇다면$ C ${\displaystyty C}$ 은 $C$ 최대 보정할 수 있다.

t=\좌측\l바닥 {\frac {d-1}{2}}\우측\표시장치

채널에서 발생한 오류( $t$ $t$ 개 이하의 오류가 $t$ 발생하더라도 최소 거리 디코딩은 여전히 잘못 전송된 코드 워드를 올바르게 디코딩할 수 있음)

이제 코드 워드 $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ $x\in \mathbb {F} _{2}^{n}$ ${\$ x $\in \mathb {F} _{2}^{n}}$ 을(를) 채널로 전송하고 $x\in \mathbb {F} _{2}^{n}$ 오류 패턴 $e\in \mathbb {F} _{2}^{n}$ $e\in \mathbb {F} _{2}^{n}$ F $e\in \mathbb {F} _{2}^{n}$ ${\$ { $F} _{2}^{n}}}}$ 이 발생한다고 $e\in \mathbb {F} _{2}^{n}$ 가정합시다. 그러면 $z=x+e$ = $z=x+e$ + $z=x+e$ $z=x+e$ 이(가) 수신된다 $z=x+e$ . 일반적인 최소 거리 디코딩은 크기 $|C|$ $displaystyle$ C $}$ 의 $z$ 표에서 $벡터$ z $z$ 을(를) 조회하여 가장 $|C|$ $c\in C$ 가까운 일치(필수적으로 고유한 것은 아님) $c\in C$ $c\in C$ $c\in C$ $c\in C$ 을(를) 검색한다.

d(c,z)\leq d(y,z)

모든 $y\in C$ $y\in C$ $y\in C$ $y\in C$ 에 대해 $y\in C$ 증후군 디코딩은 다음과 같은 패리티 매트릭스의 속성을 이용한다.

Hx=0

모든 $x\in C$ $x\in C$ $x\in C$ $x\in C$ 에 대해 $x\in C$ 수신된 $z=x+e$ = $z=x+e$ + $z=x+e$ $z=x+e$ 의 증후군은 다음과 같이 정의된다 $z=x+e$ .

Hz=H(x+e)=Hx+He=0+He=He=헤

이진 대칭 채널에서 ML 디코딩을 수행하려면 크기 $2n$ $2^{n-k}$ - k {\ $displaystyle$ 2^{ $n-k}$ 의 사전 계산된 표를 찾아 $2^{n-k}$ H $e$ $He$ 을(를) $e$ $e$ 에 $He$ 매핑해야 한다 $e$

이는 이미 표준 배열 디코딩보다 훨씬 덜 복잡하다는 점에 유의하십시오.

그러나 전송 중에 $t$ $t$ 개 이상의 오류가 $t$ 발생하지 않았다는 가정 하에 수신기는 보다 축소된 크기의 표에서 $He$ $H$ $e$ $He$ 값을 조회할 수 있다.

{\displaysty}\sum _{i=0}^{t}{\binom {n}\\end{nd}}}

목록 디코딩

정보 세트 디코딩

이는 라스베이거스 확률론적 방법의 한 계열로, 모든 오류 발생을 추측하는 것보다 오류가 없는 충분한 위치를 추측하는 것이 더 쉽다는 관찰을 바탕으로 한 것이다.

가장 간단한 형태는 Prange 때문이다. $G$ $G$ 을(를) 인코딩에 사용되는 $C$ $C$ $C$ 의 $k\times n$ $k\times n$ $k\times n$ $k\times n$ 생성기 $k\times n$ 행렬로 설정하십시오 $G$ . $G$ $G$ 의 k $K$ 열을 $k$ 임의로 $G$ 선택하고 $G$ $'$ $G$ 의 해당 $G'$ 하위 $G$ 을 가리킨다 $G$ 합리적인 $G'$ 로 G{{\ $displaystyle$ G $'}$ 은(는) 전체 순위를 가지며, 이는 $c^{}$ {{\ $displaysty c'$ 를 하위 섹션으로 $c'$ 지정하면 된다는 $G'$ 것을 의미한다.or for the corresponding positions of any codeword $c=mG$ of $C$ for a message $m$ , we can recover $m$ as $m=c'G'^{-1}$ . Hence, if we were lucky that these $k$ positions of the r인식된 단어 $y$ ${\displaystyle$ y $}$ 에 오류가 없으므로 $y$ 전송된 코드 워드의 위치와 동일하면 해독할 수 있다.

$t$ $t$ 오류가 $t$ 발생한 경우 $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}$ (n $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}$ - $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}$ $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}$ ) $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}$ / $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}$ ( $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}$ $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}$ ) ${\$ 에 의해 이러한 열 선택 가능성이 주어진다 $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}$

이 방법은 스턴과^[4] 칸토우, 센디어 등 다양한 방법으로 개선되었다.^[5]

부분 반응 최대우도

부분 응답 최대우도(PRML)는 자기 디스크나 테이프 드라이브의 헤드에서 나오는 약한 아날로그 신호를 디지털 신호로 변환하는 방법이다.

비테르비 디코더

비터비 디코더는 비터비 알고리즘을 사용하여 콘볼루션 코드에 기초한 정방향 오류 보정을 사용하여 인코딩된 비트스트림을 디코딩하는 데 사용한다. 해밍 거리는 어려운 결정 Viterbi 디코더의 측정 기준으로 사용된다. 제곱 유클리드 거리는 소프트 의사결정 디코더의 측정 기준으로 사용된다.

참고 항목

참조

^ Feldman, Jon; Wainwright, Martin J.; Karger, David R. (March 2005). "Using Linear Programming to Decode Binary Linear Codes". IEEE Transactions on Information Theory. Vol. 51, no. 3. pp. 954–972. doi:10.1109/TIT.2004.842696.
^ Aji, Srinivas M.; McEliece, Robert J. (March 2000). "The Generalized Distributive Law" (PDF). IEEE Transactions on Information Theory. 46 (2): 325–343. doi:10.1109/18.825794.
^ Beutelspacher, Albrecht; Rosenbaum, Ute (1998). Projective Geometry. Cambridge University Press. p. 190. ISBN 0-521-48277-1.
^ Stern, Jacques (1989). "A method for finding codewords of small weight". Coding Theory and Applications. Lecture Notes in Computer Science. Vol. 388. Springer-Verlag. pp. 106–113. doi:10.1007/BFb0019850. ISBN 978-3-540-51643-9.
^ Ohta, Kazuo; Pei, Dingyi, eds. (1998). Cryptanalysis of the Original McEliece Cryptosystem. Advances in Cryptology — ASIACRYPT'98. Lecture Notes in Computer Science. Vol. 1514. pp. 187–199. doi:10.1007/3-540-49649-1. ISBN 978-3-540-65109-3. S2CID 37257901.

추가 읽기

Hill, Raymond (1986). A first course in coding theory. Oxford Applied Mathematics and Computing Science Series. Oxford University Press. ISBN 978-0-19-853803-5.
Pless, Vera (1982). Introduction to the theory of error-correcting codes. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons. ISBN 978-0-471-08684-0.
van Lint, Jacobus H. (1992). Introduction to Coding Theory. Graduate Texts in Mathematics (GTM). Vol. 86 (2 ed.). Springer-Verlag. ISBN 978-3-540-54894-2.

[Feldman_2005-1] Feldman, Jon; Wainwright, Martin J.; Karger, David R. (March 2005). "Using Linear Programming to Decode Binary Linear Codes". IEEE Transactions on Information Theory. Vol. 51, no. 3. pp. 954–972. doi:10.1109/TIT.2004.842696.

[Aji-McEliece_2000-2] Aji, Srinivas M.; McEliece, Robert J. (March 2000). "The Generalized Distributive Law" (PDF). IEEE Transactions on Information Theory. 46 (2): 325–343. doi:10.1109/18.825794.

[Beutelspacher-Rosenbaum_1998-3] Beutelspacher, Albrecht; Rosenbaum, Ute (1998). Projective Geometry. Cambridge University Press. p. 190. ISBN 0-521-48277-1.

[Stern_1989-4] Stern, Jacques (1989). "A method for finding codewords of small weight". Coding Theory and Applications. Lecture Notes in Computer Science. Vol. 388. Springer-Verlag. pp. 106–113. doi:10.1007/BFb0019850. ISBN 978-3-540-51643-9.

[Ohta_1998-5] Ohta, Kazuo; Pei, Dingyi, eds. (1998). Cryptanalysis of the Original McEliece Cryptosystem. Advances in Cryptology — ASIACRYPT'98. Lecture Notes in Computer Science. Vol. 1514. pp. 187–199. doi:10.1007/3-540-49649-1. ISBN 978-3-540-65109-3. S2CID 37257901.

[1]

[2]

[3]

[4]

[5]

Search