Den Finite-State Markov Channel (FSMC) är en diskret tid varierande kanal vars variation bestäms av en nite-state Markov process. Dessa kanaler har minne på grund av kanalvariationen i Markov. Vi får FSMC kapacitet som en funktion av den villkorliga kanal tillstånd sannolikhet. Vi visar det också för I.I.D. kanalingångar, denna villkorade sannolikhet konvergerar svagt, och kanalens ömsesidiga information är då en sluten form kontinuerlig funktion av indatadistributionen. Vi överväger därefter att koda för FSMC:er. I allmänhet, komplexiteten av maximal-likelihood avkodning växer exponentiellt med kanalminnet längd. Därför används i praktiken interleaving och minneslösa kanalkoder. Denna teknik resulterar i viss prestandaförlust i förhållande till den inneboende kapaciteten hos kanaler med minne. Vi föreslår en maximal-likelihood beslutfeedback dekoder med komplexitet som är oberoende av kanalminnet. Vi beräknar kapaciteten och cuto-hastigheten av vår teknik, och visar att den bevarar kapaciteten hos vissa FSMCs. Vi jämför också prestanda av beslut-feedback dekoder med den av interleaving och minneslösa kanalkodning på en blekningskanal med 4PSK modulation. Index Termer: Finite-State Markov Channels, Kapacitet, Ömsesidig information, Beslut-Feedback Maximum-Liknande Decoding. Gilbert-Elliot Channel Låt x n 2 f0; 1g, y n 2 f0; 1g och z n = x n y n betecknar respektive kanalinmatning, kanalutmatning och kanalfel vid den n:te överföringen. I 1], kapaciteten hos Gilbert-Elliot kanalen härleds som C = lim n!1 1? E h(q n )] = 1? E h(q 1 )); där h är entropifunktionen, q n = p(z n = 1jz n?1 ), konvergerar q n till q 1 i distributionen, och q 1 är oberoende av det ursprungliga kanaltillståndet. I detta dokument härleder vi kapaciteten hos en mer allmän nite-state Markov-kanal, där kanalstaterna inte nödvändigtvis är BSC. Vi modellerar kanalen som en Markov kedja S n som tar värden i en nite tillstånd utrymme C minneslösa kanaler med nite ingång och utgång alfabet. Den villkorliga input/output sannolikhet är alltså p(y n jx n ; S n ), där x n och y n betecknar kanalen input respektive utdata. Sannolikheten för kanalövergång är oberoende av indata, så vår modell inkluderar inte ISI-kanaler. Vi hänvisar till kanalmodellen som en nite-state Markov kanal (FSMC). Om sändaren och mottagaren har perfekt tillståndsinformation, då kapaciteten hos FSMC är bara det statistiska genomsnittet över alla tillstånd av motsvarande kanalkapacitet 2]. Å andra sidan, utan någon information om kanaltillståndet eller dess övergångsstruktur, minskas kapaciteten till kapaciteten för godtyckligt Varierande kanal 3. Vi betraktar det mellanliggande fallet, där kanal övergångsstrukturen för FSMC är känd. Minnet av FSMC kommer från beroendet av det nuvarande kanaltillståndet på tidigare ingångar och utgångar. Som ett resultat, entropin i kanalens utgång är en funktion av kanaltillståndet som är beroende av alla tidigare utgångar. På samma sätt bestäms den villkorliga utdataentropin med tanke på indatan av kanalstatens sannolikhet beroende på alla tidigare indata och utdata. Vi använder detta faktum för att få en formel för kanalkapacitet i termer av dessa villkorliga sannolikheter. Vår formel kan beräknas rekursivt, vilket avsevärt minskar dess beräkning komplexitet. Vi visar också att när kanalingångarna är i.i.d., dessa villkorliga tillstånd sannolikheter konvergerar i distributionen, och deras gränsfördelningar är kontinuerliga funktioner i indatadistributionen. Alltså, för alla i.i.d. input distribution, den ömsesidiga informationen om FSMC är en sluten form kontinuerlig funktion av. Denna kontinuitet tillåter oss att nd I iid, maximal ömsesidig information i förhållande till 2 alla i.i.d. Indatadistributioner, med hjälp av enkla maximeringsmetoder. Eftersom jag iid < C, vårt resultat ger en enkel lägre gräns för kapaciteten hos allmänna FSMCs. Gilbert-Elliot-kanalen har två funktioner som underlättar dess kapacitetsanalys: dess villkorliga entropi H (Y n jX n ) är oberoende av indatadistributionen, och det är en symmetrisk kanal, så en enhetlig indatadistribution inducerar en enhetlig utdatadistribution. Vi utökar dessa egenskaper till en allmän klass av FSMCs och visar att för denna klass, I iid motsvarar kanalen kapacitet. Denna klass omfattar kanaler som varierar mellan varje nit antal BSC, samt kvantiserade additiva vita bruskanaler (AWN) med symmetriska PSK-ingångar och tidsvarierande bullerstatistik eller amplitud blekning. I princip är kommunikation över en nite-state kanal möjlig i vilket fall som helst under kanalens kapacitet. Men bra maximal-likelihood (ML) kodningsstrategier för kanaler med minne är kult att bestämma, och dekoder komplexiteten växer exponentiellt med minneslängd. Således är en gemensam strategi för kanaler med minne att sprida minnet med hjälp av en interleaver: om spännvidden för interleaver är lång, då kaskaden av interleaver, kanal, och deinterleaver kan betraktas som minneslösa, och kodning tekniker för minneslösa kanaler kan användas 4. Denna kaskadkanal har dock en lägre inneboende Shannonkapacitet än den ursprungliga kanalen, eftersom kodning är begränsad till minneslösa kanalkoder. Komplexiteten i ML-avkodning kan minskas avsevärt utan denna kapacitetsnedbrytning genom att genomföra en beslut-feedback-dekoder, som består av en rekursiv uppskattning av den kanalstatsfördelning som är beroende av tidigare ingångar och utgångar, följt av en ML-dekoder. Vi kommer att se att uppskattningen n = p(S n jx n?1 ; : :; x 1 ; y n?1 ; : :; y 1 ) är en lämplig statistik för ML dekoder indata, med tanke på alla tidigare ingångar och utdata. Därför fungerar ML-dekodern på ett minneslöst system. Den enda ytterligare komplexiteten i detta tillvägagångssätt över den konventionella metoden för interleaving och minneslös kanalkodning är rekursiv beräkning av n. Vi kommer att beräkna kapacitetspåföljden för beslut-feedback dekoder för allmänna FSMCs (oavsiktlig felutbredning), och visa att denna påföljd försvinner för en viss klass av FSMCs. Det vanligaste exemplet på en FSMC är en korrelerad blekningskanal. I 5] föreslås en FSMC modell för Rayleigh blekning, där kanaltillståndet varierar över binära symmetriska kanaler med olika crossover sannolikheter. Vår rekursiva kapacitetsformel är en generalisering av kapaciteten som finns i 5] och vi bevisar också konvergensen av deras rekursiva algoritm. Eftersom kapaciteten i allmänhet är ouppnåelig för alla praktiska kodningsprogram, anger kanalfrekvensen den praktiska informationshastigheten för en kanal med kodning. Cuto-hastigheten för korrelerade blekningskanaler med MPSK-ingångar, under antagande om kanaltillståndsinformation vid mottagaren, erhölls i 6]: vi får samma cuto-hastighet på denna kanal med hjälp av beslut-feedback-avkodning. De flesta kodning tekniker för blekning kanaler förlitar sig på inbyggd tidsmångfald i koden för att minska den blekning eekt. Kodkonstruktioner av denna typ finns i 7, 8, 9] och hänvisningarna i den. Dessa koder använder samma tidsdiversitetsidé som interleaving och minneslös kanalkodning, förutom att mångfalden implementeras med koden metrisk istället för interleaver. Liksom med interleaving och minneslös kanalkodning ignoreras således information om kanalkorrelation med dessa kodningsprogram. Maximal-likelihood sekvensuppskattning för blekning kanaler utan kodning har undersökts i 10, 11]. Det är dock svårt att genomföra kodning med dessa system på grund av kodförseningar. I vårt system resulterar inte kodningsförseningar i statliga beslutsförseningar, eftersom besluten baseras på uppskattningar av kodade bitar. Vi kan införa kodning i vårt beslut-feedback-system med en därav följande ökning av fördröjning och komplexitet, som vi kommer att diskutera i 3 xV I. Resten av tidningen är organiserad enligt följande. I xII vi de ne FSMC, och få vissa egenskaper i kanalen baserat på denna denition. I xIII härleder vi ett rekursivt förhållande för fördelningen av kanaltillståndet beroende på tidigare ingångar och utgångar, eller enbart på tidigare utgångar. Vi visar också dessa villkorade statliga distributioner konvergera för att begränsa distributioner för i.i.d. kanalingångar. I xIV får vi kapaciteten för FSMC när det gäller tillstånd fördelningar, och få en enkel formel för I iid. Enhetligt symmetriskt variabelt buller FSMCs är de ned i xV. För denna kanalklass (som inkluderar Gilbert-Elliot-kanalen) uppnås kapacitet med enhetlig i.i.d. kanalingångar. I xV I presenterar vi beslut-feedback dekoder, och få kapacitet och reducering straff för beslut-feedback avkodning systemet. Dessa påföljder försvinner för enhetliga symmetriska variabla ljudkanaler. Numeriska resultat för kapaciteten och cutohastigheten för en tvåstatsvariabel ljudkanal med 4PSK modulering och beslut-feedback avkodning presenteras i xV II. Låt S n vara tillstånd vid tidpunkten n av en irreducible, aperiodic, stationär Markov kedja med tillstånd utrymme C = fc 1 ; : :; c K g S n är positiv återkommande och ergodic. Tillståndsutrymmet C motsvarar K di erent diskreta minneslösa kanaler (DMC), med vanliga nite-ingångs- och utgångsalfabet som betecknas med X respektive Y. Låt P vara matrisen för övergångssannolikheterna för S, så P km = p(S n+1 = c m jS n = c k ); oberoende av n genom stationaritet. Vi betecknar input och output av FSMC vid tidpunkten n av x n respektive y n, och vi antar att kanalen indata är oberoende av dess tillstånd. Vi kommer att använda notationen r n 4 = (r 1 ; : :; r n ) och r n+m m 4 = (r m ; : :; r n+m ) för r = x; y; eller S. FSMC bestäms av dess villkorade input/output sannolikhet vid tiden n, som bestäms av kanaltillståndet vid tiden n: p(y n jx n ; S n ) = X k2K p k (y n jx n )I S n = c k ]; där p k (yjx) = p(yjx; S = c k ), och I ] betecknar indikatorfunktionen (I S n = k ] = 1 om S n = c k och 0 annars). Minnet av FSMC beror på Markovs struktur av statsövergångar, vilket leder till ett beroende av S n på tidigare värden. FSMC är minneslös om och endast om P km = P jm för alla k, j och m. Nite-state Markov kanal illustreras i figur 2. Enligt antagande är tillståndet vid tidpunkten n + 1 oberoende av tidigare in-/utgångspar när det konditioneras på S n : p(S n+1 jS n ; x n ; y n ) = p(S n+1 jS n ): Eftersom kanalerna i C är minneslösa, p(y n+1 jS n+1 ; x n ; S n ; x n ) = p(y n+1 jS n+1 ; x n+1 ): Om vi också antar att x n s är oberoende, då p(y n+1 ; x n+1 jS n+1 ; S n ; x n ; y n ; y n ) = p(y n+1 ; x n+1 ): p(y n ; x n jS n +1 ); och p(y n+1 jS n+1 ; S n ; y ) = p(y n+1 jS n+1 ): Den villkorade kanalens fördelning är nyckeln för att fastställa FSMC:s kapacitet genom en rekursiv algoritm. Det är också en tillräcklig statistik för indata med tanke på alla tidigare indata och utdata, vilket gör det möjligt att minska komplexiteten i beslut-feedback dekoder. I detta avsnitt visar vi att den tillståndsfördelning som är villkorad av tidigare in-/utgångspar kan beräknas med en rekursiv formel. En liknande formel härleds för den tillståndsfördelning som är villkorad enbart av tidigare utgångar, under antagande av oberoende kanalingångar. Vi visar också att dessa statsdistributioner konvergerar svagt under i.i.d. Ingångar, och den resulterande gränsfördelningen är kontinuerliga funktioner i indatadistributionen. Vi betecknar dessa villkorade tillståndsfördelningar med K-dimensionella slumpmässiga vektorer n = ( n (1); :; n (K) och n = ( n (1); : :; n (K) respektive där n (k) = p(S n = c k jy n?1 ) (9) och n (k) = p(S n = c k jx n?1 ; y n?1 ): Följande rekursiva formel för n härleds i tillägg 1. n+1 = n D(x n ; y n )P n D(x n ; y n )1 4 = f(x n ; y ; n ); där D(x n ; y n ) är en diagonal K-matris med kth diagonala p k (y n jx n ), och 1 = (1; : : :; 1) T är en K-dimensionell vektor. Ekvation (11) 1 (x n ; y n ) : f(x n ; y n ; ) = ]p(y n n n = ; x n )p(x n ): Observera att (12) är oberoende av n för stationära ingångar. För oberoende ingångar finns en liknande rekursiv formel för n: n+1 = n B(y n )P n B(y n )1 4 = f(y n ; n ); (13) där B(y n ) är en diagonal K K matris med kth diagonal term p(y n jS n = c k ) 1. Härledning av (13) liknar den i (11) i tillägg 1, där (8) används i stället för (5) och alla x-termer tas bort. Variabeln n tar också värden på tillståndsutrymmet, med initialvärde 0 = 0 och övergångssannolikhet p( n+1 = j n = ) = X yn2Y 1 y n :f(y n ; ) = ]p(y n j = ): När det gäller n är övergångssannolikheterna i (14) oberoende av n när ingångarna är stationära. Vi visar i bilaga 2 att för i.i.d. Indata, n och n är Markov-kedjor som konvergerar i distribution till gränser som är oberoende av det ursprungliga kanaltillståndet, under vissa milda begränsningar på C. Dessa konvergensresultat innebär att för alla avgränsade kontinuerliga funktioner f, finns följande gränser och är lika för alla i: och lim där i n = p(S n jx n?1 ; y n?1 ; S 0 = c i ) och i n = p(S n jy n?1 ; S 0 = c i ). Denna konvergens gör det möjligt för oss att få en sluten lösning för den ömsesidiga informationen enligt i.d. Ingångar. Vi visar också i Lemmas A2.3 och A2.5 i bilaga 2 att gränsfördelningarna för och är kontinuerliga funktioner i indatadistributionen. Lemmas A2.6 och A2.7 i tillägg 2 visar det överraskande resultatet att n och n inte nödvändigtvis är Markovkedjor när indatadistributionen är Markov. Eftersom den svaga konvergensen mellan n och n kräver denna Markov-fastighet gäller (15) och (16) inte allmänna Markov-indata. IV Entropi, ömsesidig information och kapacitet Vi härleder nu kapaciteten hos FSMC baserat på distributionerna av n och n. Vi får också några ytterligare egenskaper hos entropi och ömsesidig information när kanalen indata är i.i.d. Genom avgränsning är Markovkedjan S n en periodisk och oersättlig över ett nite tillstånd utrymme, så eekten av dess ursprungliga tillstånd dör bort exponentiellt med tid 12]. Därför är FSMC en Följande lemma, som visas i tillägg 3, gör det möjligt att skriva den ömsesidiga informationen i termer av n och n. Använda denna lemma i (19) och (20) och ersätta i (18) ger följande teorem. Teorem 4.1 Kapaciteten hos FSMC ges av var beroendet av 2 P(X n ) av distributionerna för i, i, och y i är implicit. Detta kapacitetsuttryck är lättare att beräkna än Gallager formel (17), eftersom i termer kan beräknas rekursivt. Den rekursiva beräkningen för i kräver oberoende indata. Men för många kanaler av intresse H(Y i j i ) kommer att vara en konstant oberoende av indatadistributionen (sådana kanaler diskuteras i xV ). För dessa kanaler minskar kapacitetsberäkningen till att minimera den andra termen i (23) i förhållande till indatadistributionen, och komplexiteten i denna minimering minskar kraftigt när jag kan beräknas enkelt. Med hjälp av Lemma 4.1 kan vi också uttrycka kapaciteten som (28) Nästa lemma bevisas med hjälp av konvergensresultaten för n och n och en förändring av variablerna i entropiuttrycken (26) och (28). (? log p(yjx; ))p(yjx; ) (x) (d); (29) där superscript på n, n, och p (yj ) visar sitt beroende av indatadistributionen, betecknar den begränsande fördelningen av n, och betecknar den begränsande fördelningen av n. Vi kombinerar nu ovanstående lemmas för att få en sluten form uttryck för ömsesidig information enligt i.i.d. Ingångar.  Att tillämpa Lemmas 4.1 och 4.6 kompletterar beviset. 2 Det är lätt att visa att eftersom och är kontinuerliga funktioner, Jag är också. Dessutom är beräkningen av I relativt enkel, eftersom asymptotiska värden av och erhålls med rekursiva formler (12) respektive (14). För den kanal som beskrivs i xV II närmar sig dessa rekursiva formler nära sina nationella värden efter endast 40 iterationer. Tyvärr, denna förenkling formel för ömsesidig information under i.i.d. Indata kan inte utsträckas till Markov-ingångar, eftersom n och n inte längre är Markov-kedjor under dessa förhållanden. Eftersom P(X) är kompakt och jag kontinuerlig i, Iid uppnår sin supremum på P(X), och maximeringen kan göras med hjälp av standardtekniker för kontinuerliga funktioner. Dessutom är det lätt att visa att I iid C. Således (35) ger en relativt enkel formel för att sänka kapaciteten hos allmänna FSMC. Nästa avsnitt kommer att beskriva en klass av kanaler för vilka uniform i.i.d. kanalingångar uppnå kanalkapacitet. Således, I iid = C, och kapaciteten kan hittas med hjälp av formeln för Theorem 4.2. Denna kanalklass omfattar blekning eller variabla ljudkanaler med symmetriska PSK-ingångar, samt kanaler som varierar över en nite uppsättning BSC. I detta avsnitt de ne två klasser av FSMC: jämnt symmetriska kanaler och variabla ljudkanaler. Den ömsesidiga informationen och kapaciteten hos dessa kanalklasser har ytterligare egenskaper som vi beskriver i lemmas nedan. Dessutom kommer vi i nästa avsnitt att visa att beslut-feedback-dekodern uppnår kapacitet för enhetligt symmetriskt variabelt buller FSMC. Definition: En FSMC är jämnt symmetrisk om varje kanal c k 2 C är symmetrisk. Nästa lemma, som visas i bilaga 5, visar att för enhetligt symmetriska FSMC:er maximeras den villkorliga utgångsentropin med likformigt i.i.d. Ingångar. Lemma 5.1 För enhetliga symmetriska FSMC och alla initialtillstånd S 0 = c i, H(Y n j n ), H(Y n j i n ), H(Y n j n ), och H(Y n j i n ) är alla maximerade för en enhetlig och i.i.d. indatafördelning, och dessa högsta värden är lika med log jYj. Denition: Låt X n och Y n beteckna ingång och utgång, respektive, för en FSMC. Vi säger att en FSMC är en variabel ljudkanal om det finns en funktion sådan att för Z n = (X n ; Y n ), p(Z n jX n ) = p(Z n ) och Z n är en lämplig statistik för S n (så S n är oberoende av X n och Y n ges Z n ). Vanligtvis förknippas med en additiv bruskanal, som vi diskuterar mer i detalj nedan. Om Z n är en lämplig statistik för S n, då n 4 = p(S n jX n?1 ; Y n?1 ) = p(S n jX n?1 ; Y n?1 ; Z n?1 ) = p(S n jZ n?1 ): Använda (36) och ersätta paren (X n ; Y n ) med Z n i härledning av bilaga 1, kan vi förenkla rekursiv beräkning av n : där D(z n ) är en diagonal K K matris med kth diagonal term p(z n jS n = c k ). Övergångsannolikheterna är också enkla: p( n+1 = j n = ) = X zn2Z 1 (z n ) : f(z n ; ) = ]p(z n j n = ): Nästa lemma, som visas i tillägg 5, visar att för en enhetlig symmetrisk variabel bruskanal, den utgående entropi som konditioneras på indata är oberoende av indatadistributionen. Lemma 5.2 För enhetligt symmetriskt variabelt buller FSMC och alla i, H(Y n jX n; n) och H(Y n jX n; i n) är inte beroende av indatadistributionen. Överväga en FSMC där varje c k 2 C är en AWN kanal med bullertäthet n k. Om vi låter Z = Y? X, då är det lätt att visa att detta är en variabel ljudkanal. Men sådana kanaler har ett i nite utdata alfabetet. I allmänhet är utgången av en AWN kanal kvantifieras till närmaste symbol i en nite utdata alfabet: vi kallar detta den kvantiserade AWN (Q-AWN) kanal. Om Q-AWN-kanalen har ett symmetriskt flerfasingångs alfabet av konstant amplitud och utdatafasquantization 4, sidan 80], då är det enkelt att kontrollera att p k (yjx) bara beror på p k (jy? xj), som i sin tur beror endast på bullertäthet n k. Således är det en variabel bruskanal 3. Vi visar i bilaga 6 att variabelt buller Q-AWN kanaler med samma ingång och 2 Symmetriska kanaler, de ned i 13, p. 94], är en mer allmän klass av minneslösa kanaler; en utgång symmetrisk kanal är en symmetrisk kanal med en enda utgång partition. Vad är det med dig? H(Y n jX n; n) (40) ökar med n, och C i n 4 = max H(Y n j i n)? H(Y n jX n ; i n ) (41) minskar med n. Bevis från Lemmas 5.1 och 5.2, C n, C i n, och C är alla maximerade med enhetlig i.i.d. Ingångar. Med denna ingångsdistribution, C n = log jYj? H(Y n jX n ; n) och C i n = log jYj? H(Y n jX n ; i n ). Genom att tillämpa Lemmas 4.2 och 4.3 får vi att H(Y n jX n ; n) minskar med n, H(Y n jX n ; i n) ökar med n, och båda konvergerar till samma gräns.  av Lemma 4.1 och (32). Att tillämpa Lemma 4.6 på lim n!1 H(Y n jX n ; n) slutför beviset. 2 BSC motsvarar en binär ingång Q-AWN-kanal med binär kvantisering 4]. Därför är en FSMC där c k indexerar en uppsättning BSC med olika crossover sannolikheter en jämnt symmetrisk variabel bruskanal. Därför är både proposition 4 av 1] och kapacitetsformeln som erhålls i 5] korollaries av Theorem 5.1. Ett blockdiagram för ett system med avkodning av beslut-feedback visas i figur 3. Systemet består av en konventionell (block eller convolutional) kodare för minneslösa kanaler, block interleafer, FSMC, beslut-feedback dekoder och deinterleafer. I figur 4 beskrivs utformningen av beslut-feedback-dekoder, som består av en uppskattning av kanaltillstånd följt av en ML-dekoder. Vi kommer att visa i detta avsnitt att om vi bortser från felutbredning, är ett system som använder detta beslut-feedback avkodningssystem på enhetligt symmetriska variabla ljudkanaler informationslös: det har samma kapacitet som den ursprungliga FSMC, som ges av (30) för i.i.d. Enhetliga insatser. Dessutom kommer vi att se att statsskattarens utdata är en tillräcklig statistik för den aktuella utmatningen med tanke på alla tidigare ingångar och utgångar, vilket minskar systemet i figur 3 till en diskret minneslös kanal. Därför bestäms ML-ingångssekvensen på symbol-för-symbol-basis, vilket eliminerar komplexiteten och fördröjningen av sekvensavkodare. Mellanbladen fungerar enligt följande. Utmatningen av kodaren lagras rad för rad i en J L interleafer och överförs över kanalkolonnen per kolumn. Avskiljaren utför den omvända operationen. Eftersom eekten av det ursprungliga kanaltillståndet dör bort, blir de mottagna symbolerna inom vilken rad som helst av avskiljaren oberoende när J blir i nite. Symbolerna i någon kolumn i avskiljaren tas dock emot från efterföljande kanalanvändningar, och är därför beroende. Detta beroende kallas det latenta kanalminnet, och statsskattaren gör det möjligt för ML-dekodern att använda sig av detta minne. Speci callay, staten estimator använder rekursiv relation av (11) för att uppskatta n. Det kommer att visas nedan att ML dekoder fungerar på ett minneslöst system, och kan därför bestämma ML ingångssekvensen på en per symbol basis. Ingången till ML-dekodern är kanalutgången y n och statsuppskattningen^ n, och dess utgång är x n som maximerar log p(y n ;^ n jx n ), förutsatt lika sannolika inmatningssymboler 4. Den mjuka beslut dekoder använder konventionella tekniker (t.ex., Viterbi avkodning) med grenmått m(y; ) 4 = log p(y; jx): (43) Vi utvärderar nu information, kapacitet, och cuto hastigheter i ett system med hjälp av beslutfeedback dekoder, förutsatt b n = n (dvs. ignorera felförökning). Vi kommer att använda notationen y jl 4 = y n för att explicit beteckna att y n är i j: e raden och l: e kolumnen i avskiljaren. På samma sätt jl 4 = n och x jl 4 = x n betecknar respektive stat uppskattning och interleaver indata motsvarande y jl. Antag nu att staten estimator återställs varje J iterationer så, för varje l, staten estimator går igenom j rekursioner av (11) för att beräkna jl. Genom (12), denna rekursion inducerar en distribution p( jl ) på jl som endast beror på p(X j?1 ). Således är systemet upp till utdata av staten estimator lika med en uppsättning parallella - output kanaler, där - output kanalen de ner, för en given j, av indata x jl, utdataparet (y jl ; jl ), och input / output sannolikhet p (y jl ; jl jx jl ) = X k p k (y jx jl ) jl (k) p ( jl ): 4 Om xn är inte lika troligt, då logga p (xn) måste läggas till i dekoder metrisken. För varje j är -utmatningskanalen densamma för l = 1; 2; : :; L, och därför finns det J di erent -output kanaler, var och en används L gånger. Vi därmed släppa l subscript av x jl, y jl, och jl i dekoder blockdiagram av figur 4. Den rst - output kanalen (j = 1) är likvärdig med FSMC med interleaving och minneslös kanalkodning, eftersom estimatorn återställs och därför 1l = 0 ; 1 l L. Jth - output kanalen är diskret, eftersom x jl och y jl tas från nite alfabet, och eftersom jl kan ha som mest jXj j jYj j di erent värden. Det är också asymptotiskt minneslöst med djup interleaving (stor J), som vi bevisar i bilaga 7. Slutligen visar vi i bilaga 8 att för en xed ingångsdistribution är J-utgångskanalerna oberoende, och den genomsnittliga ömsesidiga informationen för de parallella kanalerna är jämförelse (48) till (24) För enhetliga symmetriska variabla ljudkanaler, likformiga i.i.d. ingångar uppnå både C och C df, och med denna input C? C df = 0. Besluts-feedback-dekodern bevarar således dessa kanalers inneboende kapacitet. Även om kapaciteten ger den maximala datahastigheten för alla ML-kodningssystem, fungerar etablerade kodningsmetoder i allmänhet på eller under kanalens brythastighet 4]. Eftersom -utgångskanalerna är oberoende för en xed indatadistribution p(X J ), är den slumpmässiga kodexponenten för parallelluppsättningen Vi visar i bilaga 9 att för jämnt symmetriska variabla ljudkanaler, den maximala indatadistributionen i (52) där är den invarianta distributionen för under i.i.d. Enhetliga insatser. Våra beräkningar under hela detta avsnitt har ignorerat effekterna av felutbredning. Med hänvisning till figur 4, felutbredning uppstår när beslut-feedback dekoder utdata för maximal-likelihood indata symbol b x j är i fel, som sedan kommer att orsaka uppskattningen av b j för att vara i fel. Eftersom x j är värdet på den kodade symbolen, är felsannolikheten för b x j inte bene t från någon kodningsvinst. Eftersom blockerings- eller konvolutionsavkodningen medför förseningar kan besluten efter avkodningen tyvärr inte återföras till beslutsavkodningen för att uppdatera b j-värdet. Detta är exakt den sort som en adaptiv beslut-feedback equalizer (DFE), där avkodning beslut används för att uppdatera DFE tap coe cients 16]. Nya metoder för att kombinera DFE och kodning har nyligen föreslagits, och flera av dessa metoder kan användas för att få viss kodningsvinst i uppskattningen av x j matas tillbaka genom vår beslut-feedback dekoder. I synnerhet, strukturen för vår beslut-feedback dekoder redan innehåller interleafer / deinterleafer pair föreslagna av Eyubo glu för DFE med kodning 17]. I sin metod införde detta par en periodisk fördröjning av de mottagna bitarna så att försenade tillförlitliga beslut kan användas för återkoppling. Att tillämpa denna idé på vårt system kombinerar effektivt beslut-feedback dekoder, deinterleafer och dekoder. Speci caley, symbolerna som överförs över varje - output kanal dekodas tillsammans, och symbolbeslut utdata från dekoder används sedan av beslut-feedback dekoder för att uppdatera värdena för den efterföljande - output kanal. Komplexiteten och fördröjningen av denna design ökar linjärt med blocklängden av -output kanalkoden, men det är oberoende av kanalminnet eftersom detta minne fångas i den lämpliga statistiken n. En annan metod för att genomföra kodning vinst använder mjuka beslut på de mottagna symbolerna för att uppdatera n, sedan senare korrigerar denna ursprungliga n uppskattning om de avkodade symbolerna di er från sina ursprungliga uppskattningar 18]. Denna metod trunkerar antalet symboler som beror på ett felaktigt beslut, till en kostnad av ökad komplexitet för att räkna om och uppdatera n-värdena. Slutligen kan beslut-feedback avkodning göras parallellt, där varje parallell väg motsvarar en annan uppskattning av den mottagna symbolen. Antalet parallella vägar kommer att öka exponentiellt i detta fall, men vi kanske kan tillämpa några av de metoder som beskrivs i 19] och 20] för att minska antalet vägar som upprätthålls genom spaljéerna. För fordon av kategorierna M1 och N1 ska följande villkor vara uppfyllda: Inmatningen till kanalen är en 4PSK-symbol, till vilken brus av varians n G eller n B läggs, beroende på om kanalen är i tillstånd G (bra) eller B (dåligt). Vi antar att SNR är 10dB för kanal G och -5dB för kanal B. Kanalutgången kvantifieras till närmaste inmatningssymbol och eftersom detta är en enhetlig symmetrisk variabel bruskanal uppnås kapaciteten och cutohastigheten med likformig i.i.d. Ingångar. Sannolikheten för statsövergång beskrivs i figur 5. Vi antar en stationär inledande fördelning av tillståndsprocessen, så p(S 0 = G) = g=(g + b) och p(S 0 = B) = b=(g + b). Figur 6 visar den iterativa beräkningen av (12) för p( n (G) = ), där n (G) = p(S n = Gjx n?1 ; y n?1 ). I detta exempel är skillnaden mellan efterföljande distributioner efter 40 rekursioner under kvantiseringsnivån (d = :01) i grafen. Figur 7 visar kapaciteten (C j ) och cuto-hastigheten (R j ) för jth -output-kanalen, given av (47) respektive (51). Observera att C j=1 och R j=1 i denna gure är kapaciteten och cuto-hastigheten för FSMC med interleaving och minneslös kanalkodning. Skillnaden mellan de ursprungliga och de nationella värdena för C j och R j indikerar således förbättringen av besluts-feedback-dekodern jämfört med konventionella tekniker.  I figur 8 visar vi beslut-feedback dekoder kapacitet och cuto hastigheter (C df respektive R df) som funktioner av. Vi förväntar oss att dessa prestationsmått ökar som ökar, eftersom mer latens i kanalen bör förbättra noggrannheten hos stat estimator; Figur 8 conrms denna hypotes. Slutligen, i figur 9 visar vi beslut-feedback dekoder kapacitet och cuto hastigheter som funktioner av g. Parametern g är omvänt proportionell mot det genomsnittliga antalet på varandra följande B-kanaltillstånd (som motsvarar en 15dB blekning), vilket figur 9 kan tolkas som förhållandet mellan den maximala överföringshastigheten och den genomsnittliga bleka varaktigheten. Vi har härlett Shannonkapaciteten hos en FSMC som en funktion av de villkorliga sannolikheterna n (k) = p(S n = c k jy n?1 ) och n (k) = p(S n = c k jx n?1 ; y n?1 ). Det visade vi också med i.i.d. Indata, dessa villkorade sannolikheter konvergerar svagt, och kanalens ömsesidiga information under denna indatarestriktion är då en sluten form kontinuerlig funktion av indatadistributionen. Denna kontinuitet tillåter I iid, maximal ömsesidig information om FSMC över alla i.i.d. ingångar, hittas med hjälp av standard maximering tekniker. Ytterligare egenskaper hos entropin och kapaciteten för jämnt symmetriska variabla ljudkanaler härleddes också. Vi föreslog sedan en ML-beslutsavkodare, som beräknar rekursiva uppskattningar av n från kanalutgången och beslutsavkodningsutgången. Vi visade att för asymptotiskt djup interleaving, ett system som använder beslut-feedback dekoder motsvarar en diskret minneslös kanal med ingång x n och utgång (y n ; n ). Således kan ML-sekvensen avkodning göras på en symbol-för-symbol basis. Dessutom bevarar beslut-feedback-dekodern den inneboende kapaciteten hos enhetliga symmetriska variabla ljudkanaler, förutsatt att felutbredningens eekt är försumbar. Denna klass av FSMCs inkluderar blekning eller variabla ljudkanaler med symmetriska PSK-ingångar samt kanaler som varierar över en nite uppsättning av BSCs. För allmänna FSMC fick vi kapacitets- och reduceringsstraff i systemet för avkodning av beslut-feedback. Vi presenterade även numeriska resultat för beslutsfattande-feedback-dekoderns prestanda på en tvåstatsvariabel bruskanal med 4PSK-modulering. Dessa resultat visar betydande förbättring jämfört med konventionella system som använder interleaving och minneslös kanalkodning, och förbättringen är mest uttalad på kvasi-statiska kanaler. Detta resultat är intuitivt, eftersom ju längre FSMC stannar i ett givet tillstånd, desto mer exakt stat estimator kommer att förutsäga detta tillstånd. Slutligen presenterar vi resultat för dekoderns prestanda i förhållande till den genomsnittliga blekningsdurationen; som förväntat förbättras prestandan i takt med att den genomsnittliga blekningsdurationen minskar.
Kaijsers resultat användes av Goldsmith och Varaiya, inom ramen för finit-state Markov kanaler REF.
Capacity, Mutual Information, and Coding for Finite-State Markov Channels
{'venue': 'IEEE Trans. Inform. Theory', 'journal': None, 'mag_field_of_study': ['Computer Science']}