2020-02-26

Faster than Nyquist Signalingin ongelma, luulisin…

Olen pitkään miettinyt, mikä tuossa Faster than Nyquist -kamassa (FTN) on niin häiritsevää, ja vähän luulen että saatoin löytää ideanpätkän vihdoin miten osoittaa ongelma. Tämä ei ole matematiikkaa edelleenkään, tai koodausteoriaa, mutta minusta hyvä intuitio se kyllä on, ja jatkoa edelliselle.

Kaistarajattujen signaalien jäykkyys

Kaistarajatut signaalit, joiden piirissä FTN-signalointikin analysoidaan, ovat matemaattisesti katsoen äärimmäisen jäykkiä rakenteita. Näin siksi, että ne ovat paitsi reaalianalyyttisia, myös kompleksisellaisia. Tuo mahdollistaa kaikenlaista kivaa, mutta myös kaikenlaista aivan kammottavan epäintuitiivista. Esimerkiksi se jäykkyys mahdollistaa compressive sensing -tulokset, hirvittävän määrän erilaisia näytteistysteoreemoja, ja muutenkin täysin järkyttäviä informaatiomittoja, tyyliin lähes mielivaltaisen "innovaation" per aikayksikkö, tietyn aaltomuodon määrittelyssä ja käsittelyssä.

Ehkä järkyttävin tulos tästä puusta on, että teoreettisesti kaistarajatun signaalin täyteen määrittelyyn missään n annetussa pisteessä ajassa ei tarvita mitään muuta kuin että signaali näytteistetään missä vain muussa n pisteessä täydellisesti, ja n:n ylittävät vapausasteet ongelmassa oletetaan pois. Näytteistysväli voi olla vaikkapa mikä vain mielivaltaisen lyhyt suljettu väli reaaliakselilla, kuten [0,1] tai vaikka sitten [0,1/googolplex], ihan sama—numeerisesti tuo on tietysti täysin mahdoton ongelma, mutta teoreettisesti noin kuitenkin, aina.

FTN ja vapausasteet ja normaali-impulssikanta

FTN-signaloinnissa me tuotetaan kaistarajattuja impulsseja nopeammin kuin Nyquist-raja konventionaalisesti sallisi dekoodattavan. Tuo teoria on sinänsä ihan hyvin toteennäytetty: se ei riko mitään informaatioteoreettisia rajoja, se on ainakin so-so-dekoodattavissa, sen energia pysyy hallinnassa, ja se vain sotkee pohjimmiltaan viereiset kommunikaatiokanavalla yhteen, niin että tarvitaan rajumpaa dekoodausta ennen kuin juokseva kokonaissymbolijono saadaan eroteltua osikseen. Se myös lähtee varsin kiintoisasta ja totisesta minimietäisyysanalyysista, jonka jälleen on täysin todistettu johtavan lähemmäs Shannonin epäkonstruktiivista kapasiteettirajaa kuin useimmat konventionaaliset Nyquist-analyysiin pohjautuvat koodit (se voidaan katsoa eräänlaiseksi koodaus–modulaatio -yhdistelmämenetelmäksi). Siitä on nykyään jopa toimivia prototyyppejä, ja sitä mietitään osaksi 5G-järjestelmiä, ilmiselvän taajuustehokkuutensa tähden. So far so good.

Mutta mä olen silti aika varma että sillä on noiden kaistarajattujen funktioiden jäykkyyden tähden aika helpostikin osoitettavissa oleva heikkous: se ei voi olla yhtä lokaali kuin ortogonaalikoodaus parhaimmillaan on. Intuitio sanoisi, että se minkä pakkaat tiuhempaan tässä ja nyt, sanelee pahimmillaan sun tarkkailuvälin ulkopuolella jotain mitä et halua tapahtuvan.

Itse analysoisin näitä myös konventionaalisen impulssikannan suhteen, koska siitä tiedetään että se on viimeistään heikossa topologiassa suora (paikallinen) isometria jatkuvan puolen kaistarajattujen funktioiden ja kriittisesti sekä tasavälisesti näytteistettyjen diskreettien funktioiden välillä; tuo isomorfismi ei jätä mitään vapausasteisiin liittyviä tulkintoja järin epämääräisiksi, varsinkaan LTI-oletuksen jälkeen.

Ikävä aiempi esimerkki, ja hahmotelma aidosta vastaesimerkistä

