LFSR – Linear Feedback Shift Register, czyli rejestr przesuwający z liniowym sprzężeniem zwrotnym, jest powszechnie wykorzystywany jako generator liczb pseudolosowych lub też generator szumu. Opiera się on na bramkach xor lub xnor.
W poniższym artykule przedstawię, jak przeprowadzić symulację rejestru w systemie Ubuntu, korzystając z języka vhdl i narzędzia do symulacji GTKWave.
Aby rozpocząć pracę z językiem vhdl, należy najpierw zainstalować odpowiednie paczki:
sudo add-apt-repository ppa:pgavin/ghdl
sudo apt-get update
sudo apt-get install ghdl
Następnie tworzymy 2 pliki, z których jeden będzie służył do symulacji jak poniżej lub – jeżeli nie chcemy tworzyć plików – możemy je pobrać poleceniem:
wget http://szymonwojtowicz.no-ip.org/ftp/lfsr4f.tar.bz2
i rozpakować poleceniem:
tar -xvjf ./lfsr4f.tar.bz2
PLIKI DO SYMULACJI:
entity lfsr is port(ck:in bit; rst : in bit; b: out bit);
end lfsr;
architecture rtl of lfsr is
signal lfsr : bit_vector(3 downto 0) <= "0110";
begin
process(ck,rst)
variable temp : bit := '0';
begin
if rst='1' then
lfsr(3 downto 0) <= "0110";
elsif ck = '1' and ck'event then
temp := lfsr(3);
-- przypisuje wartość tymczasową do rejestru (jeżelibym tego nie zrobił zapisana
-- byłaby w kolejnej linijce kodu wartość nadpisana, czyli bieżąca rejestru)
lfsr <= (lfsr(2) xor lfsr(3)) & lfsr(1) & lfsr(0) & temp;
-- przypisuje strumieniowo do wektora wartości
b <= lfsr(3);
-- wysyła wartość rejestru 3 (może być dowolna) na wyjście układu
end if;
end process;
end rtl;
I drugi plik o nazwie lfsr_tb.vhdl
-- Plik testowy nie posiada zadeklarowanych portów
entity lfsr_tb is
end lfsr_tb;
architecture behav of lfsr_tb is
-- Deklaracja poszczególnych komponentów, które zostaną zainicjalizowane
component lfsr
port (ck : in bit; rst: in bit; b : out bit);
end component;
-- Przypisanie jednostek do składników
for lfsr_0: lfsr use entity work.lfsr;
signal b : bit;
signal ck : bit;
signal rst : bit;
begin
-- Inicjalizacja komponentów
lfsr_0: lfsr port map (ck => ck, rst => rst, b => b);
-- Proces poniżej wykonuje rzeczywistą pracę dla układu w GTKWave
process
begin
for i in 65535 downto 0 loop -- Ilość iteracji pętli
wait for 10 ps; -- Okres czasu, przez jaki zegar ma przyjmować wartość 1
ck <= '1'; -- Przypisanie wartości do ck
wait for 10 ps; -- Okres czasu, przez jaki zegar ma przyjmować wartość 0
ck <= '0'; -- Przypisanie wartości do ck
end loop; -- Zakończenie pętli
wait;
end process;
end behav;
Następnie tworzymy skrypt, który uprości proces kompilacji o nazwie run.sh:
ghdl -a lfsr.vhdl
ghdl -a lfsr_tb.vhdl
ghdl -e lfsr_tb
./lfsr_tb --vcd=out_dump.vcd
gtkwave out_dump.vcd
Po utworzeniu skryptu nadajemy mu odpowiednie uprawnienia do wykonywania w terminalu:
sudo chmod +x ./run.sh
Następnie możemy zobaczyć, jak działa algorytm w programie GTKWave poprzez wydanie polecenia w obecnym folderze ./run.sh:
Aby zobaczyć poniższą symulację należy z listy SST wybrać lfsr_0. Następnie poniżej ukażą nam się sygnały, które należy przenieść do zakładki Signals i rozwinąć (dwukrotnie klikając). Następnie trzeba dostosować długość sygnału do wygodnego rozmiaru okna, używając lupy:
Poniższy schemat przedstawia działanie naszego rejestru: CLK - clock, czyli zegar RST - reset B - sygnał emitowany na wyjściu przy każdym cyklu D0,D1,D2,D3 - poszczególne rejestry zapamiętujące stany (0 lub 1) między taktami zegara
W poniższej tabeli zostały zaprezentowane stany, jakie przyjmują poszczególne rejestry D0,D1,D2,D3 w kolejnych taktach zegarowych. Należy wspomnieć, że stan początkowy 0110 jest stanem umownym. Co za tym idzie, po pierwszym umownym cyklu następuje cykl drugi, a w nim wartość D0 jest brana z cyklu pierwszego, jaki przyjmował rejestr D3, równocześnie wartość D1 przyjmuje wartość jaką miał w pierwszym cyklu rejestr D0, a rejestr D2 przyjmuje wartość D1. Najważniejsza zmiana w całym układzie występuje w rejestrze D3, który pobierając wartości z samego siebie z poprzedniego stanu i z rejestru D2 przesyła ją przez bramkę XOR, dając odpowiednie wartości. W roli przypomnienia dołączyłem wartości, jakie przyjmuje bramka po przyjęciu odpowiednich stanów.
| p | q | p v q |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Bramka XOR to inaczej alternatywa wykluczająca. W skrócie można, przyjmując logikę jej działania, powiedzieć, że jeżeli 2 stany wejściowe są różne, to wyjście jest prawdziwe (przyjmuje stan równy 1). W pierwszym cyklu D3 i D2 kolejno przyjmują stany 0 i 1, a więc na wyjściu będziemy mieli w drugim cyklu wartość prawdziwą (równą 1).
style=”display:inline-block;width:728px;height:90px”
data-ad-client=”ca-pub-3473784311111784″
data-ad-slot=”1536038152″>
| Wartość dzeiesiętna | 8 | 4 | 2 | 1 |
| Cykl / Rejestr Wartość | D3 | D2 | D1 | D0 |
| 1 – 6 | 0 | 1 | 1 | 0 |
| 2 – 12/C | 1 | 1 | 0 | 0 |
| 3 – 1 | 0 | 0 | 0 | 1 |
| 4 – 2 | 0 | 0 | 1 | 0 |
| 5 – 4 | 0 | 1 | 0 | 0 |
| 6 – 8 | 1 | 0 | 0 | 0 |
| 7 – 9 | 1 | 0 | 0 | 1 |
| 8 – 11/B | 1 | 0 | 1 | 1 |
| 9 – 15/F | 1 | 1 | 1 | 1 |
| 11 – 7 | 0 | 1 | 1 | 1 |
| 12 – 14/E | 1 | 1 | 1 | 0 |
| 13 – 5 | 0 | 1 | 0 | 1 |
| 14 – A | 1 | 0 | 1 | 0 |
| 15 – D | 1 | 1 | 0 | 1 |
| 16 – 3 | 0 | 0 | 1 | 1 |
Poniżej został przedstawiony cykl generowania liczb pseudolosowych. Należy zwrócić uwagę, że 16 nie ma stanu 0000, czyli cyfry 0.
I na zakończenie filmik, abyście nie przestraszyli się, że nic się nie generuje: