2018-12-28

Kummallisia modulaatioita ja muita radioajatuksia, osa 2: koodiajatukseni redux

Olen jo pitkän aikaa miettinyt virheenkorjausta. Lohkokoodit eivät ole tarpeeksi hyviä, kun taas konvolutiivisissa koodeissa häiritsee se kuinka ne toteutetaan diskreetillä puolella niin aikavariantin näköisesti. Oma hytinä on, että oikeastaan se koodausongelma pohjimmiltaan etenisi jatkuvassa ajassa, niin että kooderi jatkuvasti syöttää tietyn osuuden siirrettävää dataa ja tietyn osuuden redundanssia signaaliin. Tuon pitäisi tapahtua niin että redundanssi laskee kattamistaan biteistä eksponentiaalisesti eteenpäin, eksponentilla joka juuri ja juuri alittaa AWGN-kanavan virhetodennäköisyydestä johtuvan luontaisen virhe-eksponentin. Sen jälkeen dekooderi voisi vapaasti valita kuinka pitkää viivettä se sietää, vastaan BER; pidemmällä dekoodausviiveellä lopulta päädyttäisiin asymptoottisesti kapasiteettiin, lyhyemmällä vakiovirhetodennäköisyyteen.

Tuo intuitio varmastikin pitää paikkansa, ja olen kirjoittanut siitä aiemminkin, mutta kuten koodausteoriassa yleensä, ongelmahan ei tietenkään ole tämä. Ongelma on miten tehdä tuo temppu systemaattisesti, todistettavasti ja tehokkaasti. Nyt tuli aiheesta vaihteeksi pari uutta ajatusta jotka eivät vieläkään ratkaise ongelmaa, mutta minusta ovat askel oikeaan suuntaan.

Aiempaa päättelyä

Aiemmat ajatukseni aiheesta pyörivät pohjimmiltaan jatkuvien konvoluutioiden ja uudelleennäytteistämisen ympärillä. Jos meillä on bittivirta joka on ylinäytteistetty edes vähän, tai jossa on tunnettuja bittejä silloin tällöin (vrt. se tavallisen konvoluutiokooderin aikavariantti kommutaatio), siinä on jatkuvasti pieni vakiomäärä redundanssia. Jos tuo sitten konvolvoidaan eksponentiaalisesti häipyvän, allpass-suodatinta kuvaavan impulssivasteen kanssa—pohjimmiltaan ajetaan sopivan reverberaatioefektin läpi—efekti hajauttaa tiedon ajassa tavalla joka on helposti käännettävissä, ja jossa bittien vaikutus jakautuu ajassa toivotulla tavalla sekä pseudosatunnaisesti. Sitten olin ajatellut, että tuon ajatuksen saisi jotenkin pyöristettyä bittivirraksi, kenties satunnaistaen. Dekoodaus olisi pohjimmiltaan vastakkainen suodatin Z2:ssa, joka pitäisi ylipäästösuodatettua tai tunnettuihin symboleihin kohdistuvaa redundanssia suoraan merkkinä virheestä, jonka voisi sitten ihan vain pyöristää pois ja syöttää takaisin ajassa lisäpyöristyksiä varten.

Kaunis intuitio, mutta mitä enemmän mietin, sitä vähemmän tuo tuntuu toimivan.

Uudempi ajatus

Tässä välissä on sitten tullut luettua heikan meikat radiojuttuja, ml. koodausteoria. Siltä puolelta alan vihdoinkin ymmärtää miten ja miksi Trellis-koodattu modulaatio toimii. Kun siinä sitten sekoitetaan todella koodaus ja modulaatio iloisesti toisiinsa, mieleen yhtäkkiä tuli…

Miksi ihmeessä mun oikeastaan tarttis pyöristää biteiksi ylipäänsä? Mitäs jos se koodaus sinänsä tehdään jatkuvassa ajassa konvoluutiona? Toki toteutetaan digitaalisesti koska muuten tosta systeemistä ei tule tarkkaa, mutta yksinkertaisesti ajetaan se konvoluutio suoraan ulos D/A:sta jatkuvana signaalina, ja sitten toisella puolella A/D:n kautta sisään?

