Lineare il feedback shift register?

Question

Ultimamente ho urtato più volte nel concetto di LFSR, che trovo molto interessante a causa dei suoi legami con diversi campi e anche affascinante in sé. Mi c'è voluto un po 'di sforzo per capire, l'aiuto finale è stato davvero buono pagina , molto meglio della (in un primo momento) criptico wikipedia . Così ho voluto scrivere qualche piccolo codice per un programma che ha funzionato come un LFSR. Per essere più precisi, che in qualche modo ha mostrato come funziona un LFSR. Ecco la cosa più pulita che potrei venire con dopo alcuni tentativi lenghtier (Python):

def lfsr(seed, taps):
    sr, xor = seed, 0
    while 1:
        for t in taps:
            xor += int(sr[t-1])
        if xor%2 == 0.0:
            xor = 0
        else:
            xor = 1
        print xor
        sr, xor = str(xor) + sr[:-1], 0
        print sr
        if sr == seed:
            break

lfsr('11001001', (8,7,6,1))      #example

I chiamato "xor" l'uscita della funzione XOR, non molto corretta. Tuttavia, questo è solo lo scopo di mostrare come si circonda attraverso le sue possibili stati, infatti avete notato il registro è rappresentato da una stringa. Non molto coerenza logica.

Questo può essere facilmente trasformato in un giocattolo bello si può guardare per ore (almeno ho potuto: -)

def lfsr(seed, taps):
    import time
    sr, xor = seed, 0
    while 1:
        for t in taps:
            xor += int(sr[t-1])
        if xor%2 == 0.0:
            xor = 0
        else:
            xor = 1
        print xor
        print
        time.sleep(0.75)
        sr, xor = str(xor) + sr[:-1], 0
        print sr
        print
        time.sleep(0.75)

Poi mi ha colpito, a che serve questo per iscritto software? Ho sentito che può generare numeri casuali; è vero? Come? Quindi, sarebbe bello se qualcuno potesse:

• spiegherà come utilizzare tale dispositivo un nello sviluppo di software
• venire con un certo codice, per sostenere il punto di cui sopra o semplicemente come il mio per mostrare diversi modi per farlo, in qualsiasi lingua

Inoltre, come theres roba non molto didattico intorno su questo pezzo di logica e circuiti digitali, sarebbe bello se questo potrebbe essere un posto per noobies (come me) per ottenere una migliore comprensione di questo cosa , o meglio, per capire che cosa è e come può essere utile durante la scrittura del software. Dovrebbe essere fatto un wiki comunità?

Detto questo, se qualcuno si sente come il golf ... siete i benvenuti.

Answer 1

In realtà, algoritmi basati su LFSR sono molto comuni. CRC è in realtà direttamente basa su LFSR. Naturalmente, in informatica lezioni di scienze persone parlano di polinomi quando stanno parlando di come si suppone che il valore di ingresso da XOR con il valore accumulato, in electornics ingegneria parliamo di rubinetti al posto. Sono la stessa terminologia solo diverso.

CRC32 è molto comune. E 'utilizzato per individuare gli errori in frame Ethernet. Ciò significa che quando ho postato questa risposta il mio PC utilizzato un algoritmo basato LFSR per generare un hash del pacchetto IP in modo che il mio router in grado di verificare che ciò che di trasmissione non sia danneggiato.

CAP e file Gzip sono un altro esempio. Entrambi usano CRC per il rilevamento degli errori. Zip usi CRC32 e Gzip usa sia CRC16 e CRC32.

CRC sono fondamentalmente le funzioni di hash. Ed è abbastanza buono per far funzionare Internet. Il che significa LFSR sono abbastanza buone funzioni hash. Non sono sicuro se lo sai, ma in generale buona funzioni di hash sono considerati buoni generatori di numeri casuali. Ma la cosa con LFSR è che selezionando i rubinetti corretti (polinomi) è molto importante per la qualità del numero di hash / random.

Il tuo codice è in genere il codice giocattolo dal momento che opera su una serie di uno e zero. Nel lavoro LFSR mondo reale sui bit in un byte. Ogni byte si spinge attraverso il LFSR cambia il valore accumulato del registro. Tale valore è effettivamente un checksum di tutti i byte che si spinta'VE attraverso il registro. Due modi comuni di utilizzare tale valore come un numero casuale è utilizzare su un contatore e spingere una sequenza di numeri attraverso il registro, trasformando così la sequenza lineare 1,2,3,4 per qualche sequenza hash come 15306,22,5587, 994, o per alimentare di nuovo il valore corrente nel registro per generare un nuovo numero in sequenza apparentemente casuale.

Si deve notare che facendo questo ingenuamente utilizzando LFSR bit-giocherellando è piuttosto lento poiché è necessario bit processo alla volta. Quindi le persone hanno escogitato modi utilizzando le tabelle pre-calcolate per farlo otto bit alla volta o anche 32 bit alla volta. Questo è il motivo per cui quasi mai vedere il codice LFSR in natura. In più il codice di produzione si maschera come qualcos'altro.

