LFSR 계산기 - 선형 피드백 시프트 레지스터

선형 피드백 시프트 레지스터(LFSR)는 입력 비트가 이전 상태 비트 일부의 선형 함수(XOR)로 계산되는 시프트 레지스터입니다. 매 클록 사이클마다 레지스터는 한 칸씩 이동하고, 새 입력 비트는 피드백 탭이라 불리는 특정 위치의 비트를 XOR하여 계산되며, 출력은 시프트되어 나가는 비트입니다. 결과 이진 시퀀스는 무작위처럼 보이지만 완전히 결정적이며, 반복 주기는 레지스터 길이와 탭 선택에 따라 달라집니다. LFSR은 디지털 통신, 암호학, BIST(내장 자체 테스트) 회로, 확산 스펙트럼 시스템, 의사난수 생성에 널리 사용됩니다. n단 LFSR은 반복되기 전 최대 2ⁿ − 1비트의 시퀀스를 생성할 수 있으며(모든 0 상태는 제외), 신중하게 선택한 원시 다항식 탭으로 이 최대 길이 시퀀스를 구현할 수 있으므로 LFSR은 하드웨어에서 의사난수를 효율적으로 구현하는 방식입니다. 대표적인 LFSR 아키텍처는 두 가지입니다. Fibonacci(외부 피드백) LFSR에서는 피드백 비트가 고정된 탭 위치들로부터 계산되어 맨 왼쪽 단계로 들어가고, 나머지 단계는 오른쪽으로 이동합니다. 출력은 맨 오른쪽 단계에서 가져옵니다. Galois(내부 피드백) LFSR에서는 피드백 비트가 입력으로만 되돌아가는 것이 아니라 여러 중간 단계에 직접 XOR됩니다. XOR 연산이 직렬이 아니라 병렬로 수행되기 때문에 Galois LFSR이 하드웨어에서 더 빠릅니다. 최대 길이 LFSR, 즉 반복되기 전 2ⁿ − 1개의 모든 비영(0이 아닌) 상태를 순환하는 LFSR에는 원시 다항식을 피드백 다항식으로 사용해야 합니다. 탭 위치는 이 다항식의 0이 아닌 계수에 해당합니다. 4비트 LFSR에서 탭이 4와 3에 있을 때 원시 다항식은 x⁴ + x³ + 1이며, LFSR은 15개의 비영 상태를 모두 순환합니다. 이 계산기는 레지스터 길이, 시드, 탭 위치, LFSR 유형의 모든 조합을 탐색할 수 있게 해줍니다. 결과의 주기를 확인하면 선택한 탭이 최대 길이 시퀀스를 만드는지 검증할 수 있습니다. 주기가 2ⁿ − 1이면 그 탭은 원시 다항식을 이룹니다. 제공된 예제로 잘 알려진 최대 길이 구성을 확인해 보세요. LFSR의 활용 범위는 매우 넓습니다. Wi‑Fi와 Bluetooth에서는 주파수 호핑과 직접 시퀀스 확산을 위한 확산 코드에 LFSR이 쓰입니다. 저장과 통신 분야에서는 CRC(순환 중복 검사) 회로가 LFSR로 구현됩니다. 암호 스트림 암호에서는 LFSR이 핵심 원시 요소를 이룹니다(다만 현대 암호는 선형 암호분석을 막기 위해 여러 LFSR과 비선형 구성요소를 결합합니다). 칩 테스트에서는 LFSR 기반 시그니처 분석이 테스트 응답 데이터를 작은 시그니처로 압축합니다.