Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Linear Coding, Applications and Supremus Typicality
KTH, School of Electrical Engineering (EES), Communication Theory.
2015 (English)Doctoral thesis, monograph (Other academic)
Abstract [sv]

Detta arbete börjar med att presentera en kodningssats gällande linjärkodning över ändliga ringar för kodning av korrelerade diskretaminneslösa källor. Denna sats inkluderar som specialfall motsvarandeuppnåbarhetssatser från Elias och Csiszár gällande linjär kodning överändliga kroppar. Dessutom visas det att för varje uppsättning av ändligakorrelerade diskreta minneslösa källor, så finns alltid en sekvens avlinjära kodare över vissa ändliga icke-kropp-ringar som uppnårdatakompressionsgränsen bestämd av Slepian-Wolf-regionen. Därmed slutervi problemet med linjär kodning över ändlig icke-kropps-ringar föri.i.d. datakomprimering med positiv bekräftelse gällande existens.

Vi studerar också kodning av funktioner, där avkodaren är intresseradav att återskapa en diskret mappning av data som genererats av flerakorrelerade i.i.d. källor och som kodats individuellt. Vi föreslårlinjär kodning över ändliga ringar som en alternativ lösning på dettaproblem. Vi visar att linjär kodning över ändliga ringar presterarbättre än sin ändliga-kropp-motsvarighet, liksom dessutomSlepian-Wolf-kodning, i termer av att uppnå bättre kodningshastigheterför kodning av flera diskreta funktioner.

För att generalisera ovannämnda genomförbarhetssatser, både gällandedatakompression och funktionskodningsproblemet, till Markov-källor(homogena irreducerbara Markov-källor), så introducerar vi ett nyttkoncept gällande klassificering av typiska sekvenser, benämndSupremus-typiska sekvenser. Den asymptotiska likafördelningsprincipensamt en generaliserad version av typiskhets-hjälpsatsen förSupremus-typiska sekvenser bevisas. Jämfört med traditionell (stark ochsvag) typiskhet, så tillåter Supremus-typiskhet oss att härleda bättretillgängliga verktyg och resultat, som låter oss bevisa att linjärkodning över ringar är överlägsen andra metoder. I motsats härtillmisslyckas argument baserade på den traditionella versionen antingen medatt nå liknande resultat eller så är de härledda resultaten svåra attanalysera på grund av en utmanande utvärdering av entropitakt.

För att ytterligare undersöka den grundläggande skillnaden mellantraditionell typiskhet och Supremus-typiskhet och dessutom göra våraresultat än mer allmänt gällande, så betraktar vi ävenasymptotiskt medelvärdesstationära ergodiska källor. Våra resultat visaratt en inducerad transformation med avseende på en ändligt mätbar mängdöver ett rekurrent asymptotiskt medelvärdesstationärt dynamiskt systemmed ett sigma-ändlig sannolikhetsmått är asymptotisktmedelvärdesstationär. Följaktligen så gällerShannon-McMillan-Breiman-teoremet, liksom Shannon-McMillan-teoremet, föralla reducerade processer härledda ur rekurrenta asymptotisktmedelvärdesstationära stokastisk processer. Alltså ser vi att dettraditionella typiskhetkonceptet endast realiserarShannon-McMillan-Breiman-teoremet i ett globalt hänseende, medanSupremus-typiskhet leder till att resultatet håller samtidigt även föralla härledda reducerade sekvenser.

Abstract [en]

This work first presents a coding theorem on linear coding over finite rings for encoding correlated discrete memoryless sources. This theorem covers corresponding achievability theorems from Elias and Csiszár on linear coding over finite fields as special cases. In addition, it is shown that, for any set of finite correlated discrete memoryless sources, there always exists a sequence of linear encoders over some finite non-field rings which achieves the data compression limit, the Slepian--Wolf region. Hence, the optimality problem regarding linear coding over finite non-field rings for i.i.d. data compression is closed with positive confirmation with respect to existence.

We also address the function encoding problem, where the decoder is interested in recovering a discrete function of the data generated and independently encoded by several correlated i.i.d. sources. We propose linear coding over finite rings as an alternative solution to this problem. It is demonstrated that linear coding over finite rings strictly outperforms its field counterpart, as well as the Slepian--Wolf scheme, in terms of achieving better coding rates for encoding many discrete functions.

In order to generalise the above achievability theorems, on both the data compression and the function encoding problems, to the Markovian settings (homogeneous irreducible Markov sources), a new concept of typicality for sequences, termed Supremus typical sequences, is introduced. The Asymptotically Equipartition Property and a generalised typicality lemma of Supremus typical sequences are proved. Compared to traditional (strong and weak) typicality, Supremus typicality allows us to derive more accessible tools and results, based on which it is once again proved that linear technique over rings is superior to others. In contrast, corresponding arguments based on the traditional versions either fail to draw similar conclusions or the derived results are often hard to analyse because it is complicated to evaluate entropy rates.

To further investigate the fundamental difference between traditional typicality and Supremus typicality and to bring our results to a more universal setting, asymptotically mean stationary ergodic sources, we look into the ergodic properties featured in these two concepts.Our studies prove that an induced transformation with respect to a finite measure set of a recurrent asymptotically mean stationary dynamical system with a sigma-finite measure is asymptotically mean stationary. Consequently, the Shannon-McMillan-Breiman Theorem, as well as the Shannon-McMillan Theorem, holds simultaneously for all reduced processes of any finite-state recurrent asymptotically mean stationary random process.From this, we see that the traditional typicality concept only realises the Shannon-McMillan-Breiman Theorem in the global sequence, while Supremus typicality engraves the simultaneous effects claimed in the previous statement into all reduced sequences as well.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2015. , x, 127 p.
Series
TRITA-EE, ISSN 1653-5146 ; 2015:008
Keyword [en]
Linear coding, Supremus typicality
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Research subject
Information and Communication Technology; Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-160598ISBN: 978-91-7595-462-2 (print)OAI: oai:DiVA.org:kth-160598DiVA: diva2:790472
Public defence
2015-03-20, Hörsal Q2, Osquldas väg 10, KTH, Stockholm, 16:11 (English)
Opponent
Supervisors
Note

QC 20150225

Available from: 2015-02-25 Created: 2015-02-24 Last updated: 2015-02-25Bibliographically approved

Open Access in DiVA

huangthesis(981 kB)182 downloads
File information
File name FULLTEXT01.pdfFile size 981 kBChecksum SHA-512
bb344521dde76d259ed20a3b2c3c52ca53bb80bc54d3a9329fcaa80f3cda1cdf304fae10f0a4a64998bbb84ac37e6862521b135b633516dcc8ee4271be578687
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Huang, Sheng
By organisation
Communication Theory
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 182 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 685 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf