Razvrščanje in preštevanje sosledij ničel ter enic pri projektu LFSR

Tek programa bo iz generatorja g(), ki je generator LFSR zaporedja, pobiral simbol za simbolom in ugotavljal, koliko ničel oziroma enic se nahaja zaporedoma. Za to sta pripravljeni dve funkciji. Prva šteje sosledje ničel stej0(), druga pa sosledje enic stej1(). Funkciji število simbolov pomnita v števcu st0 za ničle oziroma v st1 za enice. Izid štetja torej vsebino števca se postavlja v hram h0, ki nabira štetja ničel in hram h1, ki nabira štetja enic. Hrama sta oblikovana kot vektorja. 

sort(vh1) je program/funkcija razvrščanja. vh1 je vhodni argument, ki pove nad koliko elementi naj se vrši sortiranje.

V začetnem delu programa so nanizani izrazi, ki uvajajo števca ničel in enic st0, st1, nato sledi postavitev dveh hramov za beleženje izidov obeh podprogramov stej0() ter stej1(). Določi se začetna vrednost števca obdelanih elementov in določi število elementov meja, kolikor jih bo program obdelal.

Po uvodnem delu sledi prva postavitev elementa  data pridobljenega iz generatorja podatkov g(). V zanki , ki sledi se vrednost podatka oceni in glede na njegovo vrednost prične šteti ničle oziroma enice. Ko se zaporedje enakih simbolov konča, pri štetju ničel, je to detekcija enice oziroma pri štetju enic je to detekcija ničle se preveri število obdelanih elementov. Če je meja ni prekoračena, se vrne na začetek, kjer oceni sledeči simbol in nadaljuje po že opisanem postopku. Ko je meja prekoračena, se tek programa zastavi in na zaslon izpiše oba hrama h0 ter h1. V njiju so nanizane dolžine ugotovljenih sosledij ničel ali pa enic.

      sort(vh1) ≔             
        Prog                  
          st0 ≔               
          st1 ≔               
          h0 ≔ [st0]          
          h1 ≔ [st1]          
          vsota ≔ 0           
#1:       meja ≔ vh1          
          data ≔ g()          
          Loop                
            If data = 0       
               stej0()        
               stej1()        
            If vsota > meja   
               RETURN [h0; h1]

Postopek štetja simbolov v zaporedju enakih simbolov se prične s postavitvijo stevca na začetno vrednost, ki je ob vstopu v ta podprogram že ena, kajti predhodno šmo že opazovali en simbol. Nato v zanki ponavljamo branje naslednjih simbolov in tudi štejemo jih sproti s povečevanjem vsebine števca, dokler ne naletimo na drugačen simbol. To pomeni konec zaporedja enakih simbolov. Prične se šteje dolžine za drugačen simbol. To opravi drugi podprogram. Obenem z zajemanjem novih simbolov se proti povečuje tudi vsota, ki spremlja število obdelanih simbolov. Pri pogledu na oba podprograma, vidimo, da se razlikujeta le po odločanju pri vrednosti simbola in pri hramu, v katerega pridobljene vrednosti števca zapisujemo.

      stej0(x) ≔                     
        Prog                         
          st0 ≔ 1                    
          Loop                       
            data ≔ g()               
#2:         vsota ≔ vsota + 1        
            If data = 1              
               Prog                  
                 h0 ≔ INSERT(st0, h0)
                 RETURN 0            
               st0 ≔ st0 + 1         

podprogram za določanje dolžin sekvenc z enicami.

      stej1(x) ≔                     
        Prog                         
          st1 ≔ 1                    
          Loop                       
            data ≔ g()               
#3:         vsota ≔ vsota + 1        
            If data = 0              
               Prog                  
                 h1 ≔ INSERT(st1, h1)
                 RETURN 1            
               st1 ≔ st1 + 1         

Za preskušanje programa smo si pripravili pomožni generator simbolov in sice PNG generator naključnega zaporedja ničel  in enic, torej binarne sekvence.

#4:   g(x) ≔ RANDOM(2)

#5:   sort(128)

      ⎡ [2, 2, 1, 1, 1, 3, 2, 3, 1, 1, 8, 3, 1, 1, 2, 1, 3, 2, 1, 2, 1, 
#6:   ⎢                                                                 
      ⎣ [4, 1, 1, 3, 4, 1, 1, 3, 2, 3, 1, 2, 2, 1, 3, 1, 1, 1, 1, 1, 1, 

        1, 1, 4, 2, 1, 1, 2, 1, 3, 1, 1, 1, 1, 1, 1] ⎤
                                                     ⎥
        1, 1, 4, 1, 2, 6, 3, 1, 3, 1, 2, 2, 2, 1, 1] ⎦

Ko poženemo program sort(128) in ta obdela 128 simbolov, dobimo izid dveh nizov, ki predstavljate hram h0 ter h1.

#7:   h0

#8:   [2, 2, 1, 1, 1, 3, 2, 3, 1, 1, 8, 3, 1, 1, 2, 1, 3, 2, 1, 2, 1, 1, 

        1, 4, 2, 1, 1, 2, 1, 3, 1, 1, 1, 1, 1, 1]

#9:   h1

#10:  [4, 1, 1, 3, 4, 1, 1, 3, 2, 3, 1, 2, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 

        1, 4, 1, 2, 6, 3, 1, 3, 1, 2, 2, 2, 1, 1]

#11:  sort(128000)

Če namesto generatorja g() uporabimo LFSR, dobimo izid hram h0, kjer so nanizane dolžine sekvenc ničel in hram h1, kjer so nanizane dolžine sekvenc enic. To so izhodiščni podatki za izvedbo statistike.

V drugem delu bosta vektorja h0 ter h1 statistično obdelana. Iz njiju bomo nabrali število skupkov razvrščenih po dolžini. Uporabili bomo dve operaciji nad vektorji, in sicer sortiranje in ugotavljanje dimenzije. Iz hramov h0 ter h1 kjer so skupki razvrščeni pomešano/naključno, tako kot so nastajali, jih bomo izbirali glede na dolžino n. Postavili bomo pogoj da operacija SELECT izbere samo tiste, ki ustrezajo pogoju in jih prestavi v nov vektor. Če bo pogoj 3, pomeni, da se bodo v novem vektorju nabrala vsa komponente z vrednostjo 3. Z operacijo DIM pa bomo ta vektor pretvorili v število, ki predstavlja število najdenih elementov.

operator SELECT je zgrajen takole: select (pogoj izbora u(k), položaj elementa v vektorju k , vektor V)

#12:  SELECT(n = k, k, h0)

V našem primeru je pogoj, da je element enak neki vrednosti. Ta vrednost nam predstavlja dolžino sekvence n = k. dolžino smo prikazali kot neopredeljeno vrednost n, kajti pri računanju jo bomo obravnavali kot neodvisno spremenljivko. Operacija select bo v primru, da je dolžima enaka pogoju, element uvrstila v nov vektor, sicer pa ne. Če spreminjamo n, bomo za vsak n dobili vektor take dolžine kolikor ustreznih elementov bo v opazovanem hramu.

#13:  DIM(SELECT(n = k, k, h0))

Z operacijo DIM bomo pridobljene izide pretvorili v števila. Pričakovane dolžine sekvenc so od 10 do 1. V prvem koraku bomo iz hramah0 ali h1 izločili elemente z dolžino n. Ko imamo ta izid , ga z drugo operacijo v število zaznanih sekvenc in to potem spreminjamo od 1 do 10, za kar nam služi operator VECTOR 

#14:  VECTOR(DIM(SELECT(n = k, k, h0)), n, 1, 10)

#15:         [15896, 8110, 4009, 1970, 993, 559, 224, 130, 66, 26]