Registrul de deplasare a feedback-ului liniar

Registrul de deplasare a feedback-ului liniar (linear feedback shift register, LFSR) este un tip de registre de translație ale căror date de intrare sunt produse de o funcție liniară a stării interne.

Singurele funcții liniare ale biților unici sunt XOR și XNOR (invers invers); de aceea este un registru de traducere ale cărui biți de intrare sunt produși exclusiv sau (xor) unor biți stocați în registre.

Valoarea inițială a unui LFSR se numește semință și, din moment ce funcționarea registrului este deterministă , succesiunea valorilor produse de registru este complet determinată de starea sa curentă sau anterioară. În mod similar, deoarece registrul are un număr finit de stări posibile, mai devreme sau mai târziu valorile de ieșire se repetă; cu toate acestea, un LFSR cu o funcție de feedback bine aleasă poate produce o secvență de biți care apare aleatoriu și are o perioadă foarte lungă.

Aplicațiile LFSR includ generarea de numere pseudo-aleatorii , secvențe de pseudo-zgomot (aproximarea zgomotului alb ) și contoare digitale. Atât implementările hardware, cât și cele software sunt comune.

Cum functioneazã

Lista pozițiilor de biți care afectează următoarea stare se numește secvența de atingere . În diagrama de mai jos, secvența este [16,14,13,11].

Ieșirile care afectează intrarea se numesc robinete (în albastru în diagrama de mai jos).
Un LFSR maxim produce o secvență n (adică trece prin toate stările posibile ale registrului de deplasare, cu excepția celei care produce toate zerourile), cu excepția cazului în care starea sa inițială este compusă doar din zerouri, caz în care ieșirea rămâne constantă.

Secvența numerelor produse de un LFSR poate fi considerată un sistem de numere binare valabil ca codul Gray sau codul binar natural.

Secvența de atingere a unui LFSR poate fi reprezentată ca un modul polinomial 2. Aceasta înseamnă că coeficienții polinomului trebuie să fie 1 sau 0. Acest lucru este cunoscut sub numele de polinom de feedback sau polinom caracteristic . De exemplu, dacă atingerile sunt la 16, 14, 13 și 11 biți (ca mai jos), polinomul relativ LFSR este

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

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

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

Termenul cunoscut al polinomului („cel”) nu corespunde unei atingeri ; puterile termenilor reprezintă biții de atingere , numărând din stânga.

Dacă (și numai dacă) acest polinom este primitiv , atunci LFSR este maxim
LFSR va fi maxim numai dacă numărul de atingeri este par
Valorile robinetelor într-un LFSR maxim vor fi prime între ele (se spune că două numere sunt prime între ele dacă cel mai mare divizor comun al acestora este 1)
Poate exista mai multe secvențe de atingere care maximizează un LFSR cu lungime fixă
Odată ce a fost găsită o secvență de atingere maximă, o alta poate fi găsită cu o procedură automată: dacă secvența de atingere , într-un LFSR n- bit, este [n, A, B, C], „secvența oglindă” „este [ n, nA, nB, nC] (de exemplu secvența [32,3,2,1] are ca contrapartidă [32,31,30,29]). Ambele produc un LFSR maxim.

Proprietățile secvenței de ieșire

Uni și zerouri sunt urmate în runde (rulări). Secvența de ieșire 0110100, de exemplu, constă din cinci curse de lungime 1,2,1,1,2, respectiv. Într-o perioadă de LFSR maximă, ele apar $2^{n-1}$ ${\ displaystyle 2 ^ {n-1}}$ $2 ^ {n-1}$ rulează (de exemplu, un LFSR pe 6 biți va avea 32 de rulări); exact $1/2$ ${\ displaystyle 1/2}$ $1/2$ dintre aceste rulări va fi un pic, $1/4$ ${\ displaystyle 1/4}$ $1/4$ de 2 biți, până la o singură lovitură de $n-1$ ${\ displaystyle n-1}$ $n-1$ bit la zero și o singură rundă de $n$ ${\ displaystyle n}$ $n$ câte unul. Aceeași proprietate ar fi de așteptat într-o secvență cu adevărat aleatorie.
Secvențele de ieșire LFSR sunt deterministe : dacă cunoașteți starea curentă, puteți prevedea următoarea. Acest lucru nu este posibil în evenimente cu adevărat aleatorii, cum ar fi dezintegrarea radioactivă .

