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

2022.04.21 - [프로그래밍] - LFSR 원리와 C코드 만들어보기(2)

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

출처 : 위키피디아 , Galois LFSR

Galois LFSR

1) When the system is clocked, bits that are not taps are shifted one position to the right unchanged.

: 한번 실행할때 마다. tap이 아닌 bit는 right shift 한다. (위에 diagram에서 tap은 16, 14,13,11 이다.)

2) The taps are XORed with the output bit before they are stored in the next position. 

: tap 위치에 bit는 output bit와 XOR 연산을 한 뒤 right shift 한다. 

3) The new output bit is the next input bit. 

: XOR 연산으로 인해 output bit가 1인 경우 tap은 전부 반대로 바뀌고 right shift되고 output bit가 0인 경우는 tap은 전부 그대로 right shift 된다. 

 

 

C 코드를 생각해보자. 

 unsigned int lfsr = 1;
  while(1)
    lfsr = (lfsr >> 1) ^ (-(signed int)(lfsr & 1) & 0x8000000bu); /* taps 32 4 2 1 */

1. lfsr 은 초기 seed 값이다. 

2. 0x8000000b 는 tap의 위치를 나타낸 것이다. 

3. (-(signed int)(lfsr & 1)) output bit를 음수로 만든 것이다. 음수로 만든 이유는 위에서 이야기 했듯이 output bit가 1인 경우에는 tap을 전부 0->1 또는 1-> 0으로 바꾸기 떄문에 -1 (이진수로 1111 1111 1111 1111 1111 1111 1111 1111) 로 표현한 것이고 output bit가 0인 경우는 그 반대이다. 

4. 따라서 해당 알고리즘은 tap의 위치를 변경하면서 그 순서를 조정할 수 있다.