코딩 더 매트릭스 - 5장 행렬 (2)

필립 클라인의 저서 코딩 더 매트릭스 5장 행렬

1. 행렬-행렬 곱셈을 행렬-벡터 곱셈, 벡터-행렬 곱셈, 도트곱으로서 이해합니다.
2. 인접행렬을 사용해 그래프의 노드에서 노드까지 가는 경로의 수를 살펴봅니다.
3. 행렬-행렬 곱셈을 선형함수의 합성으로서 표현합니다.
4. 역함수와 역행렬의 관계를 이해합니다.
5. 행렬-벡터, 행렬-행렬 곱셈을 해밍코드에 적용해 봅니다.

행렬-행렬 곱셈

행렬 $A$와 $B$가 있을때 이들의 곱셈은 $AB$로 씁니다. 행렬-행렬 곱셈은 행렬-벡터 곱셈으로서, 벡터-행렬 곱셈으로서 표현할 수 있습니다.

행렬-벡터 곱셈에서 $B$의 한 열을 벡터 $s$라 하면 $A * s$는 $s$의 엔트리들을 계수로 한 $A$의 열벡터들의 선형결합입니다. 이것은 $AB$의 한 열벡터입니다. 따라서 다음과 같이 쓸 수 있습니다.

벡터-행렬 곱셈에서 $A$의 한 행을 벡터 $r$라 하면 $r * B$는 $r$의 엔트리들을 계수로 한 $B$의 행벡터들의 선형결합입니다. 이것은 $AB$의 한 행벡터입니다. 따라서 다음과 같이 쓸 수 있습니다.

엔트리 $b_i$는 $B$의 행벡터들입니다. $AB$를 벡터-행렬 곱셈으로서 정리하면 다음과 같습니다.

참고로 예시의 행렬 $A$는 단위행렬에 한번의 기본행연산을 한 행렬입니다. $AB$의 각각의 행벡터를 보면 첫번째와 세번째 행벡터는 각각 $B$의 첫번째와 세번째 행벡터와 일치하고 두번째 행벡터는 첫번째 행벡터에 2 스칼라곱 한 뒤, 두번째 행벡터와 더한 결과와 같습니다.

행렬-행렬 곱셈을 도트곱으로서 표현하면 $AB$의 엔트리 $AB_{rc}$는 $A$의 행 $r$과 $B$의 열 $c$의 도트곱의 결과입니다.

그래프와 인접행렬

행렬-행렬 곱셈을 이용해 그래프 노드들의 경로의 수를 찾을 수 있습니다. 아래와 같은 그래프가 있습니다.

그래프는 꼭지점(vertex) 또는 노드(node)와 그들을 이어주는 엣지(edge)로 이루어져 있습니다. 한 노드에서 다른 노드까지 엣지의 가짓수에 관한 표를 만들어 보겠습니다.

표를 그대로 행렬로 만들 수 있는데 이를 인접행렬이라 합니다. 인접행렬은 다음과 같습니다.

인접행렬의 행은 한 노드에서 다른 노드로 가는 가짓수를 의미합니다. 열은 다른 노드에서 한 노드로 오는 가짓수를 의미합니다. 따라서 두 인접행렬의 곱은 한 노드에서 다른 노드로 두 개의 엣지를 거쳐 가는 가짓수입니다.(경로를 나타낼 때 엣지들에 이름을 붙여 1a2b3과 같이 표현하는데 이를 워크라 합니다.) 예를 들어 두 번의 이동으로 노드 2에서 노드 2로 가는 가짓수는 $[1,0,1,0,1,0] \cdot [1,0,1,0,1,0] = 3$입니다. 인접행렬의 곱을 numpy를 이용해 코드로 작성하면 다음과 같습니다.

G = np.matrix([
    [ 0, 1, 0, 0, 1, 0 ],
    [ 1, 0, 1, 0, 1, 0],
    [ 0, 1, 0, 1, 0, 0 ],
    [ 0, 0, 1, 0, 1, 1 ],
    [ 1, 1, 0, 1, 0, 0 ],
    [ 0, 0, 0, 1, 0, 0 ]
])
G * G
>>>
matrix([
	[2, 1, 1, 1, 1, 0],
	[1, 3, 0, 2, 1, 0],
	[1, 0, 2, 0, 2, 1],
	[1, 2, 0, 3, 0, 0],
	[1, 1, 2, 0, 3, 1],
	[0, 0, 1, 0, 1, 1]
])