Vaikka tämä ei nyt ihan kuulukaan tähän, kuuluu se silti… Nimittäin, on tunnettua että tuo kaistarajattujen näytteistettyjen funktioiden palautus jatkuvaan piiriin johtaa ainakin yhteen todella iljettävään, epälokaaliin ilmiöön: siihen että näytteiden välissä voi tapahtua aivan mitä vain vaihekoherenssin tähden. Karsein (minimi)esimerkki lienee ääretön näytteistetty jono …-1,1,-1,11,-1,1,-1… Se tuottaa origossa amplitudiltaan äärettömän signaalin, siinä missä yhden ainoan -1:n lisääminen tuohon väliin taas tuottaa suoran Nyquist-taajuisen siniaallon.

Molempia signaaleja käytetään yleisesti D/A-muuntimien testauksessa idioottitesteinä, ja usein ne rikkovat sitten myös naiivit muuntimet, tavalla tai toisella. Yksi sun toinen kehittyneempikin sigma–delta-muunnin menee johonkin limit cycleen ekasta, ja joutuu toipumaan siitä ad hoc -keinoin sitten. Jotkin suodattimet jossain historiassa tuo signaali on jopa käräyttänyt suorilta.

Noh, koska ne kaistarajatut signaalit on niin jäykkiä, ja kun nyt selvästi on niin että FTN-raami injektoi lisää vapausasteita jopa perinteisen näytteistysintervallin sisälle—mitä me voitais kenties sanoa siitä miten sen määräämä signaali käyttäytyy jossain kauempana eikä vain perinteisten näytteiden välissä? Ennen kaikkea, voitaisiinko me rakentaa adversariaalinen koodisana, joka sen koodatun signaalin välttämättömän, kaistarajatun jäykkyyden kautta pakottaa sen signaalin käyttäytymään ikävästi, normaalianalyysin käsittelemän arvoalueen ulkopuolella?

Olen aika varma että noin voitaisiin tehdä, ja vielä systemaattisesti. Meinaan as per compressive sensing -kirjallisuus ja kaikki toi epätasaväliseen näytteistykseen liittyvä kirjallisuus, me voidaan lähes täysin vapaasti valita missä me samplataan asioita vaikka normaaliraamin näytteiden välissä. Eli otetaas sitten käyttöön ensin normaaliraami jossa me mitataan kaikki (koska se kaunis isometria, jolle ei sovi väittää vastaan, ja johon Shannonkin perustaa kaavansa). Otetaan blokki FTN-kamaa joka tuottaa kohtuuttomasti vapausasteita suhteessa Nyquist-rajaan. Oletetaan sen oletukset, jotka toivottavasti myös sisältää jonkin todistuksen siitä että kaikki FTN-symboliblokit häipyvät ajassa asymptoottisesti eksponentiaalisesti kuten standardiblokitkin, niin että niitä voidaan käsitellä ajallisesti lokaaleina (en usko että tuota todistusta on missään, ja aion hyökätä juuri sitä vastaan).

Sitten rakennellaan lineaarisia täyden rankin yhtälöryhmiä, jotka ovat mahdollisimman ikäviä. Jos FTN tuottaa vaikkapa tasaiset 10% lisää pulsseja ajassa kuin kriittinen Nyquist-raami, kysytään heti mikä on se kamalin juttu mitä tuosta voisi seurata seuraavalle näytteelle standardiraamissa? Voimmeko kenties optimoida asiat niin, että kun FTN-raami syöttää liikaa informaatiota ja fiksaa liian monta jäykän moduloidun funktion pistettä jo etukäteen, yhtäkkiä valitsemalla oikein syöte tuolle FTN-raamille johtaisikin siihen että koodausblokin (tai juoksevan ikkunan) ulkopuolinen arvo voitaisiinkin sitoa epämiellyttäväksi, alhaaltapäin?

Hauskin juttu tietysti olisi kasvavassa blokkikoossa FTN-signalointi, joka väkisin johtaa eksponentiaaliseen kasvuun blokin ulkopuolella, vapausaste-per-vapausaste. Mikä juuri ja juuri voisi tapahtua, jopa niin että se olisi osoitettavissa oikein valituilla signaaleilla suorasta matriisialgebrasta, per blokki.

