복호법

부호 이론에서 복호화(decoding)는 수신된 메시지를 주어진 부호의 부호 워드로 변환하는 과정이다. 메시지를 부호 워드에 매핑하는 여러 일반적인 방법이 존재한다. 이러한 방법들은 주로 이진 대칭 채널과 같은 잡음 섞인 채널을 통해 전송된 메시지를 복구하는 데 사용된다.

표기법

$C\subset \mathbb {F} _{2}^{n}$ 은 길이가 $n$ 인 이진 부호로 간주한다. $x,y$ 는 $\mathbb {F} _{2}^{n}$ 의 원소이며, $d(x,y)$ 는 해당 원소들 사이의 거리이다.

이상적 관찰자 복호화

메시지 $x\in \mathbb {F} _{2}^{n}$ 이 주어졌을 때, 이상적 관찰자 복호화(ideal observer decoding)는 부호 워드 $y\in C$ 를 생성한다. 이 과정은 다음 솔루션을 결과로 낸다.

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

예를 들어, 전송 후 메시지 $x$ 로서 수신될 가능성이 가장 높은 부호 워드 $y$ 를 선택할 수 있다.

복호화 관례

각 부호 워드가 예상되는 고정된 확률을 가지는 것은 아니다. 수신된 메시지로 변형될 가능성이 동일한 부호 워드가 둘 이상 있을 수 있다. 이러한 경우 송신자와 수신자는 복호화 관례에 대해 미리 합의해야 한다. 대중적인 관례는 다음과 같다.

부호 워드의 재전송을 요청한다 – 자동 재전송 요구(ARQ).
가장 가능성이 높은 부호 워드 집합 중에서 그에 더 가까운 임의의 부호 워드를 선택한다.
만약 다른 부호가 뒤따른다면, 부호 워드의 모호한 비트들을 소실(erasure)로 표시하고 외부 부호가 이를 명확히 해결하기를 기대한다.
시스템에 복호화 실패를 보고한다.

최대 가능도 복호화

수신된 벡터 $x\in \mathbb {F} _{2}^{n}$ 이 주어졌을 때, 최대 가능도 복호화(maximum likelihood decoding)는 다음을 최대화하는 부호 워드 $y\in C$ 를 선택한다.

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

즉, $y$ 가 전송되었다는 조건하에 $x$ 가 수신되었을 확률을 최대화하는 부호 워드 $y$ 를 찾는 것이다. 모든 부호 워드가 전송될 확률이 동일하다면 이 방식은 이상적 관찰자 복호화와 동일하다. 실제로 베이즈 정리에 의해 다음과 같이 나타낼 수 있다.

{\begin{aligned}\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})&{}={\frac {\mathbb {P} (x{\mbox{ received}},y{\mbox{ sent}})}{\mathbb {P} (y{\mbox{ sent}})}}\\&{}=\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})\cdot {\frac {\mathbb {P} (x{\mbox{ received}})}{\mathbb {P} (y{\mbox{ sent}})}}.\end{aligned}}

$\mathbb {P} (x{\mbox{ received}})$ 를 고정하면 $x$ 는 재구성되고, 모든 부호 워드가 전송될 확률이 동일하므로 $\mathbb {P} (y{\mbox{ sent}})$ 는 상수가 된다. 따라서, 변수 $y$ 의 함수로서 $\mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})$ 는 $\mathbb {P} (y{\mbox{ sent}}\mid x{\mbox{ received}})$ 가 최대화될 때 정확히 최대화되며, 주장이 성립한다.

이상적 관찰자 복호화와 마찬가지로, 유일하지 않은 복호화에 대해서는 관례를 합의해야 한다.

최대 가능도 복호화 문제는 정수 계획법 문제로 모델링될 수도 있다.^[1]

최대 가능도 복호화 알고리즘은 일반화된 분배 법칙을 적용하여 해결되는 "곱 함수 주변화"(marginalize a product function) 문제의 한 사례이다.^[2]

최소 거리 복호화

수신된 벡터 $x\in \mathbb {F} _{2}^{n}$ 이 주어졌을 때, 최소 거리 복호화(minimum distance decoding)는 해밍 거리를 최소화하는 부호 워드 $y\in C$ 를 선택한다.

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

