선형 궤환 시프트 레지스터(LFSR)의 갈루아(Galois) 다항식과 피보나치(Fibonacci) 다항식 간 변환

소개

이 페이지는 한 문장으로 요약할 수 있습니다. LFSR 다항식을 갈루아(Galois) 형태에서 피보나치(Fibonacci) 형태로 변환하려면 계수의 순서를 뒤집으면 됩니다.

예를 들어, 다음은 스크램블러(scrambler)에서 자주 쓰이는 LFSR 도면입니다.

D로 표시된 각 블록은 한 클록 사이클만큼의 지연(delay)을 나타냅니다. 이 LFSR을 갈루아 다항식으로 표현하면 다음과 같습니다.

G(x) = x¹⁶ + x⁵ + x⁴ + x³ + 1

다항식의 지수(3, 4, 5)는 각 XOR 왼쪽에 있는 지연 요소의 개수를 나타냅니다.

같은 LFSR을 피보나치(Fibonacci) 형태로 구현한 모습은 다음 그림과 같습니다.

두 그림은 비슷해 보이지만 화살표 방향은 반대입니다. 그러므로 이 두 LFSR 구현 방식은 완전히 다릅니다.

피보나치 다항식(Fibonacci polynomial), 즉 궤환 다항식(feedback polynomial)은 다음과 같습니다.

F(x) = x¹⁶ + x¹³ + x¹² + x¹¹ + 1

이 다항식의 차수는 n = 16입니다. 따라서 G(x)의 각 xⁱ 항은 F(x)에서 x^n-i로 표현됩니다. 이 페이지의 나머지 부분에서는 이것이 우연이 아님을 설명합니다.

LFSR에 대한 일반적인 설명은 이 주제에 관한 Wikipedia 문서를 참조하세요.

LFSR과 디지털 필터

디지털 필터의 이론(예: FIR, IIR)은 보통 복소수 체 위에서 전개합니다. 하지만 이 이론을 GF(2)에도 적용할 수 있습니다. GF(2)는 0과 1, 두 원소로 이루어진 유한체(finite field), 즉 갈루아 체(Galois field)입니다. 몇 가지 주의할 점이 있습니다.

• 이 체에서 덧셈 연산자는 XOR과 같습니다.
• 곱셈에는 정수만 등장합니다. 실제로 짝수를 곱하는 것은 0을 곱하는 것과 같고, 홀수를 곱하는 것은 1을 곱하는 것과 같습니다. 그 수가 양수인지 음수인지는 중요하지 않습니다.
• 이 곱셈 규칙 때문에 덧셈과 뺄셈은 같은 의미입니다. 둘 다 ⊕(XOR)로 바꿔 쓸 수 있습니다.

디지털 필터의 기본 이론은 시스템이 선형 시불변(Linear time-invariant)(LTI)이기만 하면 성립합니다. LFSR은 이 요건을 충족합니다. XOR이 선형(linear)이고 LFSR의 동작은 시불변(time-invariant)이기 때문입니다.

가장 흥미로운 점은 z 변환(z-transform)을 사용해 LFSR을 해석할 수 있다는 것입니다. 예를 들어 다음 그림을 살펴보겠습니다.

이 구조는 다음 식으로 나타낼 수 있습니다.

y(t) = x(t) ⊕ x(t-1)

여기서 t는 시간을 나타내는 정수입니다.

이것을 FIR 필터로 간주하고 이 식의 z 변환을 쓰면 다음과 같습니다.

Y(z) = X(z) + X(z)z^-1 = X(z) (1 + z^-1)

따라서 '임펄스 응답(impulse response)'은 평소와 같이 H(z) = Y(z)/X(z)로 정의할 수 있습니다. 간단히 쓰면 다음과 같습니다.

H(z) = 1 + z^-1

그런데 이 필터 두 개를 직렬로 연결하면 어떻게 될까요? 이 필터의 '임펄스 응답'은 무엇일까요?

디지털 필터 이론은 간단한 답을 알려 줍니다. 두 필터를 직렬로 연결했을 때의 전달 함수는 다음과 같습니다.

H₂(z) = H(z)H(z) = (1 + z^-1)(1 + z^-1) = 1 + 2z^-1 + z^-2

GF(2)에서는 짝수 곱셈이 0 곱셈과 같다는 점을 기억하세요. 그렇다면 위 식은 다음과 같이 됩니다.

H₂(z) = 1 + 2z^-1 + z^-2 = 1 + 0z^-1 + z^-2 = 1 + z^-2

이것은 다음 그림과 같습니다.

마지막 두 그림에 나오는 필터가 서로 같다는 것은 쉽게 눈에 띄지 않습니다. 그러나 두 필터에 같은 x(t)를 입력하면 두 필터 모두 같은 y(t)를 출력합니다. 따라서 두 번째 지연 요소에 저장되는 값이 서로 다르더라도 두 필터는 같습니다.

이 예는 z 변환(및 다항식을 이용하는 비슷한 기법)으로 논리 필터를 해석할 때 얻는 장점을 보여줍니다.

참고로 z^-1 대신 D 또는 D^-1 기호를 쓰는 경우도 많습니다. 실제로 갈루아 다항식과 피보나치 다항식에서 쓰는 x도 z^-1과 같은 의미입니다. 이 기호들은 모두 지연(delay)을 뜻합니다.

갈루아 LFSR

피보나치 표현을 찾기 위해 먼저 갈루아 LFSR부터 살펴보겠습니다.

위의 갈루아 LFSR 그림에서 지연 요소들이 늘어선 줄과 탭(tap)들을 하나의 FIR 필터로 볼 수 있습니다. 이 필터를 A(z)라고 하겠습니다. 따라서 갈루아 LFSR은 다음 구조와 같습니다.