Olen melko varma että noin tapahtuu. En osaa tehdä tätä analyysia ollenkaan oikein, mutta luulen että tuo on se kohta jossa FTN:n on pakko vihdoin näyttää "seamy undersidensä". Eikä tuo tietty tarkoita, etteikö se silti voisi olla hyödyllinen ja jopa vallankumouksellinen kommunikaatiossa. Mutta jos mun intuitio on oikeassa, ei se kyllä sitten juuri muuta ole kuin taas yksi varsin epäsystemaattinen tapa lähestyä Shannon-rajaa, eikä todellakaan niin helposti analysoitava kuin standardiraami Nyquist-pulsseineen. Ihan verrattavissa Ungerboeckin TCM-tavaraan, eli ihan siistii ja tehokasta, mutta ei kyllä mitään fundamentaalisesti maatakaatavaa ja ongelmat tyhjentävää informaatio- tai koodausteoriaa—akolyyttiensa puheensävystä riippumatta.

2020-02-22

Koodausideaani, yhden bitin kannalta

Kuten mua seuranneet tietää, olen pitkään pyöritellyt ideaa siitä, olisiko jatkuvista konvoluutioista kohinan kanssa koodausteoreettiseksi primitiiviksi. Mahdollisesti jopa tavoin, jotka takaisivat oikein käytettyinä esim. yksipuolisen dekoodauslatenssin säätämisen sekä minimoinnin. Uusimman mietteeni ajamana yritän siis vähän fundamentaalisemmalla tasolla hahamotella miksi tämä todella saattaisi kiertää niitä intuitioita jotka ovat itseänikin vaivanneet.

Perinteinen kysymyksenasettelu

Tavallisesti kun informaatioteoriassa ja käytännön demodulaatiotyössä kysytään, mikä on optimaalinen tapa ilmaista jokin signaali AWGN-kohinasta, vastaus on sovitettu suodatin/matched filter. Se on pohjimmiltaan lineaarisuodatin jonka impulssivaste on sama kuin ilmaistavan signaalin, paitsi että sen vaihevaste on käännetty. Se ei ole (yleisesti) lainkaan sama kuin käänteissuodatin/inverse filter, koska jos alkuperäisen signaalin spektri on yhtään kenossa (tai herra paratkoon menee jossain kohdin nollaan), käänteissuodatin vahvistaisi hälyä mahdollisesti voimakkaastikin, ja tekisi ilmaisulle vain hallaa. Vaihevasteen käänteisyys kuitenkin on sovitetun kuten käänteissuodattimenkin ehdoton hyöty: siinä määrin kuin ilmaistavan signaalin energia on hajonnut eri tavoin ajassa, käänteinen vaihevaste ilmaisusuodattimessa uudelleenkeskittää parhaiten energian lineaarisessa ilmaisussa, ja sitä kautta johtaa tilastollisesti vahvimpaan päätöskriteerioon. (Näin standardineliönormissa, jonka laillisuuteen AWGN-raamin on tarkoituskin johtaa.)

Näyttäisi, ettei lineaarisessa raamissa voi olla parempaa ilmaisukriteeriota kuin tuo sovitettu suodatin plus binaarinen valinta; todistushan sille on jo.

Shannon ja sen seuraamukset

Informaatioteoriassa kanavan kapasiteettilause kuitenkin pelaa ikävästi tätä vastaan. Pohjimmiltaan toisessa ääripään regiimissään, eli puhtaasti tehon hallitsemassa äärettömän kaistanleveyden kanavassa, on aivan ilmeinen teoreettinen tapa lähettää virheetön pulssi, eli bitti: tuupataan kaikki bitin siirtoon tarkoitettu energia mielivaltaisen kapeaan delta-distribuutioon. Tuo ei tietenkään sovi yhteen jatkuvan kohinaprosessin kanssa, analyysissa, sinänsä, mutta niin kauan kun Shannonin teoreeman tehoehdot täyttyvät, riittävän tehon pulssi tasoitettuna mielivaltaisen pieneen ympäristöön aina rikkoo kohinan ja on ilmaistavissa mielivaltaisella tarkkuudella. Virhetodennäköisyys ilmaisussa on ajettaissa nollaan kunhan pulssin amplitudi/teho vain on riittävä suhteessa kohinaan.

Silloin pitäisi myös kaiken järjen mukaan olla niin, että jos me lohkomme taajuuskaistan sattumanvaraisiin osiin suodattamalla tuon pulssin joukolla tiukkoja kaistanpäästösuodattimia, tulos ei muutu. Näin siksi että tuo esitys on edelleen täysin legitiimisti luotavissa, hävittämättä tai luomatta informaatiota; se on matemaattisesti ns. partition of unity, eikä se edes distribuutioraamissa kärsi mistään konvergenssiongelmista.