즉, $x$ 와 최대한 가까운 부호 워드 $y$ 를 선택하는 것이다.

이산 무기억 채널에서 오류 확률 $p$ 가 1/2보다 엄격히 작으면 최소 거리 복호화는 최대 가능도 복호화와 동일하다. 만약

d(x,y)=d,\,

이면 다음과 같기 때문이다.

{\begin{aligned}\mathbb {P} (y{\mbox{ received}}\mid x{\mbox{ sent}})&{}=(1-p)^{n-d}\cdot p^{d}\\&{}=(1-p)^{n}\cdot \left({\frac {p}{1-p}}\right)^{d}\\\end{aligned}}

이는 (p가 1/2보다 작으므로) d를 최소화함으로써 최대화된다.

최소 거리 복호화는 최근접 이웃 복호화라고도 알려져 있다. 이는 표준 배열을 사용하여 보조받거나 자동화될 수 있다. 최소 거리 복호화는 다음 조건이 충족될 때 합리적인 복호화 방법이다.

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

이러한 가정은 이진 대칭 채널을 통한 전송에서 타당할 수 있다. 그러나 디스크의 단일 흠집이 많은 인접 기호나 부호 워드에 오류를 일으킬 수 있는 DVD와 같은 다른 매체에서는 부적절할 수 있다.

다른 복호화 방법과 마찬가지로 유일하지 않은 복호화에 대해서는 관례를 합의해야 한다.

신드롬 복호화

신드롬 복호화(syndrome decoding)는 오류가 발생하는 잡음 섞인 채널에서 선형 부호를 복호화하는 매우 효율적인 방법이다. 본질적으로 신드롬 복호화는 축소된 룩업 테이블을 사용하는 최소 거리 복호화이다. 이는 부호의 선형성 덕분에 가능하다.^[3]

$C\subset \mathbb {F} _{2}^{n}$ 이 패리티 검사 행렬 $H$ 를 가진 길이 $n$ , 최소 거리 $d$ 인 선형 부호라고 가정하자. 그러면 $C$ 는 채널에서 발생한 최대

t=\left\lfloor {\frac {d-1}{2}}\right\rfloor

개의 오류를 정정할 수 있다(오류가 $t$ 개 이하로 발생하면 최소 거리 복호화가 여전히 잘못 전송된 부호 워드를 올바르게 복호화하기 때문이다).

이제 부호 워드 $x\in \mathbb {F} _{2}^{n}$ 이 채널을 통해 전송되고 오류 패턴 $e\in \mathbb {F} _{2}^{n}$ 이 발생했다고 가정하자. 그러면 $z=x+e$ 가 수신된다. 일반적인 최소 거리 복호화는 크기가 $|C|$ 인 테이블에서 벡터 $z$ 와 가장 잘 일치하는 것, 즉 모든 $y\in C$ 에 대해 다음을 만족하는 원소 $c\in C$ (반드시 유일할 필요는 없음)를 찾는다.

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

신드롬 복호화는 모든 $x\in C$ 에 대해 다음을 만족하는 패리티 행렬의 성질을 이용한다.

Hx=0

수신된 $z=x+e$ 의 신드롬(syndrome)은 다음과 같이 정의된다.

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

이진 대칭 채널에서 최대 가능도 복호화를 수행하려면 $He$ 를 $e$ 로 매핑하는 미리 계산된 크기 $2^{n-k}$ 의 테이블을 조회해야 한다.

이 방식은 이미 표준 배열 복호화의 복잡도보다 현저히 낮다.

또한, 전송 중에 $t$ 개 이하의 오류가 발생했다는 가정하에 수신자는 다음과 같이 더 축소된 크기의 테이블에서 $He$ 값을 조회할 수 있다.

{\begin{matrix}\sum _{i=0}^{t}{\binom {n}{i}}\\\end{matrix}}

리스트 복호화

정보 집합 복호화

이는 모든 오류 위치를 추측하는 것보다 충분한 수의 오류 없는 위치를 추측하는 것이 더 쉽다는 관찰에 기반한 라스베이거스 알고리즘 확률적 방법군이다.

