리드-솔로몬 부호와 벌레캠프-매시 알고리즘

통신 오류

일상 생활에서 대화를 하다보면 주변이 시끄러워서 잘 못 들을 때가 있습니다. 소리 뿐만 아니라 글을 써서 보여줄 때에도 어둡거나 글씨가 악필이면 잘못 읽는 경우가 허다합니다. 우리는 항상 통신 오류에 노출된 셈이죠. 이건 비단 인간만의 문제가 아니라서 전자 기기를 사용하더라도 마찬가지 문제를 겪습니다. 무선 통신은 당연하고(엘 베이터에서 통화하는 상황을 생각해봅시다), 아무리 단단하게 케이블을 고정해놓은 유선 통신이라도 통신 오류가 절대 안 생길 수는 없습니다.

결국 오해의 소지 없이 통신을 하려면 오류가 아예 안 생긴다고 기대하는 것보다는 오류가 생겼다는 사실을 적절히 알아채서 대응하는 것이 중요합니다. 이 글에서는 통신 오류를 어떻게 검출하고 대응하는지 살펴보겠습니다.

오류 검출

대부분의 오류 검출은 데이터에 오류를 검출할 수 있는 정보를 추가하는 방식으로 이루어집니다. 가장 간단한 방법은 패리티 비트(parity bit)라는 것으로, 데이터에 포함된 1의 개수가 홀수인지 짝수인지에 따라 1비트를 추가하는 방식입니다. 조금 더 복잡한 방법으론 데이터를 몇 바이트씩 묶은 뒤 이들의 합을 추가하는 체크섬(checksum), 데이터를 다항식으로 보고서 이를 주어진 다항식으로 나눈 나머지를 추가하는 CRC(Cyclic Redundancy Check) 등이 있습니다.

오류가 검출되었다면 대응은 크게 두 가지입니다. 첫 번째는 보낸 쪽에 재전송을 요구하는 것입니다. 물론 이 요구조차도 오류가 발생할 수 있다는 점에 주의해야겠죠. 두 번째는 복잡한 알고리즘을 써서 오류를 정정하는 것입니다. 계산량 때문에 전송 속도는 떨어지겠지만 심각할 수준으로 오류가 발생하지만 않는다면 재전송 요구 없이 일방적으로 데이터 전송이 가능합니다.

리드-솔로몬 부호

리드-솔로몬 부호(Reed-Solomon code)는 다항식의 성질을 이용하여 오류를 검출하고 정정하는 알고리즘입니다. 특히 오류가 연속으로 발생하는 군집 오류(burst error)에 대한 정정 능력이 뛰어납니다. CD, DVD, 블루레이, QR 코드, DVB, RAID 등에서 매우 널리 사용되는 알고리즘이기도 합니다.

크기 $q$인 유한체 $GF(q)$의 원소로 이루어진 길이 $k$인 데이터를 전송해야 한다고 가정합시다. 리드-솔로몬 부호는 여기에 길이 $2t$인 오류 검출 및 정정 정보를 추가해 최대 $2t$개의 오류를 검출하고 $t$개의 오류를 정정할 수 있습니다. 전송할 전체 길이는 $n=k+2t$입니다. 단, $n$이 $q$보다 작아야 합니다.

먼저 데이터를 $d_0$, $d_1$, ⋯, $d_{k-1}$라고 하고 이들을 계수로 갖는 유한체 위의 다항식 $p(x)$를 정의합니다.

그리고 생성자 다항식(generator polynomial)을 다음과 같이 정의합니다.

여기서 $g(x)$가 중근을 가지지 않도록 $\alpha$는 유한체의 원시 원소(primitive element)로 둡니다. $\alpha$와 $g(x)$는 복호화를 위해 송신측과 수신측이 공유해야 하는 값입니다. 특별히 $i=1$인 경우를 narrow sense라고 하며, 이하 이를 가정합니다.

최종적으로 길이 $n-k$의 리드-솔로몬 부호 $c_0$, $c_1$, ⋯, $c_{n-k-1}$은 $x^{n-k}p(x)$를 $g(x)$로 나눈 나머지 $c(x)$의 계수입니다.