Lisäksi, tuollainen kaistaleikkaus suodattaa periaatteessa kaikilla taajuuksilla pois saman osan kohinasta kuin itse pulssistakin. Eli pulssin jonkinlainen epämääräinen suhteellinen ilmaistavuus kullakin kanavalla pitäisi olla täysin vakio, ja siis riippua vain siitä meneekö alkuperäisen pulssin informaatio- tai koodausteoreettinen ilmaistavuus yli kapasiteettilauseen, vai eikö mene.

Kuitenkaan tuo optimaaliseksi kehuttu sovitettu suodatin ei tule lähellekään moista. Se kohisee niin maan perkeleesti. Eli mikä tässä nyt mättää? Tässä puhutaan niin lineaarisista asioistakin vielä yhden Nyquist-pulssin (rajalla deltan) kanssa, että mitään epälineaaristakaan parannuksenvaraa ei oikein näytä olevan. What gives?!?

Jäikö jotain sittenkin pöydälle?

Uusin ajatukseni on, että itse asiassa tässä pelkistetyssä yhden pulssin tapauksessa jätettiin itse asiassa koodausraamissa pöydälle hyödyntämätöntä. Nimittäin, tuo analyysi lähtee pohjimmiltaan jostain tutkatekniikasta tai aikasarja-analyysista, jossa me emme tiedä missä se ilmaistava signaali ylipäänsä alunperin oli tai ei ollut. Tuossa raamissa on aivan oikein käyttää sovitettua suodatinta, eikä lisätietoa ole saatavissa mistään.

Kommunikaatiopuolella oletus on kuitenkin vähän eri. Siellä me yleisesti ottaen tiedämme mistä tiettyä bittiä pitäisi etsiä: se on jo-tarkoituksella-synkronisoidussa pakettiliikenteessä tismalleen niin ja niin monen nanosekunnin päässä edellisestä. Eli oikea formalisaatio yksinkertaisimmalle mallille ei olekaan, löytyykö jostain joskus joku bitti vai ei, ehkä, vaan suora päätösongelma siitä onko origokeskeinen pulssi paikalla, vai ei. Ja vielä eritoten bayesilaisessa raamissa sillä priorilla, että mitään muita pulsseja ei ylipäänsä ole lähetetty, eikä mikään vastaanotettu signaali voi olla muuta kuin toinen kahdesta täsmällisestä, AWGN-hälyä (eli siis että jopa pisteittäin, jatkuvasti, kaikki poikkeamat jommasta kummasta muodosta ovat väkisin kohinaperäisiä).

Eli näin siis modulo synkronisaatio ja se mitä tiedetään jo aiemmasta datasignaalista/dekoodauksesta, ja mahdollisesti mitä tullaan tietämään myöhemmin, jos sallitaan dekoodausviive analyysiin. Mun ajatukset myös on hakemassa minimaalista viivettä lopulta.

Tämä on yhtäkkiä aivan eri pallopeli. Aiemmin tilastopäättelyn priori oli täysin tasainen ajassa sekä AWGN-muotoa. Nyt se on tuntuvasti rakenteisempi: on vain yksi tarkka origon ympäri symmetrinen pulssi joka on lähetetty (vastaanotettava koodivektori on siis eksaktisti se, jatkuvana suureena; muoto vaihtuu kaistarajauksen mukaan muttei muuta) tai jos sitä ei ole lähetetty, on lähetetty eksaktisti nollaa ajan alusta ajan loppuun. Tuota vastaan ideaalinen vektorikvantisaatio toimii aivan toisella tasolla kuin mikään matched-filter-plus-quantizer.

Lisäksi, kaistarajatussa raamissa tiedämme, että se alkuperäinen mahdollinen delta-impulssi muuntuu (alimmassa partition osassa/basebandilla) tismalleen Nyquist-pulssiksi, joka on tasavälisesti ajassa nolla, silloin kun ei ole origossa tismalleen ykkönen; jos me suodatamme basebandille tarkasti, kaikki poikkeamat nollasta (origossa ykkösestä tai nollasta) noissa pulssin herkissä kohdissa ovat välttämättä kohinan tekosia. Näytteistysteoreema vielä kaistan sisällä takaa senkin, että informaatiota ei häviä siinä kun katsellaan asioita diskreetissä versus jatkuvassa kannassa. Eli tilastollisesti optimaalinen päättely ei enää olekaan sitä että meneekö sovitettu suodatin tietyn rajan yli jos sattuu joskus menemään, vaan että meneekö sovitettu suodatin tasan origossa tasan nollaan vai tasan ykköseen, oletettaen että kaikkialla tunnetuissa kaistarajatun pulssin nollakohdissa se kuitenkin väkisin menee nollaan.