궤환 때문에 Y(z)에 대한 식은 다음과 같습니다.

Y(z) = Y(z)A(z)

그렇다면 이 FIR 필터의 매개변수와 갈루아 다항식 사이에는 어떤 관계가 있을까요? 갈루아 다항식의 일반형을 써 보겠습니다.

G(x) = xⁿ + g_n-1x^n-1 + g_n-2x^n-2 + … + g₀

이 식에는 g_n 항이 나타나지 않습니다. 이렇게 쓰는 이유는 아래 수식을 단순하게 만들기 위해서입니다. 게다가 g_n은 항상 1입니다.

G(x)와 A(z)의 관계는 다음과 같습니다.

A(z) = g_n-1z^-1 + g_n-2z^-2 + … + g₁z^1-n + g₀z^-n

왜 이렇게 될까요? 위 그림의 갈루아 LFSR을 예로 들어 이 식이 어떻게 성립하는지 살펴보겠습니다.

먼저 g₅에 해당하는 XOR을 보겠습니다. 숫자 5는 이 XOR의 왼쪽에 지연 요소가 다섯 개 있다는 뜻입니다. 그런데 z의 지수는 XOR과 FIR 출력 사이, 즉 이 XOR의 오른쪽에 있는 지연 요소 개수에 따라 결정됩니다. 전체 지연 요소는 16개이므로, g₅는 A(z)에서 g₅z^-11로 나타납니다. 이는 g_n-iz^-i 패턴과 일치합니다.

다른 설명 방법으로, A(z)를 시간 영역(time domain)에서의 FIR로 볼 수 있습니다. 이 FIR의 입력을 x(t), 출력을 y(t)라고 하면 식은 다음과 같습니다.

y(t) = x(t-16) ⊕ x(t-13) ⊕ x(t-12) ⊕ x(t-11)

여기서도 t는 시간을 나타내는 정수입니다. 이 식은 궤환이 없는 갈루아 LFSR을 나타냅니다. 이 FIR의 전달 함수(transfer function)는 다음과 같습니다.

A(z) = Y(z)/X(z) = z^-16 + z^-13 + z^-12 + z^-11

이 결과는 G(x) = x¹⁶ + x⁵ + x⁴ + x³ + 1일 때의 A(z) 일반식과 일치합니다.

피보나치 등가 형태

피보나치 형태의 LFSR은 다음 다항식으로 표현됩니다.

F(x) = f_nxⁿ + f_n-1x^n-1 + … + f₁x + 1

f₀은 항상 1이므로 이 다항식에는 나타나지 않습니다. 이것은 G(x)에서 g_n이 나타나지 않는 것과 비슷합니다.

이 다항식의 구현은 다음과 같습니다.

y(t) = f₁y(t-1) + f₂y(t-2) + … + f_ny(t-n)

이에 대한 z 변환은 다음과 같습니다.

Y(z) = f₁Y(z)z^-1 + f₂Y(z)z^-2 + … + f_nY(z)z^-n

B(z)를 다음과 같이 정의하겠습니다.

B(z) = f₁z^-1 + f₂z^-2 + … + f_nz^-n

그러면 Y(z)는 다음과 같이 쓸 수 있습니다.

Y(z) = Y(z)B(z)

위에서 Y(z) = Y(z)A(z)임을 기억하세요. 따라서 피보나치 형태의 LFSR이 갈루아 다항식으로 주어진 LFSR과 똑같이 동작한다면 A(z) = B(z)가 성립합니다. 이를 다시 쓰면 다음과 같습니다.

f_i = g_n-i (i = 1, 2, …, n)

따라서 처음에 말한 대로, LFSR 다항식을 갈루아 형태에서 피보나치 형태로 변환하려면 계수의 순서를 뒤집기만 하면 됩니다.

LFSR의 역필터

위에서 보았듯이, 다음은 LFSR의 피보나치 구현입니다.

y(t) = f₁y(t-1) + f₂y(t-2) + … + f_ny(t-n)

이 식은 다음과 같이 다시 쓸 수도 있습니다.

y(t) + f₁y(t-1) + f₂y(t-2) + … + f_ny(t-n) = 0

(GF(2)에서는 +와 –가 같다는 점을 기억하세요.)

따라서 피보나치 다항식의 계수는 결과가 항상 0이 되도록 y(t-i) 값들에 XOR을 적용하는 방법을 알려 주기도 합니다. 다시 말하면, 이것은 흥미로운 FIR 필터 하나를 나타냅니다.

마지막 식의 z 변환은 다음과 같습니다.

Y(z) + f₁Y(z)z^-1 + f₂Y(z)z^-2 + … + f_nY(z)z^-n = 0

동등하게 다음과 같이 쓸 수 있습니다.

Y(z)(1 + f₁z^-1 + f₂z^-2 + … + f_nz^-n) = Y(z)H(z) = 0

Y(z)H(z)는 필터 H(z)를 Y(z)에 적용했을 때의 출력입니다. 그리고 그 출력은 0입니다.

따라서 H(z)는 FIR 필터의 전달 함수입니다. 이 FIR 입력에 F(x)로 정의되는 LFSR의 출력을 넣으면 출력은 항상 0입니다. 위에서 정의한 B(z)로부터 이 FIR의 전달 함수는 다음과 같습니다.

H(z) = 1 + f₁z^-1 + f₂z^-2 + … + f_nz^-n

시간 영역에서 표현하면, 입력이 x(t)이고 출력이 y(t)일 때 식은 다음과 같습니다.

y(t) = x(t) ⊕ f₁x(t-1) ⊕ f₂x(t-2) ⊕ … ⊕ f_nx(t-n)

만약 x(t)가 F(x)로 정의되는 LFSR의 출력이라면, 모든 t에 대해 y(t)는 0입니다.