홍라이프 계산기LFSR 계산기 쉽게 이해하기 — 개념과 원리
선형 되먹임 시프트 레지스터(LFSR)는 길고 무작위처럼 보이는 비트열을 만드는 간단한 회로입니다. 시험 패턴 생성, 스크램블러, 카운터, 검사합에 쓰입니다. 이 계산기는 레지스터 길이, 탭, 되먹임 게이트, 시드를 넣으면 피보나치형 LFSR을 실행해 출력 비트를 보여 주고 주기를 구합니다.
계산 방법
클럭마다
- 출력 = 마지막 단 Qn
- 모든 비트가 한 단씩 이동(Q1 → Q2 → … → Qn)
- Q1에는 탭 단들의 XOR(또는 XNOR)이 들어갑니다.
주기 = 시드로 돌아올 때까지의 단계 수
최대 길이 = 2ⁿ − 1이며, 알맞은 탭(공개된 표)으로 얻습니다.
최대 길이 수열에는 1이 2ⁿ⁻¹개, 0이 2ⁿ⁻¹ − 1개 들어 있습니다.
원리
n비트 레지스터에는 2ⁿ가지 상태가 있고 각 상태가 다음 상태를 정하므로 수열은 결국 반복됩니다. XOR 되먹임에서는 전부 0인 상태가 자기 자신으로 가므로 더 긴 순환에 낄 수 없고, 가장 긴 순환은 나머지 2ⁿ − 1개 상태를 모두 돕니다. 어떤 탭이 이를 이루는지는 두 원소 위 대수에서 원시 다항식을 고르는 문제와 같으며, 길이별로 알맞은 탭이 표로 정리되어 있습니다. 되먹임이 선형이라 수열은 무작위처럼 보여도 완전히 예측할 수 있습니다.
예제 풀이
기본값인 n = 4, 표의 최대 길이 탭, XOR, 시드 1000, 30단계 표시로 계산합니다.
- 사용한 탭 = 4, 3입니다.
- 출력 비트는 0001 0011 0101 1110 0010 0110 1011 11입니다.
- 15단계 뒤 시드로 돌아오며 2⁴ − 1 = 15와 같으므로 최대 길이 예입니다.
- 30단계(두 주기) 뒤 레지스터는 다시 1000입니다.
- 한 주기의 1 개수 = 8(= 2³), 0은 7개입니다.
결과 해석
주기가 2ⁿ − 1이면 탭이 최대 길이를 만든다는 뜻입니다. 주기가 더 짧으면 상태의 일부만 돌며, 시험 패턴이나 카운터에는 보통 바람직하지 않습니다. 레지스터가 길면 주기가 천문학적으로 길어져 하드웨어에서 긴 시험 수열을 싸게 만드는 데 쓰입니다.
흔한 실수
- 잠김 상태(XOR은 전부 0, XNOR은 전부 1)에서 시작하는 경우
- 자료마다 다른 탭 번호 규칙을 섞는 경우
- 탭에서 마지막 단 n을 빼는 경우
- 암호 보안이 필요한 곳에 LFSR을 쓰는 경우
자주 묻는 질문
최대 주기가 왜 2ⁿ이 아니라 2ⁿ − 1인가요?
잠김 상태는 자기 자신으로 돌아가 주 순환에 낄 수 없기 때문입니다.
XOR과 XNOR 되먹임은 어떻게 다른가요?
XOR은 전부 0 상태에서, XNOR은 전부 1 상태에서 잠깁니다.
LFSR은 어디에 쓰이나요?
내장 자체 시험, 스크램블러, 의사 난수 카운터, CRC 계산에 쓰입니다.
출처: P. Alfke, "Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators", Xilinx Application Note XAPP 052 (1996)