선형 피드백 시프트 레지스터

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 찾기 : "선형 피드백 시프트 레지스터"– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2009년 3월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

컴퓨팅에서 LFSR(Linear-Feedback Shift Register)은 입력 비트가 이전 상태의 선형 함수인 시프트 레지스터입니다.

단일 비트에서 가장 일반적으로 사용되는 선형 함수는 배타적(XOR)입니다.따라서 LFSR은 대부분의 경우 입력 비트가 전체 시프트 레지스터 값의 일부 비트의 XOR에 의해 구동되는 시프트 레지스터입니다.

LFSR의 초기값은 시드라고 불리며 레지스터의 동작은 결정론적이기 때문에 레지스터에 의해 생성되는 값의 스트림은 현재(또는 이전) 상태에 의해 완전히 결정됩니다.마찬가지로 레지스터는 가능한 상태의 수가 한정되어 있기 때문에 최종적으로 반복 사이클에 들어가야 합니다.단, 피드백 기능이 잘 선택되는 LFSR에서는 랜덤으로 보여 사이클이 매우 긴 일련의 비트가 생성될 수 있습니다.

LFSR에는 의사난수 생성, 의사노이즈 시퀀스, 고속 디지털카운터 및 화이트닝시퀀스 등이 있습니다.LFSR의 하드웨어와 소프트웨어의 실장은 공통입니다.

전송 에러에 대한 빠른 체크를 제공하기 위해 사용되는 순환 용장성 체크의 계산은 LFSR의 ^[1]계산과 밀접하게 관련되어 있습니다.일반적으로 LFSR의 배후에 있는 산술은 LFSR을 연구 및 구현 대상으로 매우 우아하게 만듭니다.간단한 구성 요소로 비교적 복잡한 로직을 생성할 수 있습니다.단, 덜 우아하지만 더 나은 성능을 발휘하는 다른 방법도 고려해야 합니다.

피보나치 LFSR

16비트 Fibonacci LFSR표시된 피드백 탭 번호는 표의 기본 다항식에 해당하므로 레지스터는 모두 0인 상태를 제외한 최대 65535개의 상태를 순환합니다.표시된 상태 0xACE1(16진수) 뒤에 0x5670이 계속됩니다.

다음 상태에 영향을 주는 비트 위치를 탭이라고 합니다.다이어그램에서 탭은 [16,14,13,11]입니다.LFSR의 가장 오른쪽 비트는 출력 비트라고 불립니다.탭은 출력 비트와 함께 순차적으로 XOR되고 맨 왼쪽 비트로 피드백됩니다.맨 오른쪽 위치에 있는 비트의 시퀀스를 출력 스트림이라고 합니다.

• 입력에 영향을 주는 LFSR 상태의 비트는 탭이라고 불립니다.
• 최대 길이 LFSR은 모든 0을 포함하지 않는 한 m-시퀀스(즉, 모든 비트가 0인 상태를 제외한 시프트 레지스터 내의 가능한^m 모든 2-1 상태를 순환)를 생성합니다.
• LFSR의 XOR 기반 피드백 대신 ^[2]XNOR을 사용할 수도 있습니다.이 함수는 엄밀하게는 선형 맵이 아닌 아핀 맵이지만 LFSR 상태를 보완하는 동등한 다항식 카운터가 생성됩니다.XNOR 피드백 사용 시 모두 1인 상태는 XOR 사용 시 모두 0인 상태가 불법인 것과 마찬가지로 불법입니다.이 상태는 카운터가 이 상태에서 "잠긴" 상태로 유지되기 때문에 불법으로 간주됩니다.이 방법은 제로 상태에서 시작하는 플립플롭을 사용하는 하드웨어 LFSR에서 편리합니다.이는 로크업 상태에서 시작되지 않기 때문입니다.즉, 동작을 시작하기 위해 레지스터를 시드할 필요가 없습니다.

LFSR 또는 XNOR에 의해 생성되는 일련의 숫자는 그레이 코드 또는 자연 이진 코드와 마찬가지로 유효한 이진수 시스템으로 간주할 수 있습니다.

LFSR에서 피드백을 위한 탭 배열은 유한 필드 산술로 다항식 모드 2로 표현될 수 있다.즉, 다항식의 계수는 1s 또는 0s여야 합니다.이를 피드백 다항식 또는 역특성 다항식이라고 합니다.예를 들어 탭이 16번째, 14번째, 13번째 및 11번째 비트(그림 참조)일 경우 피드백 다항식은 다음과 같습니다.

