Selected Topics in Information and Coding Theory

The following sections are included:

• PREFACE

• CONTENTS

• CONTRIBUTORS

The linear complexity of a sequence is not only a measure for the unpredictability and thus suitability for cryptography but also of interest in information theory because of its close relation to the Kolmogorov complexity. However, in contrast to the Kolmogorov complexity the linear complexity is computable and so of practical significance.

It is also linked to coding theory. On the one hand, the linear complexity of a sequence can be estimated in terms of its correlation and there are strong ties between low correlation sequence design and the theory of error-correcting codes. On the other hand, the linear complexity can be calculated with the Berlekamp-Massey algorithm which was initially introduced for decoding BCH-codes.

This chapter surveys several mainly number theoretic methods for the theoretical analysis of the linear complexity and related complexity measures and describes several classes of particularly interesting sequences with high linear complexity.

In this study, we conduct a comprehensive investigation on lattices and several constructions of lattice from codes. These constructions include some known constructions such as, Construction A, B, C, D, and D′. For each construction we derive some corresponding lattice factors such as label groups, label codes, etc. Finally, we compare these constructions together to come up with a possible lattice construction with high coding gain using Turbo codes and low density parity check codes.

Cooperative communication in a wireless relay network consisting of a source node, a destination node, and several relay nodes equipped with half duplex single antenna transceivers is considered. Recently, for such a setting, it has been shown that diversity order equal to the number of relays can be achieved provided appropriate distributed space-time block codes (DSTBCs) are manufactured/used by the relay nodes, thus emulating a virtual multiple input multiple output (MIMO) system. This chapter deals with DSTBCs with low maximum likelihood (ML) decoding complexity. After a brief introduction and background to the study of STBCs and DSTBCs, a survey of STBC constructions for point to point MIMO systems that are amenable for low complexity ML decoding is presented. Then, DSTBC constructions achieving full cooperative diversity along with low ML decoding complexity are discussed separately for two cases: (i) the destination has perfect channel state information (CSI) of the source to relay as well as the relay to destination channel fading gains and no CSI is available at the source and relay nodes and (ii) the destination has full CSI and the relays have partial CSI corresponding to the phase component of the source to relay channel gains. For some of these cases, upper bounds on the maximum rate of single symbol ML decodable DSTBCs are also provided. These are counterparts of the well-known complex orthogonal designs for point to point MIMO systems that includes the Alamouti code as a special case.

This chapter introduces and elaborates on the fruitful interplay of coding theory and algebraic combinatorics, with most of the focus on the interaction of codes with combinatorial designs, finite geometries, simple groups, sphere packings, kissing numbers, lattices, and association schemes. In particular, special interest is devoted to the relationship between codes and combinatorial designs. We describe and recapitulate important results in the development of the state-of-the-art. In addition, we give illustrative examples and constructions, and highlight recent advances. Finally, we provide a collection of significant open problems and challenges concerning future research.

In this chapter, the algebra of groups ring and matrix rings is used to construct and analyze systems of zero-divisor and unit-derived codes. These codes are more general than codes from ideals (e.g. cyclic codes) in group rings. They expand the space of linear block codes, offering additional flexibility in terms of desired properties as algebraic formulations, while also have readily available generator and check matrices.

A primer is presented in the necessary algebra, showing how group rings and certain rings of matrices can be used interchangeably. Then it is shown how the codes may be derived, showing particular cases such as self-dual codes and codes from dihedral group rings.

In this chapter, low density parity check (LDPC) codes and convolutional codes are constructed and analyzed using matrix and group rings. It is shown that LDPC codes may be constructed using units or zero-divisors of small support in group rings. From the algebra it is possible to identify where short cycles occur in the matrix of a group ring element thereby allowing the construction, directly and algebraically, of LDPC codes with no short cycles. It is then also possible to construction units of small support in group rings with no short cycles at all in their matrices, thus allowing a huge choice of LDPC codes with no short cycles which may be produced from a single unit element. A general method is given for constructing codes from units in abstract systems. Applying the general method to the system of group rings with their rich algebraic structure allows the construction and analysis of series of convolutional codes. Convolutional codes are constructed and analyzed within group rings in the the infinite cyclic over rings which are themselves group rings.

This chapter gives an introduction to algebraic coding theory and a survey of constructions of some of the well-known classes of algebraic block codes such as cyclic codes, BCH codes, Reed–Solomon codes, Hamming codes, quadratic residue codes, and quasi-cyclic (QC) codes. It then describes some recent generalizations of QC codes and open problems related to them. Also discussed in this chapter are elementary bounds on the parameters of a linear code, the main problem of algebraic coding theory, and some algebraic and combinatorial methods of obtaining new codes from existing codes. It also includes a section on codes over ℤ₄, integers modulo 4, due to increased attention given to these codes recently. Moreover, a recently created database of best-known codes over ℤ₄ is introduced.

We show how universal codes can be used for solving some of the most important statistical problems for time series. By definition, a universal code (or a universal lossless data compressor) can compress any sequence generated by a stationary and ergodic source asymptotically to the Shannon entropy, which, in turn, is the best achievable ratio for lossless data compressors.

We consider finite-alphabet and real-valued time series and the following problems: estimation of the limiting probabilities for finite-alphabet time series and estimation of the density for real-valued time series, the on-line prediction, regression, classification (or problems with side information) for both types of the time series and the following problems of hypothesis testing: goodness-of- fit testing, or identity testing, and testing of serial independence. It is important to note that all problems are considered in the framework of classical mathematical statistics and, on the other hand, everyday methods of data compression (or archivers) can be used as a tool for the estimation and testing.

It turns out, that quite often the suggested methods and tests are more powerful than known ones when they are applied in practice.

This chapter contains two parts. The first part gives an introduction to a relatively new communication paradigm: Network coding, where network nodes, instead of just forwarding symbols or packets, also are allowed to combine symbols and packets before forwarding them. The second part focuses on deterministic encoding algorithms for multicast, in particular for networks, which may contains cycles.

We consider the problem of transmission of several distributed sources over a multiple access channel (MAC) with side information at the sources and the decoder. Source-channel separation does not hold for this channel. Sufficient conditions are provided for transmission of sources with a given distortion. The source and/or the channel could have continuous alphabets (thus Gaussian sources and Gaussian MACs are special cases). Various previous results are obtained as special cases. We also provide several good joint source-channel coding schemes for a discrete/continuous source and discrete/continuous alphabet channel. Channels with feedback and fading are also considered.

Low-density parity-check (LDPC) codes are a class of error-correction codes, which attract much attention recently. The LDPC codes can approach within one-tenth dB of the Shannon limits. The codes have already found many applications in practice. This chapter presents a tutorial exposition of LDPC codes and the related performance analysis methods.

The aim of this chapter is to present, in appropriate perspective, some selected topics in the theory of variable-length codes. One of the domains of applications is lossless data compression. The main aspects covered include optimal prefix codes and finite automata and transducers. These are a basic tool for encoding and decoding variable-length codes. Connections with codes for constrained channels and sources are developed in some detail. Generating series are used systematically for computing the parameters of encodings such as length and probability distributions. The chapter contains numerous examples and exercises with solutions.

In this chapter, we discuss decoding techniques and finding the minimum distance of linear codes with the use of Gröbner bases. First, we give a historical overview of decoding cyclic codes via solving systems of polynomial equations over finite fields. In particular, we mention papers of Cooper, Reed, Chen, Helleseth, Truong, Augot, Mora, Sala, and others. Some structural theorems that use Gröbner bases in this context are presented. After that we shift to the general situation of arbitrary linear codes. We give an overview of approaches of Fitzgerald and Lax. Then we introduce our method of decoding linear codes that reduces this problem to solving a system of quadratic equations. We discuss open problems and future research possibilities.

Cooperative diversity represents a new class of wireless communication techniques in which network nodes help each other in relaying information to realize spatial diversity advantages. This new transmission paradigm promises significant performance gains in terms of link reliability, spectral efficiency, system capacity, and transmission range. Cooperative diversity has spurred tremendous excitement within the academia and industry circles since its introduction and has been extensively studied over the last few years. This chapter presents an overview of cooperative diversity conveying the underlying basic principles and further discusses the latest advances and open issues in this rapidly evolving field.

For a long time, cryptography was only concerned by message confidentiality (how to convert a text in an incomprehensible form for non-authorized readers). Nowadays, with the development of network communications, cryptography is devoted to the study of numerous problems concerning security: authentication, message integrity checking, digital signatures, secure computation, …. The security of basically all real-life protocols is actually based on hard problems coming from number theory. The aim of this chapter is to show that algebraic coding theory offers an alternative way to define secure cryptographic primitives.