Catálogo de publicaciones - libros

The theoretical performance of binary codes for the additive white Gaussian noise (AWGN) channel is discussed. In particular, Gallager’s coding theorem for binary codes is treated extensively. By assuming a binomial weight distribution for linear codes, it is shown that the decoder error probability performance of some of the best, known linear, binary codes is the same as the average performance of the ensemble of all randomly chosen, binary nonlinear codes having the same length and dimension. Assuming a binomial weight distribution, an upper bound is determined for the erasure performance of any code, and it is shown that this can be translated into an upper bound for code performance in the AWGN channel. Finally, theoretical bounds on the construction of error-correction codes are discussed.

In this chapter, we discuss the performance of codes under soft and hard decision decoding. Upper and lower bounds on hard and soft decision decoding are discussed. For hard decision decoding, evaluation of the performance of specific codes shows that full decoding produces better performance than the usual bounded distance decoder. An analysis of the upper and lower union bounds on the probability of error for maximum likelihood soft decision decoding shows that contrary to hard decision decoding above relative low values of SNR per information bit, the two bounds coincide. The implications of this observation is that the soft decision decoding performance may be determined for a linear code by the number of minimum Hamming weight codewords without the need to determine the weight distribution of the code. Numerical performance comparisons are made for a wide range of different codes. It is shown that the binomial weight distribution provides a good indicative performance for codes whose weight distribution is difficult to obtain.

In many modern communication systems, the full benefits of error-correction coding are only realised if the decoder is able to utilise soft decision decoding. In this chapter, we give both approximate and exact bounds on the performance of soft decision decoding compared to hard decision decoding. The effects of soft decision quantisation are explored as a function of the number of quantisation levels. Examples are given of the different performance achieved using soft and quantised soft decision decoding for (100,50) and (200,100) binary codes. A modified version of the near maximum likelihood decoder, the Dorsch decoder described in Chap. , is presented for hard decision decoding. The performance improvements achieved by the decoder, compared to bounded distance decoding, are evaluated for some BCH codes.

The important family of binary cyclic codes is explored in this chapter. Starting with cyclotomic cosets, the minimal polynomials are introduced. The Mattson–Solomon polynomial is described and it is shown to be an inverse discrete Fourier transform based on a primitive root of unity. The usefulness of the Mattson–Solomon polynomial in the design of cyclic codes is demonstrated. The relationship between idempotents and the Mattson–Solomon polynomial of a polynomial that has binary coefficients is also described. It is shown how binary cyclic codes may be easily derived from idempotents based on the cyclotomic cosets. It is demonstrated how useful this can be in the design of high-degree non-primitive binary cyclic codes. Several code examples using this construction method are presented. A table listing the complete set of the best binary cyclic codes, having the highest minimum Hamming distance, is included for all code lengths from 129 to 189 bits.

Two of the important performance indicators for a linear code are the minimum Hamming distance and the weight distribution. This chapter is concerned with methods and tools for producing new codes which are improvements to currently known codes. The chapter discusses and describes several efficient algorithms for computing the minimum distance and weight distribution of linear codes. Several different methods of constructing codes are described and several new codes are presented which are improvements to the codes listed in the database of best-known codes. Methods of combining known codes to produce good codes are also explored in detail. These methods are applied using cyclic codes as components to the new codes and several new binary codes are found as a result.

Interpolation plays an important, mostly hidden role in algebraic coding theory. Reed–Solomon codes, BCH codes, and Goppa codes are all codes that may be constructed via interpolation. It is shown that all of these codes form part of a large family of generalised MDS codes. Also in this chapter, we discuss the encoding of BCH and Goppa codes using classical Lagrange interpolation. It is shown in detail how Goppa codes are designed and constructed starting from first principles. The parity check matrix of a BCH code is derived as a Goppa code proving that BCH codes are a subset of Goppa codes. Following on from this and using properties of the cyclotomic cosets it is explained why the minimum Hamming distance of some BCH codes exceeds the BCH bound. It is shown how these outstanding BCH codes can be identified and constructed. A little known paper by Goppa is discussed and as a result it is shown how Goppa codes and BCH codes may be extended in length with additional parity check bits resulting in increased minimum Hamming distance of the code. Several examples are given of the technique which results in some exceptional codes. Reed–Solomon codes are explored as a means of constructing binary codes resulting in some best known codes.

This chapter further discusses the Reed–Solomon codes which are exceptional, symbol based, because they are maximum distance separable (MDS) codes. Though these codes are not binary codes, they can be used as binary codes. The performance of Reed–Solomon codes when used on a binary channel is explored in this chapter and compared to codes which are designed for binary transmission. The construction of the parity-check matrices of RS codes for use as binary codes is described in detail for specific code examples. The simulation results for three differently constructed (150, 75) codes for the binary AWGN channel using a near maximum likelihood decoder are presented. Surprisingly the best performing code at error rate is not the best-known (150, 75, 23) code. It is shown that this is due to the higher multiplicities of weight 32–36 codeword errors. However, beyond error rates the best-known (150, 75, 23) code is the best code.

This chapter introduces algebraic geometry (AG) codes. Algebraic geometry codes have good properties and some families of these codes have been shown to be asymptotically good. Concepts and notions relevant to AG codes are discussed with particular emphasis laid on the construction of AG codes. A generalised construction of AG codes is introduced and improvements to the tables of best-known codes are presented. This construction utilises the notion of places of higher degree of a curve as well as a new concatenation concept.

In this chapter, self-dual and binary double-circulant codes based on primes are discussed. Many double-circulant codes are self-dual. Binary self-dual codes form an important class of codes due to their powerful error-correcting capabilities and their rich mathematical structure. This structure enables the entire weight distribution of a code to be determined. With these interesting properties, this family of codes has been a subject of extensive research for many years. For these codes that are longer than around 150 bits, an accurate determination of the codeword weight distributions has been an unsolved challenge. We show that the code structure may be used in a new algorithm that requires less codewords to be enumerated than traditional methods. We describe the new algorithm in detail and present new, complete, weight distribution results for codes of length 152, 168, 192, 194 and 200. We describe a modular congruence method and show how it can be used to check weight distributions of codes and have corrected some mistakes in previously published results for codes of length 137 and 151. For evaluation of the minimum Hamming distance for very long codes, a new probabilistic method has been presented along with results for codes up to 450 bits long. It is conjectured that the (136, 68, 24) self-dual code is the longest extremal code, meeting the upper bound for minimum Hamming distance, and that no other, longer, extremal code exists.

In this chapter, convolutional codes are explored from the point of view of their historical performance in comparison to the performance realised with modern, best decoding techniques. Convolutional codes are implemented as tail-biting block codes with near maximum likelihood decoding featuring an extended Dorsch decoder. It is shown that the convolutional codes designed for space applications and sequential decoding over 40 years ago are very good codes, comparable to the best codes known today. The performance realised back then was limited by the sequential decoder as demonstrated by the presented results. An additional 2 dB of coding gain could have been realised using the modern, extended Dorsch decoder instead of the sequential decoder. However back then, this decoder had yet to be discovered and was probably too expensive for the technology available at the time. It is also shown that convolutional codes may be used as the basis for designing double-circulant block codes and vice versa. In particular, high, guaranteed values of may be obtained by basing convolutional codes on outstanding double-circulant codes. A memory 78, non-systematic, half rate convolutional code with a of 32 is presented based on the (200, 100, 32) extended quadratic residue, double-circulant code.