On Decoding Problems, Lattices and Generalized Concatenated Codes

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Greferath, Marcus, Prof., University College Dublin, Ireland
dc.contributor.author Blomqvist, Ferdinand
dc.date.accessioned 2020-04-08T09:00:06Z
dc.date.available 2020-04-08T09:00:06Z
dc.date.issued 2020
dc.identifier.isbn 978-952-60-3835-3 (electronic)
dc.identifier.isbn 978-952-60-3834-6 (printed)
dc.identifier.issn 1799-4942 (electronic)
dc.identifier.issn 1799-4934 (printed)
dc.identifier.issn 1799-4934 (ISSN-L)
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/43730
dc.description The public defense on 22nd April 2020 at 16:00 (4 p.m.) will be organized via remote technology. Link: https://aalto.zoom.us/j/651995701 Zoom Quick Guide: https://www.aalto.fi/en/services/zoom-quick-guide
dc.description.abstract Information transfer and storage play an important part in the technical society we live in. A big challenge is the unreliable nature of wireless communication along with failure of storage devices and other technical equipment. Another challenge is the vast amount of data that needs to be handled. Claude Shannon created the mathematical theory of communication in the late 1940s. Today, this subfield of information theory is known as coding theory. One of the main problems that coding theory deals with is the question of how to achieve fast, efficient and reliable communication over an unreliable channel. Reliability can be achieved by adding redundancy to the transmitted information. This, however, comes at the price of lower efficiency since we have increased the amount of data that is transmitted over the channel. Hence, the different goals are conflicting, and one particular solution is usually only suitable for certain applications. The process of adding redundancy to the message is called encoding. The set of all encoded messages is called a code, while one encoded message is called a codeword. When a codeword is sent over an unreliable channel the channel might distort the transmitted codeword, and hence the receiver is left with the task of recovering the transmitted codeword from the distorted one. This is referred to as decoding. Lattices are mathematical objects that, at first glance, appear to be simple. However, they are the source of many hard problems, and they are useful in many different applications, including coding theory and cryptography. Formally, a lattice is a finitely generated subgroup of a real vector space. Generalized concatenation is a method of building new codes from existing ones. Codes obtained this way are known as generalized concatenated codes. The strength of generalized concatenation is that one can create long codes with good properties from short codes. Moreover, generalized concatenated codes can be decoded using decoders for the component codes. However, the decoding algorithm for generalized concatenated codes is still complex, and any developments in this area will make the adoption of these codes in practical applications easier. This is very important since many good codes can be obtained by generalized concatenation. This thesis deals with decoding problems, or more specifically, the design of efficient decoding algorithms for specific codes. We consider decoding algorithms for lattices and generalized concatenated codes. en
dc.description.abstract Informationsöverföring och -lagring är en viktig del av dagens teknikbaserade samhälle. Utmaningarna är dock många. Trådlös kommunikation är till sin natur opålitlig och lagringsenheter och annan teknisk apparatur går ofta sönder. Utöver detta är det frågan om enorma datamängder som bör processeras och lagras. Claude Shannon lade grunden för den moderna informations- och kodningsteorin under 1940talet . En av de stora frågeställningarna inom kodningsteori är hur man kan uppnå pålitlig kommunikation över en opålitlig kanal. Detta kallas för kanalkodning. Lösningen på problemet är att lägga till redundans till informationen före den skickas över kanalen. Priset för den ökade pålitligheten är en lägre effektivitet eftersom den extra redundansen gör meddelandet längre. Processen att lägga till redundans till ett meddelande kallas for enkodning. Mängden av alla möjliga enkodade meddelanden kallas för en kod och ett enkodat meddelande kallas för ett kodord. När ett kodord skickas över en opålitlig kanal kan störningarna förvränga kodordet så att mottagaren inte vet vilket ord som skickades. Ifall kodordet innehållet tillräckligt mycket redundans kan det skickade meddelandet återskapas från det förvrängda ordet. Att dechiffrera det skickade kodordet från det förvrängda orded kallas för dekodning. Gitter är matematiska objekt som vid första anblicken verkar ytterst simpla. Dock ger de upphov till många intressanta och svåra problem. Gitter är användbara inom många applikationer som t.ex. kanalkodning, kvantisering och kryptografi. Formellt definieras ett gitter som en diskret delgrupp till ett reellt vektorrum. Generaliserad konkatenering är en metod att konstruera nya koder från redan existerande koder. Koder som konstrueras med denna metod kallas för generaliserade konkatenerade koder. Generaliserad konkatenering är ett enkelt sätt att skapa långa koder med bra egenskaper från korta koder. Styrkan med dessa koder är att de kan dekodas med dekoders för komponentkoderna. Dekodningsalgoritmen för generaliserade konkatenerade koder är dock relativt komplicerad och all utveckling eller förbättring av algoritmen gör det lättare att använda koderna i riktiga kommunikationssystem. Många ytterst bra koder kan konstrueras med generaliserad konkatenering och således är detta ett viktigt forskningsområde. Denna avhandling fokuserar på utveckling av dekodningsalgoritmer för olika koder. Vi behandlar dekodning av koder baserade på gitter och så kallade generaliserade konkatenerade koder. Nyckelord Gitter, Generaliserade konkatenerade koder, Dekodning
dc.format.extent 60 + app. 60
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Aalto University en
dc.publisher Aalto-yliopisto fi
dc.relation.ispartofseries Aalto University publication series DOCTORAL DISSERTATIONS en
dc.relation.ispartofseries 59/2020
dc.relation.haspart [Publication 1]: Ferdinand Blomqvist. On Quotient Metrics and Decoding Problems. In the International Symposium on Information Theory and Its Applications, Singapore, pages 198-202, October 2018. DOI: 10.23919/ISITA.2018.8664238
dc.relation.haspart [Publication 2]: Ferdinand Blomqvist, Marcus Greferath. The Double-Plane Algorithm: A simple algorithm for the closest vector problem. In the International Symposium on Information Theory and Its Applications, Singapore, pages 193-197, October 2018. DOI: 10.23919/ISITA.2018.8664371
dc.relation.haspart [Publication 3]: Ferdinand Blomqvist. On Hard-Decision Decoding of Product Codes. Submitted to Applicable Algebra in Engineering, Communication and Computing, March 2020.
dc.relation.haspart [Publication 4]: Ferdinand Blomqvist, Oliver W. Gnilke , Marcus Greferath. On Decoding of Generalized Concatenated Codes and Matrix-Product Codes. Submitted to Applicable Algebra in Engineering, Communication and Computing, January 2020.
dc.subject.other Mathematics en
dc.title On Decoding Problems, Lattices and Generalized Concatenated Codes en
dc.type G5 Artikkeliväitöskirja fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.contributor.school School of Science en
dc.contributor.department Matematiikan ja systeemianalyysin laitos fi
dc.contributor.department Department of Mathematics and Systems Analysis en
dc.subject.keyword lattices en
dc.subject.keyword generalized concatenated codes en
dc.subject.keyword decoding en
dc.identifier.urn URN:ISBN:978-952-60-3835-3
dc.type.dcmitype text en
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.contributor.supervisor Hollanti, Camilla, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
dc.opn Kelley, Christine, Prof., University of Nebraska-Lincoln, USA
dc.contributor.lab Algebra, Number Theory, and Applications en
dc.rev Kelley, Christine, Prof., University of Nebraska-Lincoln, USA
dc.rev Schmidt, Stefan, Prof., Dresden University of Technology, Germany
dc.date.defence 2020-04-22
local.aalto.acrisexportstatus checked 2020-06-09_1858
local.aalto.formfolder 2020_04_08_klo_10_02
local.aalto.archive yes


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse