- Description
- Channel Coding in Communication Networks: From Theory to Turbo Codes
- Channel Coding in Communication Networks: From Theory to Turbocodes - Google Книги
- Channel Coding in Communication Networks

### Description

Random coding We will first consider the means of implementing random coding without questioning for the moment the motivations of its use. It will be enough for us to state here that the use of random coding was justified for Shannon due to the lack of an optimal or near-optimal channel coding technique which, besides, is still the case after 50 years of research. By demonstrating the fundamental theorem for the average of a probabilistic set of codes we guarantee the existence of a code in this set which satisfies it without having to clarify its construction.

An a posteriori reflection will enable us to better understand its significance. As a simplifying hypothesis we will admit that the set of distances between the codewords and a given word is the same regardless of what this word is, so that, if the word formed by n zeros belongs to the code, as we will suppose, the distribution of weights is identified with that of all the distances between its codewords.

This property is perfectly verified for the important class of linear codes, which will be defined in Chapter 2. In addition we only consider the average properties of random coding, admitting that a code with an average distribution of distances of random coding is good. Let us suppose initially that we randomly draw 2n binary codewords with a length n with the same probability and independent of each other.

We thus obtain on average all the n-tuples, i. Since we have demonstrated the need for redundancy obtained by selection of codewords, we only need to draw 2k codewords, with k 24 Channel Coding in Communication Networks 1. Gilbert-Varshamov bound This method of construction of a quasi-random code, by decimation of the set of n-tuples, supposes that its minimal weight wmin is at least equal to a limit, which we will calculate as follows.

