선형 되먹임 시프트 레지스터

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 동작 구조
3. 출력 스트림 특성
4. 응용
- 4.1. 카운터로서의 활용
- 4.2. 회로 테스트에서의 사용
5. 한국의 LFSR 관련 연구 및 활용
6. 최장 LFSR이 되는 다항식의 예
참조

1. 개요

선형 되먹임 시프트 레지스터(LFSR)는 탭이라고 불리는 특정 비트들의 XOR 연산을 통해 새로운 입력 비트를 생성하고, 이를 레지스터에 되먹임하는 방식으로 작동하는 시프트 레지스터의 한 종류이다. 탭의 위치에 따라 다양한 LFSR을 구현할 수 있으며, 피보나치 LFSR과 갈루아 LFSR이 대표적이다. LFSR은 최대 길이 시퀀스(m-시퀀스)를 생성하여, 카운터, 의사 난수 생성, 회로 테스트 등 다양한 분야에 활용된다.

더 읽어볼만한 페이지

유사난수 생성기 - RC4
RC4는 로널드 라이베스트가 1987년에 설계한 스트림 암호 알고리즘으로, 과거 널리 사용되었으나 보안 취약점 때문에 현재는 안전하지 않은 암호로 간주된다.
유사난수 생성기 - 메르센 트위스터
메르센 트위스터는 마츠모토 마코토와 니시무라 타쿠지가 개발한 유사난수 생성 알고리즘으로, 긴 주기와 고차원 균등 분포를 특징으로 하지만 암호학적으로 안전하지 않고 상태 크기가 크다는 단점이 있어 다양한 변종이 개발되었다.
디지털 레지스터 - 명령 레지스터
디지털 레지스터 - 시프트 레지스터
시프트 레지스터는 클럭 신호에 따라 데이터를 순차적으로 이동시키는 디지털 회로로, 입출력 방식에 따라 다양한 종류가 있으며, 데이터 변환, 지연 회로, 펄스 폭 확장, 스택 구현, I/O 핀 확장 등 다양한 용도로 활용된다.
암호 알고리즘 - 이진 코드
이진 코드는 0과 1을 사용하여 정보를 표현하는 시스템으로, 고대 중국의 주역에서 기원하며, 컴퓨터 과학, 통신 등 다양한 분야에서 활용된다.
암호 알고리즘 - 메시지 인증 코드
메시지 인증 코드(MAC)는 메시지 무결성을 보장하기 위해 사용되는 암호화 기법으로, 송신자와 수신자가 동일한 키를 공유하여 MAC 생성, 확인 과정을 거친다.

선형 되먹임 시프트 레지스터
개요
유형	시프트 레지스터
속성	선형
응용 분야	의사 난수 생성 암호화 오류 검출 화이트 노이즈 생성
정의
정의	선형 피드백 시프트 레지스터(LFSR)는 그 다음 값이 이전 값들의 선형 함수인 시프트 레지스터이다.
피드백 함수	XOR을 사용하여 레지스터의 값을 계산한다.
선형 함수	단일 비트에 대한 배타적 논리합이다.
레지스터의 초기값	시드(seed)라고 부른다.
동작 원리
동작 방식	레지스터는 일련의 상태를 거친다. 레지스터가 최대 길이일 경우 모든 가능한 상태를 한 번씩 거친다. 0 상태는 예외이다.
탭(tap)	레지스터의 특정 위치를 의미한다. 레지스터의 상태를 결정하기 위해 XOR 된다.
갈로아 LFSR (Galois LFSR)	XOR 게이트가 레지스터 사이에 삽입된다. 출력이 탭 위치의 비트와 XOR 된다.
응용
의사 난수 생성	LFSR은 간단하고 효율적인 의사 난수 생성기이다.
암호화	스트림 암호에 사용될 수 있다. LFSR의 선형성 때문에 LFSR 기반 암호는 취약하다.
오류 검출	순환 중복 검사에 사용된다.
화이트 노이즈 생성	LFSR을 사용하여 근사적인 화이트 노이즈를 생성할 수 있다.
종류
피보나치 LFSR (Fibonacci LFSR)	출력이 탭 위치의 비트와 XOR 되어 다음 상태를 만든다.
갈로아 LFSR (Galois LFSR)	XOR 게이트가 레지스터 사이에 삽입된다.
장점
구현 용이성	하드웨어로 구현하기 쉽다.
빠른 속도	빠른 속도로 동작할 수 있다.
긴 주기	적절한 탭 선택 시 긴 주기를 가질 수 있다.
단점
선형성	선형성 때문에 예측 가능하고 보안에 취약하다.
초기값 의존성	초기값(seed)에 따라 생성되는 난수열이 결정된다.

