On Decoding Problems, Lattices and Generalized Concatenated Codes
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Doctoral thesis (article-based)
| Defence date: 2020-04-22
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2020
Major/Subject
Mcode
Degree programme
Language
en
Pages
60 + app. 60
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 59/2020
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.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, DekodningDescription
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
Supervising professor
Hollanti, Camilla, Prof., Aalto University, Department of Mathematics and Systems Analysis, FinlandThesis advisor
Greferath, Marcus, Prof., University College Dublin, IrelandKeywords
lattices, generalized concatenated codes, decoding
Other note
Parts
-
[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 View at publisher
-
[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 View at publisher
- [Publication 3]: Ferdinand Blomqvist. On Hard-Decision Decoding of Product Codes. Submitted to Applicable Algebra in Engineering, Communication and Computing, March 2020.
- [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.