Microsoft MVP성태의 닷넷 이야기
Math: 19. 행렬 연산으로 본 해밍코드 [링크 복사], [링크+제목 복사],
조회: 25411
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
 
(연관된 글이 1개 있습니다.)

행렬 연산으로 본 해밍코드

코딩 더 매트릭스 책에,

코딩 더 매트릭스 
; http://www.yes24.co.kr/24/goods/17967245

해밍코드를 설명하는 절이 나옵니다. 그런데, 번역서를 보면 이게 도대체 무슨 말인가 싶을 정도로 난해합니다. 왜냐하면, 글을 쓴 저자는 이미 독자가 해밍코드와 행렬의 관계에 대해 알고 있다는 가정으로 글을 쓴 것이기 때문에 다소 뜬금없는 내용이 나옵니다.

예를 들어, "5.7.4 선형 코드" 절에 보면 다음과 같은 말이 나옵니다.

선형코드에서 코드워드의 집합 C는 행렬 H의 영공간이다.

라고 하는데, 행렬 H가 어떤 것이라는 설명이 없습니다. 그러면서 "5.7.5 해밍코드" 절에서는 다음과 같은 설명이 등장합니다.

해밍코드에서 코드워드들은 7-벡터들이다.



그러니까 마치 그다음의 H 행렬이 코드워드의 표현인 것처럼 번역된 것입니다. 그런데, 원문은 다음과 같이 설명하고 있습니다.

In the Hamming code, the codewords are 7-vectors, and 



원문에는 ", and"가 있어서 의미가 확 달라집니다. 즉, 원래는 다음과 같이 번역되어야 하는 것입니다.

해밍 코드에서는, 코드워드는 7-벡터들이고 행렬 H는 다음과 같이 정의된다.






기왕 말이 나왔으니, 좀 더 정리를 해볼까요? ^^

책에서 예를 든 해밍 코드는 데이터 4비트 기준으로 패리티 3비트를 합치는 7-벡터의 코드워드를 기준으로 설명합니다. 그리고 해밍 코드 내용을 읽기 전, 해밍 코드를 행렬 연산으로 다룰 때 나오는 G와 H라는 2개의 대표적인 행렬을 알아야 합니다.

우선 행렬 G는 다음과 같습니다.



이 행렬이 재미있는 것은 4비트의 값을 G 행렬에 곱하면 인코딩된 7비트의 코드워드가 나온다는 점입니다.

이 과정을 MATLAB(또는 Octave)로 표현해 보면 다음과 같습니다. 우선, 행렬 G를 표현하고,

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];

4비트가 가질 수 있는 데이터의 행렬을 마련한 다음,

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 ];

행렬 곱셈을 위해 행렬 data를 전치시킨 후 곱하고 2의 나머지를 취한 값으로 정리합니다.

codewords = G * data';
codewords = mod(codewords, 2);

마지막으로 나온 codewords를 읽기 쉽게 전치시켜서 출력해 보면,

>> 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

이렇게 4비트의 데이터 값에 따른 각각의 인코딩된 7벡터의 코드워드 집합을 얻을 수 있습니다.

그래서, 행렬 G를 해밍 코드의 부호화에 사용하는 "생성 행렬"이라고 합니다. 그다음 행렬 H를 알아보기 전 잠시 "영공간(Null space)"에 대해 설명하겠습니다.

"코딩 더 매트릭스 " 책 182페이지에 정의된 것을 보면,

행렬 A의 영공간은 집합 {v: A * v = 0}이다. 이것은 Null A로 나타낸다.

라고 정의되어 있는데 쉽게 말하면 행렬 A에 어떤 벡터를 곱셈했을 때 그 결과가 0 벡터로 나오게 하는 그 벡터들의 집합을 영공간이라고 하는 것입니다.

예를 들면 행렬 A가 다음과 같다면,



A * [1, 1, -1]을 곱하면 그 결과가 0 벡터가 나옵니다. MATLAB으로는 다음과 같이 간단하게 연산할 수 있습니다.

>> 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

또한 [2 2 -2]를 곱해도 0 벡터가 나오고 , [3 3 -3],... 을 곱해도 0 벡터가 나옵니다. 이랬을 때 이 값들의 집합을 "영공간(Null sapce)"라고 하는 것입니다.

해밍 코드의 행렬 연산에서 재미있는 것은, 4비트 데이터 + 3비트 패리티 비트가 표현된 7-벡터의 코드 워드들이 전부 행렬 H에 대해 '영공간'이라는 것입니다. 확인을 위해 MATLAB(또는 Octave)으로 다음과 같이 간단하게 계산할 수 있습니다.

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);

결과값인 행렬 result는 이렇게 나옵니다.

>> 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

즉, 데이터 4비트가 인코딩된 7-벡터의 코드워드들은 무조건 행렬 H와 곱셈을 했을 때 결과가 0 벡터가 나와야 합니다. 이 때문에 행렬 H를 "확인 행렬"이라고도 합니다.