2. 동작 구조

선형 되먹임 시프트 레지스터(LFSR)는 다음 상태에 영향을 주는 비트 위치인 "탭"의 값들을 XOR 연산하여 새로운 입력 비트를 생성하고, 이를 레지스터에 되먹임하는 방식으로 동작한다.

16비트 피보나치 수열 LFSR. 표시된 피드백 탭 번호는 표의 원시 다항식에 해당하므로 레지스터는 모두 0인 상태를 제외하고 최대 65535개의 상태를 순환합니다. 표시된 상태 0xACE1 (16진수) 다음에는 0x5670이 옵니다.

위치 28과 31에 탭이 있는 피보나치 31비트 선형 되먹임 시프트 레지스터로, 이 속도에서 최대 주기와 기간은 거의 6.7년입니다.

다음 상태에 영향을 미치는 비트 위치를 ''탭''이라고 한다. 다이어그램에서 탭은 [16, 14, 13, 11]이다. LFSR의 가장 오른쪽에 있는 비트를 출력 비트라고 하며, 항상 탭이기도 하다. 다음 상태를 얻으려면 탭 비트를 순차적으로 XOR한다. 그런 다음 모든 비트를 한 자리 오른쪽으로 이동시키고 가장 오른쪽 비트를 버리고 탭 비트를 XOR한 결과는 현재 비어 있는 가장 왼쪽 비트로 피드백된다. 의사 난수 출력 스트림을 얻으려면 각 상태 전환 후에 가장 오른쪽 비트를 읽는다.

최대 길이 LFSR은 m-시퀀스를 생성한다(즉, 모든 비트가 0인 상태를 제외하고 시프트 레지스터 내에서 가능한 모든 2^''m'' − 1 상태를 순환합니다).

LFSR의 XOR 기반 피드백 대신 XNOR을 사용할 수도 있다.^[2] 이 기능은 엄밀히 말하면 선형 변환이 아닌 아핀 맵이지만, 상태가 LFSR 상태의 보수인 동등한 다항식 카운터가 생성된다. XOR을 사용할 때 모든 0 상태가 불법인 것과 마찬가지로 XNOR 피드백을 사용할 때는 모든 1 상태가 불법이다. 이 상태는 카운터가 이 상태에서 "잠금"된 상태로 유지되기 때문에 불법으로 간주된다.

LFSR 또는 XNOR의 숫자의 시퀀스는 그레이 코드 또는 자연 이진 코드만큼 유효한 이진수로 간주될 수 있다.

LFSR에서 피드백을 위한 탭 배열은 유한체 산술에서 다항식 mod 2로 표현할 수 있다. 즉, 다항식의 계수는 1 또는 0이어야 한다. 이를 피드백 다항식 또는 상호 특징 다항식이라고 한다. 예를 들어, 탭이 16, 14, 13, 11비트에 있으면 (표시된 대로) 피드백 다항식은 다음과 같다.

:

x^{16} + x^{14} + x^{13} + x^{11} + 1.

다항식의 "1"은 탭에 해당하지 않으며, 첫 번째 비트(즉, ''x''⁰, 이는 1과 동일)에 대한 입력에 해당한다. 항의 거듭제곱은 왼쪽에서부터 계산하여 탭된 비트를 나타낸다. 첫 번째 비트와 마지막 비트는 각각 입력 및 출력 탭으로 항상 연결된다.

해당 피드백 다항식이 원시이면 LFSR은 최대 길이이며, 갈루아체 GF(2)에 있다.^[3]^[4] 즉, 다음 조건이 필요하다(그러나 충분하지 않음).

탭의 수는 짝수이다.
탭 집합은 집합적 서로소이다. 즉, 모든 탭에 공통적인 1 이외의 제수가 없어야 한다.

