LFSR 의 개념과 원리 (Linear Feedback Shift Register)

 

오늘은 디지털 회로 중 하나인 LFSR, Linear Feedback Shift Register 에 대해 다뤄보겠습니다. LFSR 은 flip-flop 들을 이용해 random number 를 생성하는 데 쓰이는 디지털 논리 회로입니다. 즉 난수 생성을 위한 회로이죠. 간단한 회로 예부터 아래에서 살펴보도록 하죠.

 

(출처 : 위키피디아)

 

위는 xor 과 4개의 flip-flop 을 이용해 만든 간단한 4bit 의 LFSR 입니다. 이전 값이 어떤 값이었는지에 따라 다음 값이 결정되는 구조를 볼 수 있습니다. 예를 들어, 초깃값이 1000 값이면 논리 조합에 의해 그 다음 값은 0100 이 나오게 되는 일종의 deterministic 한 구조이죠. 결국 LFSR 은 진정한 의미의 random number gernerator 는 아니며, 초기 seed 값에 의해 start 값이 바뀌는 구조입니다. 특정 주기를 갖고 일정 수열을 주기적으로 뱉어내는 구조이죠. 하지만 논리 구조를 잘 짜게 되면 주기가 매우 길고 무작위적으로 보이는 것처럼 수열을 생성할 수 있습니다.

 

일반적으로 LFSR 은 위와 같이 여러 개의 flip-flop 과 XOR 을 이용해 설계됩니다. 몇 bit 의 난수가 필요하냐에 따라 flip-flop 개수를 설정하면 되며, xor 을 잘 이용해 난수 수열을 설정할 수 있습니다.

 

또한 어떤 flip-flop 들을 reset 시키냐에 따라 초깃값이 달라질 수 있겠죠. 이 초깃값이 달라지면 수열의 초깃값이 바뀌게 되어 다른 종류의 난수가 생성되는 것처럼 보일 수 있습니다. 따라서 이 seed 값이 중요함을 알 수 있습니다.

 

참고로 어떤 xor 구조를 사용하느냐에 따라서 위와 같이 피보나치 구조의 LFSR 또한 설계 가능합니다.

 

원하는 LFSR 를 설계하기 위해서는 위와 같이 flip-flop 과 xor 의 구조를 가졌을 때 직접 truth table 을 그려 설계하는 것이 좋습니다. 이상입니다.