세 번에 거쳐 다른 노드로 가는 가짓수를 알고 싶다면 G * G * G를 출력하면 됩니다.

G * G * G
>>>
matrix([
	[2, 4, 2, 2, 4, 1],
	[4, 2, 5, 1, 6, 2],
	[2, 5, 0, 5, 1, 0],
	[2, 1, 5, 0, 6, 3],
	[4, 6, 1, 6, 2, 0],
	[1, 2, 0, 3, 0, 0]
])

행렬-행렬 곱셈과 함수 합성

행렬 $A$, $B$가 있을 때 다음과 같이 함수를 정의할 수 있습니다.

행렬의 곱 $AB$에 대해서는 합성함수 $f \circ g$ 로 쓸 수 있습니다. 행렬의 곱셈을 함성함수로 나타낼 수 있다는 것은 간단히 증명 가능합니다. $x = [ x_1, x_2, ..., x_n ]$이고 B의 열벡터들을 $b_1, b_2, ..., b_n$이라 할때 $g(x)$를 행렬-벡터 곱셈의 선형결합으로 다음과 같이 쓸 수 있습니다.

위 식을 $f(x) = A * x$에 대입하면

행렬-행렬 곱셈을 코드로 옮겨보겠습니다.

class Mat:
	def __mul__(self, other):
		.
		.
		.
		elif isinstance(other, Mat):
			return self.mat_mul(other)

	def mat_mul(self, other):
        if self.D[1] != other.D[0]:
            raise Exception('Invalid multiplication')
        res = zero_mat((self.D[0], other.D[1]))
        for r1, c in self.f:
            for r2 in other.D[1]:
                res[r1, r2] += self.f[r1, c] * other[c, r2]
        return res

행렬-행렬 곱의 전치

$R \times C$행렬 $A$와 $C \times T$행렬 $B$가 있을때 $(AB)^T = B^TA^T$입니다.

역함수와 역행렬

선형함수의 역함수는 선형함수입니다. 예를 들어 선형함수 $f$와 그의 역함수 $g$가 있습니다. 역함수의 정의에 의해 $(f \circ g)(x) = x$입니다. $g$가 선형함수이기 위해서 다음 두 가지 성질을 만족해야합니다.

$y = f(x)$, $g(y) = x$라 할때 $f$가 선형함수임을 이용해 다음과 같이 쓸 수 있습니다.

함수 $f(x) = Ax$와 $g(x) = Bx$가 서로 역함수일때 행렬 $A$와 $B$를 서로 역행렬이라 합니다. 역함수는 많아야 하나이므로 역행렬도 많아야 하나 존재합니다. 가역행렬 $A$의 역행렬은 $A^{-1}$로 나타냅니다.

대각행렬

$\begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 4 \end{bmatrix}$ 의 역행렬은 존재하지 않습니다. 행렬을 함수로 나타낼때 $f([x,y,z]) = [2x,0,4z]$이므로 $f$는 단사함수가 아닙니다. 따라서 $f$는 역함수가 아니고 대응하는 행렬의 역행렬도 존재하지 않습니다.

$AB$의 역행렬 $(AB)^{-1} = B^{-1}A^{-1}$는 입니다. 행렬 $A$, $B$를 각각 함수로 대응해 $f$, $g$라 하면 $(f \circ g)^{-1} = g^{-1} \circ f^{-1}$이므로 $(AB)^{-1} = B^{-1}A^{-1}$입니다.

한편 $AB$가 단위행렬일때 항상 $A$와 $B$가 역행렬은 아닙니다. 다음은 그 예입니다.

해밍코드

서로 데이터를 주고 받는 밥과 앨리스가 있습니다. 밥이 보낸 데이터가 전송 도중 에러가 발생해 원문과 달라진다면 앨리스는 어떻게 다시 원문을 복구할 수 있을까요? 이런 물음에 벨 연구소에 있었던 수학자 리처드 해밍은 에러정정코드를 이용해 문제를 해결합니다. 그리고 해밍의 이름을 따 이 코드를 해밍 코드라 부르게 됩니다.

