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
Detection for multiple input multiple output channels: analysis of sphere decoding and semidefinite relaxation
KTH, School of Electrical Engineering (EES), Signal Processing.ORCID iD: 0000-0001-6630-243X
2006 (English)Doctoral thesis, monograph (Other scientific)
Abstract [en]

The problem of detecting a vector of symbols, drawn from a finite alphabet and transmitted over a multiple-input multiple-output (MIMO) channel with Gaussian noise, is of central importance in digital communications and is encountered in several different applications. Examples include, but are not limited to; detection of symbols spatially multiplexed over a multiple-antenna channel and the multiuser detection problem in a code division multiple access (CDMA) system.

Two algorithms previously proposed in the literature are considered and analyzed. Both algorithms have their origin in other fields of science but have gained mainstream recognition as efficient algorithms for the detection problem considered herein. Specifically, we consider the sphere decoder and semidefinite relaxation detector. By incorporating assumptions applicable in the communications context the performance of the two algorithms is addressed.

The first algorithm, the sphere decoder, offers optimal performance in terms of its error probability. Further, the algorithm has proved extremely efficient in terms of computational complexity for moderately sized problems at high signal to noise ratio (SNR). Although it is recognized that the algorithm has an exponential worst case complexity, there has been a widespread belief that the algorithm has a polynomial average complexity at high SNR. A contribution made herein is to show that this is incorrect and that the average complexity, as the worst case complexity, is exponential in the number of symbols detected. Instead, another explanation of the observed efficiency of the algorithm is offered by deriving the exponential rate of growth and showing that this rate, although strictly positive for finite SNR, is small in the high SNR regime.

The second algorithm, the semidefinite relaxation (SDR) detector, offers polynomial complexity at the expense of suboptimal performance in terms of error probability. Nevertheless, previous numerical observations suggest that error probability of the SDR algorithm is close to that of the optimal detector. Herein, the near optimality is of the SDR algorithm is given a precise meaning by studying the diversity of the SDR algorithm when applied to the (real valued) i.i.d.~Rayleigh fading channel and it is shown that the SDR algorithm achieves the same diversity order as the optimal detector. Further, criteria under which the SDR estimates coincide with the optimal estimates are derived and discussed.

Abstract [sv]

Ett grundläggande problem som påträffats inom digital kommunikation är detektering av en symbolvektor, tillhörande ett ändligt symbolalfabet, som sänts över en MIMO (från engelskans multiple-input multiple-output) kanal med Gausiskt brus. Detta problem påträffas bland annat då symboler sänts över en trådlös kanal med flera antenner hos mottagaren och sändaren samt då flera användare i ett CDMA system simultant skall avkodas.

In denna avhandling behandlas två mottagaralgoritmer konstruerade för detta ändamål. Algoritmerna har sin bakgrund i andra forskningsområden men kan i nuläget sägas vara mycket välkända inom kommunikationsområdet. De benämns vanligtvis som sfäravkodaren (eng. sphere decoder) samt den semidefinita relaxeringsdetektorn (eng. semidefinite relaxation detector). Algoritmerna analyseras i denna avhandling matematiskt genom att införa förenklande antaganden som är relevanta och applicerbara för de kommunikationsproblem som är av intesse.

Den första algoritmen, sfäravkodaren, löser dessa detektionsproblem på ett optimalt sätt i betydelsen att den minimerar sannolikheten för att detektorn fattar ett felaktigt beslut rörande det sända meddelandet (symbolvektorn). Också vad gäller algoritmens komplexitet har simuleringar visat att den är oväntat låg, åtminstone vid höga signalbrusförhållanden (SNR). Trots att det är allmänt känt att algoritmen i sämsta fall har exponentiell komplexitet så har detta lett till den allmänt spridda uppfattningen att medelkomplexiteten (eller den förväntade komplexiteten) endast är polynomisk vid höga signalbrusförhållanden. Ett av huvudbidragen i denna avhandling är att visa att denna uppfattning är felaktig och att också medelkomplexiteten växer exponentiellt i antalet symboler som simultant detekteras. Ytterligare ett bidrag ligger i att ge en alternativ förklaring till den observerat låga medelkomplexiteten. Det visas att den exponentiella hastighet med vilken komplexiteten växer beror på signalbrusförhållande, och att den är låg för höga SNR.

Den andra algoritmen, den semidefinita relaxeringsdetektorn, erbjuder polynomisk komplexitet vid en något högre felsannolikhet. Intressant nog har dock felsannolikheten tidigare, genom simuleringar, visat sig vara endast marginellt högre än felsannolikheten hos den optimala mottagaren. Bidraget som relaterar till den semidefinita relaxeringsmottagaren ligger i att både förklara och i att ge en specifik kvatifierbar mening åt uttalandet att felsannolikheten endast är marginellt högre. I syfte att åstadkomma detta studeras diversitetsordningen för detektorn, och det bevisas att diversitetsordningen för den semidefinita relaxeringsdetektorn är densamma som för den optimala mottagaren. Utöver detta karakteriseras också de krav som måste uppfyllas för att den detektorn skall finna den optimala lösningen.

Place, publisher, year, edition, pages
Stockholm: KTH , 2006. , viii, 137 p.
Series
Trita-EE, ISSN 1653-5146 ; 2006:058
Keyword [en]
Telekommunications, MIMO, Detection, Sphere Decoder, Semidefinite Relaxation
National Category
Telecommunications
Identifiers
URN: urn:nbn:se:kth:diva-4199ISBN: 978-91-7178-519-0 (print)OAI: oai:DiVA.org:kth-4199DiVA: diva2:11183
Public defence
2006-12-07, F3, Lindstedtsvägen 26, KTH, 09:15
Opponent
Supervisors
Note
QC 20100901Available from: 2006-11-30 Created: 2006-11-30 Last updated: 2010-09-01Bibliographically approved

Open Access in DiVA

fulltext(1029 kB)1573 downloads
File information
File name FULLTEXT01.pdfFile size 1029 kBChecksum MD5
e5f66000c32f582e079c813de1b690c4d0c27160e98d9850f2d6100d8bf024408def8d8a
Type fulltextMimetype application/pdf

Authority records BETA

Jaldén, Joakim

Search in DiVA

By author/editor
Jaldén, Joakim
By organisation
Signal Processing
Telecommunications

Search outside of DiVA

GoogleGoogle Scholar
Total: 1573 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: 719 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