On Decoding Problems, Lattices and Generalized Concatenated Codes

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.