밥과 앨리스의 데이터 통신은 다음과 같습니다.

데이터의 비트는 GF(2)상에서 정의합니다. 밥이 보낸 4비트의 데이터는 생성행렬 $G$가 곱해져 7비트의 코드워드가 됩니다. 코드워드는 전송 도중 에러가 발생해 변조될 수 있습니다. 앨리스는 코드워드에 복호행렬 $R$을 곱해 원문 또는 변조된 데이터 4비트를 얻게 됩니다. 생성행렬 $G$와 복호행렬 $R$은 다음과 같습니다.

만약 밥이 4비트 데이터 $[1,1,0,1]$를 보낸다면 다음과 같이 7비트 코드워드를 얻게 됩니다.

코드워드 $[0,1,1,0,0,1,1]$을 코드워드 $c$라 하겠습니다. $c$에 복호행렬 $R$을 곱하면 다시 4비트 원문이 나옵니다.

행렬 $G$와 $H$를 활용한 생성과 복호를 직접 구현해보겠습니다. 우선 행라벨과 열라벨이 0부터 1씩 증가하는 정수일때 이를 간단히 행렬로 만드는 함수 listlist2mat을 정의하겠습니다.

def listlist2mat(L):
    row_labels = set(range(len(L)))
    col_labels = set(range(len(L[0])))

    return Mat(
        (row_labels, col_labels),
        { (r, c): L[r][c] for r in row_labels for c in col_labels if L[r][c] }
    )

from GF2 import one

G = listlist2mat([
    [ one,0,one,one ],
    [ one,one,0,one ],
    [ 0,0,0,one ],
    [ one,one,one,0 ],
    [ 0,0,one,0 ],
    [ 0,one,0,0 ],
    [ one,0,0,0 ]
])
R = listlist2mat([
    [ 0,0,0,0,0,0,one ],
    [ 0,0,0,0,0,one,0 ],
    [ 0,0,0,0,one,0,0 ],
    [ 0,0,one,0,0,0,0 ]
])

listlist2mat을 이용해 행렬 $G$와 $R$을 간단히 만들 수 있습니다. 4비트 원문을 $p$라 할때 7비트 코드워드 $G * p = c$와 $R * c$값을 구해보겠습니다.

from vecutil import list2vec

p = list2vec([ one,one,0,one ])
c = G * p
print(c)
print(R * c)

>>>
0  1  2  3  4  5  6
-------------------
0  1  1  0  0  1  1

>>>
0  1  2  3
----------
1  1  0  1

그도 그럴것이 $R * G$는 단위행렬이므로 7비트 코드워드의 값에 변조가 없다면 행렬 $R$을 곱했을때 다시 4비트 원문을 얻게 됩니다.

이제 앨리스는 7비트 코드워드가 밥이 보낸 코드워드 값과 같은지 아닌지를 판별해야 합니다. 만약 전송 도중 에러가 발생했다면 앨리스는 $c$와 다른 코드워드를 전달받을 것입니다. 해밍은 이러한 상황을 해결하기 위해 검사행렬 $H$를 도입했습니다.

$H$는 7비트 코드워드에 곱해져 결과값이 항상 영벡터이기를 기대합니다. $H$와 앞 예시의 코드워드 $c$를 곱하면 다음과 같습니다.

$H * G = 0$이기 때문에 에러가 없는 코드워드 $c$에 대해 항상 $H * G * p = 0$이 성립합니다.

코드워드에 에러가 발생한 상황을 생각해보겠습니다. 에러는 많아야 한 비트에서 발생한다고 가정합니다. 예를 들면 에러 $e$는 $[1,0,0,0,0,0,0]$, $[0,0,1,0,0,0,0]$와 와 같은 형태입니다. 변조된 코드워드는 $\tilde{c} = c + e$로 쓸 수 있습니다.(GF(2)상의 값들이므로 한 비트에 1을 더하는 것은 XOR 연산을 의미합니다.) $\tilde{c}$를 검사행렬 $H$에 곱한 값 $H * \tilde{c}$을 에러 신드롬이라 하고 다음과 같이 쓸 수 있습니다.

