LFSR->Płytka rozwojowa

Zimol · Czerwiec 14, 2022

LFSR

czyli

Linear Feedback Shift Register

1.TEORIA

LFSR, czyli rejestr przesuwający z liniowym sprzężeniem zwrotnym. Jest najprostszym generatorem bitów pseudolosowych.

Najzwyklejszy LFSR jest zbudowany z rejestru przesuwającego (zazwyczaj SIPO) o długości m, jednej lub kilku bramek XOR (lub XNOR) podłączonych do równoległych wyjść rejestru w odpowiedni sposób. Taktowany zazwyczaj zegarem o stałej częstotliwości f₀ . Wyjściem sekwencji pseudolosowych bitów najczęściej identyfikujemy ostatni człon rejestru (m).

Do generacji bitów układ potrzebuje ziarna (seed). W rejestrze 4 bitowym jest !15! możliwości. Pomija się tutaj ziarno złożone z samych zer. W takim przypadku układ się "zatrzaśnie", bramka XOR wyrzucać będzie zawsze stan niski.

Maximum Length Sequence

Gdy odpowiednio podłączymy wejścia bramek do rejestru osiągniemy tzw. "ciąg maksymalnie długi", inaczej nazywany także m-sekwencja, N-sekwencja albo MLS (Maximum Length Sequence).

Jeśli wielomian charakterystyczny rejestru liniowego ze sprzężeniem zwrotnym jest nierozkładalny, to ciąg bitów nazywamy maksymalnie długim.

Ilość stanów w takim przypadku wynosi:

K = 2^m - 1

m -> długość rejestru

I tak dla rejestru 16 bitowego, w momencie uzyskania MLS posiadamy 2¹⁶-1 stanów, czyli K = 65 535.

Ilość takich wielomianów można obliczyć stosując wzór:

ϕ(2^m-1)/m

m -> długość rejestru

ϕ -> funkcja Eulera (tocjent)

Dla rejestru 5 bitowego mamy 6 wielomianów.

ϕ(2⁵-1)/5=ϕ(31)/5=30/5=6

A są to:

X⁵+X⁴+X³+X²+1
X⁵+X⁴+X³+X¹+1
X⁵+X³+X²+X¹+1
X⁵+X⁴+X²+X¹+1
X⁵+X²+1
X⁵+X³+1

Symulacja potwierdza, że są to wielomiany MLS:

Jak działa LFSR z MLS a jak bez?

GIF przedstawia symulację dwóch oddzielnych LFSR, o dwóch różnych wielomianach, jeden wielomian jest nierozkładalny, drugi zwykły. Ziarno takie samo (1111) oraz taktowanie wspólne.

Właściwości MLS:

1. W każdym pełnym cyklu (K) liczba jedynek jest większa od liczby zer o 1. Dodatkowa jedynka wynika z wyłączenia stanu 0. Oznacza to, że orzeł i reszka są równie prawdopodobne. Dla przykładu rejestr 5-bitowy z MLS zawsze wygeneruje 16 jedynek i 15 zer. (Obrazki pewnie małe, może kliknięcie coś da )

2. W jednym pełnym cyklu 1/2 sekwencji jedynek i zer mają długość jeden;

1/4 sekwencji jedynek i zer mają długość dwa.

1/8 mają długość trzy.

1/16 długość cztery oraz (tylko jedynki) -> pięć.

Zastosowanie:

-Do generowania pseudoszumu

-Do szyfrowania strumieniowego, jednakże bardzo prosto jest złamać taki szyfr

-Do tworzenia odpowiednich zwartych dzielników modulo m

-Do testowania łączy szeregowych (BER)

-W systemach telefonii komórkowej (CDMA)

-W transmisji telewizji cyfrowej

-W systemach radarowych

Koniec teorii, teraz praktyka

2. PRAKTYKA

Zamysł był prosty: Zrobić prostą płytkę z 4 rejestrami, 4 bramkami i kilkoma dodatkowymi elementami. Montaż mieszany, trochę THT, trochę SMD.

Na płytce znajduje się 4 rejestry uniwersalne 74194, 4 bramki XOR 7486, Tact-switche, przyciski samoblokujące, kilka rezystorów THT/SMD, dużo gold-pinów i diody LED sygnalizujące stany na poszczególnych rejestrach.

Oto schemat:

Oraz płytka PCB:

Kilka zdjęć oraz filmik z działania 16 bitowego LFSR (jakość średnia):

Edytowano Czerwiec 15, 2022 przez Zimol
literówki

Gieneq · Czerwiec 15, 2022

@Zimol ciekawy projekt

16 godzin temu, Zimol napisał:

Do generacji bitów układ potrzebuje ziarna (seed).

Widzę że seed masz na przyciskach. Myślałeś może jak wygląda seedowanie generatora wartością losową? Pierwsze co przyszło mi do głowy to zasilanie rejestru z przerzutników z nieużytym asynchronicznym resetem, ale w nich ta losowość jest często dość deterministyczna.

Zimol · Czerwiec 15, 2022

Przed chwilą, Gieneq napisał:

@Zimol ciekawy projekt

Widzę że seed masz na przyciskach. Myślałeś może jak wygląda seedowanie generatora wartością losową? Pierwsze co przyszło mi do głowy to zasilanie rejestru z przerzutników z nieużytym asynchronicznym resetem, ale w nich ta losowość jest często dość deterministyczna.

Może jakieś wyłapywanie zakłóceń np przez układy CMOS? (ten zegar 1.0, niepodłączone wejścia).

W Sztuce Elektroniki zaproponowali generator wykorzystujący "szum napięcia w wyniku przebicia lawinowego złącza półprzewodnikowego"

Gieneq · Czerwiec 15, 2022

@Zimol no tak, dobry pomysł.

Przypomniało mi się, że kiedyś podłączyłem w złej kolejności wyjścia rejestru do XORów. Przy szybkim przełączaniu wyglądało jak sygnał losowy i zacząłem szukać problemu w zakłóceniach.

FlyingDutch · Czerwiec 15, 2022

2 godziny temu, Zimol napisał:

Może jakieś wyłapywanie zakłóceń np przez układy CMOS? (ten zegar 1.0, niepodłączone wejścia).

W Sztuce Elektroniki zaproponowali generator wykorzystujący "szum napięcia w wyniku przebicia lawinowego złącza półprzewodnikowego"

Cześć,

tak w zamierzchłych czasach elektroniki analogowej diody zenera były wykorzystywane jako źródło szumu.

Pozdrawiam