Ma a volte un po 'LFSR-giocherellando pianura può tornare utile. Una volta ho scritto un href="http://en.wikipedia.org/wiki/Modbus" rel="nofollow noreferrer"> Modbus conducente non sto scherzando ). Così ho dovuto usare un LFSR.

Answer 2

Da quando sono alla ricerca di un LFSR-implementazione in Python, sono incappato in questo argomento. Ho trovato, tuttavia, che il seguente è stato un po 'più precisa in base alle mie esigenze:

def lfsr(seed, mask):
    result = seed
    nbits = mask.bit_length()-1
    while True:
        result = (result << 1)
        xor = result >> nbits
        if xor != 0:
            result ^= mask

        yield xor, result

Il sopra LFSR-generatore è basato su GF (2 ^k ) Modulo di calcolo (GF = Galois campo ). Avendo appena completato un Algebra Naturalmente, ho intenzione di spiegare questo il modo matematico.

La partenza di Let da presa, per esempio, GF (2 ⁴ ), che equivale a {a ₄ x ⁴ + un ₃ x ³ + un ₂ x ² + un ₁ x ¹ + un ₀ x ⁰ | un ₀ , a ₁ , ..., un ₄ ? Z ₂ } (per chiarire, Z < sub> n = {0,1, ..., n-1} e quindi Z ₂ = {0,1}, cioè un bit). Ciò significa che questo è l'insieme di tutti i polinomi di quarto grado con tutti i fattori di essere presente o meno, ma non avendo multipli di questi fattori (ad esempio non c'è 2x ^k ). x ³ , x ⁴ + x ³ , 1 e x ⁴ + x ³ + x ² + x + 1 sono tutti esempi di membri di questo gruppo.

Prendiamo questo set modulo un polinomio di quarto grado (cioè, P (x) ? GF (2 ⁴ )), ad esempio P (x) = x ⁴ + x ¹ + x ⁰ . Questa operazione modulo su un gruppo viene anche indicato come GF (2 ⁴ ) / P (x). Per il vostro riferimento, P (x) descrive i 'rubinetti' ai LFSR.