지정된 LFSR 길이에 대해 최대 길이 탭 시퀀스가 둘 이상 있을 수 있다. 또한 최대 길이 탭 시퀀스 중 하나를 찾으면 다른 시퀀스가 자동으로 뒤따른다. ''n''비트 LFSR의 탭 시퀀스가 이면 여기서 0은 ''x''⁰ = 1 항에 해당하고, 해당 "미러" 시퀀스는 이다. 따라서 탭 시퀀스 는 을 대응한다. 둘 다 최대 길이 시퀀스를 제공한다.

16비트 갈루아 LFSR. 위의 레지스터 번호는 피보나치 예제와 동일한 기약 다항식에 해당하지만 시프트 방향과 반대 방향으로 계산됩니다. 이 레지스터는 또한 모든 0 상태를 제외하고 최대 65535개의 상태를 순환합니다. 표시된 ACE1 16진수 상태는 E270 16진수를 따릅니다.

2. 1. 피보나치 LFSR

피보나치 LFSR은 탭들을 순차적으로 XOR 연산한 결과를 최상위 비트(MSB)로 되먹임하는 구조를 가진다.^[2] 다음 상태에 영향을 미치는 비트 위치를 ''탭''이라고 하며, 다이어그램에서 탭은 [16, 14, 13, 11]이다. LFSR의 가장 오른쪽에 있는 비트를 출력 비트라고 하며, 항상 탭이기도 하다. 다음 상태를 얻으려면 탭 비트를 순차적으로 XOR 연산을 한다. 그런 다음 모든 비트를 한 자리 오른쪽으로 이동시키고 가장 오른쪽 비트를 버리고 탭 비트를 XOR한 결과는 현재 비어 있는 가장 왼쪽 비트로 피드백된다. 의사 난수 출력 스트림을 얻으려면 각 상태 전환 후에 가장 오른쪽 비트를 읽는다.

LFSR의 XOR 기반 피드백 대신 XNOR을 사용할 수도 있다.^[2]

LFSR에서 피드백을 위한 탭 배열은 유한체 산술에서 다항식 mod 2로 표현할 수 있다. 예를 들어, 탭이 16, 14, 13, 11비트에 있으면 (표시된 대로) 피드백 다항식은 다음과 같다.

:

x^{16} + x^{14} + x^{13} + x^{11} + 1.

다항식의 "1"은 탭에 해당하지 않으며, 첫 번째 비트(즉, ''x''⁰, 이는 1과 동일)에 대한 입력에 해당한다. 항의 거듭제곱은 왼쪽에서부터 계산하여 탭된 비트를 나타낸다. 첫 번째 비트와 마지막 비트는 각각 입력 및 출력 탭으로 항상 연결된다.

해당 피드백 다항식이 원시이면 LFSR은 최대 길이이며, 갈루아체 GF(2)에 있다.^[3]^[4] 즉, 다음 조건이 필요하다(그러나 충분하지 않음).

탭의 수는 짝수이다.
탭 집합은 집합적 서로소이다. 즉, 모든 탭에 공통적인 1 이외의 제수가 없어야 한다.

최대 길이 LFSR은 m-시퀀스를 생성한다(즉, 모든 비트가 0인 상태를 제외하고 시프트 레지스터 내에서 가능한 모든 2^''m'' − 1 상태를 순환합니다).^[2]

지정된 LFSR 길이에 대해 최대 길이 탭 시퀀스가 둘 이상 있을 수 있다. 또한 최대 길이 탭 시퀀스 중 하나를 찾으면 다른 시퀀스가 자동으로 뒤따른다. ''n''비트 LFSR의 탭 시퀀스가 이면 여기서 0은 ''x''⁰ = 1 항에 해당하고, 해당 "미러" 시퀀스는 이다. 따라서 탭 시퀀스 는 을 대응한다. 둘 다 최대 길이 시퀀스를 제공한다.

C/C++ 코드 예시는 다음과 같다.

#include

unsigned lfsr_fib(void)