"코딩 더 매트릭스 " 책에서는 이를 "선형코드에서 코드워드의 집합 C는 행렬 H의 영공간이다"라는 한마디로 표현한 것입니다.

위의 행렬 연산을 염두에 두고 책을 다시 보면 이제 대충 이해가 갑니다.

4비트 데이터가 인코딩된 코드워드를 c, 오류 비트가 발생한 것을 e라고 보면 다음과 같이 TeX가 계산됩니다.



물론, 오류 비트가 하나도 없다면 e = [0 0 0 0 0 0 0 ]일 뿐이고 c == TeX가 될 뿐입니다. 반면, 오류 비트가 한 개 있는 경우라면 TeX를 수신한 측에서 어떻게 TeX만을 보고 오류 계산을 할 수 있는지 다음과 같은 수식으로 풀립니다.

H * TeX = H * (c + e)
       = H * c + H * e 
       = 0 + H * e 
       = H * e

위의 수식에서 "H * c + H * e = 0 + H * e"가 되는데요. 왜냐하면 "선형코드에서 코드워드의 집합 C는 행렬 H의 영공간"이기 때문에 결국 "H * c"의 결과는 0 벡터가 되는 것입니다.

따라서, 최종 정리는 "H * TeX = H * e"가 됩니다. 수신 측은 행렬 H가 알려져 있고 수신된 TeX 값을 가지고 있으므로 그것을 곱셈 연산을 하면, 그 결과는 "H * e"와 동일하게 되는 것입니다. 결국, 행렬 H와 수신된 코드워드만으로 오류가 발생한 e 벡터의 값을 알게 된 것입니다.

정말이지... 대단한 수학자들입니다. ^^




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]






[최초 등록일: ]
[최종 수정일: 7/10/2021]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 




... 181  182  183  184  185  186  187  188  189  190  191  [192]  193  194  195  ...
NoWriterDateCnt.TitleFile(s)
177정성태11/2/200517826COM 개체 관련: 17. CoGetClassObjectFromURL파일 다운로드1
176정성태3/29/200623121.NET Framework: 52. covariance? [1]파일 다운로드1
175정성태10/31/200518569.NET Framework: 51. MSXML 6.0에서 디지털 서명 기능을 제거!
180정성태11/15/200518900    답변글 VS.NET IDE: 51.1. MSXML 6.0 정식 릴리스
174정성태10/31/200519778.NET Framework: 50. app.config 예시 [1]
173정성태10/30/200518449스크립트: 5. 스크립트 호출 관계
172정성태10/25/200526876.NET Framework: 49. ASP.NET 오류 유형 : 액세스가 거부되었습니다. [2]
171정성태11/14/200528613VC++: 19. 다국어 지원: setlocale( LC_TIME, "" ) 관련 [1]
170정성태11/14/200523143VS.NET IDE: 34. Visual SourceSafe 2005: Remote Internet Access over HTTP : 80 이외의 포트를 지정
206정성태2/1/200619678    답변글 VC++: 34.1. [추가]: Internet Access Plug-in 사용 시 유의 사항
168정성태11/14/200520750VS.NET IDE: 33. IIS 6.0 AppPool 설정 - Enable rapid-fail protection
169정성태10/14/200522440    답변글 VS.NET IDE: 33.1. Enable rapid-fail protection 상황 재현 방법
166정성태11/14/200519618.NET Framework: 48. IE를 죽이는 스크립트 소스
165정성태11/14/200520288.NET Framework: 47. MOM (Microsoft Operations Manager) 2005 서버 설치 가이드
164정성태11/14/200517458.NET Framework: 46. 도메인에 속한 컴퓨터의 Local Computer Policy 변경 방법
162정성태10/3/200520089.NET Framework: 45. VS.NET 2005 IDE에서 Web App를 .NET 2.0 (x64) 머신에 배포
161정성태11/14/200522876.NET Framework: 44. IIS 관리자에서 ASP.NET 탭이 없는 경우.
159정성태9/28/200518894VS.NET IDE: 32. Virtual Server 2005 64bit SP1 Beta 테스트 [2]
163정성태10/3/200516889    답변글 VS.NET IDE: 32.1. 왜...?
158정성태11/14/200519218VS.NET IDE: 31. SQL 2005 - A connection was successfully established with the server
157정성태9/21/200519193기타: 10. SQL2000 설치 시, Invalid Product Key 오류
156정성태9/16/200521143.NET Framework: 43. Wisptis.exe 프로세스
155정성태5/31/200517454.NET Framework: 42. .NET Installer Class에서 Install 메서드 - 설정 사항들 알아내는 코드
154정성태5/13/200516418VS.NET IDE: 30. Windows 2003 for x64에 추가된 레지스트리 Run 노드
152정성태5/5/200519802VC++: 18. VC++ 7.0에서부터 ? : 연산자 처리가 바뀌었습니다.
153정성태5/12/200520090    답변글 VC++: 18.1. VC++ 8.0에서부터 바뀐 CRT 소개
... 181  182  183  184  185  186  187  188  189  190  191  [192]  193  194  195  ...