맥윌리엄스 항등식 (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}) \]
매스매티카 파일 및 계산 리소스
사전 형태의 자료
리뷰, 에세이, 강의노트
- 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'}]