의사 난수 생성 - 3. LFSR (Linear Feedback Shift Register)

PS (Problem Solving) 문제의 입력 데이터 생성을 위해서 재현 가능한 난수가 필요 합니다. 어찌보면 "재현 가능하다"와 "난수"라는 개념이 상반되지만 암호학에서 pseudo-noise sequence, 통신에서 whitening sequence 등이 필요한 곳에서 사용하는 방법으로 실제 상황과 유사하게 임의의 데이터를 발생 시켜서 입력 해야 하지만 분석을 위해서 재현 가능한 패턴이 필요한 것이죠. 사용되는 선형 함수를 잘 선택하면 주기가 길고 무작위적인 실제와 매우 유사한 입력 데이터를 생성할 수 있다고 합니다. 이를 의사 난수 생성(Pseudo Random Number Generation: PRNG)이라고 합니다.

이 때 사용되는 것 중에서 한가지 방법이 1965년에 만들어진 LFSR 이라는 개념입니다.

LFSR은 Shift Register에 입력되는 값이 이전 상태의 선형 함수로 다시 되먹임되는 Linear Feedback 구조 입니다.

또한 이전 상태가 Feedback 되어 다음 상태를 만들기 때문에 "결정론적이다"라고 하기도 합니다.

Shift Register가 시작하는 값을 seed라고 하는데 아래와 같이 2진수로 표현된 Shift Register의 seed가 있을 때

2^7 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1 로 표현 합니다.

아래 XOR 게이트로 연산 해서 전체 값을 한쪽으로 SHIFT 이동 해서 마지막 값을 버리고 새롭게 생긴 빈자리에 이 연산 결과를 적어 줍니다.

이 때 XOR 게이트 연산 하는 것을 "선형 함수로 계산한다"라고 하고 아래와 같은 수식으로 나타냅니다. X의 지수승은 XOR 게이트의 입력이 연결된 2진수의 자리수 입니다.

X^4 + X^3 + X^1 + 1

이 방식을 피보나치 (Fibonacci) LFSR 이라고 합니다. C 언어로 구현해 보면 아래와 같습니다.

#define MAX_BIT_SHFIT    (7) // 8bit binary shift

unsigned lfsr_fib(void)
{
    uint8_t start_state = 0xB6u;
    uint8_t lfsr = start_state;
    uint8_t bit; 
    unsigned period = 0;

    do {   /* feedback polynomial: x^4 + x^3 + x^1 + 1 */
        bit = ((lfsr >> (MAX_BIT_SHFIT-4)) 
        	^ (lfsr >> (MAX_BIT_SHFIT-3)) 
            ^ (lfsr >> (MAX_BIT_SHFIT-1))) & 1u;
        lfsr = (bit << MAX_BIT_SHFIT) | (lfsr >> 1);
        ++period;
    } while (lfsr != start_state);

    return period;
}

LFSR로 만들어 질 수 있는 수들을 MLS (Maximum Length Sequence)라고 합니다. (MLS: 0이 아니고 모든 bit의 조합으로 나타낼 수 있는 2진수)

그런데 다른 방식으로 아래아 같이 구현 할 수도 있습니다. 이를 갈루아 (Galois) LFSR라고 합니다.

unsigned lfsr_galois(void)
{
    uint8_t start_state = 0xB6u;  /* Any nonzero start state will work. */
    uint8_t lfsr = start_state;
    unsigned period = 0;

    do {
        unsigned lsb = lfsr & 1u;  /* Get LSB (i.e., the output bit). */
        lfsr >>= 1;                /* Shift register */
        lfsr ^= (-lsb) & 0x1Au;       /* If the output bit is 1, apply toggle mask. */
        ++period;
    } while (lfsr != start_state);

    return period;
}

아래 그림과 같이 SHIFT 이동 후 추출되는 값을 기준으로 XOR 게이트 연산을 수행하여 빈공간에 다시 입력하는 방식입니다.

이를 간단히 표현하면 아래와 같이 줄일 수 있습니다.

unsigned lfsr_galois(void)
{
    uint8_t start_state = 0xB6u;  /* Any nonzero start state will work. */
    uint8_t lfsr = start_state;
    unsigned period = 0;

    do {
        lfsr = (lfsr >> 1) ^ (-(signed char)(lfsr & 1) & 0x1A);
        ++period;
    } while (lfsr != start_state);

    return period;
}

George Marsaglia와 Richard P. Brent가 XOR과 Shift 연산만으로 2003년에 제안한 Xorshift LFSRs 방식이 아래와 같은데 차이점은 이해가 되지 않고 있습니다. 😨

#define MAX_BIT_SHFIT    (7) // 8bit binary shift

unsigned lfsr_fib(void)
{
    uint8_t start_state = 0xB6u;
    uint8_t lfsr = start_state;
    unsigned period = 0;

    do {
        lfsr ^= lfsr >> (MAX_BIT_SHFIT-4);
        lfsr ^= lfsr >> (MAX_BIT_SHFIT-3);
        lfsr ^= lfsr >> (MAX_BIT_SHFIT-1);
        ++period;
    } while (lfsr != start_state);

    return period;
}

참고: (아래 주소의 내용들을 제가 이해한대로 다시 정리하였습니다.)

https://en.m.wikipedia.org/wiki/Linear-feedback_shift_register

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%98%95_%EB%90%98%EB%A8%B9%EC%9E%84_%EC%8B%9C%ED%94%84%ED%8A%B8_%EB%A0%88%EC%A7%80%EC%8A%A4%ED%84%B0

https://en.m.wikipedia.org/wiki/Maximum_length_sequence

https://en.m.wikipedia.org/wiki/Pseudorandom_number_generator

https://en.m.wikipedia.org/wiki/List_of_random_number_generators