LFSR(선형귀환시프트레지스터) 수열 생성기
탭(피드백 다항식)과 초기 시드를 넣으면 선형귀환시프트레지스터의 출력 비트열과 주기를 계산합니다. 표준 최대길이 탭을 고르면 2ⁿ−1개의 상태를 겹치지 않고 도는 최대길이수열이 되는지도 바로 확인할 수 있습니다.
쉼표로 구분. 이 길이의 최대길이 탭은 {4, 3}입니다.
0과 1로 길이 4짜리 비트열(예: 1000). 전부 0이면 안 됩니다.
n=4, 탭 {3, 4}
최대길이 — 주기 15
2ⁿ−1 = 15과 같습니다. 0이 아닌 모든 상태를 한 번씩 방문합니다.
단계별 자취
| # | 상태(위치1..4) | 피드백 | 출력 |
|---|---|---|---|
| 0 | 1000 | 0 | 0 |
| 1 | 0100 | 0 | 0 |
| 2 | 0010 | 1 | 0 |
| 3 | 1001 | 1 | 1 |
| 4 | 1100 | 0 | 0 |
| 5 | 0110 | 1 | 0 |
| 6 | 1011 | 0 | 1 |
| 7 | 0101 | 1 | 1 |
| 8 | 1010 | 1 | 0 |
| 9 | 1101 | 1 | 1 |
| 10 | 1110 | 1 | 0 |
| 11 | 1111 | 0 | 1 |
| 12 | 0111 | 0 | 1 |
| 13 | 0011 | 0 | 1 |
| 14 | 0001 | 1 | 1 |
「상태」는 왼쪽이 위치1(피드백이 들어가는 자리), 오른쪽이 위치4(다음 걸음에 출력되는 자리)입니다. 매 걸음 전부 한 칸씩 오른쪽으로 밀리고, 탭 위치들을 XOR한 피드백이 왼쪽으로 새로 들어갑니다.
사용 방법
- 1레지스터 길이 n을 정합니다.
- 2탭(피드백 다항식)을 넣거나 「최대길이 탭으로 채우기」 버튼을 누릅니다.
- 30이 아닌 초기 시드를 넣습니다.
- 4출력 비트열과 주기를 확인합니다. 최대길이 탭이면 주기가 2ⁿ−1과 같습니다.
자주 묻는 질문
레지스터의 특정 위치(탭)에 있는 비트들을 XOR해 피드백 비트 하나를 만들고, 나머지 비트를 한 칸씩 밀어낸 뒤 그 피드백 비트를 빈자리에 채웁니다. 밀려나간 맨 끝 비트가 그 걸음의 출력입니다.
레지스터를 위치 1~n으로 부르고, 다항식 x^n + x^k + ... + 1의 지수를 그대로 탭 번호로 씁니다(최고차항 n도 포함됩니다). 예를 들어 4비트에서 탭 {4,3}은 다항식 x^4+x^3+1을 뜻합니다. 이 계산기는 피드백이 위치1로 들어가고 위치n에서 출력이 나가는 방향으로 탭을 셉니다.
탭이 원시다항식(primitive polynomial)에서 온 것이면, 0이 아닌 어떤 시드로 시작해도 2ⁿ−1개의 0 아닌 상태를 정확히 한 바퀴씩, 겹치지 않고 방문합니다. 이런 탭 조합을 「최대길이 탭」이라 부르고, 이 계산기가 각 레지스터 길이마다 하나씩 제시합니다. 탭을 아무렇게나 고르면 이보다 짧은 여러 순환으로 쪼개질 수 있습니다.
피드백도 XOR뿐이라 상태가 전부 0이면 다음 상태도 전부 0이 되어 영원히 이 상태에서 못 벗어납니다. 그래서 시드는 0이 아니어야 하고, 최대길이 탭이라도 이 상태만은 예외로 순환에 포함되지 않습니다.
반대 방향입니다. 베를레캄프–매시는 출력 비트열만 보고 그것을 만들어 낼 수 있는 가장 짧은 LFSR(탭·차수)을 역으로 찾아내고, 이 계산기는 탭과 시드를 직접 정해 순방향으로 비트열을 만듭니다. 이 계산기의 출력을 베를레캄프–매시(법 2)에 넣으면 같은 차수의 점화식이 그대로 복원됩니다.
CRC(순환중복검사) 계산, 스트림 암호의 구성 요소, 통신의 스크램블러, 통계 시뮬레이션용 유사난수 등에 쓰입니다. 다만 순수 LFSR 하나만으로는 선형이라 예측이 쉬워, 암호에는 비선형 결합이나 필터를 반드시 섞습니다(dev/berlekamp-massey FAQ 참고).
전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 탭이 원시다항식일 때 정말로 주기가 2ⁿ−1이 되는지, 3~14비트는 「모든」 0 아닌 시드에 대해 전수로, 15~20비트는 대표 시드로 검증했습니다.
- 탭 표는 Xilinx XAPP052("Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators")와 이를 그대로 인용한 오픈소스 LFSR 구현(github.com/mfukar/lfsr의 lfsr_table.txt)에서 받아 대조했습니다. 탭 번호를 세는 방향과 피드백을 넣는 위치는 표를 그대로 넣었을 때 실제로 최대길이가 나오는 쪽으로 전수 테스트를 거쳐 확정했습니다 — 반대 방향으로 구현했을 때는 0이 아닌 시드가 전부-0 상태로 빨려 들어가 주기가 훨씬 짧아지는 것을 직접 확인하고 방향을 바로잡았습니다.
- 이 도구가 만든 출력을 dev/berlekamp-massey(법 2)에 넣으면 같은 차수가 복원되고, 복원한 점화식으로 다시 만든 수열이 원래 출력과 정확히 일치하는지도 3~10비트에서 대조했습니다. 이 대조 과정에서 베를레캄프–매시 쪽 구현에 있던 버그(특정 수열에서 배열에 빈 칸이 생겨 무한루프에 빠지는 문제)를 발견해 함께 고쳤습니다.
- 전부-0 시드는 흡수 상태(영원히 0)가 되는지, 최대길이 시드는 전부-0 상태를 방문하지 않는지도 검사합니다.
- 레지스터는 20비트까지, 출력은 200개까지 다룹니다. 주기 계산은 정수 비트연산으로 하지만 20비트라도 최대 100만 번 넘게 돌 수 있어 그 이상은 받지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 8일 · 결과는 참고용 추정치입니다.