선형 되먹임 시프트 레지스터

선형 되먹임 시프트 레지스터(Linear feedback shift register, LFSR)는 시프트 레지스터의 일종으로, 레지스터에 입력되는 값이 이전 상태 값들의 선형 함수로 계산되는 구조를 가지고 있다. 이때 사용되는 선형 함수는 주로 배타적 논리합(XOR)이다. LFSR의 초기 비트 값은 시드(seed)라고 부른다.

LFSR의 동작은 결정론적이기 때문에, LFSR로 생성되는 값의 수열은 그 이전 값에 의해 결정된다. 또한, 레지스터가 가질 수 있는 값의 개수는 유한하기 때문에, 이 수열은 특정한 주기에 의해 반복된다. 하지만 선형 함수를 잘 선택한다면 주기가 길고 무작위적으로 보이는 수열을 생성할 수 있다.

LFSR는 의사 난수, 의사 난수 잡음(PRN), 빠른 디지털 카운터, 백지화 수열 등의 분야에서 사용된다.

동작 구조

다음상태에 영향을 주는 비트위치의 목록은 탭 수열이라고 불린다. 아래의 다이어그램에서, 수열은 [16,14,13,11]이다.

입력에 영향을 미치는 출력은 "탭"이라고 불린다. (아래의 다이어그램에서 파란부분임)
최대 LFSR는 결코 변하지 않을 경우에, 모두 영을 포함하는 경우를 제외하고, 최대 길이 수열을 생성한다. (즉 모든비트가 영인 상태를 제외하고 시프트 레지스터내에서 가능한 모든 $2^{n}-1$ 상태를 지나는 주기)

LFSR로 생성된 수열은 그래이 코드나 이진 코드에 유용하도록 이진수로 고려할 수 있다.

LFSR의 탭 수열은 다항 합동 2로 나타낼 수 있다. 이것은 다항식의 계수가 반드시 1이거나 0이어야 한다는 것을 뜻한다. 이것은 되먹임 다항식 혹은 특성 다항식이라고 불린다. 예시로, 만약 탭이 (아래처럼) 16번째, 14번째, 13번째 및 11번째 비트라면, LFSR 다항식은 아래와 같다.

x^{11}+x^{13}+x^{14}+x^{16}+1

다항식에서 '일'은 탭에 일치되지 않는다. 그 항의 거듭제곱은 왼쪽에서 계산된, 탭비트를 나타낸다.

만약 이 다항식이 원시 다항식인 경우에만, LFSR은 최대이다.
LFSR는 탭의 수가 짝수일 경우에만 최대일 것이다.
최대 LFSR에서 탭값은 서로소일 것이다.
주어진 LFSR 길이에서 최대 탭 수열보다 더 긴 수열이 될 수 있다.
최대 탭 수열이 발견되면, 나머지는 자동으로 따른다. n비트 LFSR에서, 탭 수열이, [n,A,B,C,0]이면, 0은 $x^{0}=1$ 항과 일치하고, 그러면 일치한 '거울' 수열은 [n,n-C,n-B,n-A,0]이다. 그래서 탭 수열 [5,3,2,0]은 카운터 일부인 [32,30,29,0]을 갖는다. 양쪽 다 최대 수열을 갖는다.

출력 스트림 특성

일과 영은 '연산'중에 발생된다. 예시로, 출력 스트림 0110100은 순서대로 1,2,1,1,2 길이의 연산으로 구성된다. 최대 LFSR의 기간동안에, $2^{n-1}$ 번 연산이 발생된다. (예시로, 여섯 비트 LFSR는 32번 연산할 것이다) 영 $n-1$ 비트 길이와, 일 $n$ 비트 길이의 한번의 연산에 이르기 위해서, 정확히 이런 연산의 $1/2$ 는 한비트 길이일 것이고, $1/4$ 은 두비트 길이일 것이다. 이 동일한 속성은 통계적으로 진정한 임의의 수열처럼 예상한다.
LFSR 출력 스트림은 결정론적이다. 만약 현재상태를 알고 있다면, 다음상태를 예측할 수 있다. 이것은 방사성 붕괴처럼 진정한 임의의 사건을 발생시키지 못한다.
출력 스트림은 반대로 될 수 있다; 미러 탭 수열이 인가된 LFSR는 반대 순서의 상태로 반복될 것이다.

응용

LFSR는 하드웨어로 구현할 수 있고, 직접 시퀀스 확산 스펙트럼(DSSS) 무선같은, 매우 빠른 의사 난수 수열의 생성이 요구되는 응용에 유용하게 사용된다.