보통은 송신할 데이터와 부호를 하나의 다항식으로 합쳐서 나타냅니다.

$c(x)$는 $n-k$차 미만의 다항식이므로 $s(x)$의 계수는 $p(x)$의 계수와 동일합니다. 한편 $s(x)$가 $g(x)$의 배수임은 쉽게 보일 수 있습니다.

복호화

수신측에서 다항식 $r(x)$를 받았다고 합시다. 통신 오류가 있다면 $r(x)$는 송신측에서 보낸 다항식 $s(x)$과 다를 것입니다. 복호화의 목표는 오류가 발생한 항과 그 항의 계수를 정정하는 것입니다.

오증

$r(x)$에 생성자 다항식 $g(x)$의 근을 대입하여 얻은 값을 오증(syndrome)이라고 합니다.

그런데 $s(x)$가 $g(x)$의 배수이므로 $r(x) = s(x)$이면 오증은 모두 0이 됩니다. 반대로 0이 아닌 오증이 있는 경우에는 통신 오류가 발생했다고 의심할 수 있겠죠.

오류 위치 다항식

오류가 난 항이 $\nu$개이고 각각의 차수가 $i_k$($1\le k \le\nu$)라고 하면 $r(x)$와 $s(x)$의 차는 다음과 같이 표현 가능합니다.

오증의 정의를 다시 쓰면

오류 위치(error locator) $X_k$와 오류값(error value) $Y_k$를 다음과 같이 정의합니다.

따라서 오증은

$\alpha$는 사전에 공유한 값이므로 $X_k$를 구하면 $i_k$도 구할 수 있습니다. 오류 위치 다항식(error locator polynomial)을 다음과 같이 정의합시다.

정의에 의해 오류 위치 다항식은 $X_k^{-1}$을 해로 가지므로

양변에 $Y_kX_k^{j+\nu+1}$를 곱합시다.

이를 $k=1$부터 $\nu$까지 더하면

또는

즉, 오증의 수열 $S_0$, ⋯, $S_{n-k-1}$이 오류 위치 다항식을 계수로 하는 선형 점화식을 가진다는 놀라운 결과를 얻습니다! 오증은 앞에서 다 구했으니까 적절한 $\nu$를 골라서 적절한 점화식이 성립하는지 확인하면 됩니다. 참고로 오증은 $n-k=2t$개이므로 $\Lambda_k$에 대한 방정식을 $2t-\nu$개 만들 수 있고 $\Lambda_k$는 총 $\nu$개니까 $\Lambda_k$를 유일하게 구할 수 있을 조건은 $\nu \le 2t-\nu$ 또는 $\nu\le t$입니다. 처음에 언급했던 $t$개 이하의 오류만 수정 가능하다는 점이 여기서 증명되죠.

벌레캠프-매시 알고리즘

벌레캠프-매시 알고리즘(Berlekamp-Massey algorithm)은 유한체 상에서 유한 수열이 주어질 때 그 수열의 최소 선형 점화식을 구하는 알고리즘입니다. 원래 벌레캠프가 발표한 알고리즘은 점화식과 관련 없이 $\nu$의 최솟값과 그 때의 $\Lambda_k$를 찾는 것이었는데, 매시가 위와 같은 과정을 거쳐 벌레캠프의 알고리즘이 오증 수열의 선형 점화식을 찾는 것과 동치임을 증명했습니다. 벌레캠프-매시 알고리즘은 리드-솔로몬 부호의 복호화 과정에서 핵심일 뿐만 아니라 수열과 연관된 다른 곳에서도 많이 쓰입니다.

식 \eqref{eq:recur}에서 점화식의 오차 $d$를 다음과 같이 정의합시다.

