PROJEKT LFSR  (Linear Feedback Shift Register)

Zasnujte, izdelajte in uporabite program, ki bo v svojem teku ponazarjal delovanje pomikalnega registra z EXOR decizijo v povratni vezavi. Tako vezavo se uporablja pri cikličnem redundančnem kodiranju (CRC) ob prenosu digitalnih signalov, da jih zaščitimo pred napakami, ki se pojavljajo na prenosni poti. Enaka vezja uporabljamo tudi pri premešavanju digitalnih podatkov (scrambling), da jim spremenimo spektralne lastnosti. Tretji način uporabe je prisoten pri informacijskem ščitenju podatkov, ki jih prenašamo v digitalni obliki, lahko bi rekli pri šifriranju podatkov. Vezje, je prikazano na spodnji skici. 

Vezje vsebuje:

-- deset pomnilnih celic vezanih v zaporedje, ki predstavljajo 
   pomikalni register
-- decizijsko vezje, ki stanja posebej izbranih celic preračuna v 
   vrednost za ponovni vpis v pomikalni register 
-- To vrednost se preračuna z EXOR logičnimi operatorji. Prikazujemo 
   jo kot spremenljivko vhod
-- Spremenljivka vhod je uporabljena za oblikovanje izhodne sekvence.  
   Element izhodne sekvence imenujemo izhod, ta zapušča vezje in je  
   nekakšen linijski signal, torej je ta pretvorba linijski kodirnik.

Tako vezje je v literaturi večkrat označeno kot PNG. Pomeni generator naključnih vrednosti (pseudo noise generation). Druga oznaka, ki je obarvana bolj matematično, pa je LFSR (linear feedback shift register). V naš izračun bomo vnesli deset-bitni generator. Glede na kombinacijo celic, ki vplivajo na vsebino spremenljivke vhod, tej kombinaciji rečemo polinom, dobimo ponavljajočo sekvenco ki ima lahko največjo dolžino 
2^n -1 bitov. Pri tem pomeni n dolžino pomikalnega registra. Izbor uporabljenih polinomov, bo generiral omenjeno torej maksimalno dolžino to je 1023 bitov. To sekvenco boste s programom skicirali, jo izvrgli na papir (okoli 20 oziroma 10 listov) in jo statistično obdelali.                       
                  
Predhodno našteti elementi bodo v programu nekakšni objekti, dodani pa bosta še dve ali štiri procedure in sicer začetno polnjenje pomikalnega registra, pomikanje podatkov vzdolž pomikalnega registra ter pretvorba vsebine registra v vhodno obliko in ta bo pretvorjena v izhodno obliko, kar bo skrito v spremenljivki izhod.

 ________
|        |<_________________________________________________ 
|        |<____________________________________________     |
| vhodna |<_______________________                     |    |  
|decizija|<_____________          |                    |    |
|        |<________     |         |                    |    |
|        |<___     |    |16-bitni | pomikalni register |    |
|________|  __|____|____|__:____:_|__:____:____:_______|____|_  
       |    | H0 | H1 | H2 |                         | H8 | H9 |
       |--->|    |    |    |                         |    |    |
       |vhod|____|____|____|_________________________|____|____|
       |     __________
       |     |         |  izhodno zaporedje
       |---->| izhod   |--------------->
             |_________|

Elementi:

-- deset celic pomikalnega registra označenih s H0 do H9                   
-- decizija izražena z logičnim izrazom                      
-- spremenljivka vhod kot izid decizijskega izraza
-- spremenljivka izhod kot izid preoblikovanja spremenljivke vhod
-- procedura postavi, ki napolni register z začetnimi podatki
-- procedura pomakni, ki pomakne vsebino registra za eno celico v smeri  
   večanja celičnega oštevilčenja

Program bomo sestavili po korakih.
Najprej deklariramo konstanto z, s katero napolnimo pomikalni register. Ko konstanta zavzame vrednost 0, bo register napolnjen s samimi ničlami. To stanje registra ga zadržuje v njem in ne more generirati LFSR sekvence. Konstanta z vrednostjo 1 napolni register z neko binarno kombinacijo, ki je različna od predhodno omenjene. Taka povzroči tek psevdonaključne sekvence.

#1:   z ≔ 1

Register napolnimo s kombinacijo 0000000000, če je z = 0 in s kombinacijo  1111001010, če je z = 1. funkcijo postavi(z) z argumentom z tvorimo s programskim blokom Prog. Blok izvaja izraze v zapisanem zaporedju. Zadnji izraz vrne. Pri nas bo vrnjeni izraz imel obliko H0:= z ali H0:= 0 ali H0:= 1, glede na vnešeni argument

      postavi(z) ≔
        Prog      
          H9 ≔ z  
          H8 ≔ z  
          H7 ≔ z  
          H6 ≔ z  