위성항법장치는 시간 보정과 관련된 고정밀 위치를 가리키는 수열을 신속하게 전송하기 위해서 LFSR을 사용한다.

그래이 코드 카운터를 대체하는 드롭인

어떤 응용은 특별한 값과 특정 거리에 따라서 개별적인 위치를 표시할 필요가 있다. 예시로, 대부분의 줄자는 각 인치나 센티미터에 십진수 표시 체계를 사용하여 독특한 숫자로 표시된다. 컴퓨터 목차나 틀 위치가 기계적으로 판독이 가능할 필요가 있을 경우에, LFSR 수열을 사용하여 표시하기도 한다. 왜냐하면 LFSR 컴퓨터는 단순하고 이진 컴퓨터의 다른 종류보다 빠르기 때문이다. LFSR는 자연 이진 카운터 및 그레이 코드 카운터보다 빠르다. 주어진 출력 수열은 벌러캠프-매시 알고리즘을 사용하여 최소화된 크기의 LFSR을 구성할 수 있다.

갈루아 선형 되먹임 시프트 레지스터

에바리스트 갈루아 LFSR 혹은, 갈루아 설정의 LFSR는, 전통적인 LFSR처럼 동일한 수열을 생성할 수 있는 대체 구조이다.

갈루아 설정에서, 시스템에 클럭이 인가될때, 탭되지 않은 비트는 일반적으로 시프트된다. 반대로, 탭은, 새로운 출력과 배타적 논리합되어서, 항상 새로운 입력이 된다. 동일한 수열을 생성하기 위해서, 탭의 순서는 전통적인 LFSR의 순서와 반대로 된다.

갈루아 LFSR는 새로운 입력을 생성하는데 모든 탭과 연결되지 않는다. (배타적 논리합은 LFSR내에서 완료되고 배타적 논리합이 직렬로 연산되는 것은 없다. 그러므로 연산 시간은 전체 회로보다 더 빠른 하나의 배타적 논리합으로 감소된다.) 그러므로 각 탭이 병렬로 연산하는 것이 가능해서, 실행 속도를 증가시킨다.
LFSR의 소프트웨어 구현에서, 갈루아 형식은 더 효과적인 만큼 배타적 논리합 연산이 한번에 워드를 연산할 수 있다: 출력 비트만은 개별적으로 검토되어야 한다.

32비트 최대 주기를 갖는 갈루아 LFSR의 C 예제 코드:

  unsigned int lfsr = 1;
  while(1)
    lfsr = (lfsr >> 1) ^ (-(signed int)(lfsr & 1) & 0x8000000bu); /* taps 32 4 2 1 */

암호학에서 사용

LFSR는 스트림 암호 (특히 군대 암호학)에 의사 난수 생성기로 오랫동안 사용됐다. 왜냐하면 간단한 전기역학이나 전자 회로로 쉽게 구성해서, 긴 주기와, 매우 균일한 분포 출력을 얻기 때문이다. 그러나 LFSR의 출력은 암호를 상당히 단순하게 하는, 완전한 선형이다.

세가지 일반적인 방법은 LFSR 기반의 스트림 암호에 위 문제를 해소하기 위해서 사용된다.

LFSR 상태로부터 몇 비트의 비선형 조합;
두개 이상 LFSR 출력의 비선형 조합; 혹은
LFSR의 불규칙적인 클럭 주기.

주요한 LFSR기반의 스트림 암호는 A5/1, A5/2, E0과 시링크 생성기가 포함된다.

디지털 방송과 통신에서 사용

분선 형태로부터 짧게 반복되는 수열(예시, 0이나 1의 흐름)을 방지하는 것은 수신기가 부호를 추적하는 것을 복잡하게 하거나 다른 전송을 방해할 것이며, 선형 되먹임 레지스터는 종종 전송된 비트스트림을 "임의화"하는데 사용된다. 임의화는 복조후에 수신기에서 제거된다. LFSR이 전송하는 부호스트림과 동일한 속도로 실행될때, 이 기술은 스크램블러처럼 사용된다. LFSR이 부호스트림보다 상당히 빠르게 실행되면, 전송하는 신호의 대역폭이 증가되고, 이것이 DSSS (직접 시퀀스 확산 스펙트럼)이다.

설계는 암호나 암호화로 혼동해서는 안 된다; LFSR로 전송하는 것은 외부로 새는 정보를 보호하지 않는다.

선형 되먹임 레지스터를 사용하는 디지털 방송 시스템