성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] Roll A Lisp In C - Reading ; https...
[정성태] Java - How to use the Foreign Funct...
[정성태] 제가 큰 실수를 했군요. ^^; Delegate를 통한 Bein...
[정성태] Working with Rust Libraries from C#...
[정성태] Detecting blocking calls using asyn...
[정성태] 아쉽게도, 커뮤니티는 아니고 개인 블로그입니다. ^^
[정성태] 질문이 잘 이해가 안 됩니다. 우선, 해당 소스코드에서 ILis...
[양승조
] var대신 dinamic으로 선언해서 해결은 했습니다. 맞는 해...
[양승조
] 또 막혔습니다. ㅠㅠ var list = props[i].Ge...
[양승조
] 아. 감사합니다. 어제는 안됐던것 같은데....정신을 차려야겠네...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>행렬 연산으로 본 해밍코드</h1> <p> 코딩 더 매트릭스 책에,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 코딩 더 매트릭스 ; <a target='tab' href='http://www.yes24.co.kr/24/goods/17967245'>http://www.yes24.co.kr/24/goods/17967245</a> </pre> <br /> 해밍코드를 설명하는 절이 나옵니다. 그런데, 번역서를 보면 이게 도대체 무슨 말인가 싶을 정도로 난해합니다. 왜냐하면, 글을 쓴 저자는 이미 독자가 해밍코드와 행렬의 관계에 대해 알고 있다는 가정으로 글을 쓴 것이기 때문에 다소 뜬금없는 내용이 나옵니다.<br /> <br /> 예를 들어, "5.7.4 선형 코드" 절에 보면 다음과 같은 말이 나옵니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 선형코드에서 코드워드의 집합 C는 행렬 H의 영공간이다. </pre> <br /> 라고 하는데, 행렬 H가 어떤 것이라는 설명이 없습니다. 그러면서 "5.7.5 해밍코드" 절에서는 다음과 같은 설명이 등장합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 해밍코드에서 코드워드들은 7-벡터들이다. <script type="math/tex"> H = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{bmatrix} </script> </pre> <br /> 그러니까 마치 그다음의 H 행렬이 코드워드의 표현인 것처럼 번역된 것입니다. 그런데, 원문은 다음과 같이 설명하고 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > In the Hamming code, the codewords are 7-vectors<span style='color: blue; font-weight: bold'>, and</span> <script type="math/tex"> H = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{bmatrix} </script> </pre> <br /> 원문에는 ", and"가 있어서 의미가 확 달라집니다. 즉, 원래는 다음과 같이 번역되어야 하는 것입니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 해밍 코드에서는, 코드워드는 7-벡터들이고 행렬 H는 다음과 같이 정의된다. <script type="math/tex"> H = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{bmatrix} </script> </pre> <br /> <hr style='width: 50%' /><br /> <br /> 기왕 말이 나왔으니, 좀 더 정리를 해볼까요? ^^<br /> <br /> 책에서 예를 든 해밍 코드는 데이터 4비트 기준으로 패리티 3비트를 합치는 7-벡터의 코드워드를 기준으로 설명합니다. 그리고 해밍 코드 내용을 읽기 전, 해밍 코드를 행렬 연산으로 다룰 때 나오는 G와 H라는 2개의 대표적인 행렬을 알아야 합니다.<br /> <br /> 우선 행렬 G는 다음과 같습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > <script type="math/tex"> G = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ \end{bmatrix} </script> </pre> <br /> 이 행렬이 재미있는 것은 4비트의 값을 G 행렬에 곱하면 인코딩된 7비트의 코드워드가 나온다는 점입니다.<br /> <br /> 이 과정을 MATLAB(또는 Octave)로 표현해 보면 다음과 같습니다. 우선, 행렬 G를 표현하고,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > G = [1 0 0 0; 0 1 0 0; 0 0 1 0; 0 0 0 1; 0 1 1 1; 1 0 1 1; 1 1 0 1]; </pre> <br /> 4비트가 가질 수 있는 데이터의 행렬을 마련한 다음, <br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > data = [0 0 0 0; 0 0 0 1; 0 0 1 0; 0 0 1 1; 0 1 0 0; 0 1 0 1; 0 1 1 0; 0 1 1 1; 1 0 0 0; 1 0 0 1; 1 0 1 0; 1 0 1 1; 1 1 0 0; 1 1 0 1; 1 1 1 0; 1 1 1 1 ]; </pre> <br /> 행렬 곱셈을 위해 행렬 data를 전치시킨 후 곱하고 2의 나머지를 취한 값으로 정리합니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > codewords = G * data'; codewords = mod(codewords, 2); </pre> <br /> 마지막으로 나온 codewords를 읽기 쉽게 전치시켜서 출력해 보면,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > >> codewords' ans = 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 </pre> <br /> 이렇게 4비트의 데이터 값에 따른 각각의 인코딩된 7벡터의 코드워드 집합을 얻을 수 있습니다. <br /> <br /> 그래서, 행렬 G를 해밍 코드의 부호화에 사용하는 "생성 행렬"이라고 합니다. 그다음 행렬 H를 알아보기 전 잠시 "영공간(Null space)"에 대해 설명하겠습니다.<br /> <br /> "<a target='tab' href='http://www.yes24.co.kr/24/goods/17967245'>코딩 더 매트릭스 </a>" 책 182페이지에 정의된 것을 보면,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 행렬 A의 영공간은 집합 {<span style='color: blue; font-weight: bold'>v</span>: A * <span style='color: blue; font-weight: bold'>v</span> = <span style='color: blue; font-weight: bold'>0</span>}이다. 이것은 Null A로 나타낸다. </pre> <br /> 라고 정의되어 있는데 쉽게 말하면 행렬 A에 어떤 벡터를 곱셈했을 때 그 결과가 0 벡터로 나오게 하는 그 벡터들의 집합을 영공간이라고 하는 것입니다.<br /> <br /> 예를 들면 행렬 A가 다음과 같다면,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > <script type="math/tex"> A = \begin{bmatrix} 1 & 4 & 5 \\ 2 & 5 & 7 \\ 3 & 6 & 9 \\ \end{bmatrix} </script> </pre> <br /> A * [1, 1, -1]을 곱하면 그 결과가 0 벡터가 나옵니다. MATLAB으로는 다음과 같이 간단하게 연산할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > >> A = [1 2 3; 4 5 6; 5 7 9]' A = 1 4 5 2 5 7 3 6 9 >> A * [1 1 -1 ]' ans = 0 0 0 </pre> <br /> 또한 [2 2 -2]를 곱해도 0 벡터가 나오고 , [3 3 -3],... 을 곱해도 0 벡터가 나옵니다. 이랬을 때 이 값들의 집합을 "영공간(Null sapce)"라고 하는 것입니다.<br /> <br /> 해밍 코드의 행렬 연산에서 재미있는 것은, 4비트 데이터 + 3비트 패리티 비트가 표현된 7-벡터의 코드 워드들이 전부 행렬 H에 대해 '영공간'이라는 것입니다. 확인을 위해 MATLAB(또는 Octave)으로 다음과 같이 간단하게 계산할 수 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > H = [0 0 0 1 1 1 1; 0 1 1 0 0 1 1; 1 0 1 0 1 0 1]; result = (H * codewords)'; result = mod(result, 2); </pre> <br /> 결과값인 행렬 result는 이렇게 나옵니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > >> result result = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 </pre> <br /> 즉, 데이터 4비트가 인코딩된 7-벡터의 코드워드들은 무조건 행렬 H와 곱셈을 했을 때 결과가 0 벡터가 나와야 합니다. 이 때문에 행렬 H를 "확인 행렬"이라고도 합니다.<br /> <br /> "<a target='tab' href='http://www.yes24.co.kr/24/goods/17967245'>코딩 더 매트릭스 </a>" 책에서는 이를 "선형코드에서 코드워드의 집합 C는 행렬 H의 영공간이다"라는 한마디로 표현한 것입니다.<br /> <br /> 위의 행렬 연산을 염두에 두고 책을 다시 보면 이제 대충 이해가 갑니다.<br /> <br /> 4비트 데이터가 인코딩된 코드워드를 c, 오류 비트가 발생한 것을 e라고 보면 다음과 같이 <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=\bar{c}">가 계산됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > <script type="math/tex"> \bar{c} = {c + e} </script> </pre> <br /> 물론, 오류 비트가 하나도 없다면 e = [0 0 0 0 0 0 0 ]일 뿐이고 c == <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=\bar{c}">가 될 뿐입니다. 반면, 오류 비트가 한 개 있는 경우라면 <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=\bar{c}">를 수신한 측에서 어떻게 <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=\bar{c}">만을 보고 오류 계산을 할 수 있는지 다음과 같은 수식으로 풀립니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > H * <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=\bar{c}"> = H * (c + e) = <span style='color: blue; font-weight: bold'>H * c</span> + H * e = <span style='color: blue; font-weight: bold'>0</span> + H * e = H * e </pre> <br /> 위의 수식에서 "H * c + H * e = 0 + H * e"가 되는데요. 왜냐하면 "선형코드에서 코드워드의 집합 C는 행렬 H의 영공간"이기 때문에 결국 "H * c"의 결과는 0 벡터가 되는 것입니다.<br /> <br /> 따라서, 최종 정리는 "H * <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=\bar{c}"> = H * e"가 됩니다. 수신 측은 행렬 H가 알려져 있고 수신된 <img alt='TeX' src="http://chart.apis.google.com/chart?cht=tx&chl=\bar{c}"> 값을 가지고 있으므로 그것을 곱셈 연산을 하면, 그 결과는 "H * e"와 동일하게 되는 것입니다. 결국, 행렬 H와 수신된 코드워드만으로 오류가 발생한 e 벡터의 값을 알게 된 것입니다.<br /> <br /> 정말이지... 대단한 수학자들입니다. ^^<br /> </p><br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
2064
(왼쪽의 숫자를 입력해야 합니다.)