{

uint16_t start_state = 0xACE1u; /* 모든 0이 아닌 시작 상태가 작동합니다. */

uint16_t lfsr = start_state;

uint16_t bit; /* 코드에서 나중에 bit<<15를 허용하려면 16비트여야 합니다. */

unsigned period = 0;

do

{ /* 탭: 16 14 13 11; 피드백 다항식: x^16 + x^14 + x^13 + x^11 + 1 */

bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u;

lfsr = (lfsr >> 1) | (bit << 15);

++period;

}

while (lfsr != start_state);

return period;

}

빠른 패리티 또는 팝카운트 연산을 사용할 수 있는 경우 피드백 비트는 레지스터와 특성 다항식의 내적으로 보다 효율적으로 계산할 수 있다.

bit = parity(lfsr & 0x002Du);, 또는 이와 동등하게
bit = popcnt(lfsr & 0x002Du) /* & 1u */;. (& 1u는 popcnt를 실제 패리티 함수로 변환하지만 나중에 bit << 15는 더 높은 비트를 관련 없게 만듭니다.)

회전 연산을 사용할 수 있는 경우 새 상태는 다음과 같이 계산할 수 있다.

lfsr = rotateright((lfsr & ~1u) | (bit & 1u), 1);, 또는 이와 동등하게
lfsr = rotateright(((bit ^ lfsr) & 1u) ^ lfsr, 1);

피보나치 LFSR(16비트 탭 [16, 15, 13, 4])의 파이썬 구현 예시는 다음과 같다.

