선형 되먹임 시프트 레지스터
위키백과 ― 우리 모두의 백과사전.
선형 되먹임 시프트 레지스터(Linear feedback shift register, 줄여서 LFSR)는 입력비트가 이전 상태에 대해 선형적인 시프트 레지스터이다.
하나의 비트에 대한 선형 함수는 배타적 논리합과 반전 배타적 논리합 뿐이므로, LFSR은 입력비트가 전체 시프트 레지스터값의 어떤 비트의 배타적 논리합(xor)에 의하여 재입력되는 시프트 레지스터이다.
LFSR의 초기값은 시드라고 불리고, 레지스터의 동작은 결정론적이기 때문에, 레지스터로 발생되는 값의 수열은 현재 (혹은 이전) 상태에 의하여 완전히 결정된다. 마찬가지로, 레지스터가 가질 수 있는 상태의 수는 유한하기에, 이는 일정한 주기를 갖고 반복되게 된다. 그러나, 되먹임 함수를 잘 선택하기만 하면 LFSR은 거의 무작위적인 것으로 보일 정도로 긴 주기를 갖는 비트 수열을 생성할 수 있다.
LFSR의 응용은 생성된 의사 난수, 의사 잡음 수열(pseudo-noise sequence), 빠른 디지털 카운터와, 백지화 수열 등이 있다. LFSR의 하드웨어 구현과 소프트웨어 구현은 모두 흔한 일이다.
목차 |
[편집] 어떻게 동작하나?
다음상태에 영향을 주는 비트위치의 목록은 탭 수열이라고 불린다. 아래의 다이어그램에서, 수열은 [16,14,13,11]이다.
- 입력에 영향을 미치는 출력은 "탭"이라고 불린다. (아래의 다이어그램에서 파란부분임)
- 최대 LFSR는 결코 변하지 않을 경우에, 모두 영을 포함하는 경우를 제외하고, 최대 길이 수열을 생성한다. (즉 모든비트가 영인 상태를 제외하고 시프트 레지스터내에서 가능한 모든 2n − 1 상태를 지나는 주기)
LFSR로 생성된 수열은 그래이 코드나 이진 코드에 유용하도록 이진수로 고려할 수 있다.
LFSR의 탭 수열은 다항 합동 2로 나타낼 수 있다. 이것은 다항식의 계수가 반드시 1이거나 0이어야 한다는 것을 뜻한다. 이것은 되먹임 다항식 혹은 특성 다항식이라고 불린다. 예시로, 만약 탭이 (아래처럼) 16번째, 14번째, 13번째 및 11번째 비트라면, LFSR 다항식은 아래와 같다.
다항식에서 '일'은 탭에 일치되지 않는다. 그 항의 거듭제곱은 왼쪽에서 계산된, 탭비트를 나타낸다.
- 만약 이 다항식이 원시 다항식인 경우에만, LFSR은 최대이다.
- LFSR는 탭의 수가 짝수일 경우에만 최대일 것이다.
- 최대 LFSR에서 탭값은 서로소일 것이다.
- 주어진 LFSR 길이에서 최대 탭 수열보다 더 긴 수열이 될 수 있다.
- 최대 탭 수열이 발견되면, 나머지는 자동으로 따른다. n비트 LFSR에서, 탭 수열이, [n,A,B,C,0]이면, 0은 x0 = 1 항과 일치하고, 그러면 일치한 '거울' 수열은 [n,n-C,n-B,n-A,0]이다. 그래서 탭 수열 [32,3,2,0]은 카운터 일부인 [32,30,29,0]을 갖는다. 양쪽 다 최대 수열을 갖는다.
[편집] 출력 스트림 특성
- 일과 영은 '연산'중에 발생된다. 예시로, 출력 스트림 0110100은 순서대로 1,2,1,1,2 길이의 연산으로 구성된다. 최대 LFSR의 기간동안에, 2n − 1번 연산이 발생된다. (예시로, 여섯 비트 LFSR는 32번 연산할 것이다) 영 n − 1 비트 길이와, 일 n 비트 길이의 한번의 연산에 이르기 위해서, 정확히 이런 연산의 1 / 2는 한비트 길이일 것이고, 1 / 4은 두비트 길이일 것이다. 이 동일한 속성은 통계적으로 진정한 임의의 수열처럼 예상한다.
- LFSR 출력 스트림은 결정론적이다. 만약 현재상태를 알고 있다면, 다음상태를 예측할 수 있다. 이것은 방사성 붕괴처럼 진정한 임의의 사건을 발생시키지 못한다.
- 출력 스트림은 반대로 될 수 있다; 미러 탭 수열이 인가된 LFSR는 반대 순서의 상태로 반복될 것이다.
[편집] 응용
LFSR는 하드웨어로 구현할 수 있고, 직접 시퀀스 확산 스펙트럼(DSSS) 무선같은, 매우 빠른 의사 난수 수열의 생성이 요구되는 응용에 유용하게 사용된다.
위성항법장치는 시간 보정과 관련된 고정밀 위치를 가르키는 수열을 신속하게 전송하기 위해서 LFSR을 사용한다.
[편집] 그래이 코드 카운터를 대체하는 드롭인
어떤 응용은 특별한 값과 특정 거리에 따라서 개별적인 위치를 표시할 필요가 있다. 예시로, 대부분의 줄자는 각 인치나 센티메타에 십진수 표시 체계를 사용하여 독특한 숫자로 표시된다. 컴퓨터 목차나 틀 위치가 기계적으로 판독이 가능할 필요가 있을 경우에, LFSR 수열을 사용하여 표시하기도 한다. 왜냐하면 LFSR 컴퓨터는 단순하고 이진 컴퓨터의 다른 종류보다 빠르기 때문이다. LFSR는 자연 이진 카운터 및 그레이 코드 카운터보다 빠르다. 주어진 출력 수열은 Berlekamp-Massey 알고리즘을 사용하여 최소화된 크기의 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과 시링크 생성기가 포함된다.
[편집] 디지털 방송과 통신에서 사용
[편집] 같이 보기
- 핀톱니바퀴
- 메르센 트위스터
- 의사 난수 수열
- 최대 길이 수열
[편집] 바깥 고리
- ((영어)) 인터네셔널 텔레커뮤니케이션 연합 권고안 O.151 (1992년 8월)
- ((영어)) 3 ~ 168 길이와 최대길이 선형 되먹임 시프트 레지스터 표
- ((영어)) 의사 난수 생성기 루틴
- ((영어)) http://www.ee.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html
- ((영어)) http://www.quadibloc.com/crypto/co040801.htm
- ((영어)) 공학자를 위한 선형 되먹임 시프트 레지스터의 간단한 설명
- ((영어)) 되먹임 기간
- ((영어)) 일반적인 선형 되먹임 시프트 레지스터 이론
- ((영어)) 최대탭 수열의 표
- ((영어)) UC 버클리 강의의 선형 되먹임 시프트 레지스터 이론
- ((영어)) 시프트 레지스터 코드 생성기