${\displaystyle x^{16}+x^{14}+x^{13}+x^{11}+1.}$

다항식의 "1"은 탭과 일치하지 않으며, 첫 번째 비트에 대한 입력(즉, x⁰, 1과 동일)에 해당합니다.용어의 거듭제곱은 왼쪽부터 셀 수 있는 탭 비트를 나타냅니다.첫 번째 비트와 마지막 비트는 항상 각각 입력 및 출력 탭으로 연결됩니다.

LFSR은 대응하는 피드백 다항식이 원시적인 경우에만 최대 길이입니다.즉, 다음과 같은 조건이 필요합니다(충분하지는 않습니다.

• 탭 수는 짝수입니다.
• 탭 세트는 설정된 co-prime입니다.즉, 모든 탭에 공통인 1 이외의 제수가 없어야 합니다.

최대 길이 LFSR을 구성할 수 있는 원시 다항식의 표는 다음과 같이 참조된다.

특정 LFSR 길이에 여러 개의 최대 길이 탭시퀀스가 존재할 수 있습니다.또한 하나의 최대 길이 탭 시퀀스가 발견되면 다른 탭 시퀀스가 자동으로 이어집니다.n비트 LFSR의 탭 시퀀스가 [n, A, B, C, 0]인 경우, 여기서 0은 x = 1 항에⁰ 해당하며, 대응하는 "mirror" 시퀀스는 [n, n - C, n - B, n - A, 0]입니다.따라서 탭 시퀀스[32, 22, 2, 1, 0]에는 대응 부품[32, 31, 30, 10, 0]이 있습니다.둘 다 최대 길이 시퀀스를 제공합니다.

C의 예를 다음에 나타냅니다.

#실패하다 < stdint >h> 서명되어 있지 않다 lfsr_module(무효) {     uint16_t start_state = 0xACE1u;  /* 0이 아닌 모든 시작 상태가 작동합니다.*/     uint16_t lfsr = start_state;     uint16_t 조금;                    /* 비트를 허용하려면 16비트여야 합니다. 코드 내에서 나중에 15비트 미만*/     서명되어 있지 않다 기간 = 0;      하다     {   /* 탭: 16 14 13 11, 피드백 다항식: x^16 + x^14 + x^13 + x^11 + 1 */         조금 = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u;         lfsr = (lfsr >> 1)   (조금 << > 15);         ++기간;     }     하는 동안에 (lfsr != start_state);      돌아가다 기간; } 

고속 패리티 또는 팝카운트 연산을 사용할 수 있는 경우 특성 다항식을 사용하여 피드백 비트를 레지스터의 닷 곱으로 보다 효율적으로 계산할 수 있습니다.

• bit = parity(lfsr & 0x002Du);또는 동등하게
• bit = popcnt(lfsr & 0x002Du) /* & 1u */;. (the.& 1upopcnt를 진정한 패리티 함수로 변환하지만 비트 시프트는 나중에 실행됩니다.bit << 15더 높은 비트는 중요하지 않습니다.)

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

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

이 LFSR 설정은 표준, 다대일 또는 외부 XOR 게이트라고도 합니다.대체 Galois 설정에 대해서는 다음 섹션에서 설명합니다.

Python의 예

유사한 (16,15,13,4에서 16비트 탭) 피보나치 LFSR의 python 구현 예는 다음과 같습니다.

start_state = 1 << > 15   1 lfsr = start_state 기간 = 0  하는 동안에 진실의:     #탭: 16 15 13 4, 피드백 다항식: x^16 + x^15 + x^13 + x^4 + 1     조금 = (lfsr ^ (lfsr >> 1) ^ (lfsr >> 3) ^ (lfsr >> 12)) & 1     lfsr = (lfsr >> 1)   (조금 << > 15)     기간 += 1     한다면 (lfsr == start_state):         인쇄물(기간)         브레이크. 

16비트의 레지스터가 사용되고 4비트, 13비트, 15비트 및 16비트의 xor 탭이 최대 시퀀스 길이를 설정합니다.

갈로아 LFSR

16비트 Galois LFSR위의 레지스터 번호는 피보나치 예시와 동일한 원시 다항식에 해당하지만 이동 방향과는 반대로 카운트됩니다.이 레지스터는 또한 모두 0 상태를 제외한 최대 65535개의 상태를 순환합니다.표시된 ACE1 16진수 상태 뒤에 E270 16진수가 이어집니다.

프랑스 수학자 Evariste Galois의 이름을 딴 Galois 구성의 LFSR은 모듈러형, 내부 XOR 또는 일대다 LFSR로도 알려져 있으며, 기존 LFSR과 동일한 출력 스트림을 생성할 수 있는 대체 구조입니다(단,^[3] 시간 오프셋).Galois 구성에서는 시스템이 클럭되면 탭이 아닌 비트는 변경되지 않고 오른쪽으로 한 위치 이동됩니다.반면 탭은 다음 위치에 저장되기 전에 출력 비트와 XOR됩니다.새 출력 비트가 다음 입력 비트입니다.그 결과 출력 비트가 0이면 레지스터의 모든 비트가 변경되지 않고 오른쪽으로 이동하며 입력 비트가 0이 됩니다.출력 비트가 1이면 탭의 비트가 모두 플립 위치(0이면 1이 되고 1이면 0이 됨)에 도달한 다음 전체 레지스터가 오른쪽으로 이동하고 입력 비트가 1이 됩니다.

동일한 출력 스트림을 생성하기 위해 탭 순서는 기존 LFSR 순서의 반대(상기 참조)입니다.그렇지 않으면 스트림이 반대입니다.LFSR의 내부 상태가 반드시 같을 필요는 없습니다.표시된 Galois 레지스터는 첫 번째 섹션의 피보나치 레지스터와 동일한 출력 스트림을 가집니다.스트림 사이에 시간 오프셋이 존재하므로 각 사이클에서 동일한 출력을 얻으려면 다른 시작점이 필요합니다.

• Galois LFSR은 새로운 입력을 생성하기 위해 모든 탭을 연결하는 것이 아니다(XORing은 LFSR 내에서 이루어지며 XOR 게이트는 직렬로 실행되지 않으므로 전파 시간이 전체 체인이 아닌 하나의 XOR로 감소하므로 각 탭이 병렬로 계산되어 실행 속도가 향상된다).
• LFSR의 소프트웨어 구현에서는 XOR 연산을 한 번에 한 단어씩 구현할 수 있으므로 Galois 형식이 더 효율적입니다. 출력 비트만 개별적으로 검사해야 합니다.

그림에서 16비트의 최대 주기 Galois LFSR 예시의 C 코드 예를 다음에 나타냅니다.

#실패하다 < stdint >h> 서명되어 있지 않다 lfsr_galois(무효) {     uint16_t start_state = 0xACE1u;  /* 0이 아닌 모든 시작 상태가 작동합니다.*/     uint16_t lfsr = start_state;     서명되어 있지 않다 기간 = 0;      하다     { #왼쪽         서명되어 있지 않다 lsb = lfsr & 1u;  /* LSB(출력 비트)를 가져옵니다.*/         lfsr >>= 1;                /* 시프트 레지스터 */         한다면 (lsb)                   /* 출력 비트가 1인 경우 */             lfsr ^= 0xB400u;       /* 토글 마스크를 적용합니다.*/ #실패하다         서명되어 있지 않다 MSB = (int16_t) lfsr < > 0;   /* MSB(출력 비트)를 가져옵니다.*/         lfsr <<=> 1;                          /* 시프트 레지스터 */         한다면 (MSB)                             /* 출력 비트가 1인 경우 */             lfsr ^= 0x002Du;                 /* 토글 마스크를 적용합니다.*/ #엔디프         ++기간;     }     하는 동안에 (lfsr != start_state);      돌아가다 기간; } 

브런치if (lsb) lfsr ^= 0xB400u;라고도 쓸 수 있다lfsr ^= (-lsb) & 0xB400u;컴파일러에 따라서는 보다 효율적인 코드를 생성할 수 있습니다.또한 MSB는 다음 코드 추가의 캐리어이기 때문에 왼쪽 시프트 변형은 훨씬 더 나은 코드를 생성할 수 있습니다.lfsr자기 자신한테.

비바이너리 Galois LFSR

위에 표시된 것과 같은 2진수 갈로아 LFSR은 임의의 q-ary 알파벳 {0, 1, ..., q -1}로 일반화할 수 있습니다(예: 2진수, q = 2, 알파벳은 단순 {0, 1)).이 경우 배타적 성분은 가산 모듈로q(XOR는 가산 모듈로 2)로 일반화되며 피드백 비트(출력 비트)에 특정 탭 포인트별로 일정하게 q-ary 값을 곱한다(모듈로-q).이는 피드백에 0(피드백 없음, 즉 탭 없음) 또는 1(피드백 있음)을 곱하는 바이너리 케이스의 일반화이기도 합니다.적절한 탭 구성을 지정하면 이러한 LFSR을 사용하여 q의 임의의 프라임 값에 대한 Galois 필드를 생성할 수 있습니다.

Xorsshift LFSR

George Marsaglia에^[4] 의해 보여지고 Richard P에 의해 추가로 분석되었듯이. 브렌트 ^[5]선형 피드백 시프트 레지스터는 XOR 및 시프트 연산을 사용하여 구현할 수 있습니다.이러한 조작은 일반적으로 최신 프로세서 명령에 효율적으로 매핑되기 때문에 이 접근방식은 소프트웨어에서의 신속한 실행에 적합합니다.

다음은 John Metcalf의 ^[6]7,9,13 트리플렛을 사용하는 16비트 최대 주기 Xorsshift LFSR의 C 코드 예를 나타냅니다.

#실패하다 < stdint >h> 서명되어 있지 않다 lfsr_xtiftors(무효) {     uint16_t start_state = 0xACE1u;  /* 0이 아닌 모든 시작 상태가 작동합니다.*/     uint16_t lfsr = start_state;     서명되어 있지 않다 기간 = 0;      하다     {   // http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html에서 7,9,13 트리플렛         lfsr ^= lfsr >> 7;         lfsr ^= lfsr << > 9;         lfsr ^= lfsr >> 13;         ++기간;     }     하는 동안에 (lfsr != start_state);      돌아가다 기간; } 

매트릭스 형식

$(\$의 행렬을 사용하여 피보나치 및 갈로아 구성의 이진 LFSR을 선형 함수로 표현할 수 있습니다(GF(2) [7]참조).LFSR 특성 다항식의 동반행렬을 사용하여 시드를 열 벡터$a_{0},$로 나타내며$,$ Fibonac $style$kci 이후 $레지스터$의 $상태$를 나타냅니다.

${\displaystyle{\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&1&\dots &\vdots &\vdots &\dots &\ddots &\ddots &\0&\cdots &\cdots &\cdots &\cdots &\end{pmatrix}{pm}{\catrix}{\cdots\cdots}$

대응하는 Galois 형식의 매트릭스는 다음과 같습니다.

${\displaystyle {pmatrix} c_{0} &\cdots & 0\cdots &\vdots &\vdots &\cdots &\cdots & 0\cdots & 0\cdots & 0\cdots & 0\cdots & 0\cdots\cdots & 0\cdots }$

적절한 초기화를 위해

${\displaystyle a'_{i}=\sum _{i=0}^{j}a_{i-j}c_{n-j},\0\leq i<n}$

열 벡터의 최상위 계수:

${\displaystyle {pmatrix} c_{0} &\cdots & 0\cdots &\vdots &\vdots &\cdots &\cdots & 0\cdots & 0\cdots & 0\cdots & 0\cdots & 0\cdots\cdots & 0\cdots }$

는 원래 시퀀스의 a라는_k 용어를 제공합니다.

이러한 양식은 임의의 필드에 자연스럽게 일반화됩니다.

최대 LFSR에 대한 다항식 예제

다음 표에는 최대 24개의 시프트 레지스터 길이에 대한 최대 길이 피드백 다항식(기본 다항식)의 예가 나와 있습니다.최대 길이 LFSR의 형식주의는 솔로몬 W. 골롬이 1967년 그의 ^[8]저서에서 개발한 것입니다.서로 다른 원시 다항식의 수는 시프트 레지스터 길이에 따라 기하급수적으로 증가하고 오일러의 전체 함수를 사용하여 정확하게^[9] 계산할 수 있습니다(OEIS의 시퀀스 A011260).

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

Xilinx는 최대 168비트까지 탭 카운터의 확장 목록을 공개했습니다.최대 길이의 다항식 표는 http://users.ece.cmu.edu/~koopman/lfsr/에서 구할 수 있으며 https://github.com/hayguen/mlpolygen 프로젝트에서 생성할 수 있습니다.

출력 스트림 속성

• 1과 0은 "실행"에서 발생합니다.예를 들어 출력 스트림 1110010은 길이 3, 2, 1, 1의 4개의 실행으로 구성됩니다.최대 LFSR의 1개 기간에는 2개의ⁿ⁻¹ 실행이 발생합니다(위의 예에서는 3비트 LFSR에는 4개의 실행이 있습니다).이들 실행의 정확히 절반은 1비트 길이, 1/4은 2비트 길이, 최대 1회의 0~1비트 실행 및 1회의 n비트 실행입니다.이 분포는 정말로 랜덤한 시퀀스의 통계 기대치와 거의 동일합니다.그러나 실제로 랜덤 시퀀스의 표본에서 정확히 이 분포를 찾을 확률은 다소^[vague] 낮습니다.
• LFSR 출력 스트림은 확정적입니다.LFSR 내의 XOR 게이트의 현재 상태 및 위치를 알고 있으면 다음 상태를 ^[10]예측할 수 있습니다.이것은 정말로 랜덤한 이벤트에서는 불가능합니다.최대 길이 LFSR을 사용하면 길이마다 LFSR의 수가 제한되기 때문에 다음 상태를 계산하기가 훨씬 쉽습니다.
• 출력 스트림은 반전할 수 있습니다.미러링된 탭이 있는 LFSR은 출력 시퀀스를 역순으로 순환합니다.
• 모든 0으로 구성된 값은 표시할 수 없습니다.따라서 길이n의 LFSR을 사용하여 2개의 값을 모두 생성할ⁿ 수 없습니다.

적용들

LFSR은 하드웨어에 실장할 수 있기 때문에 다이렉트시퀀스 스펙트럼 확산 무선 등 매우 빠른 의사 랜덤시퀀스 생성을 필요로 하는 어플리케이션에서 유용합니다.LFSR은 다양한 프로그램 가능한 사운드 제너레이터에서 대략적인 백색 노이즈를 발생시키는 데도 사용되어 왔습니다.

카운터로 사용

LFSR의 상태 시퀀스의 반복에 의해, 컴퓨터의 인덱스나 프레이밍 로케이션을 기계로 ^[10]판독할 필요가 있는 경우와 같이, 비바이너리 시퀀스가 받아들여질 때는, LFSR 를 클럭 디바이다 또는 카운터로서 사용할 수 있습니다.LFSR 카운터는 내추럴바이너리 카운터나 그레이 코드카운터보다 피드백로직이 심플하기 때문에 높은 클럭환율로 동작할 수 있습니다.다만, 예를 들면, 기동시에 시퀀스내의 다른 스테이트로 프리셋 하는 등, LFSR 가 all-zeros 스테이트가 되지 않게 할 필요가 있습니다.원시 다항식 표는 LFSR이 최대 주기를 주기 위해 피보나치 또는 갈로아 형태로 어떻게 배열될 수 있는지를 보여준다.일부 상태를 건너뛰어 시퀀스를 단축하는 로직이 긴 LFSR에 추가함으로써 다른 기간을 얻을 수 있습니다.

암호화에 사용

LFSR은 간단한 전기 기계 회로 또는 전자 회로, 장기 및 매우 균일하게 분포된 출력 스트림의 구축이 용이하기 때문에 스트림 암호에 사용되는 의사 난수 생성기로 오랫동안 사용되어 왔습니다.그러나 LFSR은 선형 시스템이기 때문에 암호 해독이 상당히 용이합니다.예를 들어, 기존의 평문과 대응하는 암호문을 사용하면 공격자는 시스템에서 사용되는 LFSR 출력 스트림을 가로채 회복할 수 있으며, 이 출력 스트림을 통해 Berlekamp-Massey 알고리즘을 사용하여 의도한 수신기를 시뮬레이트하는 최소 크기의 LFSR을 구축할 수 있습니다.다음으로 이 LFSR에 인터셉트된 출력 스트림의 스트레치를 공급하여 나머지 평문을 회복할 수 있습니다.

LFSR 기반 스트림 암호에서는 이 문제를 줄이기 위해 다음 3가지 일반적인 방법이 사용됩니다.

• LFSR 상태의 여러 비트의 비선형 조합
• 2개 이상의 LFSR 출력 비트의 비선형 조합('발전기 축소'도 참조) 또는 진화 알고리즘을 사용하여 비선형성을 ^[11]도입합니다.
• 교대 스텝 제너레이터와 같이 LFSR의 불규칙한 클로킹.

LFSR 기반의 중요한 스트림 암호에는 GSM 휴대폰에서 사용되는 A5/1 및 A5/2, Bluetooth에서 사용되는E0 및 축소 제너레이터가 포함됩니다.A5/2 암호는 파손되어 A5/1과 E0 모두에 중대한 ^[12][13]취약성이 있습니다.

선형 피드백 시프트 레지스터는 선형 합동 ^[14]생성기와 강한 관계가 있습니다.

회로 테스트에 사용

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2016년 5월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

LFSR은 테스트 패턴 생성(전면 테스트, 의사 랜덤 테스트 또는 의사-전면 테스트) 및 시그니처 분석에 사용됩니다.

테스트 패턴 생성

완전 LFSR은 n 입력회선의 가능한 모든 입력을 커버하기 때문에 일반적으로 철저한 테스트를 위한 패턴 생성기로 사용됩니다.최대 길이 LFSR 및 가중치 LFSR은 의사 랜덤 테스트애플리케이션의 의사 랜덤테스트 패턴 생성기로 널리 사용됩니다.

시그니처 분석

임베디드 셀프 테스트(BIST) 기술에서는 모든 회로 출력을 칩에 저장하는 것은 불가능하지만 회로 출력을 압축하여 나중에 (양호회로의) 골든 시그니처와 비교하여 고장을 검출할 수 있습니다.이 압축은 손실이 발생하기 때문에 출력 장애로 인해 골든시그니처와 같은 시그니처가 생성되어 장애를 검출할 수 없는 경우가 항상 있습니다.이 상태를 에러 마스킹 또는 에일리어스라고 부릅니다.BIST는 LFSR의 일종인 Multiple-Input Signature Register(MISR 또는 MSR; 다중 입력 시그니처 레지스터)를 사용하여 구현됩니다.표준 LFSR에는 단일 XOR 또는 XNOR 게이트가 있으며 게이트 입력은 여러 "탭"에 연결되고 출력은 첫 번째 플립 플랍 입력에 연결됩니다.MISR의 구조는 동일하지만 모든 플립플랍에 대한 입력은 XOR/XNOR 게이트를 통해 공급됩니다.예를 들어, 4비트 MISR에는 4비트 병렬 출력과 4비트 병렬 입력이 있습니다.첫 번째 플립 플랍 입력은 병렬 입력 비트 0과 "탭"이 있는 XOR/XNORd입니다.다른 모든 플립 플랍 입력은 앞의 플립 플랍 출력과 대응하는 병렬 입력 비트를 가진 XOR/XNORd입니다.따라서 MISR의 다음 상태는 현재 상태뿐만 아니라 마지막 몇 가지 상태에 따라 달라집니다.따라서 입력 시퀀스가 항상 같으면 MISR은 항상 같은 골든시그니처를 생성합니다.최근 어플리케이션에서는^[15] LFSR의 "탭"으로 set-reset 플립 플랍을 제안하고 있습니다.이를 통해 BIST 시스템은 스토리지를 최적화할 수 있습니다.이는 셋셋 플립 플랍이 초기 시드를 저장하여 LFSR에서 전체 비트스트림을 생성할 수 있기 때문입니다.그럼에도 불구하고, 이것은 BIST의 아키텍처를 변경해야 하며, 특정 애플리케이션에 대한 옵션입니다.

디지털 방송 및 통신에 사용

스크램블

짧은 반복 시퀀스(예: 0초 또는 1초의 실행)가 수신기에서 심볼 추적을 복잡하게 하거나 다른 전송을 방해할 수 있는 스펙트럼 라인을 형성하지 않도록 데이터 비트 시퀀스는 변조 및 전송 전에 선형 피드백 레지스터의 출력과 결합됩니다.이 스크램블링은 복조 후에 리시버에서 삭제됩니다.LFSR이 송신된 심볼스트림과 같은 비트환율로 동작하는 경우 이 기술은 스크램블링이라고 불립니다.LFSR이 심볼스트림보다 상당히 빠르게 동작하는 경우 LFSR에 의해 생성된 비트시퀀스는 치핑코드라고 불립니다칩 코드는 배타적 또는 바이너리 위상 편이 키잉 또는 유사한 변조 방법을 사용하여 전송하기 전에 데이터와 결합됩니다.결과 신호는 데이터보다 대역폭이 높기 때문에 이는 스펙트럼 확산 통신 방식입니다.스펙트럼 확산 속성에만 사용되는 이 기술은 직접 시퀀스 확산 스펙트럼이라고 불립니다.동시에 같은 채널로 송신되는 여러 신호를 동시에 구별하기 위해 사용되는 경우 코드 분할 다중 액세스라고 불립니다.

암호화 또는 암호화와 혼동해서는 안 됩니다.LFSR을 사용한 스크램블링 및 확산은 정보를 도청으로부터 보호하지 않습니다.대신 견고하고 효율적인 변조 및 복조를 가능하게 하는 편리한 엔지니어링 특성을 가진 동등한 스트림을 생성하는 데 사용됩니다.

선형 피드백 레지스터를 사용하는 디지털 방송 시스템:

• ATSC 표준 (디지털 TV 전송 시스템 - 북미)
• DAB(디지털 오디오 방송 시스템 - 라디오용)
• DVB-T(디지털 TV 전송 시스템– 유럽, 호주, 아시아 일부)
• NICAM(텔레비전용 NICAM

LFSR을 사용하는 기타 디지털 통신 시스템:

• INTELSAT 비즈니스 서비스(IBS)
• 중간 데이터 레이트(IDR)
• HDMI 2.0
• SDI(시리얼 디지털 인터페이스 전송)
• PSTN을 통한 데이터 전송(ITU-T V 시리즈 권장 사항에 따름)
• CDMA(코드분할다중접속) 셀룰러 텔레포니
• LFSR을 사용한100BASE-T2 "고속" 이더넷스크램블 비트
• 기가비트 이더넷의 가장 일반적인 형식인1000BASE-T 이더넷은 LFSR을 사용하여 비트를 스크램블합니다.
• PCI Express
• SATA^[16]
• 시리얼 접속 SCSI(SAS/SPL)
• USB 3.0
• LFSR을 사용한 IEEE 802.11a의 비트 스크램블
• Bluetooth Low Energy Link Layer는 LFSR(미백)을 사용하고 있습니다.
• GPS와 GLONASS와 같은 위성 내비게이션 시스템.현재의 모든 시스템은 LFSR 출력을 사용하여 렌징 코드의 일부 또는 전부를 생성하거나(CDMA 또는 DSSS의 치핑코드로서) 데이터 없이 반송파를 변조합니다(GPS L2 CL 렌징 코드 등).GLONASS는 DSSS와 결합된 주파수 분할 다중 액세스도 사용합니다.

기타 용도

LFSR은 무선 교란 시스템에서도 사용되며, 의사 랜덤 노이즈를 발생시켜 대상 통신 시스템의 노이즈 플로어를 상승시킵니다.

독일 시간 신호 DCF77은 진폭 키잉과 더불어 9단계 LFSR에 의해 구동되는 위상 편이 키잉을 사용하여 ^[17]노이즈가 있는 경우 수신 시간의 정확성과 데이터 스트림의 견고성을 높입니다.

「 」를 참조해 주세요.

• 바람개비
• 메르센 트위스터
• 최대 길이 시퀀스
• 아날로그 피드백 시프트 레지스터
• NLFSR, 비선형 피드백 시프트 레지스터
• 링 카운터
• 의사 랜덤 바이너리 시퀀스
• 금계열
• JPL 시퀀스
• 카사미 수열
• 베를캄프-매시 알고리즘

레퍼런스

추가 정보

• http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
• https://web.archive.org/web/20161007061934/http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf
• http://users.ece.cmu.edu/~koopman/lfsr/index.dex : 2 ~64비트의 최대 길이 피드백 다항식 테이블.
• https://github.com/hayguen/mlpolygen - 최대 길이 피드백 다항식을 생성하는 코드

외부 링크

• LSFR과 랜덤성의 본질적 생성:NKS로부터의 메모