Registre de desplaçament

Registre a decalatge SISO o SIPO

En electrònica i en informàtica, un registre a decalatge és un registre de mida fixa en el qual els bits es desplaçen a cada cop de rellotge (en el cas d'un sistema síncron sobre el rellotge).

Un registre a decalatge en general està constituït d'una cadena de biestables sincronitzada en base al rellotge, la sortida de cada biestable està connectada a l'entrada de la següent. Es desenvolupa en diverses variants:

• SIPO (Serial In - Parallel Out )
• SISO (Serial In - Serial Out)
• PISO (Parallel In - Serial Out)
• PIPO (Parallel In - Parallel Out)

Les entrades o sortides en paral·lel permeten inserir i recuperar diversos bits al mateix temps.

Prenenet d'exemple d'una informació de 4 bits (ex.: 1001).

• Paral·lel es refereix a 4 fils que retornen cadascun un bit. Per tant, el primer fil retorna "1" al mateix temps que el segon retorna "0" així de successivament.

• Sèrie es refereix a 1 fil que tramet "1" seguit de "0" i de "0" i finalment d'"1". El sistema sèrie empra per tant menys fils però més temps.

També hi ha registres a decalatge reversibles, registres on la diferència s'efectua cap a la dreta o cap a l'esquerra en funció del nivell lògic aplicat a l'entrada "Sentit de diferència".

Exemples d'aplicacions

• SISO : La informació que es vol introduir en el registre és presentada a l'entrada del primer biestable. En el moment d'un impuls de rellotge, el bit d'informació s'introdueixt al registre, i tots els altres bits es desplaçen. El bit que era memoritzat a l'última biestable es pert si no s'emmagatzema o no és reinsereix en l'estructura d'una manera qualsevol. Els registres SISO s'utilitzen per realitzar les línies amb retard numèric. El termini entre l'entrada de la informació al registre i la seva sortida depèn del nombre de biestables i de la freqüència del rellotge.

• PIPO : Desplaçant tots els bits d'un nombre binari cap a la dreta o cap a l'esquerra, es divideix o es multiplica el nombre per 2. Per tant, un registre PIPO es pot fer servir per efectuar càlculs (multiplicació o divisió per una potència de 2). N'hi ha prou amb efectuar el nombre adequat de decalatges cap a l'esquerra o la dreta entre el moment en què s'introdueixen els bits en el registre i el moment en què se'ls recupera.

• PISO i SIPO : Aquests dos tipus de registres es fanservir els enllaços sèrie ; són la base dels UART i dels mòdems. Suposant que es vol transmetre una informació entre dos ordinadors distants alguns metres o desenes de metres. Transmetre la informació en "paral·lel" necessitaria almenys 9 fils (8 per als 8 bits, un per a la massa), sense comptar els fils suplementaris per al protocol de comunicacions entre els ordinadors. És més senzill fer servir un registre PISO per transformar els bits que constitueixen cada octet que es vol transmetre en una successió de 8 bits que apareixen l'un després de l'altre en una sola línia de comunicació. Al final de la línia, un registre SIPO rep els bits que arriben a la cua un a un i reconstitueix els octets que es transmeten a l'ordinador de destinació.

• Registres SISO reversibles: Permeten per exemple realitzar el que s'anomena de les piles LIFO (Last In, First Out): es carreguen els bits al registre; després s'inverteix el sentit del dicalatge. Els bits apareixen a la sortida del primer biestable en ordre invers de la seva entrada.

Registre a decalatge amb retroacció lineal

Article principal: Linear feedback shift register

Es tracta d'una variant amb una unitat lògica o aritmètica (Linear Feedback Shift Register o LFSR en anglès). El o els bit(s) al sortir del registre experimenten una sèrie d'operacions i de transformacions per ser reinserits en el registre. Aquest tipus de registre es fa servir en criptografia per a les implementacions en hardware de certs algorismes de xifratge de flux. Es troben també a certs microprocessadors dedicats al tractament del senyal (DSP), en particular per al filtrat.

Aquest tipus de circuit també es fa servir en el moment de la fase de test dels circuits integrats i permeten la generació automàtica d'entrades (vectors de tests).

Retroacció basada en un XOR entre diversos bits

Descripció matemàtica

Representació per successions

Les successions de bits podent ser produïdes per un registre a decalatge a retroacció lineal són senzills a descriure matemàticament: són les successions recurrents lineals. En altres paraules, es pot obtenir el terme $t+n~$ a partir dels termes $t,...,t+n-1~$ per una equació lineal del tipus

$u_{t+n}=\alpha _{n}u_{t}+\alpha _{n-1}u_{t+1}+...+\alpha _{1}u_{t+n-1}~$

on els $\alpha _{i}~$ valen $0$ o $1$.

Representació polinòmica

També és possible descriure'ls utilitzant les sèries formals: si a una successió $U=(u_{i})~$ s'associa la seria $U(X)=\sum _{i=0}^{\infty }u_{i}X^{i}~$ llavors l'equació de damunt es pot posar sota la forma següent:

$U(X)P(X)=T(X)~$

on

• $T(X)=\sum _{i=0}^{n-1}u_{i}X^{i}$
• $P(X)=1+\alpha _{1}X+.+\alpha _{n}X^{n}~$

El polinomi $T~$ correspon a la inicialització del registre, al'hora que el polinomi $P$, anomenat polinomi de retroacció, caracteritza el registre.

Periodicitat

És fàcil veure que una successió produïda per tal registre és necessàriament periòdica: el nombre de possibilitats per a un $n$-pla és com a màxim $2^{n}$, per tant $f:t\mapsto (u_{t},...,u_{t+n-1})$ és exhaustiva, sigui $\exists t_{0},t_{1},f(t_{0})=f(t_{1})$. Però, clarament es té $\forall x,y$ i $i$, $f(x)=f(y)\Rightarrow f(x+i)=f(y+i)$. Prenent $i=\max(t_{0}-t_{1},t_{1}-t_{0})$ es té per tant un múltiple del període de la successió.

El període màxim és $2^{n}-1$ ja que si la $n$-pla arriba a ser tot zeros, la successió és necessàriament constant igual a zero. Es pot preveure quan s'assoleix aquest valor, una condició necessària i suficient és que el polinomi de retroacció sigui primitiu -- és a dir que sigui irreductible i tal com, a l'anell $F_{2}[X]$ dels polinomis amb coeficients binaris, el més petit t tal com aquest polinomi divideix $X^{t}-1$ és $2^{n}-1$ (és el polinomi mínim d'un element d'ordre multiplicatiu $2^{n}-1$ al cos amb $2^{n}$ elements).

Una successió de període màxim s'anomenam-seqüència en la terminologia anglosaxona.

Noció de complexitat lineal

Tota $m$-pla de bits pot ser generada per un LFSR. Més precisament existeix sempre un LFSR -- i.e. un polinomi de retroacció així com una inicialització -- tal que les $m$ primeres sortides d'aquest LFSR corresponen a la $m$-pla. En el pitjor dels casos es pren un registre de longitud $m$, el polinomi de retroacció importa poc en aquestes condicions.

Això dóna lloc a la definició de la complexitat lineal d'una successió (finita) com la longitud mínima d'un LFSR que genera aquesta successió. Com ho prova l'observació de damunt aquesta complexitat està limitada superiorment per la longitud de la successió.

Aquesta noció intervé sobretot en criptografia a causa de l'existència del algorisme de Berlekamp-Massey.

Registre en diferència i criptografia

Generació de nombres pseudoaleatoris

Un problema fonamental en criptografia és la producció de successions de bits «tan aleatoris com sigui possible». Un exemple evident és la generació de les claus de xifratge (simètric o asimètric).

Aquest problema es descompon de fet en dues parts: d'una part la generació de bits per procediments físics -- mesura de temps entre impressions de tecles sobre un teclat, desplaçament del ratolí. ..., i d'altra banda l'expansió d'una successió aleatòria de bits curta en una successió molt més gran. En aquest últim cas, es parla de successió pseudoaleatora.

El xifratge de Vernam il·lustre bé el tema. En aquest xifratge, el text avaluat es produeix per addició bit a bit (modulo 2) de la clau de xifratge. El desxiframent s'efectua també per addició bit a bit de la clau. El problema és que llavors cal compartir una dada secreta, és a dir la clau, de la mateixa mida que el missatge a intercanviar. Molt sovint és impracticable. Llavors apareix la idea d'e generar la clau a partir d'un procediment determinista -- cal poder-ho fer igual al xifratge i al desxiframent -- fent servir una dada secreta més petita. És probablement en part l'origen del xifratge per flux.

Una primera possibilitat consisteix a escollir un LFSR i a utilitzar la dada secreta compartida com a inicialització del registre. Tanmateix, l'algorisme de Berlekamp-Massey aviat posa fi a aquesta temptativa: un coneixement encara que molt parcial de la successió produïda permet trobar totes les informacions desitjades.

Per tant, en la pràctica, els LFSRs no es fan servir de manera aïllada, sinó essencialment sota la forma de registres combinats o filtrats.

Algorisme de Berlekamp-Massey

Un LFSR de mida $n$ produeix successions recurrents lineals d'ordre $n$, el coneixement de $n$ termes consecutius d'una successió i de l'equació lineal -- o bé el que és equivalent del polinomi de retroacció -- determina tota la successió.

Si se suposa desconegut el polinomi de retroacció, es pot deduir de l'observació d'una part de la sortida del LFSR? per exemple els termes $u_{t_{0}},u_{t_{0}+1},.,u_{t_{0}+L-1}$? L'algoritme de Berlekamp-Massey respon a aquesta pregunta de la manera següent: si $L$ és superior o igual a dues vegades la mida del més petit LFSR que genera la successió $(u_{i})$

llavors es poden trobar el polinomi de retroacció i la inicialització del registre. Abreviant: tot. Així, apareix la complexitat lineal com el paràmetre que permet considerar la quantitat d'informació necessària per recrear una successió en forma de LFSR.

L'algorisme de Berlekamp-Massey va ser introduït el 1969 per James Massey (Massey, J l "Shift-Register Synthesis and BCH Decoding." IEEE Trans. Informació Th. 15, 122-127, 1969.). És una adaptació d'un algorisme, de Elwyn Berlekamp, de descodificació de codis correctors -- els codis de Bose-Chaudhuri-Hocquenghem.

Utilització

• Xifratge per flux

• Divisió entre una potència de dos (diferència cap a l'esquerra o la dreta)

• Buffers per a la recepció de dades (FIFO: first in - first out )

• Comptador, temporitzador

Enllaços externs

• (francès) Registres a retroacció lineal

• (francès) Shift generator