```python

start_state = 1 << 15 | 1

lfsr = start_state

period = 0

while True:

# 탭: 16 15 13 4; 피드백 다항식: x^16 + x^15 + x^13 + x^4 + 1

bit = (lfsr ^ (lfsr >> 1) ^ (lfsr >> 3) ^ (lfsr >> 12)) & 1

lfsr = (lfsr >> 1) | (bit << 15)

period += 1

if lfsr == start_state:

print(period)

break

2. 2. 갈루아 LFSR

갈루아 LFSR은 기존 LFSR과 동일한 출력 수열을 생성할 수 있는 대체 구조이다. 갈루아는 프랑스 수학자 에바리스트 갈루아의 이름에서 따왔다. 갈루아 설정에서는 시스템에 클럭이 인가될 때 탭이 아닌 비트는 한 자리 오른쪽으로 시프트된다. 탭은 다음 위치에 저장되기 전에 출력 비트와 배타적 논리합(XOR) 연산된다.^[5] 새로운 출력 비트는 다음 입력 비트가 된다. 출력 비트가 0일 때는 레지스터의 모든 비트가 변경되지 않은 상태로 오른쪽으로 시프트되고, 입력 비트는 0이 된다. 출력 비트가 1일 때는 탭 위치의 비트들이 모두 반전되고, 전체 레지스터가 오른쪽으로 시프트되며, 입력 비트는 1이 된다.^[5]

동일한 출력 스트림을 생성하기 위해 탭의 순서는 기존 LFSR의 순서와 대응된다.^[5] 그렇지 않으면 스트림이 반전된다. LFSR의 내부 상태는 반드시 동일하지 않다.^[5]

갈루아 LFSR의 특징은 다음과 같다.

갈루아 LFSR는 새로운 입력을 생성하기 위해 모든 탭을 연결하지 않는다. XOR 연산은 LFSR 내에서 완료되고, 직렬로 연산되는 XOR 게이트가 없으므로 전파 시간이 하나의 XOR 연산 시간으로 줄어든다. 따라서 각 탭을 병렬로 계산하는 것이 가능하여 실행 속도를 증가시킨다.
LFSR의 소프트웨어 구현에서 갈루아 형식은 XOR 연산을 한 번에 워드 단위로 구현할 수 있으므로 더 효율적이다. 출력 비트만 개별적으로 검사하면 된다.

2. 3. Xorshift LFSR

조지 마르살리아(George Marsaglia)가 제시하고^[6] 리처드 P. 브렌트(Richard P. Brent)가 추가 분석한 바와 같이,^[7] 선형 되먹임 시프트 레지스터는 XOR 및 시프트 연산을 사용하여 구현할 수 있다.^[6]^[7] 이 방식은 XOR, 시프트 연산이 최신 프로세서 명령어에 효율적으로 매핑되기 때문에 소프트웨어에서 빠르게 실행할 수 있다.

2. 4. 행렬 형태

피보나치 및 갈루아 구성의 이진 LFSR은 GF(2)에서 행렬을 사용하여 선형 함수로 표현할 수 있다.^[9] LFSR의 특성 다항식의 동반 행렬을 사용하고 시드를 열 벡터로 표시하면, 피보나치 구성에서 k 단계 후 레지스터의 상태를 구할 수 있다.

피보나치 구성에서 k 단계 후 레지스터의 상태는 다음과 같이 표현된다.

:

\begin{pmatrix} a_{k} \\ a_{k+1} \\ a_{k+2} \\ \vdots \\ a_{k+n-1} \end{pmatrix} =\begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 0\\ 0 & 0 & \cdots & 0& 1\\ c_{0} & c_{1} & \cdots & \cdots & c_{n-1} \end{pmatrix}\begin{pmatrix} a_{k-1} \\ a_{k} \\ a_{k+1} \\ \vdots \\ a_{k+n-2} \end{pmatrix} =\begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 0\\ 0 & 0 & \cdots & 0& 1\\ c_{0} & c_{1} & \cdots & \cdots & c_{n-1} \end{pmatrix}^k\begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n-1} \end{pmatrix}

갈루아 형태의 행렬은 다음과 같다.

:

\begin{pmatrix} c_0 & 1 & 0 & \cdots & 0 \\ c_1 & 0 & 1 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 0\\ c_{n-2} & 0 & \cdots & 0& 1\\ c_{n-1} & 0 & \cdots & \cdots & 0 \end{pmatrix}

적절한 초기화를 위해, 열 벡터의 최상위 계수는 다음과 같다.

:

\begin{pmatrix} c_0 & 1 & 0 & \cdots & 0 \\ c_1 & 0 & 1 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 0\\ c_{n-2} & 0 & \cdots & 0& 1\\ c_{n-1} & 0 & \cdots & \cdots & 0 \end{pmatrix}^k\begin{pmatrix} a'_0 \\ a'_1 \\ a'_2 \\ \vdots \\ a'_{n-1} \end{pmatrix}

이는 원래 시퀀스의 항을 제공한다. 이러한 형태는 임의의 필드로 일반화할 수 있다.

3. 출력 스트림 특성

선형 되먹임 시프트 레지스터(LFSR)의 출력은 1과 0이 "런(run)" 형태로 나타난다. 예를 들어, 0110100은 1, 2, 1, 1, 2 길이의 런으로 구성된다. 최대 길이 LFSR의 경우, 한 주기에서 2^''n''−1개의 런이 발생하며, 이 런의 절반은 길이가 1비트, 4분의 1은 길이가 2비트이다. 0의 최장 런은 ''n'' − 1 비트, 1의 최장 런은 ''n'' 비트이다. 이러한 분포는 진정한 무작위 시퀀스의 통계적 기댓값과 거의 같다.^[12]

LFSR의 출력 스트림은 결정론적이어서, 현재 상태와 LFSR의 XOR 게이트 위치를 알면 다음 상태를 예측할 수 있다.^[12] 미러 탭 수열을 갖는 LFSR을 통해 출력 스트림을 반전시킬 수 있다. 또한, 모든 비트가 0인 상태는 나타날 수 없다.

4. 응용

선형 되먹임 시프트 레지스터(LFSR)는 하드웨어로 구현이 가능하며, 직접 시퀀스 확산 스펙트럼(DSSS) 무선과 같이 매우 빠른 의사 난수 수열 생성이 필요한 응용 분야에 유용하게 사용된다.^[12] 또한, LFSR은 다양한 프로그래밍 가능한 사운드 생성기에서 백색 잡음의 근사치를 생성하는 데에도 사용되어 왔다.

LFSR은 레이더에서 송신파와 수신파의 시간차를 측정하여 반사체까지의 거리를 판정하는 데 사용된다. GPS는 LFSR을 사용하여 고정밀 상대 시간 오프셋을 나타내는 시퀀스를 빠르게 전송한다. 패밀리 컴퓨터는 사운드 시스템의 일부로 LFSR을 갖추고 있다([https://web.archive.org/web/20140426044512/http://nocash.emubase.de/everynes.htm]).

4. 1. 카운터로서의 활용

LFSR의 반복되는 상태 시퀀스를 통해 클럭 분주기 또는 카운터로 사용할 수 있다.^[12] LFSR 카운터는 일반적인 이진 카운터나 그레이 코드 카운터보다 피드백 로직이 단순하여 더 높은 클럭 속도로 작동할 수 있다. LFSR이 록업 상태(XOR 기반 LFSR의 경우 모두 0, XNOR 기반 LFSR의 경우 모두 1)에 들어가지 않도록 해야 한다.^[12]

LFSR은 하드웨어로도 구현할 수 있으므로, 고속의 의사 난수 생성이 필요한 경우에 편리하다.

레이더는 LFSR을 사용하여 송신파와 수신파의 시간차를 측정하여 반사체까지의 거리를 판정하기도 한다. GPS는 LFSR을 사용하여 고정밀 상대 시간 오프셋을 나타내는 시퀀스를 고속으로 전송한다. 패밀리 컴퓨터는 사운드 시스템의 일부로 LFSR을 갖추고 있다.

4. 2. 회로 테스트에서의 사용

LFSR은 회로 테스트에서 테스트 패턴 생성(전수 테스트, 의사 난수 테스트 또는 의사 전수 테스트) 및 시그니처 분석에 사용된다. 완전한 LFSR은 모든 가능한 입력을 포함하므로, 전수 검사를 위한 패턴 생성기로 일반적으로 사용된다. 최대 길이 LFSR과 가중 LFSR은 의사 무작위 테스트 적용을 위한 의사 난수 테스트 패턴 생성기로 널리 사용된다.

내장 자체 검사 (BIST) 기술에서, 칩에 모든 회로 출력을 저장하는 것은 불가능하지만, 회로 출력을 압축하여 결함을 감지하기 위해 나중에 골든 시그니처 (정상 회로의)와 비교할 시그니처를 형성할 수 있다. 이 압축은 손실 압축이므로, 결함이 있는 출력도 골든 시그니처와 동일한 시그니처를 생성하여 결함을 감지할 수 없는 가능성이 항상 있으며, 이를 오류 마스킹 또는 앨리어싱이라고 한다. BIST는 다중 입력 시그니처 레지스터 (MISR 또는 MSR)로 수행되며, 이는 일종의 LFSR이다. 표준 LFSR과 다르게 MISR은 모든 플립플롭의 입력이 XOR/XNOR 게이트를 통해 공급되는 구조를 가진다.

최근에는 LFSR의 "탭"으로 설정-재설정 플립플롭을 사용하는 방식이 제안되어, BIST 시스템의 저장 공간 최적화를 가능하게 한다.

LFSR은 하드웨어로도 구현할 수 있으므로, 고속의 의사 난수 생성이 필요한 경우(직접 시퀀스 확산 무선 통신 등])에 편리하다. 레이더, GPS, 패밀리 컴퓨터 등에서도 LFSR이 활용된다.

5. 한국의 LFSR 관련 연구 및 활용

6. 최장 LFSR이 되는 다항식의 예

다음 표는 시프트 레지스터 길이 24까지의 최대 길이 피드백 다항식(원시 다항식)의 예시를 나타낸다. 최대 길이 LFSR에 대한 공식은 솔로몬 골롬이 1967년에 저술한 저서에서 개발되었다.^[10] 서로 다른 원시 다항식의 수는 시프트 레지스터 길이에 따라 지수적으로 증가하며, 오일러 피 함수^[11]를 사용하여 정확하게 계산할 수 있다.

비트 (n)	피드백 다항식	탭	탭 (16진수)	주기( $2^n - 1$ )
2	$x^2 + x + 1$	11	0x3	3
3	$x^3 + x^2 + 1$	110	0x6	7
4	$x^4 + x^3 + 1$	1100	0xC	15
5	$x^{ 5 }+x^{ 3 }+1$	10100	0x14	31
6	$x^{ 6 }+x^{ 5 }+1$	110000	0x30	63
7	$x^{ 7 }+x^{ 6 }+1$	1100000	0x60	127
8	$x^{ 8 }+x^{ 6 }+x^{ 5 }+x^{ 4 }+1$	10111000	0xB8	255
9	$x^{ 9 }+x^{ 5 }+1$	100010000	0x110	511
10	$x^{ 10 }+x^{ 7 }+1$	1001000000	0x240	1,023
11	$x^{ 11 }+x^{ 9 }+1$	10100000000	0x500	2,047
12	$x^{ 12 }+x^{ 11 }+x^{ 10 }+x^{ 4 }+1$	111000001000	0xE08	4,095
13	$x^{ 13 }+x^{ 12 }+x^{ 11 }+x^{ 8 }+1$	1110010000000	0x1C80	8,191
14	$x^{ 14 }+x^{ 13 }+x^{ 12 }+x^{ 2 }+1$	11100000000010	0x3802	16,383
15	$x^{ 15 }+x^{ 14 }+1$	110000000000000	0x6000	32,767
16	$x^{ 16 }+x^{ 15 }+x^{ 13 }+x^{ 4 }+1$	1101000000001000	0xD008	65,535
17	$x^{ 17 }+x^{ 14 }+1$	10010000000000000	0x12000	131,071
18	$x^{ 18 }+x^{ 11 }+1$	100000010000000000	0x20400	262,143
19	$x^{ 19 }+x^{ 18 }+x^{ 17 }+x^{ 14 }+1$	1110010000000000000	0x72000	524,287
20	$x^{ 20 }+x^{ 17 }+1$	10010000000000000000	0x90000	1,048,575
21	$x^{ 21 }+x^{ 19 }+1$	101000000000000000000	0x140000	2,097,151
22	$x^{ 22 }+x^{ 21 }+1$	1100000000000000000000	0x300000	4,194,303
23	$x^{ 23 }+x^{ 18 }+1$	10000100000000000000000	0x420000	8,388,607
24	$x^{ 24 }+x^{ 23 }+x^{ 22 }+x^{ 17 }+1$	111000010000000000000000	0xE10000	16,777,215

[https://docs.xilinx.com/v/u/en-US/xapp052 자일링스]는 168비트까지의 확장된 탭 카운터 목록을 발표했다. 최대 길이 다항식 테이블은 http://users.ece.cmu.edu/~koopman/lfsr/ 에서 구할 수 있으며, https://github.com/hayguen/mlpolygen 프로젝트에서 생성할 수 있다.

참조

_[1] 웹사이트 Cyclic Redundancy Check Computation: An Implementation Using the TMS320C54x https://www.ti.com/l[...] Texas Instruments 2016-10-16
_[2] 문서 Linear Feedback Shift Registers in Virtex Devices http://www.xilinx.co[...]
_[3] 서적 Random number generation and Monte Carlo methods https://www.worldcat[...] Springer 2003
_[4] 간행물 Random Numbers Generated by Linear Recurrence Modulo Two https://www.ams.org/[...] 1965-04
_[5] 서적 Numerical Recipes: The Art of Scientific Computing, Third Edition Cambridge University Press
_[6] 간행물 Xorshift RNGs https://www.jstatsof[...] 2003-07
_[7] 간행물 Note on Marsaglia's Xorshift Random Number Generators https://www.jstatsof[...] 2004-08
_[8] 웹사이트 16-Bit Xorshift Pseudorandom Numbers in Z80 Assembly http://www.retroprog[...] 2022-01-05
_[9] 서적 Stream Ciphers Springer
_[10] 서적 Shift register sequences Aegean Park Press 1967
_[11] 웹사이트 Primitive Polynomial https://mathworld.wo[...] 2021-04-27
_[12] PDF http://www.xilinx.co[...] 2022-03
_[13] 문서 Generating High Quality Pseudo Random Number Using Evolutionary Methods http://www.computer.[...] 2008-05
_[14] 간행물 Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication https://www.cs.techn[...] 2019-09-15
_[15] 서적 Advances in Cryptology – CRYPTO 2005 http://www.terminode[...]
_[16] 문서 RFC 4086
_[17] 문서 LFSR generation for high test coverage and low hardware overhead https://livrepositor[...] 2019-08-21
_[18] 문서 Section 9.5 of the SATA Specification, revision 2.6
_[19] 학술회의 Time dissemination via the LF transmitter DCF77 using a pseudo-random phase-shift keying of the carrier https://www.ptb.de/c[...] 2011-10-11
_[20] 문서 Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2; Document 2: SNOW 3G specification https://portal.3gpp.[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com