$d$가 0이면 현재 $\nu$와 $j$에 대해 점화식이 잘 성립하는 겁니다. $j$를 1 증가시켜 그 다음 오증에 대해서도 점화식이 성립하는지 확인합니다. 반대로 0이 아니면 점화식, 즉 오류 위치 다항식 $\Lambda(x)$를 수정해야 합니다. 이때 수정된 오차 위치 다항식은 그 이전 오증들에 대해서 점화식을 잘 성립하게 하면서 동시에 현재 오증 $S_{j+\nu}$에 대해서도 점화식이 성립하게 해야 합니다. 벌레캠프-매시 알고리즘은 다음과 같이 오류 위치 다항식을 수정합니다.

여기서 $\Lambda_\text{old}(x)$는 이전에 사용했던 적당한 오류 위치 다항식이고, $f$는 그 오류 위치 다항식이 점화식을 만족하는 데 실패한 첫 $j$값이며, 그 때의 오차 $d$가 $d_\text{old}$입니다.

새로 구한 오류 위치 다항식은 $S_{j+\nu}$에 대한 점화식을 만족할까요? 정의에 따라 계산해보면

이므로 잘 만족합니다. 오류 위치 다항식에서 점화식으로 가는 부분이 헷갈릴 수 있는데 계수는 그대로 두고 $x^i$를 $S_{j+\nu-i}$로 바꾼다고 생각하면 편합니다.

한편 이전 오증들에 대해서는 위 식에서 $j$와 $f$ 대신 $j-1$과 $f-1$를 대입한 경우 등과 동치이므로 밑줄로 표시한 부분이 둘 다 0이 되어(이전 오증들에 대해서는 $\Lambda(x)$든 $\Lambda_\text{old}(x)$든 점화식을 잘 만족하니까) 오차가 0입니다. 결과적으로 벌레캠프-매시 알고리즘은 오류 위치 다항식을 수정하는 데 성공했습니다. 이제 $\Lambda(x)$를 업데이트하고 다음 오증으로 넘어가 계속 위 과정을 반복하면 됩니다. 언젠가는 마지막 오증까지 만족하는 점화식을 구하게 되겠죠.

한 가지 문제는 이전에 사용했던 오류 위치 다항식 중 어느 것을 선택해야 좋겠냐는 것인데, 여기서는 최소 선형 점화식을 찾고 싶은 거니까 $\Lambda_\text{new}(x)$의 차수가 최소가 되도록 선택해야 합니다. 식 \eqref{eq:update_lambda}에서 $\Lambda(x)$의 차수는 $\nu$이고, $\Lambda_\text{old}(x)$의 차수를 $\nu_\text{old}$라 할 때 우변 두 번째 항의 차수는 $j - f + \nu_\text{old}$이므로 $\Lambda_\text{new}(x)$의 차수는

입니다. 이걸 최소로 하려면 $f - \nu_\text{old}$가 가장 큰 이전 오류 위치 다항식을 선택하면 되겠네요. 따라서 오차가 발생한 매 단계에서 새 오류 위치 다항식을 계산한 뒤, $j - \nu$가 $f - \nu_\text{old}$보다 더 크면 $\Lambda_\text{old}(x)$를 $\Lambda(x)$로 업데이트해주면 됩니다.

마지막으로 초기값을 살펴봐야 합니다. 처음 $j_0$개의 오증이 0이고 $S_{j_0}\neq0$이면 선형 점화식의 길이가 $j_0$ 이하는 절대 될 수 없으므로 $\nu$의 초기값은 $j_0+1$이어야 합니다. $\Lambda(x)$의 초기값은 어차피 점화식에 오차가 있으면 수정될 것이므로 사실 상관이 없는데, 굳이 계산을 복잡하게 만들 이유는 없으니

로 두는 게 제일 편합니다. 그리고 이전 오류 위치 다항식은

으로 두고, 위치 $f=j_0$에서 오차 $d_\text{old}=S_{j_0}$가 처음 발생했다고 두는 것이 합리적입니다.

위 내용을 코드로 구현하면 다음과 같습니다.

