Seznam bibliografije

Tekoči projekti:

Polinomska minimaks aproksimacija s koeficienti iz končne množice

Na tem problemu delam, s presledki, od leta 1975. Začelo se je z aplikacijo, v kateri je bilo treba koeficiente KEO digitalnega filtra z linearno fazo predstaviti z največ 8 biti. Zaokroževanje tako imenovanih "neskončno natančnih" koeficientov na končno število bitov b je bilo (in pogosto še vedno je) običajen postopek. Vendar pa zaokroževanje ne da optimalnih koeficientov s končno dolžino besede in skoraj vedno obstaja veliko boljša množica koeficientov.

Iskanje optimalnih b bitnih koeficientov je težko, ker vodi do aproksimacijskega problema s koeficienti iz končne množice. Problem je skoraj zanesljivo NP težak, čeprav formalnega dokaza zaenkrat še ni. Poleg tega na začetku ni bilo jasno ali je problem sploh vredno reševati, ker je razlika med zaokroženim in optimalnim filtrom morda zanemarljiva. V času, ko skoraj nihče še ni poskusil izračunati optimalnih b bitnih koeficientov za filter praktične velikosti, je bilo to pomembno vprašanje. Za odgovor nanj je bil uporabljen splošno namenski programski paket za celoštevilčno programiranje, kar je opisano v naslednjem članku. Rezultati so nakazali, da je optimalen filter v resnici pogosto  bistveno boljši od zaokroženega. To je vodilo k razvoju prve izvedbe programa, ki uporablja posebne lastnosti problema minimaks aproksimacije s koeficienti iz končne množice. Ta program je veliko hitrejši od splošno namenskega in je omogočil izvedbo eksperimentov na veliki množici primerov v pametnem času. Ti eksperimenti so potrdili prvotne ugotovitve: optimalni filtri so lahko do 30 dB boljši od zaokroženih, kar lahko vidimo iz naslednjega primera. Za praktično načrtovanje digitalnih filtrov s končno dolžino besede je potreben učinkovit algoritem, kar spada v problem s področja kombinatorične optimizacije. Razvoj takega algoritma je možen samo, če dobro razumemo teoretične lastnosti problema minimaks aproksimacije s koeficienti iz končne množice. Večina dela je bila zato usmerjena v študij tega problema. Izpeljan je bil izrek o spodnji meji aproksimacijske napake, ki se je izkazal kot zelo uporaben pri pospeševanju algoritma. Tu je zanimivo omeniti, da so doseženi teoretični rezultati bolj splošni in veljajo za veliko skupino problemov, v kateri je načrtovanje filtrov samo poseben primer. Nekateri od teh rezultatov so zbrani v naslednjih člankih.

Čeprav je problem skoraj zanesljivo NP težak to ne pomeni, da ga ni mogoče rešiti v pametnem času tudi pri bolj zahtevnih praktičnih primerih, ko je število koeficientov veliko. Ena od nekoliko presenetljivih lastnosti problema je namreč ta, da  za vsak filter obstaja maksimalno število ne-ničelnih koeficientov. Ali drugače povedano, obstaja polinomska stopnja nmax (zaradi simetrije to ustreza dolžini filtra Nmax=2nmax), od katere dalje so vsi koeficienti vedno enaki nič. Število nmax je odvisno od števila bitov b in od frekvenčnih zahtev, vendar je v praksi najpogosteje manjše od 50. To dejstvo naredi problem obvladljiv, pa čeprav je NP težak.

Teoretična razlaga obstoja maksimalne stopnje nmax in opis preproste metode, ki oceni vrednost nmax, sta podani v članku

"Length limit of optimal finite wordlength FIR filters," D. M. Kodek, Digital Signal Processing, vol. 25, no. 5, str. 1798-1805, Sep. 2013.

Najnovejše delo je usmerjeno na primer, pri katerem je proporcionalni velikostni faktor (imenovan tudi ojačenje filtra) spremenljivka in ne konstanta kot je bila v dosedanjih raziskavah. To poveča kompleksnost problema vendar dobimo manjšo aproksimacijsko napako. Daljnoročni cilj je razvoj programa, ki bi bil uporaben za načrtovanje praktično uporabnih digitalnih filtrov s končno dolžino besedo v nekem pametnem času. Sedanja izvedba programa FWFIR ni daleč od tega cilja. Optimalni FIR filtri z linearno fazo dolžin do okrog N=100 (ustreza n=50 polinomskim koeficientom) in številom bitov b do 14 se lahko izračunajo v približno eni minuti računalniškega časa (na 3 GHz Core i7). Tu je pomembno omeniti, da se v praksi le redko potrebuje večje število bitov b.

Optimalni algoritem za razred "flowshop scheduling" problemov

Ta razred "scheduling" problemov se pojavlja, na primer, pri minimizaciji proizvodnega časa cikla linije za izdelavo tiskanih vezij. Je NP težak in priznano zahteven za reševanje. V algoritmu je uporabljen povsem nov pristop na osnovi spodnje meje časa cikla. Izračun spodnje meje podproblema v branch-and-bound drevesu je lažji kot rešitev podproblema. Zato ni več potrebna uporaba simpleks algoritma, kar naredi algoritem zelo hiter. Eksperimenti so pokazali, da deluje dobro na problemih z velikim številom spremenljivk.

Algoritem je opisan v naslednjem članku. Pripombe so zaželene.

Ne-standardne okenske funkcije v kratkočasovni frekvenčni analizi

Standardne okenske funkcije (Hann, Hamming, itd) so vse simetrične. Ta lastnost jim da linearno fazo, kar je koristno v mnogih aplikacijah. Istočasno pa jih naredi podoptimalne gledano s stališča čistega amplitudnega odziva. Asimetrično okno bi zato v principu moralo biti boljše pri analizi signalov v katerih fazna informacija ni pomembna. Govor je primer takega signala. V ta namen je bilo razvitih več vrst ne-standardnih asimetričnih oken, ki so bila preizkušena na dveh različnih sistemih za razpoznavanje govora. Začetni rezultati so zelo obetavni in kažejo na bistveno izboljšanje robustnosti obeh razpoznavalnikov.

Nekateri od rezultatov so opisani v naslednjem članku.

Nazaj domov.