Abbiamo anche prendere un polinomio di grado a caso 3 o inferiore (in modo che non è influenzato dal nostro modulo, altrimenti potremmo altrettanto bene eseguire l'operazione di modulo direttamente su di esso), ad esempio, A ₀ (x) = x ⁰ . Ora ogni successiva A _i (x) è calcolato moltiplicando con x: A _i (x) = A _i-1 (x) * x mod P (x).

Dato che siamo in un campo limitato, l'operazione di modulo può avere un effetto, ma solo quando la risultante A _i (x) presenta almeno un fattore x ⁴ (il nostro fattore più alto in P (x)). Si noti che, poiché stiamo lavorando con numeri in Z ₂ , eseguendo l'operazione di modulo in sé non è altro che determinare se ogni a _i diventa 0 o 1 aggiungendo due valori P (x) e A _i (x) insieme (cioè 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0, o 'XOR' questi due).

Ogni polinomio può essere scritta come un insieme di bit, ad esempio x ⁴ + x ¹ + x ⁰ ~ 10011. L'A ₀ (x) può essere visto come il seme. Il 'volte x' operazione può essere vista come uno spostamento funzionamento rimanente. L'operazione di modulo può essere vista come un'operazione di mascheramento di bit, con la maschera essendo il nostro P (x).

L'algoritmo descritto sopra quindi genera (un flusso infinito di) validi quattro modelli bit LFSR. Ad esempio, per il nostro definito A ₀ (x) (x ⁰ ) e P (x) (x ⁴ + x ¹ + x ⁰ ) , possiamo definire i seguenti risultati primo apportati in GF (2 ⁴ ) (nota che a ₀ non è ceduto fino alla fine del primo round - matematici genere inizia il conteggio a '1'):

 i   Ai(x)                   'x⁴'  bit pattern
 0   0x³ + 0x² + 0x¹ + 1x⁰   0     0001        (not yielded)
 1   0x³ + 0x² + 1x¹ + 0x⁰   0     0010
 2   0x³ + 1x² + 0x¹ + 0x⁰   0     0100
 3   1x³ + 0x² + 0x¹ + 0x⁰   0     1000
 4   0x³ + 0x² + 1x¹ + 1x⁰   1     0011        (first time we 'overflow')
 5   0x³ + 1x² + 1x¹ + 0x⁰   0     0110
 6   1x³ + 1x² + 0x¹ + 0x⁰   0     1100
 7   1x³ + 0x² + 1x¹ + 1x⁰   1     1011
 8   0x³ + 1x² + 0x¹ + 1x⁰   1     0101
 9   1x³ + 0x² + 1x¹ + 0x⁰   0     1010
10   0x³ + 1x² + 1x¹ + 1x⁰   1     0111
11   1x³ + 1x² + 1x¹ + 0x⁰   0     1110
12   1x³ + 1x² + 1x¹ + 1x⁰   1     1111
13   1x³ + 1x² + 0x¹ + 1x⁰   1     1101
14   1x³ + 0x² + 0x¹ + 1x⁰   1     1001
15   0x³ + 0x² + 0x¹ + 1x⁰   1     0001        (same as i=0)

Si noti che la maschera deve contenere un '1' alla quarta posizione per assicurarsi che il vostro LFSR genera risultati di quattro bit. Si noti inoltre che un '1' deve essere presente nella posizione zeroth per assicurarsi che il vostro flusso di bit non sarebbe finire con un po 'modello 0000, o che il bit finale sarebbe diventato inutilizzato (se tutti i bit vengono spostati a sinistra, si sarebbe anche finire con uno zero nella posizione 0th dopo un turno).

Non tutti P (x) 's necessariamente sono generatori di GF (2 ^k ) (cioè, non tutte le maschere di k bit generare tutti 2 ^k-1 - 1 numeri). Ad esempio, x ⁴ + x ³ + x ² + x ¹ + x ⁰ genera 3 gruppi di 5 polinomi distinti ciascuno, o "3 cicli di periodo di 5": 0001,0010,0100,1000,1111; 0011,0110,1100,0111,1110; e 0101,1010,1011,1001,1101. Si noti che 0000 non può mai essere generato, e non in grado di generare qualsiasi altro numero.

Normalmente, l'uscita di un LFSR è il bit che è 'spostato', il che è un '1' se viene eseguita l'operazione di modulo, e un '0' quando non lo è. LFSR di un periodo di 2 ^k-1 -1, chiamato anche pseudo-rumore o di PN-LFSR, aderire alla postulati casualità di Golomb, che dice quanto che questo bit di uscita è casuale 'sufficiente'.

Le sequenze di questi bit hanno quindi il loro utilizzo nella crittografia, per esempio nel A5 / 1 e A5 / 2 standard di cifratura mobili, o lo standard E0 Bluetooth. Tuttavia, essi non sono così sicuro come si vorrebbe: il Berlekamp-Massey algoritmo può essere utilizzato per decodificare il polynomal caratteristica (P (x)) del LFSR. s standard di crittografia forte quindi usa non lineare FSR 'o funzioni non lineari simili. Un argomento correlato a questo sono il S-Boxes utilizzata in AES.

---

Si noti che ho usato il int.bit_length() operazione . Questo non è stato attuato fino Python 2.7.
Se desideri solo come uno schema di bit finita, si potrebbe verificare se il seme è uguale al risultato e quindi rompere il ciclo.
È possibile utilizzare il mio LFSR-metodo in un ciclo for (ad esempio for xor, pattern in lfsr(0b001,0b10011)) oppure è possibile chiamare più volte l'operazione .next() sul risultato del metodo, restituendo una nuova (xor, result) coppia ogni volta.

Answer 3

Ci sono molte applicazioni di LFSR. Uno di loro sta generando rumore, ad esempio la SN76489 e varianti (utilizzato sul sistema master, Game Gear, MegaDrive, NeoGeo Pocket, ...) utilizzare un LFSR per generare rumore bianco / periodica. C'è davvero una buona descrizione di di SN76489 LFSR in questa pagina .

Answer 4

per renderlo davvero elegante e Pythonic, cercare di creare un generatore, yield-ing valori successivi dal LFSR. Inoltre, il confronto ad un punto 0.0 flottante è inutile e confusione.

Un LFSR è solo uno dei tanti modi per creare numeri pseudo-casuali nel computer. Pseudo-casuale, perché ci numeri non sono davvero a caso - si può facilmente ripetere partendo con il seme (valore iniziale) e di procedere con le stesse operazioni matematiche.

Answer 5

Di seguito è una variazione sul vostro codice usando numeri interi e operatori binari, invece di stringhe. Esso utilizza anche il rendimento come qualcuno ha suggerito.

def lfsr2(seed, taps):
    sr = seed
    nbits = 8
    while 1:
        xor = 1
        for t in taps:
            if (sr & (1<<(t-1))) != 0:
                xor ^= 1
        sr = (xor << nbits-1) + (sr >> 1)
        yield xor, sr
        if sr == seed:
            break

nbits = 8
for xor, sr in lfsr2(0b11001001, (8,7,6,1)):
    print xor, bin(2**nbits+sr)[3:]

Answer 6

Se assumiamo che seme è una lista di interi piuttosto che una stringa (o convertirlo se non lo è) allora il seguente dovrebbe fare quello che vuoi con un po 'più elegante:

def lfsr(seed, taps) :
  while True:
    nxt = sum([ seed[x] for x in taps]) % 2
    yield nxt
    seed = ([nxt] + seed)[:max(taps)+1]

Esempio:

for x in lfsr([1,0,1,1,1,0,1,0,0],[1,5,6]) :
  print x

Answer 7

list_init=[1,0,1,1]
list_coeff=[1,1,0,0]
out=[]
for i in range(15):
    list_init.append(sum([list_init[i]*list_coeff[i] for i in range(len(list_init))])%2)
    out.append(list_init.pop(0))
print(out)

#https://www.rocq.inria.fr/secret/Anne.Canteaut/encyclopedia.pdf