맥윌리엄스 항등식 (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