선형 피드백 시프트 레지스터(LFSR)

선형 피드백 시프트 레지스터(LFSR)

LFSR이란?

- Linear Feedback Shift Register의 약자이며, 시프트 레지스터의 일종이다.

- 레지스터에 입력되는 값이 이전 상태 값들의 선형 함수로 계산되는 구조를 가지고 있다.

- 이 때 사용되는 선형 함수는 주로 배타적 논리합(XOR) 이다.

- LFSR의 초기 비트 값은 시드(seed)라고 부른다.

- LFSR의 동작은 결정론적이기 때문에, LFSR로 생성되는 값의 수열은 그 이전 값에 의해 결정된다.

- 레지스터가 가질 수 있는 값의 개수는 유한하기 때문에, 이 수열은 특정한 주기에 의해 반복된다.

- 하지만 선형 함수를 잘 선택한다면 주기가 길고 무작위적으로 보이는 수열을 생성할 수 있다.

LFSR 예시:

각 상태는 4bit의 크기를 가지며, input bit는 이전 상태 비트의 XOR로 계산되고 있다.

자료 출처: 위키 백과