Aplicații

LFSR-urile pot fi implementate în hardware, ceea ce le face utile în aplicații care necesită generarea foarte rapidă de numere pseudo-aleatorii, cum ar fi tehnica radio Direct Sequence Spread Spectrum , utilizată de exemplu în UMTS .

Sistemul de poziționare globală (GPS) folosește LFSR-uri pentru a transmite rapid o secvență care indică instanțe relative cu precizie ridicată, exploatând determinismul lor: de fapt, este suficient să transmită semințele utilizate în transmițător și secvența generată va fi, de asemenea, identică pe receptor.

Posibil înlocuire pentru codurile Grey

Unele aplicații trebuie să marcheze pozițiile individuale la o anumită distanță cu valori unice. De exemplu, mulți metri marchează fiecare centimetru cu un număr unic folosind sistemul metric . Când indicii și pozițiile trebuie să fie ușor de înțeles de o mașină, acestea sunt adesea marcate folosind secvențe LFSR, deoarece contoare LFSR sunt cele mai simple și mai rapide dintre contoare binare, chiar mai mult decât contoare bazate pe cod Gray . Având în vedere o secvență de ieșire, este posibil să se construiască o dimensiune minimă LFSR utilizând algoritmul Berlekamp-Massey .

LFSR din Galois

Un Galois LFSR sau o configurație Galois LFSR este o variantă a schemei clasice LFSR.

În configurația Galois, atunci când sistemul este cronometrat , biții non- robinet sunt traduse ca de obicei; de robinete , pe de altă parte, XOR se face cu noua ieșire, iar rezultatul devine apoi noua intrare.

LFSR-urile Galois nu leagă fiecare robinet pentru a produce noua intrare, prin urmare este posibil să se calculeze robinetele în paralel, crescând astfel viteza de execuție: operația XOR se efectuează în LFSR și nu există XOR în serie, prin urmare propagarea timpii sunt reduși la cei ai unui XOR în loc de cei ai unui lanț al acestuia.

Utilizare în criptografie

LFSR-urile sunt componente utilizate pe scară largă în cifrele de flux ca generatoare de numere pseudo-aleatorii , deoarece pot fi ușor și economic implementate în hardware și pot fi analizate matematic dacă este necesar. Cu toate acestea, utilizarea LFSR-urilor singure este insuficientă pentru a oferi o bună securitate. Au fost propuse numeroase scheme pentru creșterea siguranței LFSR-urilor.

Funcții combinatorii neliniare

Deoarece LFSR-urile sunt inerent liniare, o tehnică pentru eliminarea liniarității este aplicarea unei funcții booleene neliniare la rezultatele mai multor LFSR-uri în paralel și să formeze un generator de combinație . Mai multe proprietăți ale acestor funcții combinatorii sunt esențiale pentru a asigura securitatea schemei rezultate, de exemplu, pentru a evita atacurile bazate pe corelație .

Generatoare controlate de ceas

În mod normal, LFSR-urile iau măsuri regulate. O abordare pentru introducerea neliniarităților este utilizarea unui ceas neregulat pentru LFSR, controlat de ieșirea unui al doilea LFSR. Astfel de generatoare includ generatorul stop-and-go, generatorul alternativ de pas și generatorul de micșorare.

Generatorul stop-and-go (Beth și Piper, 1984) este format din două LFSR. Un LFSR ceasuri dacă a doua ieșire este un "1", în caz contrar, își repetă ieșirea anterioară. Această ieșire este apoi (în unele versiuni) combinată cu ieșirea unui al treilea LFSR cu ceas normal.

Generatorul de micșorare adoptă o abordare diferită. Folosește două LFSR-uri, ambele cu ceasuri obișnuite. Dacă ieșirea primului LFSR este „1”, ieșirea celui de-al doilea LFSR este ieșirea generatorului. Dacă primul LFSR produce un "0", totuși, ieșirea celui de-al doilea este eliminată, iar generatorul nu produce biți. Acest mecanism este vulnerabil la atacurile temporizate asupra celui de-al doilea generator, deoarece viteza de ieșire este variabilă în funcție de starea celui de-al doilea generator. Această problemă poate fi atenuată prin păstrarea unei porțiuni din ieșire într-un buffer .