"맥윌리엄스 항등식 (MacWilliams Identity)"의 두 판 사이의 차이
둘러보기로 가기
검색하러 가기
Pythagoras0 (토론 | 기여) (section '관련논문' added) |
Pythagoras0 (토론 | 기여) |
||
| 1번째 줄: | 1번째 줄: | ||
==개요== | ==개요== | ||
| − | * 유한체 | + | * 유한체 <math>\mathbb{F}_2</math>위에 정의되는 선형코드 <math>C\subset \mathbb{F}_2^{n}</math>와 그 쌍대 <math>C^{\perp}</math>의 weight enumerator 사이에 성립하는 관계식 |
* 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) | W_{C^{\perp}}(X)=\frac{(1+X)^n}{|C|}W_{C}\left(\frac{1-X}{1+X}\right) | ||
| − | + | </math> | |
| 12번째 줄: | 12번째 줄: | ||
==동차다항식 버전== | ==동차다항식 버전== | ||
* weight enumerator를 다음과 같은 동차다항식으로 쓰기도 한다 | * weight enumerator를 다음과 같은 동차다항식으로 쓰기도 한다 | ||
| − | + | :<math> | |
W(C;X,Y)=\sum_{\mathbf{a}\in C} X^{w(\mathbf{a})}Y^{n-w(\mathbf{a})} | 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) | W(C^{\perp};X,Y)=\frac{1}{|C|}W(C;Y-X,Y+X) | ||
| − | + | </math> | |
| 24번째 줄: | 24번째 줄: | ||
==예== | ==예== | ||
===해밍코드=== | ===해밍코드=== | ||
| − | * [8,4,4] [[해밍코드(Hamming codes)]] | + | * [8,4,4] [[해밍코드(Hamming codes)]] <math>C</math>의 weight enumerator는 다음과 같다 |
| − | + | :<math> | |
W_C(x)=x^8+14 x^4+1 | 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}) | 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)]] | + | * [24,12,8] [[골레이 코드 (Golay code)]] <math>C</math>의 경우 |
| − | + | :<math> | |
W_C(x)=x^{24}+759 x^{16}+2576 x^{12}+759 x^8+1 | 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}) | W_{C^{\perp}}(x)=W_{C}(x)=\frac{(1+x)^{24}}{4096}W_C(\frac{1-x}{1+x}) | ||
| − | + | </math> | |
2020년 11월 13일 (금) 07:01 판
개요
- 유한체 \(\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