def BerlekampMassey(S):
    Lambda = [1]
    Lambda_old = [1]
    f = -1
    d_old = 0

    for j in range(len(S)):
        # Calculate d
        d = S[j]
        for z in range(1, len(Lambda)):
            d = gf_add(d, gf_mul(Lambda[z], S[j-z]))

        if d == 0:
            continue

        if f == -1:
            # S_j is the first non-zero syndrome
            # Initialize variables
            Lambda = [1] + [0] * (j+1)
            Lambda_old = [1]
            f = j
            d_old = d
        else:
            # Calculate Lambda_new(x)
            tmp = [0] * (j-f) + Lambda_old
            dd = gf_mul(d, gf_inv(d_old))
            Lambda_new = Lambda + [0] * (len(tmp) - len(Lambda))
            for z in range(len(tmp)):
                Lambda_new[z] = gf_sub(Lambda_new[z], gf_mul(dd, tmp[z]))

            # Update Lambda_old(x)
            if (j - len(Lambda) > f - len(Lambda_old)):
                Lambda_old = Lambda
                f = j
                d_old = d

            Lambda = Lambda_new

    return Lambda

여기서 gf_add, gf_sub, gf_mul, gf_inv는 유한체 위에서 각각 덧셈, 뺄셈, 곱셈, 곱셈에 대한 역원을 계산하는 함수입니다. 예를 들어 소수 $p$에 대한 나머지로 정의되는 유한체 $GF(p)$ 상에서는 아래과 같이 구현할 수 있습니다.

def gf_add(x, y):
    return (x + y) % p

def gf_sub(x, y):
    return (p + x - y) % p

def gf_mul(x, y):
    return (x * y) % p

def gf_inv(x):
    # By Fermat's little theorem
    return pow(x, p-2, p)

한번 예제 3과 4를 넣고 직접 실행해보시기 바랍니다.

포니 알고리즘

벌레캠프-매시 알고리즘으로 오류 위치 다항식을 구했으면 오류가 발생한 항을 구하는 건 쉽습니다. 인수 분해로 해 $X_k^{-1}$를 직접 찾고 역원을 계산한 뒤 로그를 취해 $i_k$를 구해도 되고, $n$이 작다면 $\Lambda(x)$에 $\alpha^{-1}$부터 $\alpha^{-n}$까지 대입해서 언제 0이 되는지 확인하는 게 더 효과적입니다.

이제 남은 건 오류값 $Y_k$를 찾는 것 뿐입니다. 가장 쉽게 생각할 수 있는 방법은 식 \eqref{eq:SXY}에 $S_j$와 $X_k$를 대입하여 다음과 같은 선형계를 만들어 푸는 것입니다.

하지만 역행렬을 구하는 것은 복잡한데다가 전자 회로로 구현하기 힘들기 때문에 이보다 더 좋은 포니 알고리즘(Forney algorithm)을 보통 사용합니다. 먼저 오증 다항식(syndrome polynomial)을 오증들을 계수로 가지는 다항식으로 정의합니다.

식 \eqref{eq:SXY}를 대입하면

$S(x)$와 $\Lambda(x)$를 곱해봅시다.

위 식의 우변 첫 번째 항은 $\nu-1$차 이하의 항으로만, 두 번째 항은 $n-k$차 이상의 항으로만 이루어져 있으므로 $x^{n-k}$에 대한 나머지를 취하면 두 번째 항을 없앨 수 있습니다. 이를 오류 평가 다항식(error evaluator polynomial)이라고 합니다.

여기에 $X_l^{-1}$($1\le l\le\nu$)을 대입하면 $k=l$인 경우만 남습니다.

한편 $\Lambda(x)$를 미분한 결과는

유한체 상의 다항식에 대한 미분이 조금 생소할 수 있는데 계수만 유한체의 정의에 맞게 계산해준다면 일반적인 미분과 동일합니다.formal derivative라고 합니다. 정의에 극한을 사용하지 않고 다항식에 대해서만 정의합니다. 이제 똑같이 $X_l^{-1}$을 대입하면

마지막으로 \eqref{eq:omega}과 \eqref{eq:lambda-prime}을 연립하여 $Y_l$을 얻습니다.

남은 건 $X_k$와 $Y_k$로 $e(x)$를 구한 후 $r(x)$에서 빼는 것 뿐입니다.