*

  • her ne kadar elektronikcilere ve iletisim muhendislerine hitap edecek olsa da, icerdigi zeka pariltisini gostermesi ve akilli insanlarin keskin gozlemlerle teknolojiyi nasil ilerlettiklerine ornek teskil etmesi acisindan sozlukle paylasmak farz olmustur.

    biraz motivasyon olsun diye, viterbinin ne kadar onemli oldugundan kisaca bahsedelim: bugun dunyanin sayili sirketlerinin ve universitelerinin girisinde, fosforlu kalemle yazildigi icin gunduzleri gozukmese de "viterbi algoritmasini bilmeyen giremez" yazar *. gazi aldinizsa baslayalim.

    ofdm basliginda da bahsetmistim, artik bitleri bir sinusoidal dalgayla tek tek yollamak yerine, bircok sinusoidal dalgayi ustuste koymak suretiyle olusturulan ve bir halta benzemeyen sinyallerle bircok bit ayni anda yollaniyor. bunlarin birbirine karismamasi icin de degisik teknikler var, dedigim gibi (bkz: ofdm)

    formalite icabi olsun diye sunu da anlatayim sonra zevkli kismina gelecegiz. bu iletisim tekniklerinden biri de otdmdir veya stream modulation. buna gore ayni dalgayi, ufak araliklarla yollarsiniz ama araliklar o kadar ufaktir ki dalgalarin buyuk kismi ustuste biner. yani 5 milisaniyede bir dalga yollayacaginiza ornegin, kismen ustuste binmis 8 dalgayi 10 milisaniyede yollarsiniz, her dalga da bir bit (veya daha fazla) bilgi icerir. bunun guzelligi, sadece bir tane filter koyarak ve bu filterla, sinyali, tam bu dalgalarin kesistigi zamanlarda sample ederek, sirayla tum bitleri cozebilmenizdir.

    simdi bunlari anlamaniz sart degil, onemli olan nokta su: digelim sisteminiz oyle bir dizayn edilmis ki, boyle ustuste binmeli her dalga 10 milisaniye suruyor ve siz her birinden 8 bitlik bilgi cikarmak durumundasiniz. yani ilk sinyali aldiginizda olasiliklar arasinda 000..00'dan tutun da 10101001'e kadar 2 uzeri 8 tane kombinasyon var. klasik sistemlerde bu her olasilik icin ayri filterlar ve devreler konur, o zaman da oda buyuklugunde cep telefonunuz olur. oysa bu yeni sistemlerde dedigim gibi bir filter var cunku orthogonality sayesinde, kombinasyonlar yerine tek tek bitlere bakabiliyoruz. ilk bite bakmak icin, atiyorum, sinyale 1.2 milisaniyede baktiniz ve 0 ya da 1 olmasina bir olasilik atadiniz. (aslinda matched filter denen guzide teknikle yapiliyor ki bu da sinyali, onceden hazirlanmis sample'inizla correlate etmekten ibaret ama simdilik bunlar onemsiz)

    ikinci bite sira geldiginde buna da bir olasilik atadiniz. simdi ne oldu kuzum, 4 tane olasiligimiz oldu. 00, 01, 10, 11. bu boyle gider. ornegin, 3. bitin sifir olmasina bir olasilik atanir, sonra bu olasilik 00 kombinasyonunun halihazirdaki toplam * olasiligiyla toplanir ve 000 olasiligi bulunur. ayni olaslik 11'in halihazirdaki olasiligiyla toplanirsa 110'in ihtimali bulunur. dolayisiyla 8 bitin sonunda 2 uzeri 8 ihtimalimiz var. yani ilkel sistemlerde 2 uzeri 8 matched filterimiz ve ilgili devrelerimiz varken simdi bu sayi sadece bir ama yine de bu kombinasyonlarin sayisini degistirmedi ve butun bunlari akilda tutmak ve en sonunda da karsilastirip en kuvvetlisini bulmak icin hem guclu sistemlere ihtiyacimiz var, hem de dizaynimiz daha cok guc tuketiyor.

    simdi viterbinin onemini anlamadan once su sisteme bir ekleme daha yapalim. karmasik sistemlerde bir hafiza vardir ve bir finite state machinele modellenir. bu artis isim sizi korkutmasin, olan biten kisaca sudur: eskiden sifir gondermek icin sinusoidal dalgami mesela -1 ile carpiyordum, boylece dalga aliciya geldiginde eger ortamda parazit yoksa -1 volt degerinde oluyordu. eger bitim 1 ise, dalgayi bir ile carpiyordum. (aslinda bu degerler binary phase shift keying icin tam tersidir) neyse, simdi diyorum ki, ulan duduk, onun yerine ben mesela -3/5 ile carpayim dalgami. ondan sonra eger +3/5 gonderirsem bu 01 demek olsun, yok eger -1/5 gonderirsem 11 olsun. (anlatmasi uzun ama kisaca, boyle yapinca bitler arasindaki hata payi azaliyor, bilenler icin minimum euclidian distance artiyor)

    simdi bir onceki bitde ne gondermis oldugumu bilmem icin sistemin o anki halini state machine olarak modelliyorum. ornegin 8 bitlik serinin en basinda, 1. stateten basladim. 1 geldi 2. state'e gectim, 0 geldi 1. de kaldim. 11 gelirse, 2. den 3. ye gecerim, 10 gelirse 2.den tekrar bire donerim, yok 01 gelirse birinciden 4e gecerim filan.. bu iliskileri karmasiklastirarak hizimizi arttirmak bile mumkun. yani 1. state'deyken -1/5 gelirse ornegin bu 001 olsun (bir kerede uc bit) ve bizi 9.state'e gotursun, orada +3/5 gelirse 111 olsun bambaska diyarlara gidelim bir dahaki sefere. fakat ayni +3/5 biz 7. statede iken gelirse bu 101 olsun gibi.

    neyse bu kavrami sekillerle anlatmak cok daha kolay ama bu noktada anlamamiz gereken tek sey, stateler arttikca sistemin karmasikliginin ve hizinin arttigi ve her statein kendisinde bir sequence barindirdigi. yani o ana kadar, o pakette gonderilmis bitlerin (paketimiz ornegimizde 8 bitlik) bir tahmini gibi. ornegin 10 milisaniyelik paket suremiz basladi ve eger bu sequencein ilk 5 biti, 00101 olmussa benim 4. state'de olmam lazim. tipki yukarida anlattigim gibi bu 00101 kombinasyonun bir olasiligi var (sinyali gozluyoruz o zamana kadar) ve bu olasilik da o statede tutuluyor.
  • iste viterbi efendi bu olaya bakiyor ve amma de hiyarmisiz diye hayiflaniyor. zira dogru karari verebilmek icin, 10 milisaniyenin sonunda tum bitler gozlemlenmisken, 2 uzeri 8 ihtimalin her birinin karsilastirilmasina hic gerek yok. cunku stateler bu elemeyi daha onceki adimlarda is karmasiklasmadan yapabilirler. nasil, nasil diye heyecandan kudurdugunuzu, cayiniz demleyip dinlemeye koyuldugunuz gorur gibiyim sevgili bilim dostlari.

    simdi tekrar ornekle baslayalim. sinyalin ilk kismina bakarak, bunun sifir bitini tasiyor oldugu olasiligini hesapladik (baslangicta -3/5 voltluk bir sinyal sifiri belirtsin diyelim, simdilik bu 3/5.,1/5 olayini unutabiliriz, bir ve sifira yogunlasin, hayatin anlami bunlarda) ve gercekten sifir gelmis olacagini varsayarak, bu olasiligi kaydettik. (42%). simdi state 0 da baslamistik ve eger hakkaten sifir gelmisse tekrar state sifirdayiz demek. yani 2. bite bakmadan hemen once, benim state sifirda olma ihtimlaim 42% ve bu ihtimal 0 sequenceina karsilik geliyor. (daha sequence falan yok tabii, alt tarafi bir bit) ote yandan birinci bitin 1 gelmis olasiligi da var ve bu olursa state 1'e geciyoruz, vs. simdi zamanda ilerliyoruz ve 2. bite bakiyoruz. state sifirdaki olasiligimiza, bu yeni bitin de sifir olmas olasiligini ekleyip 00 olasiligini hesapliyoruz ve bunu, bu adima karsilik gelen state sifira kaydediyoruz. ote yandan 1. statede bulunan olasiligimiz (ilk bitin 1 geldigini varsayan) belli. digerine yaptigimiz gibi buna da ikinci bitin 0 veya 1 gelme olasiliklarini ekliyoruz ve toplam olasiliklari, belirttikleri sequencelariyla beraber, bir sonraki adimdaki statelere kaydediyoruz. simdi diyleim ikinci bitin sifir gelme olasiligi, 3. biti gozlemlemeye baslamadan hemen once, bizi 1. stateden sifirinci state'e getiriyor. yani 10 sequence'i. hatirlayalim, ayni zamanda 00 sequence'i da bu state 0'a tekabul ediyordu. yani ayni state'te bulunan ve birbiriyle yarisan iki sequence var, 00 ve 10. klasik yontemle bu ilk iki bitin devami olan butun olasiliklar hesaplanip en sonunda karsilastiriyordu. oysa viterbi diyor ki, ulan 00 ihtimali o ana kadar toplam yuzde 32 ise, 10 ihtimali de yuzde 18 ise (dikkat edin daha iki bit cozduk yani toplam dort olasilik var) o zaman hicbir sekilde 10,000000 sekansi(ahan da "turkcesini" hatirladim) 00,000000 sekansindan daha olasi olmayacak. cunku ilk iki bitten sonrasi ayni, yani common future tabir edllen hadise. sonucta butun o sonraki sifirlarin birer birer ihtimalleri her iki sekans icin de ayni olacak, dolaysiiyla hersey toplandiginda, farki yaratan bu ilk iki bit arasindaki olasilik farki olacak. e biz bunu zaten daha ikinci biti cozdugumuzde biliyoruz. oyleyse 10 ile baslayan tum sekanslari cope atmamizda hicbir zarar yok. bu oyle bir tasarruf ki, 10i takib edecek olan 6 bitin olusturacagi 2 uzeri 6lik, yani 64 kombinasyonluk bir hesaplamayi yapmak zorunda degiliz. ayni tasarruf her state'de yasaniyor. yani her adimda (her bitin gozlemi sonrasinda) ortak gelecegi bulunan sekanslardan, sadece o ana kadar daha fazla olasiligi bulunan sekans hayatta kaliyor. *

    iste boylece 8 biti tamamladigimizda, az sayida hesaplamayla dogru bit sekansini bulabiliyoruz. simdi 8 bit orneginde belli olmayabilir ama sistemimiz eger bir paket icinde 64 bit yolluyorsa, edilen tasarrufun haddi hesabi yok. iste o kic cebinize, hatta sutyeninizin gizemli derinliklerine giren cep telefonlarinin iletisim alt birimlerinin bu kadar ufak olmasinin en onemli nedenlerinden biridir viterbinin bu zeki gozlemi ve algoritmasi.

    her ne kadar burada olayi cok basitlestirerek ve kolay anlasilmasi icin bazi ayrintilara sadik kalmayarak anlatmis olsam da, bu fikrin ozu sonucta her normal homo sapiensin anlayabilecegi duzeyde ve guzelligi de burada. matematikcilerin elegant teorileri gibi, bu da ince ama cok guclu bir muhdendislik cozumu.

    (ilgilenenler icin ozel not: buna benzer bir fikir de , mesela frequency selective kanallarda kullanilan otdm/ocdm algoritmalarini basitlestirmek (sub-optimal preformans kaydiyla tabii) icin birebir olan ungerboeck algoritmasidir. bir ara onu da yazariz, lakin acil isiniz varsa bununla ilgili, mesaj vasitasiyla kalplerimiz bulusacaktir)
  • eger yukaridaki tanimlama karisik geldiyse buyrun, kisa bir versiyonu icin bir de buradan yakin. fil kardesimiz mesaj vasitasiyla yardimci olmus, ben de tembelligimden aldim aynen buraya koydum [yoksa kendisi de ehil ve kendine guvenen bir kisidir, isteseydi pekala entry olarak da yazardi]

    bir state ulasmak icin birden fazla yol olabilir. ornegin nth bit 0'dir; daha onceki n-1 bitden dolayi bu bitle biten 2^(n-1) adet farkli sekans vardir. mr. viterbi (qualcomm) aliciya gelen ilk n bit'i olasi transmission sekanslariyla karsilastirarak, gonderilme ihtimali en yuksek olanini bulur. yalniz mr viterbi tikkatlidir, kendisi 2^n path'e bakmaz (uzun surer), viterbi bey bir onceki state n-1'ininci state ulasmak icin en kestirme yollari aklinda tutar; bu kestirme yollar n-2'inci state ulasmak icin kullanilan kestirmeler ve n-2 ve n-1 arasindaki yollardan olusur. bir tur labirent'te en kisa yolu bulmak gibi birsey.

    ayrica benzer bellman - ford algorithmasi falan da shortest path algorithmasi olarak bilinirler. bellman -ford router'larda kullanilirlar. iki node arasinda minimum delay'li path bulmaya yarar. viterbinin guzelligi additive cost function'larinda linear search bazli minimum distance path'i vermesi oluyor. [editorun notu: aman hulki cevizogluna sikayet edip bizi rezil etmeyin, vallahi networkculer boyle akronimlerle, acayip terimlerle konusurlar hep, ozumuzde iyi insanlariz]
  • convolutional encoding yapilmis datayi acmak icin kullanilabilen leziz algoritma.
    (bkz: hidden markov model)
  • uydu haberlesmesi, cep telefonlarinda kullanilan sesli komut ve el yazisi tanima sistemleri bu algoritmayı temel alir. gelistiren italyan asilli amerikali bay viterbi' dir. bugun kullandıgimiz samsung basta olmak uzere cep telefonlarindaki qualcomm devresini ureten sirketin sahibidir.
  • dinamik programlama sayesinde dışa yansıyan sonuçlar, durumlar arası geçiş olasılıkları ve her durumun yansıttığı sonuçlara dair verilere dayanarak gizli markov durumlarını ortaya çıkarmakta kullanılabilen bir algoritma. örnek vermek gerekirse, size insanların hava durumuna bağlı olarak giydikleri kıyafetlerin olasılıkları, hava durumunun geçiş tahminleri ve 100 gün boyunca insanların ne tür giysi giydiğine dair veriler verilirse, bu 100 gün boyundaki en muhtemel hava durumu serisini bulmanızı sağlar. biyoinformatikte de sıkça kullanılan bir algoritmadır.
  • anlatılana göre ilk makale olarak yayınlandığı zaman gerekli etkiyi yaratamamış algoritmadır. daha sonra aynı algoritmayı başka bir zat daha sunulabilir bir şekilde yeni bir makale olarak yayımlayınca herkesin jetonu düşmüştür.
  • sampling su anda ufak tefek seyler disinda (ornegin diffusion modellerde kullanilan classifier free guidance, olasilik dagiliminin daha yuksek oldugu yere dogru ittiriyor hicbir ekstra sampling'e gerek duymadan ama bunun disinda ornekler sinirli) genelde en iyi sonuclarin alinmasina yariyor (bkz: nlp) (bkz: speech recognition). ama sampling'in en buyuk sorunu, her adimda network'ten tekrardan bir forward pass yapma gerekliligi ve hesaplanacak seylerin exponential bir complexity'si var.

    gozunuzun onune bir decision tree getirin. bu tree'nin amaci a noktasindan b'ye gitmenin en kisa yolunu bulmak olsun. butun mesafeleri hesaplamaya calisirsaniz, node sayisi arttikca islem masrafi (hesaplanacak mesafe) artar. viterbi burada cok basit bir gozlemde bulunuyor: gittigimiz yollar ortak bir yerde bulusuyorsa, o zamana kadarki daha uzun mesafe yolu takip etmeyi birakabiliriz.

    ornegin a->x->y->z->k->l->b ve a->x->m->k->l->b yollarini dusunelim. eger [a->x->y->z] yolu [a->x->m] yolundan kisaysa, ikinci yolun [k->l->b] kismini hesaplamaya gerek yok, cunku ne olursa olsun yolun m node'una kadarki mesafesinde [a->x->y->z]'yi takip etmek daha kolay. ana fikri bu.

    alakali olarak (bkz: beam size) (bkz: nucleus sampling) (bkz: top-k sampling)
hesabın var mı? giriş yap