가장 단순한 형태는 프랑에(Prange)에 의한 것이다. $G$ 를 인코딩에 사용된 $C$ 의 $k\times n$ 생성 행렬이라고 하자. $G$ 에서 $k$ 개의 열을 무작위로 선택하고, 이에 대응하는 $G$ 의 부분 행렬을 $G'$ 라고 하자. 적절한 확률로 $G'$ 는 전체 계수(full rank)를 가질 것이며, 이는 메시지 $m$ 에 대한 $C$ 의 부호 워드 $c=mG$ 의 해당 위치 부분 벡터를 $c'$ 라고 할 때, $m$ 을 $m=c'G'^{-1}$ 로 복구할 수 있음을 의미한다. 따라서 수신된 단어 $y$ 의 이 $k$ 개 위치에 오류가 포함되지 않아 전송된 부호 워드의 위치와 일치하는 운 좋은 경우라면 복호화가 가능하다.

만약 $t$ 개의 오류가 발생했다면, 이와 같이 운 좋게 열을 선택할 확률은 $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}\approx \exp(-tk/n)$ 로 주어진다.

이 방법은 스턴(Stern)^[4] 및 안 캉토(Anne Canteaut)와 상드리에(Sendrier)^[5] 등에 의해 다양한 방식으로 개선되었다.

부분 응답 최대 가능도

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

비터비 복호화기

비터비 복호화기는 길쌈 부호에 기반한 순방향 오류 정정을 사용하여 인코딩된 비트스트림을 복호화하기 위해 비터비 알고리즘을 사용한다. 해밍 거리는 하드 결정 비터비 복호화기의 척도로 사용된다. 제곱 유클리드 거리는 소프트 결정 복호화기의 척도로 사용된다.

최적 결정 복호화 알고리즘 (ODDA)

비대칭 TWRC 시스템을 위한 최적 결정 복호화 알고리즘(ODDA).^[6]

같이 보기

오류 검출 정정

각주

↑ Feldman, Jon; Wainwright, Martin J.; Karger, David R. (March 2005). 《Using Linear Programming to Decode Binary Linear Codes》. 《IEEE Transactions on Information Theory》 51. 954–972쪽. CiteSeerX 10.1.1.111.6585. doi:10.1109/TIT.2004.842696. S2CID 3120399.
↑ Aji, Srinivas M.; McEliece, Robert J. (March 2000). 《The Generalized Distributive Law》 (PDF). 《IEEE Transactions on Information Theory》 46. 325–343쪽. doi:10.1109/18.825794.
↑ Beutelspacher, Albrecht; Rosenbaum, Ute (1998). 《Projective Geometry》. 케임브리지 대학교 출판부. 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 388. Springer-Verlag. 106–113쪽. doi:10.1007/BFb0019850. ISBN 978-3-540-51643-9.
↑ Ohta, Kazuo; Pei, Dingyi 편집 (1998). 《Advances in Cryptology — ASIACRYPT'98》. Lecture Notes in Computer Science 1514. 187–199쪽. doi:10.1007/3-540-49649-1. ISBN 978-3-540-65109-3. S2CID 37257901.
↑ Siamack Ghadimi (2020), 《Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system;》, Universal Journal of Electrical and Electronic Engineering

외부 링크

Hill, Raymond (1986). 《A first course in coding theory》. Oxford Applied Mathematics and Computing Science Series. 옥스퍼드 대학교 출판부. 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》 2판. Graduate Texts in Mathematics (GTM) 86. 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》 51. 954–972쪽. CiteSeerX 10.1.1.111.6585. doi:10.1109/TIT.2004.842696. S2CID 3120399.

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

[Beutelspacher-Rosenbaum_1998-3] Beutelspacher, Albrecht; Rosenbaum, Ute (1998). 《Projective Geometry》. 케임브리지 대학교 출판부. 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 388. Springer-Verlag. 106–113쪽. doi:10.1007/BFb0019850. ISBN 978-3-540-51643-9.

[Ohta_1998-5] Ohta, Kazuo; Pei, Dingyi 편집 (1998). 《Advances in Cryptology — ASIACRYPT'98》. Lecture Notes in Computer Science 1514. 187–199쪽. doi:10.1007/3-540-49649-1. ISBN 978-3-540-65109-3. S2CID 37257901.

[6] Siamack Ghadimi (2020), 《Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system;》, Universal Journal of Electrical and Electronic Engineering

[1]

[2]

[3]

[4]

[5]

[6]