$H * c = 0$는 이므로 $H * \tilde{c} = H * e$로 고쳐 쓸 수 있습니다. 따라서 에러가 발생하지 않았다면 $H * \tilde{c} = 0$입니다.

$H * \tilde{c} \neq 0$ 일때 즉 에러가 발생했을때 어떻게 에러 $e$를 찾을 수 있을까요? 7비트 벡터 $e$를 $[e_1,e_2, ..., e_7]$이라 하고 $H$의 열벡터들을 $h_1, h_2, ..., h_7$이라 하면 $H * e$는 $e$의 엔트리들과 $H$의 열벡터들의 선형결합입니다.

에러 $e$가 많아야 한개의 비트에서 발생한다고 가정했으므로 에러신드롬 $H * e$은 $e$의 어느 비트에서 값이 1인지 알려줄 수 있습니다. 만약 $e_1$이 1이라면 에러신드롬은 $[0,0,1]$이고 $e_3$가 1이라면 에러신드롬은 $[0,1,1]$입니다. 다음 프로시저 find_error는 입력된 에러신드롬에 대해 에러 $e$를 반환합니다.

def find_error(es):
    i = 0
    err = zero_vec(set(range(0,7)))
    for d in es.D:
        if es[d]:
            i += 1 << (2-d)
    if i != 0:
    	err[i - 1] = one
    return err

이제 에러를 찾을 수 있으므로 식 $R * (\tilde{c} + e)$식을 이용하면 원문 4비트를 구할 수 있습니다. $\tilde{c}$에 $e$를 빼지 않고 더하는 이유는 $\tilde{c} + e$가 에러비트에 대한 XOR 연산과 같기 때문입니다. 4비트 원문 $p = [1,1,0,1]$과 에러 $e = [0,0,0,1,0,0]$를 이용해

1. 원문을 7비트 코드워드로 변환하고 $G * p$
2. 에러가 발생했다고 가정한 뒤 $c + e$
3. 에러신드롬을 구해 $H * (c + e)$
4. 에러 $e$를 찾고
5. 원문을 구하는 과정을 $R * (\tilde{c} + e)$ 코드로 요약하면 다음과 같습니다.

p = list2vec([ one,one,0,one ])
c = G * p
e = list2vec([ 0,0,0,one,0,0,0 ])
c_e = c + e
es = H * (c_e)
print('p\n', p)
print('c\n', c)
print('c + e\n', c_e)
print('error syndrome\n', es)
print('err\n', find_error(es))
print('c\n', (c_e + find_error(es)))
print('decode\n', R * (c_e + find_error(es)))

>>>
p
0  1  2  3
----------
1  1  0  1

c
0  1  2  3  4  5  6
-------------------
0  1  1  0  0  1  1

c + e
0  1  2  3  4  5  6
-------------------
0  1  1  1  0  1  1

error syndrome
0  1  2
-------
1  0  0

err
0  1  2  3  4  5  6
-------------------
0  0  0  1  0  0  0

c
0  1  2  3  4  5  6
-------------------
0  1  1  0  0  1  1

decode
0  1  2  3
----------
1  1  0  1

해밍코드 - 문자열 전송

문자열 데이터의 전송을 해밍코드에 적용해 보겠습니다. 먼저 문자열을 1바이트(8비트)의 아스키코드 문자로 쪼갠 뒤 다시 1바이트 문자를 니블(4비트)로 쪼개 행렬에 저장하는 프로시저가 필요합니다.

def str2bits(s):
    flags = [1 << i for i in reversed(range(8))]
    return [one if ord(c) & flag else 0 for c in s for flag in flags]

def bits2str(L):
    flags = [1 << i for i in reversed(range(8))]
    return ''.join([
        chr(sum([ flag if j else 0 for j, flag in zip(L[i:i+8], flags) ]))
        for i in range(0, len(L), 8)
    ])

str2bits는 문자열의 문자들에 대해 비트연산으로 8비트 시퀀스를 얻습니다. 예를 들어 문자열 str2bits("abc")는 아스키코드에서 97(a), 98(b), 99(c)를 이용해 $[0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1]$이 됩니다. bits2str은 역으로 GF(2)상의 값들의 시퀀스로부터 문자열을 얻습니다.

