5.4. 5.4. Arimoto-Blahut algoritmus

Zajos csatorna kapacitásának kiszámítására általános módszert Arimoto [ 2 ] és Blahut [ 6 ] adtak először egymástól függetlenül 1972-ben. A módszer ismertetése előtt nézzük milyen kifejezésekre lesz szükségünk.

Legyen a csatorna egy lehetséges bemeneti eloszlása, valamint eloszlás a csatorna kimenetén. Ha az adókarakterisztika mátrix, akkor a bemeneti eloszlásból a kimeneti eloszlást a mátrix-vektor szorzat adja. Bontsuk fel az adókarakterisztika mátrixot oszlopvektoraira és a mátrix -edik oszlopát jelölje . Továbbá legyen

Legyen tetszőleges eloszlás. Képezzük az alábbi iterációs formula alapján eloszlásoknak egy sorozatát, valamint konstansok egy sorozatát:

Ekkor a

eloszlások sorozata konvergál valamely optimális csatornabemeneti eloszláshoz és a

konstansok sorozata alulról konvergál a csatorna kapacitásához.

Bizonyítás. Legyen egy tetszőleges bemeneti eloszlás és

Arimoto eredeti bizonyítása alapján kapjuk a következőt:

Ebből következik, hogy

mert bármely -ra, és , ugyanis

Ezenfelül az is látszik, hogy

Ennek következtében fennáll a következő határérték

Legyen egy részsorozata a sorozatnak , melyre igaz a következő:

Az függvény folytonosságából következik, hogy

A korábbi egyenlőségekből beláthatjuk, hogy

Az előző egyenlőségek alapján

Ennélfogva azt kapjuk, hogy továbbá ha

Nézzünk pár egyszerű példát a csatornakapacitás meghatározására diszkrét, emlékezetnélküli csatorna esetén. A következő példák megtalálhatóak a [ 3 ], illetve a [ 18 ] irodalomban.

5.3. Példa. Legyen a csatorna adókarakterisztika mátrixa a következő:

Ekkor és az optimális bemeneti eloszlás pedig

Az algoritmus pedig a következő eredményeket szolgáltatja pontossággal:

Az eredmények előállításához iterációra volt szükség.

5.4. Példa. Legyen a csatorna adókarakterisztika mátrixa

Ez egy gyengén szimmetrikus, diszkrét, emlékezetnélküli csatorna. A csatorna kapacitása

Az optimális bemeneti eloszlásra pedig igaz a következő:

Az Arimoto-Blahut algoritmussal kapott eredmények:

Az eredmények előállításához iterációra volt szükség.

5.5. Példa. Legyen a csatorna adókarakterisztika mátrixa

A csatorna kapacitása

az optimális bemeneti eloszlás

Az Arimoto-Blahut algoritmussal kapott eredmények pedig a következőek:

Az eredmények előállításához iterációra volt szükség.

5.6. Példa. Legyen a csatorna adókarakterisztika mátrixa

A csatorna kapacitása

Ha akkor

Az Arimoto-Blahut algoritmussal kapott eredmények pedig a következőek:

Az eredmények előállításához iterációra volt szükség.

5.7. Példa.

A csatorna kapacitása . Ha akkor . Legyen ekkor

Az Arimoto-Blahut algoritmussal kapott eredmények pedig a következőek:

és

Az eredmények előállításához iterációra volt szükség.