We note that the obtained limit [1. A geometrical interpretation For a binary symmetric channel with a probability of error p and coding by blocks where the codewords have the length n, the number of erroneous binary symbols per codeword is a random variable F with Bernoulli distribution, that is: The set En of binary n-tuples can be considered, from a geometrical point of view, as a space with n dimensions. Every n-tuple is a point of this space whose coordinates are binary.

The distances between these points are measured using the Hamming metric introduced at the beginning of section 1. We will suppose that the decimation carried out to pass from the set of 2n points of space to a subset comprising only 2k points is such that its distribution of weight is close to the average weight distribution of random coding, without further exploring the means of carrying it out. According to section 1. However, the redundancy of code means that its codewords are rare in En , and much more so are the codewords at a minimum distance from a given codeword, which makes this occurrence highly improbable.

We will obtain much better bounds of the probability of error decreasing as a function of the exponential of n in the following section. In this geometrical interpretation, random coding appears as a means of distributing the points in En as regular as possible, whereas in general we know of no deterministic means of obtaining this result. The improvement of the performance of the code through an increase of the length n of the codewords can be surprising, since it tends to render certain the presence of many errors in the codeword. The important fact is that the law of large numbers also makes the received codeword almost certainly localized on the surface of a Hamming sphere centered on the transmitted codeword, with a known radius np.

If the spheres with np radius centered on all the transmitted codewords are not connected, it is enough to take an n large enough to render the probability of error as small as we wish. We will encounter this property again for the channel with additive white Gaussian noise considered in section 1. This proof does not have a spontaneous nature, in the sense that it starts with an increase of the probability of error chosen so as to lead to the already known result sought, but it has the merit of providing very interesting details on the possible performances of block codes.

In addition, it implements random coding, a basic technique introduced by Shannon for the proof of the theorem and already discussed in section 1. Here is what the simplifying assumptions consist of: This type of coding is called block coding. Information Theory 27 — Less essentially, the channel is supposed to be without memory, this assumption being introduced during the proof.

Upper bound of the probability of error Let Xn be the set of possible codewords of length n at the channel input and Yn be the set of codewords that can be received at its output. We suppose finite Xn and Yn. A code of M words is used, defined by a bijective mapping of the set of message indices, i. The emission of the mth codeword represents the mth message. We suppose that the reception occurs with maximum probability, i. The expression between brackets is thus larger than 1, a property that remains after the expression is taken to the positive power of s.

It leads to [1. Use of random coding This upper bound is valid for any code, but it is generally too complicated to be useful directly. To go further it is necessary to draw on the method of random coding already mentioned. We no longer consider a single code how could code be specified a priori which would minimize the probability of error? It will be easy to calculate an upper bound of its average probability of error.

It will then be shown that if the inequality [1. According to this method, random coding consists of choosing each codeword independently of the others with a probability P x defined over the set of sequences of input Xn. We will calculate an upper bound of the average P em of Pem with respect to the set of codes constructed in this manner.

Conditional probabilities in the right-hand side of [1. They have been selected independently of each other as belonging to the code, so that these conditional probabilities are independent random variables. We will represent the averages by superscript bars in the rest of this section. We can then note that in [1. We thus deduce from [1.

After substitution according to [1. In the case of a channel without memory, in the sense that the successive errors in it are independent, this limit can be simplified. The independence of the successive transitions in the channel leads to: The sum then relates to the products in the form: Indicating by a1 , a2 ,. We note that the bound obtained is independent of the transmitted message m. Form of exponential limits The bound [1. Without getting into detail of the discussion of [1. For example, in the case of the binary symmetric channel, the largest upper bound of the probability of error is obtained [1.

Pe is the capacity of the channel, [13,14]. We see that the factor of n in the exponent of [1. Channels with continuous noise 1. Introduction Up until now we could satisfy ourselves with the description of a discrete channel by its transition probabilities and took the example of the binary symmetric channel, which is the simplest model there is. We will now consider some more realistic channel models.

One of the principal restrictions made above relates to the finite character of the channel input and output alphabets. For the input alphabet it stems naturally from the choice made to limit ourselves to finite discrete, i. The omnipresence of thermal noise, modeled well by the addition of white Gaussian noise, makes the assumption of a finite output alphabet exaggeratedly restrictive.

We will thus devote a particular development to the channel with additive Gaussian noise. The noise will be initially supposed to be white, but this restriction will be easily raised. More briefly, we will also consider the channel with fadings where the received signal undergoes fluctuations represented by a Rayleigh process multiplying its amplitude before adding white Gaussian noise. Let X be a continuous random variable with probability density function pX x , i. This value has some but not all of the properties of the entropy of a discrete variable.

Thus, it can be negative and loses certain properties of invariance. Its principal interest lies in the fact that the mutual information generalized to continuous variables is still expressed, as in [1. Information Theory 33 By analogy with the discrete case where the capacity of a binary symmetric channel is equal to mutual information for the probability distribution of the input symbols making their entropy maximal, we will admit that the capacity of the channel is obtained for the distribution of input variables, which is here continuous, which renders the differential entropy maximal.

To reach the capacity we will admit that the distribution of the channel input variables must be such. The mutual information between the input and output variables both Gaussians expressed by the difference between differential entropies at output, respectively not conditional and conditional at input, is thus equal to half of the logarithm of the ratio of the corresponding variances. However, the addition of Gaussian noise to the channel input variable X gives a variable Y which is also Gaussian with variance equal to the sum of those of channel noise and input signal.

Indeed, the sum of two Gaussian variables is a Gaussian, the noise and the signal are independent so that their variances are added and, in addition, the differential entropy of Y conditionally to the input variable X is equal to the differential entropy of noise because it is additive. The assumption of a source without memory has its equivalent here in the limitation of the band to a certain value B, so that the sampling theorem makes it possible to represent exactly and reversibly any signal pertaining to the set of functions in a band limited to B by the sequence of values which it takes with periodic intervals, known as samples.

Thus, thanks to the discretization of time realized by the sampling of interval T , we find the same diagram of communication as in our introduction, with the difference that the channel input alphabet has become the entire set of real numbers. Its symbols, the samples, undergo the sole disturbance of the addition of noise present in the band B. The capacity of this channel is thus equal to: This is the capacity by symbol or sample ; the capacity in shannons by second stems from that by multiplying it by the frequency 2B of samples, that is: It has paradoxical consequences for the role of the bandwidth in communications through a channel with additive white Gaussian noise.

This conclusion is radically opposed to the dominant trend in traditional radio-electronics, where apparent common sense suggests limiting the bandwidth as much as possible in order to reduce the noise entering the receiver. It is true that the channel coding function2 was then unknown, although it alone can exploit the increase in capacity due to band widening.

Generalization to the case where the noise power spectral density varies in the signal band is easy the noise is then known as colored. It suffices to divide the band into infinitesimal intervals, each considered as defining a channel with additive white Gaussian noise and to treat these channels in parallel.

The total capacity is equal to the sum of the capacities of the constituent channels. The calculation of variations indicates how to maximize it when the total power of the useful signal is given: This result can be expressed by an image: Information Theory 35 by a horizontal, which we could obtain by pouring a liquid whose volume would represent the total power of the signal a result introduced by Shannon, often called water-filling.

Communication via a channel with additive white Gaussian noise We note that the capacity [1. Even if the signal thus obtained does not rigorously conform with the assumption of band limitation, the geometrical representation of signals in an Euclidean space with a finite number of dimensions remains, at the cost of a redefinition of the bandwidth; see, for example [1], p.

Coding is only useful if the signal to noise ratio is small enough so that the capacity [1. We will note that the capacity calculated supposing an alphabet of finite size q is very close to [1. More refined means of distributing points in Euclidean space using codes defined for finite alphabets will be shown in Chapter 4. Demodulation, decision margin The continuous character of the received signals requires detailed attention.

With regard to decoding, two unequally effective and complex strategies are possible: We are then brought back to the problem considered in Paragraph 1. In this case we speak of a soft decision, although this is rather a case of an absence of an explicit decision. Information Theory 37 The second strategy exploits information that the first strategy lacks carried by the margin y of each decision providing information on its reliability.

It is thus more effective in principle: However, the implementation of this second strategy is more difficult, because it requires the decoder to deal with real numbers: However, an important branch of the studies of channel coding is based on the algebraic properties of finite bodies.

The use of soft decisions prohibits treating decoding as an algebra problem, even though the construction of the code makes use thereof. A random variable A of unitary variance following the Rayleigh law has as a probability density function: We suppose that the signal is transmitted with constant amplitude. It is, therefore, modulated only in phase. The received average power is equal to P and we admit that the signal band remains limited to B this assumption is not rigorously exact, but can be allowed by way of an approximation.

An interleaving and disinterleaving device provides the successive samples of the received signal, after disinterleaving sufficiently distant in time in the channel to be regarded as independent. These samples are none other than those of one of the two components in signal quadrature. Since the amplitude of the signal follows the Rayleigh law [1. We have already calculated the capacity [1. The presence of fadings of Rayleigh thus does not modify the capacity, although it complicates the reception notably and, in practice, often degrades the result.

The conservation of the capacity of the channel with additive Gaussian noise in the presence of Rayleigh fadings suggests that it must be possible to arbitrarily reduce the degradation which they cause. When auxiliary devices, in particular, those of interleaving and diversity, make it possible to effectively employ error correcting codes, we will note that the benefit of coding, measured by the increase in the signal to noise ratio needed without coding to obtain the same probability of error as with coding, is much more important for the channel with fadings than where the only disturbance is the addition of Gaussian noise.

Indeed, the probability of error in the absence of coding decreases when the signal to noise ratio increases a lot less quickly in the presence of signal fadings, and the benefit brought by the system of coding is a reduction of the probability of error. Information theory and channel coding The presence of disturbances in the channel limits the possible flow of information, but not the quality with which the message can be restored: The limitation of the flow of information to a value smaller than the channel capacity is achieved by the introduction of redundancy, but it is only one of the conditions necessary to control the error rate upon decoding.

The entire problem of channel coding lies in the manner of doing it. The ultimate possible limit in information theory, i. Turbocodes and the extraordinary torrent of research that they unleashed have contradicted this assertion and now it is in tenths of a decibel that we express the variation of the best experimental results with respect to capacity, for a channel with additive white Gaussian noise.

Which consists of jointly exploiting several supports of the same information. Information Theory 39 The key question of channel coding is the complexity of decoding. If we could get rid of it, almost any code would be satisfactory. Indeed, not only random coding is good on average, but it is known that almost all codes are good. Unfortunately, the complexity of decoding for a random code increases exponentially with the length of the code, which must be large in order to obtain small probabilities of error. Efficient use of random coding is thus absolutely out of the question; we can only hope to employ codes provided with a structure which facilitates their decoding.

Coding being incomparably easier than decoding, two extreme manners of undertaking the study of channel coding were conceivable and both were actually tried out: Very schematically, the first tendency gave rise to algebraic codes and the second led to the development of convolutional codes, for which the principal results are, in fact, not families of codes, but decoding algorithms.

The results of these studies were initially confronted with reality in space communication applications, where the channel is well modeled by the addition of white Gaussian noise, and where the improvement of coding and decoding devices that the immense progress of electronic technology now allows with reliability and economy costs much less than the improvement of the energy cost of the connection. We saw that the weighting of decoding avoids a costly loss of information. The ease of its implementation in algorithms stemming from the second tendency is the main reason for its success.

Research in channel coding in the simplest cases binary symmetric channel and channel with additive white Gaussian noise with a weak signal to noise ratio have produced an impressive arsenal of tools. Apart from the important exception of the Reed-Solomon codes, these are mainly binary codes. For other, often much more complicated, channels in general we still employ the means created in this manner, but auxiliary techniques interleaving diversity.

Application aux techniques de communication, Masson, These articles have been reprinted with a commentary of W. Weaver in the form of a book entitled The mathematical theory of communication, University of Illinois Press, Chapter 2 Block Codes 2. The fundamental question of message redundancy We wish to transmit messages from point A to point B through space transmission channel , or from point A to point A through time recording channel.

Any transmission of information is a voluntary energy modulation. The channel which allows the transmission is traversed by random energy impulses. This parasitic energy produces transmission errors: In a binary transmission, 1 is transformed into 0, and conversely. When we have difficulties transmitting a word or a message because of the noise, we naturally tend to repeat the word or the message. It is then said that we add redundancy to the information. Now, let us consider that the message to be transmitted is coded into binary, i.

One of the first problems that had to be dealt with during World War II was how to contact the American spies in hostile German territory. The spies could not ask for retransmission for fear of being discovered. If the message was short it was completely destroyed by jamming if the jamming affected it.

If the message was reinforced with redundancy, there was more chance than it would be affected, but it was less susceptible. The question that would then arise was the following: The answer was provided by C. He created the information theory, which led him to formalize the problem, to define a mathematical measure of Chapter written by Alain P OLI. The lower bound of this quantity is determined on the basis of a channel characteristic: The empirical proof was provided very quickly before by Hamming, Golay, and others who offered examples of codes constructions.

Unstructured codes In the rest of this section we restrict ourselves to binary codes, i. Each codeword has the same length n. We wish to code a set of messages. Each message, or information word, is coded by a binary word codeword. The set of codewords is called the code. The Hamming distance between x and y is the number of positions where these two vectors are different.

It is noted dH x, y. The Hamming weight of x is equal to the number of non-zero components. It is noted wH X. It is also equal to dH x, 0n , where 0n indicates the vector 0,.

- Account Options.
- Wentworth Rock!
- Waltzing the Tango: A Late Boomer Dances to the Wrong Tune.
- Product details.
- Cold Hands and Other Stories;

The Euclidean distance between them is equal to: Code parameters A code is a set of codewords, characterized by a family of parameters: It is also said that the code has a length n, 2 the number M of codewords. It characterizes the transmission capacity of the code, Block Codes 43 3 the minimum distance d of the code. It is related to the capacity of correction of the code, 4 the maximum correction capacity per codeword, noted t, 5 the minimum weight of a code, noted w.

Find w and d. If yes, find w and d. Code, coding and decoding In this section we introduce the concepts of code, coding and decoding with maximum probability. An unstructured binary code of length n is a family of vectors included in F2 n. The assumption made is thus equivalent to supposing that it is more probable that the distance between the transmitted word and the received word is 0 rather than 1, 1 rather than 2, etc.

Maximum likelihood decoding thus implies decoding the word received by the nearest codeword. If this codeword is not unique we do not decode. Bounds of code parameters The parameters n, M and d are connected with each other by various constraints. If two are fixed values, then the value of the third is limited by certain traditional inequalities. In general, we cannot calculate the best possible value for this third parameter. A bound on M is as follows. What is the largest number of words M of length n in a code allowing the correction of t errors per word?

The disjoint spheres are counted and total volume is calculated. It is necessary to have: Thus, M is less than or equal to 5. It should be noted that it may not be possible to obtain the value M. Similarly, M being fixed, the best error correcting capability can be much lower than the value of t obtained from the previous formula.

Linear codes As we can see it from the exercises in the preceding section, it is very difficult to construct unstructured codes. The best possible code is equivalent to the best packing of spheres, which is a very complex problem. In order to be able to build codes more easily, we agree to lose some freedom by imposing an algebraic structure on the code. We will thus consider the binary codes with a particular property: Introduction These codes have a structure of vector subspaces of F2 n. If the code C is a vector subspace of dimension k, it is said that the dimension of the linear code C is k.

The number of words in C is then 2k. Properties of linear codes These codes have properties used for their decoding or construction. Block Codes 45 2. Minimum distance and minimum weight of a code The following proposition makes it possible to simplify obtaining the minimum distance when the code is linear. The minimum weight of a code is equal to its minimum distance. Linear code base, coding Let us simply demonstrate on an example a particular basic form of a code systematic form.

It is a free family. In systematic form this base is described as: We call a linear code generator matrix C n, k, d any matrix whose rows are vector representations of a base of C. Systematic coding corresponds to the fol- i1 , i2 ,. Put G in systematic form. Encode with G. Encode with I3 R. Encode a, b, c with the two matrices, and compare. Singleton bound The following proposition introduces the Singleton inequality and the Singleton bound. Let n, k, d be a linear code C n, k, d.

We have the inequality called Singleton inequality: Consider a generator matrix in systematic form. The verification is direct. Reminders of the Gaussian method To pass from a generator matrix of C to a parity check matrix and reciprocally we often use the method of Gaussian pivots. In F2 we take: In F3 we take: In F3 we takes: The element u is called a representative of the class Cu.

This is used in certain decodings. The set of lateral classes of C forms a partition of F2 n , in parts of the same cardinal. Any u of F2 n is in its own class. The set of classes is thus a repetition of F2 n. It remains to prove that two distinct classes do not have common elements, which stems from the previous proposition. Syndromes Now we introduce the concept of a vector syndrome.

The proof bears on the necessity and the sufficiency of the condition: Calculate H[v]T [v]T is v transposed. Let H be a parity check matrix of the code C: This makes it possible to simplify the decoding practice. Decoding and syndromes Let v be a received word. Lateral classes, syndromes and decoding We use maximum likelihood decoding. Thus we decode by a codeword of C which is the closest to the received word in the sense of Hamming distance.

If v is the received word, then the error is any element of the class of v. The error can be , , , , , , , We will suppose maximum likelihood decoding and, thus, that the error was The decoded word will then be In fact, we calculate the syndrome of the received word v. This syndrome is the same for any element of Cv. We then suppose that the error is the word with the smallest weight in Cv this is maximum likelihood decoding. Parity check matrix and minimum code weight The following proposition expresses a property of minimum code distance and parity check matrix.

We take as code C the code known as the Hamming code 7,4,3. Its parity check matrix: The minimum distance of C is 3. We take as code C the Hsiao code 8,4,4 whose parity check matrix is: Hamming codes have a parity check matrix formed by all the non-zero r-tuples. An RM code with a length of 2m and order r is built on the basis of vectors v0 , v1 ,.

The codewords of an RM code of length 2m and order r are all the products component by component of a maximum vi. The code has , , , , , , , , as words. Decoding of linear codes There are various more or less complex decodings possible, such as, for example, lattice decoding, studied by S. Step by step decoding Let us now introduce a very easy algorithm that can be used for all linear codes.

Let there be a linear code C, of length n, corrector of t errors by word, for which we take a generator matrix G. We will suppose that C is binary, although this decoding extends directly to non-binary codes. Preparation of decoding The following steps must be performed before proceeding to decoding: Initialization phase The initialization phase comprises three stages: The iterative stage comprises two stages: If it is not found, the error cannot be corrected.

Let C be a BCH code see section 2. Its generator matrix is: Block Codes 53 Iterative phase: We also presume that the concept of ring of polynomials on the Fp field is also known. An important result concerning the ring of polynomials is the following. Any non-zero polynomial of degree n has at most n roots in a field.

The proof is outside the scope of this book. We easily prove that it is a ring. We see that we obtain a circular shift with each multiplication by X. If there are two irreducibles of the same degree n, then we have two representations of the same Fq field. It is sometimes necessary for example for certain decodings to seek the roots of a polynomial in a given field.

Let us give an example of such a search for the roots of a polynomial b Y in a finite field. It is a root. Let us note that it is invertible because it is in a field. Block Codes 55 2. E is finite because it is part of a finite field. We find that its order is 5. We find that its order is Properties of the order The three following propositions express the properties of the order.

We know that the cardinal of a subgroup divides the cardinal of the group which it contains. Lastly, e is the cardinal of the subgroup. We will see that there always exists such an element in a field. We will prove the existence, then give the number of such elements in Fq. There thus exist particular elements y1 , y2 ,. Its order is pm 1. Using the same argument we also obtain the elements z2 ,.

Let E be the order of t. Let x be a primitive. The group of invertibles thus has 6 elements. Element 2 has an order 6. It is a primitive from the group of invertibles.

## Channel Coding in Communication Networks: From Theory to Turbo Codes

The invertibles 1, 3, 5, 7 have the respective orders 1, 2, 2, 2. Thus, there are no primitives. The number of primitives The number of primitives is specified by the following result. Use of the primitives The primitive elements are often used in the application of error correcting codes. It is a rather complex operation, both time and power consuming. Therefore, in practice it is interesting to change the representation of the field. The advantage is as follows. This disadvantage can be mitigated by using a Zech table. We have the following representation: The Zech table is presented as follows: How to find a primitive We cannot find a primitive formally, but we can use the following algorithm: Exponentiation We saw how to search for the order of an element, and how find out if it is primitive.

For large fields i. One of the best methods is to proceed as follows: We prove that the complexity is in O log i instead of O i. This method is used, for example, for calculations necessary for the use of RSA in cryptography. There exists a polynomial with binary coefficients, which admits all the elements of this part as the set of its roots. This polynomial is irreducible. It is a finite part, because it is included in a finite field. It has the symmetrical functions of its roots as coefficients. Thus, each of its coefficients is invariant under exponentiation by 2.

Each coefficient is, therefore, binary. This polynomial is irreducible, since otherwise it would have a divisor of a strictly smaller degree than it does. As this class is invariant under exponentiation by 2, and according to proposition 2. This is impossible according to proposition 2. Thus, this divisor strictly cannot exist. If x has as an order n, it is said that it is a nth primitive root of unity.

The set of nth roots of unity forms a subgroup thereof. Block Codes 61 Proof. We can build a particular geometry, known as projective geometry.

- A Defence Of The Opinion Concerning Personal Identity (With Active Table of Contents).
- Cómo hacer un generador de energía solar por menos de $ 300 (Spanish Edition).
- Channel Coding in Communication Networks: From Theory to Turbocodes;
- Postcards From the Hedge!
- Dominique Ansel: The Secret Recipes.

It is a subspace of dimension 1 deprived of 0. The points are as follows: The projective straights are as follows: The set of the points can thus be arranged like a cyclic sequence. Cyclic codes After the theoretical results of C. Shannon and the first linear code constructions Hamming, Golay American engineers were required to be able to obtain codes stable not only under addition linear codes , but also stable under circular sliding or shift. The codes obtained cyclic codes are linear codes with additional properties. An ideal A is a non-empty part, stable under addition, and stable under multiplication by any element of A.

## Channel Coding in Communication Networks: From Theory to Turbocodes - Google Книги

It is a cyclic code of length n. Everywhere hereinafter n is odd. Introduction The following results express the properties of a cyclic code. Any code C, stable under addition and circular shift may be represented as an ideal A. The circular shift on the right represents the multiplication by X in A. The code C is thus stable under addition and multiplication by X.

It is therefore stable under addition and multiplication by any polynomial: He passed away after a long illness on September 25th, at the age of Principal coding functions 5 1. Source coding 5 1. Channel coding 6 1. Standardization of the Shannon diagram blocks 8 1. Fundamental theorems 9 1. Quantitative measurement of information 9 1. Measurement of self-information 10 1. Entropy of a source 11 1. Mutual information measure 12 1. Channel capacity 14 1.

Comments on the measurement of information 15 1. Source coding 15 1. Decodability, Kraft-McMillan inequality 16 1. Demonstration of the fundamental theorem 17 1. Outline of optimal algorithms of source coding 18 1. Channel coding 19 1. Introduction and statement of the fundamental theorem 19 1. General comments 20 1. Need for redundancy 20 1.

## Channel Coding in Communication Networks

Example of the binary symmetric channel 21 1. A geometrical interpretation 25 1. Channels with continuous noise 32 1. A reference model in physical reality: Communication via a channel with additive white Gaussian noise 35 1. Channel with fadings 37 1. Information theory and channel coding 38 1. Bibliography 40 Chapter 2. Unstructured codes 41 2. The fundamental question of message redundancy 41 2. Unstructured codes 42 2. Linear codes 44 2. Properties of linear codes 44 2. Dual code 46 2. Some linear codes 50 2. Decoding of linear codes 51 2.

Finite fields 53 2. Basic concepts 53 2. Irreducible polynomial modulo calculations: Minimum polynomials 59 2. The field of nth roots of unity 60 2. Projective geometry in a finite field 61 2. Cyclic codes 62 2. Base, coding, dual code and code annihilator 63 2. Certain cyclic codes 68 2. Existence and construction of cyclic codes 74 2. Applications of cyclic codes 82 2. Electronic circuits 82 2.

Basic gates for error correcting codes 82 2. Shift registers 83 2. Circuits for the correct codes 83 2. Polynomial representation and representation to the power of a primitive representation for a field 87 2. Decoding of cyclic codes 88 2. Meggitt decoding trapping of bursts 88 2. Decoding by the DFT 89 2. The book concludeswith a chapter on the implementation of turbocodes in circuits.

As such, anyone involved in the areas of channel coding anderror correcting coding will find this book to be of invaluableassistance. It starts with a description of information theory,focusing on the quantitative measurement of information andintroducing two fundamental theorems on source and channel coding. The basics of channel coding in two chapters, block Channel Coding in Communication Networks: From Theory to Turbocodes.