행렬 연산으로 본 해밍코드
코딩 더 매트릭스 책에,
코딩 더 매트릭스
; 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라고 보면 다음과 같이
가 계산됩니다.
물론, 오류 비트가 하나도 없다면 e = [0 0 0 0 0 0 0 ]일 뿐이고 c ==
가 될 뿐입니다. 반면, 오류 비트가 한 개 있는 경우라면
를 수신한 측에서 어떻게
만을 보고 오류 계산을 할 수 있는지 다음과 같은 수식으로 풀립니다.
H * = 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 *
= H * e"가 됩니다. 수신 측은 행렬 H가 알려져 있고 수신된
값을 가지고 있으므로 그것을 곱셈 연산을 하면, 그 결과는 "H * e"와 동일하게 되는 것입니다. 결국, 행렬 H와 수신된 코드워드만으로 오류가 발생한 e 벡터의 값을 알게 된 것입니다.
정말이지... 대단한 수학자들입니다. ^^
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]