Ja siis, itse asiassa, tässä on nyt sellainenkin hauska, että hyvin suunnitellut reverb-hännät ovat pseudorandomia niin että niiden autokorrelaatiofunktio on jokseenkin impulssi. Ne voidaan skaalata niin, että ne eivät hukkaa tai luo energiaa. Ne eivät luo uusia taajuuksiakaan kun ovat lineaarisia. Ne ovat tuskallisia toteuttaa riittävään numeeriseen tarkkuuteen, varsinkaan häviöttömästi, näin pitkillä impulssivasteilla, mutta musiikkisignaalinkäsittelystä löytyy kyllä pitkät pätkät kaikenlaista hyödyllistä sovellusta varten. FFT-OLA/OLS mahdollistaa suorastaan suunnitellun FIR-vasteen käyttämisen, kymmeniä sekunteja pitkiin vasteisiin—joskin tuo on audiotaajuista signaalia varten eli ei edusta järin paksua datavirtaa. Toisaalta me lhdetään biteistä eikä täysistä sampleista, eikä akustiikka kiinnosta vaan vain häipyvä allpass-vaste ja tehokkuus.

Kun itse asiassa mietin kirjoittaessani, se ylisamplaus ei ehkä ole oikein ratkaisu, koska tässä muodossaan se jättää kaistaa vain käyttämättä. (Vai onko? Sehän se miehekästä olisi jos ton systeemin redundanssi ois just siinä että kaistan tiedetään olevan tietyn pisteen yläpuolelta nolla, jolloin sitä ei tarvitse lähettää!) Ehkäpä pitäisi käyttää vain suosiolla täysikaistaisia pulsseja, mutta harvemmin? Silloin pulssimuoto varmaankin olisi raised-cosine -tyyppiä, koska siitä saadaan täsmälleen ylimääräsen kaistan levyinen ja Nyquistin ISI-kriteerion täyttävä samanaikaisesti ja helposti. Vai pitäisikö se yläkaista jotenkin sitoa epälineaarisesti alempaan? Hmm…

Oli miten oli, tuossa systeemissä vastaanottimen käänteissuodatin (allpass-suodattimella sama kuin matched!) hajottaa virheet niin, että periaatteessa ne pitäisi olla mahdollista ihan vain pyöristää pois (tiukimmalla, molemminpuolisella!) slicerillä. Toi systeemi on välttämättä partial response ja IIR molempiin suuntiin jollei pyöristetä häntää pois, mutta niin systemaattinen/lokaali se kyllä on kuin vain voi. Osittaindekoodatessa homma menee niin, että käännetään tietty lohko, slicetetään bittiarvoihin, ja syötetään poistettu virhe hamaan tulevaisuuteen negatiivisena koodaussuodattimen läpi. Käännettävän sen pituus määrää koodausviiveen, ja molemmat suodattimet voi toteuttaa nollaviiveisellä FFT-konvoluutiolla. Jos kanava on valikoiva, optimivastaus on Wiener-suodatin, joka pohjimmiltaan on yhdistelmä alkuperäistä signalointipulssia systeemivasteen osoittajassa (matched-osa) ja kohinan valkaisua (inverse-osa) nimittäjässä; tuo johtaa ideaalitilanteessa samaan kuin ylläoleva päättely, kaistarajoituksine kaikkineen, samalla kun yleisessä tilanteessa se on todistettavasti optimaalinen kuitenkin; suodattimen voi jakaa halutulla tavalla lähettimen ja vastaanottimen kesken, tyyliin valkaisu prefiltteriksi että lähetetään vain niillä taajuuksilla joilla on signaali–kohina-suhdetta, ja erit. niillä joilla vaste ei häivy. Kohina voi edelleen tuottaa ongelmia esim. virhepropagaation muodossa, varsinkin kun allpass-suodattimet välittävät kohinaenergian läpi sellaisenaan (paitsi että kaistarajoitus poistaa siitä aina redundanssin verran), mutta tuon ei pitäisi olla iso ongelma kun vaste kuitenkin häviää nopeasti (?) ajassa ja takaisinsyötön magnitudi voidaan rajoittaa väkisin noita tilanteita silmälläpitäen. Optimaalinen dekoodaus saattaisi edellyttää iteraatiota ajassa eteen- ja taaksepäin, mutta vähän luulisin että mulkkaamalla (pisteittäistä!) pyöristysfunktiota (yksi muoto soft-decodingista), kenties ditheröimällä, ja ottaen huomiooon että joka iteraation osana korkeampi signaalienergia pyöristetään kaistarajaan ja vastekin kuolee eksponentiaalisesti ajassa, tuosta voisi olla kenties jopa mahdollista näyttää että prosessi konvergoituu maximum likelihood -mielessä korkealla todennäköisyydellä nopeasti&ndashd;karsean kaunis tulos jos se on mahdollista saavuttaa.

Parina variaationa vois miettiä sitäkin että pulssit ovat koko kaistan levyisiä ja suodatin sopiva niiden ilmaisuun, sillä synkronisaationäkökohdat, bipolaarista signalointia, ja sitä että dekooderi katselisi lisätyn kokonaisenergian määrää (helppoa koska allpass-rakenne, mutta ehkä siksi jopa tarpeetonta). Myös L1-normiin -perustuvia optimointialgoritmeja voisi periaatteessa kokeilla, kun niillä on hiukkasen samaa rakennetta (vrt. esim. iterative shrinkage -tyyppiset algoritmit). Samoin, jos tuosta vaihtuvasta dekoodausviiveestä tingitään, epäilemättä olisi tehokkaampaa käyttää filtterinä syklistä FFT-konvoluutiota ihan vain sattumanvaraisilla vaiheviiveillä, koska niin laskennallisesti kuin koodausviiveellä annettuun virhetiheyteen ei-häipyvä vaste allpass-suodattimella sotkee kyllä lyhyellä aikavälillä tehokkaammin virheet ja datan keskenään.

Ylipäänsä viimein kaikki toi koneisto on ihan jäätävän simppeliä sekä tehokasta suhteessa siihen kuinka joustavaa se on. Jos toi toimis edes vähän sinnepäin, oijoi, oltais yhtäkkiä tasan aikakirjoissa!

Post scriptium: Yksinkertaisempi analyysi

Oletetaan että käytössä on kaistarajaamaton kanava ja tietty määrä energiaa per bitti, joka menee absoluuttisen Eb/N0-rajan yli (muistaakseni circa -0.58dB). Täydellinen koodi olisi lähettää signaali sarjana tuon energian kantavia delta-funktioita, koska ne ylittävät minkä tahansa jatkuvan valkoisen kohinan hetkellisen tason; siirto olisi täydellinen ihan vain koodaamatta yhtään mitään, sikäli kuin signaali saataisiin näytteistettyä ajassa niin että pätkääkään jatkuvaa lisäkohinaa ei pääse mukaan.

Fysikaalisesti tällainen järjestelmä on tietenkin mahdotonta toteuttaa, koska sen hetkellinen lähetysteho on ääretön, kuten on kaistanleveyskin, ja niin on vielä vastaanottimelta vaadittava nopeuskin. Joten sen sijaan tyydymme levittämään tutkajärjestelmistä tutulla tavalla noiden pulssien energian ajassa ("pulse compression"), kunnes keskimääräinen tehorajoite tavataan. Tämä onnistuu äärettömällä kaistanleveydellä jo varsin lyhyillä allpass-vasteilla (tässä vielä epämääräinen käsite, mutta menkööt toistaiseksi). Seuraavaksi rajaamme signaalin kaistanleveyden äärelliseksi, jolloin kanavalle ilmaantuu äärellinen kapasiteetti. Lisäksi teemme hienoisen approximaation siinä, että hetkellinen tehokin on rajattu eikä vain keskimääräinen; tämä arvio ei ole järin rajoittava koska AWGN-kanava hankaluudestaan huolimatta saa äärimmäisiä arvoja vain harvoin ylärajan funktiona.