#2:       H5 ≔ 0  
          H4 ≔ 0  
          H3 ≔ z  
          H2 ≔ 0  
          H1 ≔ z  
          H0 ≔ z  

Ker je argument že bil postavljen (#1) uporabimo izraz 

#3:   postavi()

#4:                                 H0 ≔ 1

Preverimo  recimo samo deseti bit H9 pomikalnega registra. Postavil se je na predvideno vrednost 1

#5:   H9

#6:                                    1

Naslednja funkcija , ki jo bomo tvorili, bo pomaknila vsebino v pomikalnem registru za celico naprej. Iz H8 v H9, iz H7 v H8 in tako naprej do H0 v H1.Pred pričetkom pomikanja je potrebno na podlagi vsebin v celicah, ki jih določa polinomska funkcija, izračunati vhodno spremenljivko, ki se jo zapiše v celico H0. Izračunano vrednost predstavlja spremenljivka vhod. Dobimo jo z vrednostima H9 ,H8 ter H6, ki jih povežemo z operatorjem xor. Funkcija je oblikovana kot blok. Na začetku tvorimo spremelnjivko vhod, nato sledi pomik za eno celico, in sicer pri vseh devetih celicah, le deseta (H0) sprejme novo vrednost, ki jo vsebuje vhod. Zadnji izraz bloka Prog bo vrnjena vrednost. Vrnjeno vrednost pripravimo. Poimenujemo jo izhod. Njena oblika je sestava dveh točk. Ti dve točki bomo kasneje povezano narisali. S tem bomo dobili grafično podobo LFSR sekvence. Prva točka vsebuje koordinato časa t in velikost trenutne amplitude LFSR signala. Druga točka predstavlja isto amplitudo v kasnejšem času t+1. Programski blok je sklenjen z izrazom izhod, ki ga funkcija vrne. 

      pomakni(t, vhod, izhod) ≔         
        Prog                            
          vhod ≔ H9 ⊻ H8 ⊻ H6           
          H9 ≔ H8                       
          H8 ≔ H7                       
          H7 ≔ H6                       
          H6 ≔ H5                       
#7:       H5 ≔ H4                       
          H4 ≔ H3                       
          H3 ≔ H2                       
          H2 ≔ H1                       
          H1 ≔ H0                       
          H0 ≔ vhod                     
          izhod ≔ [t, vhod; t + 1, vhod]
          izhod                         

Argumenta vhod in izhod sta potrebna le zato, ker znotraj bloka ta izraza uporabimo, Pri uporabi funkcije pa izrabljamo le časovni parameter t.

#8:   pomakni(t)

Vrnjeni izid je matrika, ki v sebi skriva dve točki. Za matriko iz zgleda vstavimo čas t = 3 

                                 ⎡   t    0 ⎤
#9:                              ⎢          ⎥
                                 ⎣ t + 1  0 ⎦

#10:  t ≔ 3

#11:                                 t ≔ 3

                                   ⎡ 3  0 ⎤
#12:                               ⎢      ⎥
                                   ⎣ 4  0 ⎦

in jo skicirajmo s povezanima točkama.

Vzemimo še en izid in ga skicirajmo.

Funkcijo vklopimo v zaporedno preračunavanje, v katerem povečujemo čas t. Izid bo zaporedje izrazov, matrik. Izris bo kazal časovni potek psevdonaključne sekvence. Uporabimo funkcijo vector in tvorimo niz pomikov, pri katerih teče čas od t = 1 do t = 50.

#13:  VECTOR(pomakni(t), t, 1, 50)

      ⎡⎡ 1  1 ⎤  ⎡ 2  0 ⎤  ⎡ 3  0 ⎤  ⎡ 4  1 ⎤  ⎡ 5  1 ⎤  ⎡ 6  1 ⎤  ⎡ 7  
#14:  ⎢⎢      ⎥, ⎢      ⎥, ⎢      ⎥, ⎢      ⎥, ⎢      ⎥, ⎢      ⎥, ⎢    
      ⎣⎣ 2  1 ⎦  ⎣ 3  0 ⎦  ⎣ 4  0 ⎦  ⎣ 5  1 ⎦  ⎣ 6  1 ⎦  ⎣ 7  1 ⎦  ⎣ 8  

        1 ⎤  ⎡ 8  1 ⎤  ⎡  9  0 ⎤  ⎡ 10  0 ⎤  ⎡ 11  0 ⎤  ⎡ 12  1 ⎤  ⎡ 13  
          ⎥, ⎢      ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢     
        1 ⎦  ⎣ 9  1 ⎦  ⎣ 10  0 ⎦  ⎣ 11  0 ⎦  ⎣ 12  0 ⎦  ⎣ 13  1 ⎦  ⎣ 14  

        1 ⎤  ⎡ 14  0 ⎤  ⎡ 15  0 ⎤  ⎡ 16  1 ⎤  ⎡ 17  1 ⎤  ⎡ 18  1 ⎤  ⎡ 19 
          ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢    
        1 ⎦  ⎣ 15  0 ⎦  ⎣ 16  0 ⎦  ⎣ 17  1 ⎦  ⎣ 18  1 ⎦  ⎣ 19  1 ⎦  ⎣ 20 

         1 ⎤  ⎡ 20  1 ⎤  ⎡ 21  0 ⎤  ⎡ 22  1 ⎤  ⎡ 23  0 ⎤  ⎡ 24  1 ⎤  ⎡ 
           ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢ 
         1 ⎦  ⎣ 21  1 ⎦  ⎣ 22  0 ⎦  ⎣ 23  1 ⎦  ⎣ 24  0 ⎦  ⎣ 25  1 ⎦  ⎣ 

        25  1 ⎤  ⎡ 26  0 ⎤  ⎡ 27  0 ⎤  ⎡ 28  1 ⎤  ⎡ 29  0 ⎤  ⎡ 30  1 ⎤  
              ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, 
        26  1 ⎦  ⎣ 27  0 ⎦  ⎣ 28  0 ⎦  ⎣ 29  1 ⎦  ⎣ 30  0 ⎦  ⎣ 31  1 ⎦  

        ⎡ 31  1 ⎤  ⎡ 32  0 ⎤  ⎡ 33  0 ⎤  ⎡ 34  1 ⎤  ⎡ 35  0 ⎤  ⎡ 36  0 
        ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       
        ⎣ 32  1 ⎦  ⎣ 33  0 ⎦  ⎣ 34  0 ⎦  ⎣ 35  1 ⎦  ⎣ 36  0 ⎦  ⎣ 37  0 

        ⎤  ⎡ 37  1 ⎤  ⎡ 38  0 ⎤  ⎡ 39  0 ⎤  ⎡ 40  1 ⎤  ⎡ 41  0 ⎤  ⎡ 42  
        ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢     
        ⎦  ⎣ 38  1 ⎦  ⎣ 39  0 ⎦  ⎣ 40  0 ⎦  ⎣ 41  1 ⎦  ⎣ 42  0 ⎦  ⎣ 43  

        0 ⎤  ⎡ 43  0 ⎤  ⎡ 44  0 ⎤  ⎡ 45  0 ⎤  ⎡ 46  0 ⎤  ⎡ 47  0 ⎤  ⎡ 48 
          ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢       ⎥, ⎢    
        0 ⎦  ⎣ 44  0 ⎦  ⎣ 45  0 ⎦  ⎣ 46  0 ⎦  ⎣ 47  0 ⎦  ⎣ 48  0 ⎦  ⎣ 49 

         0 ⎤  ⎡ 49  0 ⎤  ⎡ 50  1 ⎤⎤
           ⎥, ⎢       ⎥, ⎢       ⎥⎥
         0 ⎦  ⎣ 50  0 ⎦  ⎣ 51  1 ⎦⎦

Vtrta skica te 50 elementov dolge sekvence je

Na tak način, kot je prikazano v uvodnem delu, boste konstruirali vašo LFSR sekvenco, ki se v svoji celotni dolžini razteza skozi 1023 bitov. Uporabili boste dodeljen polinom, ki je podan v preglednici POLINOMI

#15:  VECTOR(pomakni(t), t, 1, 1023)

Zaradi statistične obdelave ga boste podali v podaljšani obliki

#16:  VECTOR(pomakni(t), t, 1, 1050)

Iz te oblike boste lahko preverili , če se ponavlja na 1023 mestu. Ugotovili boste kje se nahaja kombinacija desetih zaporednih enic, ki je v sekvenci prisotna samo enkrat. Samo enkrat je prisotna tudi kombinacija devetih zaporednih ničel. Izvedli boste statistiko pojavljanja devetih zaporednih enic, osmih zaporednih enic in tako naprej do pojavljanja posameznih enic. Tudi zaporedno pojavljanje ničel boste vzeli v precep. 
En od načinov izdelave statistike je, da si sekvenco po delih, recimo po okoli 50 bitov na skico, stiskate na papir in preštevate po njem in izide preštevanja vnesete v preglednico. Da se izvesti tudi na programski način, ki pa si ga morate izdelati po svoji zamisli.

Predlog preglednic

Položaj 10 	-tih enic	
x-ti	bit	

       PREGLEDNICA ZAPOREDIJ	
            ENIC	           NIČEL	
10		__		
9		9		
8		8		
7		7		
6		6		
5		5		
4		4		
3		3		
2		2		
1		1