Tuo on aivan hysteerisen paljon vahvempi priori kuin mitä olen koskaan nähnyt käytettävän tämän sortin analyysissa. Vaikka se on minusta täysin hyvin perusteltu, ja ehkä jopa ilmeinen: joko sinä lähetit bitin/pulssin tai et, jos teit sen oikein niin se näyttää ideaalisesti sinc()-funktiolta jolla on täsmällinen muoto, näytteistysteoreeman eri versiot antaa sun pomppia aika vapaasti noiden distribuutio- ja diskreettien yms. formalismien välillä sotkematta matikkaa, eikä kukaan siinä standardianalyysissa muutenkaan selitä miksei käsitteellisestä signalointihetkestä ajallisesti eroavaa nollatietoa oteta aktiiviseksi prioriksi tuossa kaistarajatussa raamissa. Vaikka kaikkihan jo tietää että kaistarajaus on väkisinkin epälokaali operaatio sinänsä. Varsin vittumainenkin sellainen vielä, kun se sinc()-pulssi häviää ajassa sub-eksponentiaalisesti, niin ettei kaistarajattua kommunikaatiota ylipäänsä voida millään mittarilla edes puoliksi pitää aikalokaalina abstraktiona.

Hilpeänä esimerkkinä tuosta muuten… Noin teknisesti, jos sulla on mitkä vain n näytettä kaistarajatusta signaalista, ja ikään kuin loput (äärettömät, huoh—) näytteet (tarkemmin vapausasteet) on nollia, mitkä vain muut annetut n näytettä siitä—täysin ajasta tai mistään riippumatta—on täydellisesti rekonstruoitavissa. En yrittäis tota hetä numeerisesti, koska ongelma on ihan jäätävän ill-posed, mutta noin teoreettisesti kaistarajatut funktiot on just noin jäätävän jäykkiä. Matemaatikon mielessä kompleksianalyyttisyydensä tähden. Eli ne siis sallii tosi perverssejä, epälokaaleja manipulaatioita. Ne vaatii esim. välttämättä epäkausaalisuutta, niin etteivät voine kuvata koskaan fysikaalista todellisuutta järin tarkasti.

Sovellukseni

Jos siis käytät sovitettuna suodattimena kaistarajattua impulssia (taajuuspuolella toi on kaistallaan identiteetti, koska se on määritelmällisesti nollavaiheinen ja ykkösmagnitudinen kaistan yli) ajassa-nolla lähetetyn impulssin päätösongelmaan, kaikesta siitä kivasta lineaarikoneistosta minusta noin intuitiivisesti pitäisi seurata, että sovelletaan sitä suodatinta muuallakin kuin vain origossa. Katsotaan mitä hälinää siitä tuli läpi, ja kun tiedetään a priori että kaikkialla muualla tietyissä tasavälisissä pisteissä se alkuperäinen signaali meni nollaan, no konditionalisoidaan koko ongelma sen mukaan myös. Ja kun tää nyt on niinkin simppeliä lineaarikoneistoa, ainakin vähennetään se energia joka meni överiksi noin alkuun: jos vastaanotit jotain mikä on muuta kuin nolla siellä impulssin reunanollakohdissa, jostain se energia tuli, eli otetaan se vaan pois ja suodatetaan lineaarisesti takaisin. Vähintäänkin toi on turvallinen operaatio, ja jos siitä voi jotenkin kehittää kontraktiivisen iteraation, no sitten vakaa piste ois jo olemassa.

Toki tuonkin jälkeen meillä olisi käsissä edelleen vektorikvantisaatio-ongelma. Mutta tällä kertaa sillä olisi selvä numeerinen ja voimakkaan lineaarialgebrallinen rakenne, joka viittaa separoituvuuteen. Ei pitäisi olla erityisen vaikeaa tasoittaa sen koordinaattikohtaisia virhekontribuutioita yli koko virhevektorin, matkalla kohti globaalia VQ-optimia. Varsinkaan kun tässä (ja omissa allpass-ajatuksissani aiemmin) on läsnä kuitenkin taatusti häipyvä aikarakenne, joka tekee kaikenlaisesta numeerisesta optimoinnista lokaalista myös. Ja miltei vähän luulen myös, että algoritmit joissa väliin lyödään harkittu konvoluutio ja sitten vasta pyöristystä ja/tai iterative shrinkingiä, voisivat ratkaista ongelman aidosti.