패리티-체크 매트릭스

코딩 이론에서 선형 블록 코드 C의 패리티-체크 매트릭스는 코드 워드의 구성요소가 충족해야 하는 선형 관계를 설명하는 매트릭스다. 특정 벡터가 암호어인지, 알고리즘 디코딩에도 사용되는지를 결정하는 데 사용할 수 있다.

정의

형식적으로, 선형 코드 C의 패리티 체크 매트릭스 H는 이중 코드 C의^⊥ 제너레이터 매트릭스다. 즉, 매트릭스 벡터 제품 Hc^⊤ = 0인 경우에만 코드워드 c가 C에 있다는 것을 의미한다(일부^[1] 저자는 이를 동등한 형태로, cH^⊤ = 0).

패리티 검사 행렬의 행은 패리티 검사 방정식의 계수다.^[2] 즉, 각 코드 워드의 특정 숫자(성분)의 선형 조합이 0과 어떻게 같은지를 보여준다. 예를 들어 패리티 검사 매트릭스

H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]

=

H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]

[ 0

H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]

H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]

H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]

1 1

H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]

H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]

H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]

{\

패리티 검사 방정식을 압축적으로 나타낸다.

{\

}}&=0\\c_{1}+c_{2

}}&=0\end{aigned

벡터 $(c_{1},c_{2},c_{3},c_{4})$ $(c_{1},c_{2},c_{3},c_{4})$ , $(c_{1},c_{2},c_{3},c_{4})$ c $(c_{1},c_{2},c_{3},c_{4})$ , $(c_{1},c_{2},c_{3},c_{4})$ $(c_{1},c_{2},c_{3},c_{4})$ , $(c_{1},c_{2},c_{3},c_{4})$ 4 $(c_{1},c_{2},c_{3},c_{4})$ ) ${\displaystyle(c_{1},c_{2},c_{3},c_{4}})$ 이(가) C의 코드 워드가 되도록 충족되어야 $(c_{1},c_{2},c_{3},c_{4})$ 한다.

패리티-체크 매트릭스의 정의에서 그것은 패리티-체크 매트릭스 H의 모든 d - 1 열이 선형적으로 독립되어 있는 반면 H의 d 열은 선형적으로 종속되어 있는 최소 숫자 d이다.

패리티 검사 매트릭스 생성

주어진 코드에 대한 패리티 검사 매트릭스는 해당 제너레이터 매트릭스(또는 그 반대)에서 파생될 수 있다.^[3] [n,k] 코드의 제너레이터 매트릭스가 표준 형식인 경우

{\

I_{k} P\end{bmatrix

패리티 검사 매트릭스는 다음과 같이 제공된다.

H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}

=

H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}

[

H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}

-

H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}

H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}

H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}

H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}

-

H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}

H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}

{\

때문에

GH^{\top }=P-P=0

GH^{\top }=P-P=0

GH^{\top }=P-P=0

=

GH^{\top }=P-P=0

-

GH^{\top }=P-P=0

=

GH^{\top }=P-P=0

GH^{\top }=P-P=0

.

부정은 유한장 F에서_q 수행된다. 기본 필드의 특성이 2진수 코드처럼 2(즉, 해당 필드의 1 + 1 = 0)이면 -P = P이므로 부정은 불필요하다는 점에 유의한다.

예를 들어, 2진수 코드에 제너레이터 매트릭스가 있는 경우

G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]

=

G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]

[ 1

G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]

G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]

G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]

1

G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]

G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]

G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]

G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]

{\

G

=\왼쪽[{\begin{array}{cc ccc}1&0&1&1&1&1\\\end{array

패리티 검사 매트릭스는

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

=

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

[ 1

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

0

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]

{\

\\\

1&0&0&0\\\nd{array

G가 $k\times n$ $k\times n$ $k\times n$ $k\times n$ 행렬인 $k\times n$ 반면 H는 $(n-k)\times n$ (n $(n-k)\times n$ - $(n-k)\times n$ ) $(n-k)\times n$ $(n-k)\times n$ $(n-k)\time n$ 행렬인 $(n-k)\times n$ 것을 확인할 수 있다.

신드롬

주변 벡터 공간의 (행) 벡터 x에 대해 s = Hx는^⊤ x의 증후군이라고 불린다. 벡터 x는 s = 0인 경우에만 코드 워드다. 신드롬의 계산은 신드롬 해독 알고리즘의 기초가 된다.^[4]

참고 항목

해밍 코드

메모들

^ 예를 들어, 1992년 로마 페이지 200
^ 1992년 로마서 201쪽
^ 1998 페이지 9
^ 1998년 페이지 20

참조

Hill, Raymond (1986). A first course in coding theory. Oxford Applied Mathematics and Computing Science Series. Oxford University Press. pp. 69. ISBN 0-19-853803-0.
Pless, Vera (1998), Introduction to the Theory of Error-Correcting Codes (3rd ed.), Wiley Interscience, ISBN 0-471-19047-0
Roman, Steven (1992), Coding and Information Theory, GTM, vol. 134, Springer-Verlag, ISBN 0-387-97812-7
J.H. van Lint (1992). Introduction to Coding Theory. GTM. Vol. 86 (2nd ed.). Springer-Verlag. pp. 34. ISBN 3-540-54894-7.

[1] 예를 들어, 1992년 로마 페이지 200

[2] 1992년 로마서 201쪽

[3] 1998 페이지 9

[4] 1998년 페이지 20

[1]

[2]

[3]

[4]

Search

패리티-체크 매트릭스

네임스페이스

더

목차

정의

패리티 검사 매트릭스 생성

신드롬

참고 항목

메모들

참조