Periaatteessa nyt pitäisi käydä samalla niin, että pulssikompression minimipituudelle ilmaantuu myös alaraja. Näin siksi, että rajatulla kaistalla esiintyy vakiomäärä innovaatiota signaalista ja melusta per aikayksikkö. Jos hajautus ajassa ei ole riittävää, yksinomaan näytteistetyn signaalin (eli sen rekonstruktioon tarvittavan sinc(x)-funktion) hajautuneisuus tuo tietyn määrän epävarmuutta näytteistysajan ulkopuolelta mihin vain äärelliseen ikkunaan. Niinpä, vaikka kohinattoman kaistarajatun kanavan kokonaistilan pystyy periaatteessa päättelemään kuin lyhyeltä ajalta otettujen riittävän monien näytteiden perusteella (johtuu kaistarajattujen signaalien analyyttisyydestä, joka mahdollistaa niiden pohjattoman ekstrapoloinnin ajassa), kohinan läsnäollessa pitäisi keskimäärin käydä niin, että signaali on hajautettava ajassa eksponentiaalisesti laskevasti, jotta se voidaan rekonstruoida kasvattamatta optimaalisen rekonstruktion kohinaa rekompaktoidusta energiasta enempää kuin tietty kiinteä raja. Tuon rajan luulisi määräytyvän suoraan kaistanleveys–teho—aika-symmetriasta, eli olevan epätarkkuusperiaatteen yksi versio.

Tuosta eteenpäin konstruktio etenee kuten yllä. Käytämme pulssikompressioon eksponentiaalisesti häipyvää AWGN-signaalia, josta saadaan ortogonaliteetti peräkkäisten pulssien välillä kaikkien valittujen kaistojen sisällä automaationa. Ainoa probleemi on ISI, mutta sehän tietysti menee nolliin kun valitaan pohjimmainen signalointitaajuus ennen hajautusta Nyquist-kriteerion mukaan.

Viimein, käytännölliseen kanavaan saatetaan tarvita jotakin duobinaryn tapaista että tiukat suodatinrajat natsaavat. Myös laajennos korkeamman SNR:n kanaviin pitää miettiä. Mutta periaatteessahan niitä voi arvioida venyttämällä koodia ja säätämällä käytettyä energiaa, sekä tietysti menemällä kapasiteettia lähestyvästä tilanteesta N kertaa niin moneen PAM-signaloinnin tasoon; todistuksen ei pitäisi muuttua, ja tilaa interpolaatiolle diskreettien ratkaisupisteiden välillä pitäisi olla reippaasti. Valittu rajattu dekoodausvirhe selvenee sitten luonteeltaan niin, että varsinaisen inversion pituus määrää kuinka suuri osa hajautetun pulssin energiasta todella rekompaktoidaan, minkä jälkeen pyöritys digitaalisiksi signaaleiksi tuottaa annetun eksponentiaalisesti laskevan virhetason, ja syöttö takaisin käsittelemättömän dekooderihännän läpi vähentää koodauksen itselleen tuottamaa jäännösvirhettä, muttei vähennä virhettä kohti kapasiteettirajaa, koska kyseinen virhe vain poistettaan tulevista laskuista, ei rekompaktoida auttamaan S/N-tasoa. Dekoodauksen pitäisi vieläpä noiden eksponentiaalisesti laskevien häntien tähden olla varsin vakaa, sen sijaan että menisi katastrofaaliseksi kuten monissa muissa päätösorientoituneissa raameissa. Joskin tietty se 1/T-termi, joka tulee Nyquist-pulssin rakenteesta ja laskee hitaasti, mutta se nyt on muutenkin jo välttämättä rakennettu sisään itse näytteistykseen, eli laskee siedettäville tasoille yhtä nopeasti kuin A/D:si konvergenssi ylipäänsä, niin että varsinkaan nopeilla näytteistystaajuuksilla sen ei pitäisi käytännössä kohota merkittäväksi suhteessa realistisesti käytettyjen hajautussekvenssien pituuteen.

Ainiin, se tarpeellinen redundanssi…

Tosiaan niin, kun toimitaan kohisevassa kanavassa, joka on myös kaista- ja energiarajattu niin että sille syntyy kapasiteetti, se ei yksinään riitä että hajotetaan tällä tavalla energiaa ajassa. Ylläkin puhun decision–feedback -tyylin päättelystä, joka on erittäin epälineaarinen operaatio, ja tähtää hälyn poispyöristämiseen enemmän tai vähemmän optimaalisesti. Omassa raamissani jopa siihen, että skalaarinen kvantisointi riittäisi energian LTI-rekompaktion kanssa tekemään temput.

