맥윌리엄스 항등식 (MacWilliams Identity)

개요

• 유한체 \(\mathbb{F}_2\)위에 정의되는 선형코드 \(C\subset \mathbb{F}_2^{n}\)와 그 쌍대 \(C^{\perp}\)의 weight enumerator 사이에 성립하는 관계식
• weight enumerator를 다음과 같이 정의하자

\[W_C(X)=\sum_{\mathbf{a}\in C} X^{w(\mathbf{a})}\]

정리

\[ W_{C^{\perp}}(X)=\frac{(1+X)^n}{|C|}W_{C}\left(\frac{1-X}{1+X}\right) \]

동차다항식 버전

• weight enumerator를 다음과 같은 동차다항식으로 쓰기도 한다

\[ W(C;X,Y)=\sum_{\mathbf{a}\in C} X^{w(\mathbf{a})}Y^{n-w(\mathbf{a})} \]

정리

\[ W(C^{\perp};X,Y)=\frac{1}{|C|}W(C;Y-X,Y+X) \]

예

해밍코드

• [8,4,4] 해밍코드(Hamming codes) \(C\)의 weight enumerator는 다음과 같다

\[ W_C(x)=x^8+14 x^4+1 \]

• 다음을 만족한다

\[ W_{C^{\perp}}(x)=W_{C}(x)=\frac{(1+x)^8}{16}W_C(\frac{1-x}{1+x}) \]

콜레이 코드

• [24,12,8] 골레이 코드 (Golay code) \(C\)의 경우

\[ W_C(x)=x^{24}+759 x^{16}+2576 x^{12}+759 x^8+1 \]

• 다음이 성립한다

\[ W_{C^{\perp}}(x)=W_{C}(x)=\frac{(1+x)^{24}}{4096}W_C(\frac{1-x}{1+x}) \]

매스매티카 파일 및 계산 리소스

• https://docs.google.com/file/d/0B8XXo8Tve1cxMC1PaF82cU52d1k/edit

사전 형태의 자료

• http://en.wikipedia.org/wiki/Enumerator_polynomial

리뷰, 에세이, 강의노트

• Robin Chapman. The MacWilliams identity

관련논문

• Azniv Kasparian, Ivan Marinov, Mac Williams identities for linear codes as polarized Riemann-Roch conditions, arXiv:1604.08538 [cs.IT], April 28 2016, http://arxiv.org/abs/1604.08538

메타데이터

위키데이터

• ID : Q4454980