다음은 문자열로부터 얻은 비트 시퀀스를 행렬로 바꾸는 프로시저와 행렬을 비트 시퀀스로 바꾸는 프로시저입니다.

def bits2mat(L):
    cols = len(L) // 4
    f = {(r,c): one for c in range(cols) for r in range(4) if L[4 * c + r]}
    return Mat((set(range(4)), set(range(cols))), f)

def mat2bits(M):
    L = []
    for c in sorted(M.D[1]):
        for r in sorted(M.D[0]):
            L.append(M[r,c])
    return L

이제 문자열을 4비트 열벡터들의 행렬로, 행렬을 문자열로 바꿀 수 있습니다. 위의 프로시저들을 이용해 문자열 "abc"를 행렬로 바꾸고 다시 문자열로 되돌려 보겠습니다.

bits = str2bits('abc')
print(bits)
>>>
[0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1]

M = bits2mat(bits)
print(M)
>>>
      0  1  2  3  4  5
    ------------------
0  |  0  0  0  0  0  0
1  |  1  0  1  0  1  0
2  |  1  0  1  1  1  1
3  |  0  1  0  0  0  1

print(bits2str(mat2bits(M)))
>>>
abc

문자열 "abc"의 전송에 해밍코드를 적용해 보겠습니다. 아래는 에러를 발생시키는 간단한 프로시저 noise입니다.

def noise(M, freq):
    f = {(i,j):one for i in M.D[0] for j in M.D[1] if random.random() < freq}
    return Mat(M.D, f)

noise프로시저는 행렬 M과 빈도율 freq을 인수로 받아, 행렬 M과 행라벨, 열라벨이 같고 빈도율 freq를 고려한 에러 행렬을 반환합니다. 이전에 7비트 코드워드 하나를 3비트 에러신드롬으로 바꾸고 7비트 에러 $e$를 찾는 프로시저 find_error를 작성했었습니다. 이번에는 7비트 코드워드 열벡터들로 이루어진 행렬에 대해 에러행렬 $e$를 찾아내는 프로시저가 필요합니다.

def find_error_matrix(S):
    res = zero_mat((set(range(0,7)), S.D[1]))
    for c in S.D[1]:
        i = 0
        for r in S.D[0]:
            if S[r,c]:
                i += 1 << (2 - r)
        if i != 0:
            res[i-1, c] = one
    return res

프로시저 find_error_matrix는 3비트 에러신드롬 열벡터들로 이루어진 행렬 S를 받아 각각의 에러신드롬 열벡터로부터 에러비트를 찾은 뒤 7비트 에러 열벡터들로 이루어진 행렬을 반환합니다.

원문 "abc"와 프로시저 noise를 활용해

1. 문자열을 $4 \times n$ 행렬 $M$로 바꾸고
2. 7비트 코드워드로 변환 $G * M$,
3. 에러가 발생했다고 가정한 뒤 $c + noise(M, frag)$
4. 에러신드롬 행렬을 구해 $H * (c + e)$
5. 에러행렬 $e$를 찾고
6. 원래의 $4 \times n$ 행렬을 구해 $R * (\tilde{c} + e)$
7. 원문 문자열로 바꾸는 과정을 코드로 쓰면 다음과 같습니다.

bits = str2bits('abc')
M = bits2mat(bits)
c = G * M
c_e = c + noise(c, 0.02)
es = H * c_e
error = find_error_matrix(es)
decoded = R * (c_e + error)
print(bits2str(mat2bits(decoded)))

>>>
abc

위 코드의 출력값인 bits2str(mat2bits(decoded))는 noise프로시저의 에러생성률에 따라 값이 다를 수 있습니다. 만약 한 7비트 에러벡터에 2개 이상의 비트가 1이라면 정확한 에러를 찾을 수 없을 것입니다. 예를 들어 에러신드롬 $[0,1,1]$의 에러는 $[0,0,1,0,0,0,0]$ 뿐만아니라 $[1,1,0,0,0,0,0]$도 될 수 있습니다.