LFSR 원리와 C 코드 만들어보기 (1)

LFSR은 Linear Feedback Shift Register의 줄임말이다. 이는 현재 상태에서의 선형 연산(?!)을 통해 다음 상태를 생성하는 레지스터라고 한다.

LFSR은 주로 난수를 만드는데 사용된다고 한다. LFSR은 seed 라는 수가 있다. 주로 몇 bit로 표현한다. 즉 16bit seed를 사용, 32bit seed를 사용한다 라고 많이들 표현한다. 해당 seed를 특정한 규칙이 있는 XOR 계산을 통해 주기를 갖는 수를 생성한다고 한다. 그 주기는 seed의 bit수에 따라 달라진다. 16bit이면 2^16-1 개 만큼의 주기를 갖는다고 한다. 여기서 -1을 한 이유는 0을 제외했기 때문이다.

자 예를 가지고 설명해보자.

우리에게 위와 같이 8bit 짜리 seed가 정해졌다고 하자. 해당 수는 2진법으로 표현했고 10진법으로 나타내면 116이다. 위에서 설명할때 특정한 규칙의 XOR 계산이 있다고 했다. 이는 다항식으로 표현할 수 있다고 한다.

왼쪽부터 순서대로 1,2,3,4,5,6,7,8 까지의 index를 주어진다고 가정했을때 7번과 6번을 XOR 한 값을 2번과 XOR을 해서 0번째 bit에 그 결과를 넣고 기족에 있던 1~7 --> 2~8로 shift 시켜준다. 이를 다항식으로 표현하면

그런데 왜 이렇게 다항식을 꾸미는지는 잘 모르겠다. 그런데도 내가 다항식을 적어보고 규칙을 이해하려는 까닭은 다항식이 주어지고 LFSR을 설계하라고 했을 때 어떻게 할지 생각해 본 것이다. 다항식으로 spec을 주는게 편하니까 말이다.
자 다시 와서 8bit seed는 116이고 다항식은 위와 같을때 그 다음 seed값은 어떻게 될까?

7번 bit의 위치와 6번 bit를 XOR --> 1
위에 결과와 2번 위치의 bit를 XOR --> 0

따라서 연산결과 생기는 값은 0이다. 그 다음에는 Shift를 하면 아래와 같이 58이라는 다음 seed가 나오게 된다.

다음에는 이 것을 통해 C 코드로 구현해 보려 한다.

*같이 읽으면 좋은 글*
https://jun-study.tistory.com/67

LFSR 원리와 C코드 만들어보기(2)

https://jun-study.tistory.com/m/68

LFSR 원리와 C코드 만들기(3) (feat. Galoris LFSR)