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

개요

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

<math>W_C(X)=\sum_{\mathbf{a}\in C} X^{w(\mathbf{a})}</math>

정리

<math>

W_{C^{\perp}}(X)=\frac{(1+X)^n}{|C|}W_{C}\left(\frac{1-X}{1+X}\right) </math>

동차다항식 버전

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

<math>

W(C;X,Y)=\sum_{\mathbf{a}\in C} X^{w(\mathbf{a})}Y^{n-w(\mathbf{a})} </math>

정리

<math>

W(C^{\perp};X,Y)=\frac{1}{|C|}W(C;Y-X,Y+X) </math>

예

해밍코드

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

<math>

W_C(x)=x^8+14 x^4+1 </math>

• 다음을 만족한다

<math>

W_{C^{\perp}}(x)=W_{C}(x)=\frac{(1+x)^8}{16}W_C(\frac{1-x}{1+x}) </math>

콜레이 코드

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

<math>

W_C(x)=x^{24}+759 x^{16}+2576 x^{12}+759 x^8+1 </math>

• 다음이 성립한다

<math>

W_{C^{\perp}}(x)=W_{C}(x)=\frac{(1+x)^{24}}{4096}W_C(\frac{1-x}{1+x}) </math>

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

• 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

Spacy 패턴 목록

• [{'LOWER': 'enumerator'}, {'LEMMA': 'polynomial'}]