Mutta–mutta, miten tismalleen hoitaa sellaiset kanavat joissa se hyötysignaali on haudattu kauas kohinan alle? Tai ylipäänsä hoitaa se perusongelma, että vaikka meillä on pari gaussilaista signaalia, kohina ja hyöty, joilla on teoreettisesti riittävä ero energiassaan per bitti, miten vaikkapa vaihtaa sitten kaistanleveyttä, tehoa ja aikaa toisiinsa luontevasti? Tuo vaatii koodausta ja sen teoriaa; eritoten jonkinlaista redundanssin käsitettä joka sopii kivasti yhteen raamini kanssa. Tähän asti en tullut puhuneeksi siitä miten tuolla tavalla jatkuvassa raamissa voitaisiin tuottaa rendundanssia, vaikka aiemmissa ajatuksissani keskityin juuri siihen.

Enpä vielä täysin tiedä, tässä raamissa. Mutta eka intuitio olisi että signaloidaan sitten hitaammin kuin kaista vaatii. Tuo voisi mennä päällekkäisillä pulsseilla, duobinary-partial-response-tyyliin tjsp. Mutta itse asiassa vähän luulen että eka jota pitäisi kokeilla olisivat raised–cosine -tyyliset pulssit. Nyt vain käytettynä hiukka väärin päin. Niitä kun yleensä käytetään niin, että ne myötäävät kaistarajaa Nyquist-pulsseista ylöspäin. Mutta mitäs jos niitä käytettäisiinkin tarkoituksella sillä tavalla alaspäin, että tarvittava kaista menisi alaspäin, kuten signalointitaajuuskin, ja konstruktion ehdoton, tarkka, kaistaraja sekä erillinen signalointitaajuus täyttäisivät mun systeemissä varatun kokonaiskaistan, by design? Tuolloin raised-cosinen basebandissa varaama (äärellinen, tarkka) lisäkaista olisi se redundanssi jota vastaan koodauksessa voidaan vaihtaa muita juttuja.

Noin suunnitellen signalointinopeudella voitaisiin edelleen täysin pyöristää skalaarisesti niin kohinan kuin dekoodaamattoman itseaiheutetun hälynkin energia pois; "silmä" olisi dekonvoluution/matched-filterin jälkeen edelleen täysin auki, ja ainoa virhe kohinan sekä dekonvoluutioikkunan trunkaation aiheuttamaa. Se olisi eksponentiaalisesti häipyvää kaikki, eli ei johtaisi vaikeasti korjattavaan virhepropagaatioon myöskään, vaikka toi systeemi muuten onkin aika epämiellyttävän oloista partial response -kamaa. Epäilen, että kun toi on niin suoraa ja lähes-lineaarista matikkaa, siitä vois osoittaa aika helposti jopa jotain optimaalisuustuloksia—ja jollei heti kanna, ainakin toi näyttää suuntaa johonkin kivaan jota en ole aiemmin nähnyt.

Isoin ongelma varmaankin on, miten optimaalisesti käyttää hyväksi sitä indusoitua jatkuvan ajan koodia. Mä olen nyt sanonut, että se energiakompaktio on lupaava intuitio, kuten on bitin energian jakaminen pitkillä eksponentiaalisesti häipyvillä LTI-impulssivasteillakin, jossain suhteessa signalointinopeuteen ja signalointiperiodin sisällä vastaan tappelemaan gaussisen melun tuottamaan lisävirhetodennäköisyyteen. Mä epäilen että toi indusoi tietyn enimmäkseen lineaarisen rakenteen, josta on tavallista helpompaa päätellä mikä meni pieleen, ihan vain invertoimalla ja pyöristämällä virheet ajassa pois (poispyöristetyt virheet korreloivat alkuperäisen virheen kanssa vaikka flippaisivat bitin. Viimeistäänkin jonkin iterative shrinkage -tyylin algoritmin pitäisi siinä dekoodausikkunassa ajaa pienin mahdollinen määrä bittejä ympäri, samalla kun kohina pyöristyy pois. Hintana olisi pallottelu koodaussuodattimen yli useampia kertoja.

No comments:

Post a Comment