Microsoft MVP성태의 닷넷 이야기
Math: 19. 행렬 연산으로 본 해밍코드 [링크 복사], [링크+제목 복사],
조회: 15829
글쓴 사람
정성태 (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

비밀번호

댓글 작성자
 




1  2  3  4  5  6  7  8  9  10  11  12  13  14  [15]  ...
NoWriterDateCnt.TitleFile(s)
13258정성태2/13/20234317오류 유형: 846. .NET Framework 4.8 Developer Pack 설치 실패 - 0x81f40001
13257정성태2/13/20234385.NET Framework: 2094. C# - Job에 Process 포함하는 방법 [1]파일 다운로드1
13256정성태2/10/20235234개발 환경 구성: 665. WSL 2의 네트워크 통신 방법 - 두 번째 이야기
13255정성태2/10/20234573오류 유형: 845. gihub - windows2022 이미지에서 .NET Framework 4.5.2 미만의 프로젝트에 대한 빌드 오류
13254정성태2/10/20234488Windows: 223. (WMI 쿼리를 위한) PowerShell 문자열 escape 처리
13253정성태2/9/20235234Windows: 222. C# - 다른 윈도우 프로그램이 실행되었음을 인식하는 방법파일 다운로드1
13252정성태2/9/20234062오류 유형: 844. ssh로 명령어 수행 시 멈춤 현상
13251정성태2/8/20234521스크립트: 44. 파이썬의 3가지 스레드 ID
13250정성태2/8/20236344오류 유형: 843. System.InvalidOperationException - Unable to configure HTTPS endpoint
13249정성태2/7/20235191오류 유형: 842. 리눅스 - You must wait longer to change your password
13248정성태2/7/20234236오류 유형: 841. 리눅스 - [사용자 계정] is not in the sudoers file. This incident will be reported.
13247정성태2/7/20235124VS.NET IDE: 180. Visual Studio - 닷넷 소스 코드 디버깅 중 "Decompile source code"가 동작하는 않는 문제
13246정성태2/6/20234273개발 환경 구성: 664. Hyper-V에 설치한 리눅스 VM의 VHD 크기 늘리는 방법 - 두 번째 이야기
13245정성태2/6/20234838.NET Framework: 2093. C# - PEM 파일을 이용한 RSA 개인키/공개키 설정 방법파일 다운로드1
13244정성태2/5/20234176VS.NET IDE: 179. Visual Studio - External Tools에 Shell 내장 명령어 등록
13243정성태2/5/20235017디버깅 기술: 190. windbg - Win32 API 호출 시점에 BP 거는 방법 [1]
13242정성태2/4/20234469디버깅 기술: 189. ASP.NET Web Application (.NET Framework) 프로젝트의 숨겨진 예외 - System.UnauthorizedAccessException
13241정성태2/3/20233938디버깅 기술: 188. ASP.NET Web Application (.NET Framework) 프로젝트의 숨겨진 예외 - System.IO.FileNotFoundException
13240정성태2/1/20234104디버깅 기술: 187. ASP.NET Web Application (.NET Framework) 프로젝트의 숨겨진 예외 - System.Web.HttpException
13239정성태2/1/20233766디버깅 기술: 186. C# - CacheDependency의 숨겨진 예외 - System.Web.HttpException
13238정성태1/31/20235844.NET Framework: 2092. IIS 웹 사이트를 TLS 1.2 또는 TLS 1.3 프로토콜로만 운영하는 방법
13237정성태1/30/20235520.NET Framework: 2091. C# - 웹 사이트가 어떤 버전의 TLS/SSL을 지원하는지 확인하는 방법
13236정성태1/29/20235111개발 환경 구성: 663. openssl을 이용해 인트라넷 IIS 사이트의 SSL 인증서 생성
13235정성태1/29/20234666개발 환경 구성: 662. openssl - 윈도우 환경의 명령행에서 SAN 적용하는 방법
13234정성태1/28/20235747개발 환경 구성: 661. dnSpy를 이용해 소스 코드가 없는 .NET 어셈블리의 코드를 변경하는 방법 [1]
13233정성태1/28/20237125오류 유형: 840. C# - WebClient로 https 호출 시 "The request was aborted: Could not create SSL/TLS secure channel" 예외 발생
1  2  3  4  5  6  7  8  9  10  11  12  13  14  [15]  ...