Essentials of Error-Control Coding - Hardcover

Farrell, Patrick

9780470035726: Essentials of Error-Control Coding

Hardcover

ISBN 10: 0470035722 ISBN 13: 9780470035726

Publisher: John Wiley & Sons Inc, 2006

This specific ISBN edition is currently not available.

Rapid advances in electronic and optical technology have enabled the implementation of powerful error-control codes, which are now used in almost the entire range of information systems with close to optimal performance. These codes and decoding methods are required for the detection and correction of the errors and erasures which inevitably occur in digital information during transmission, storage and processing because of noise, interference and other imperfections.

Error-control coding is a complex, novel and unfamiliar area, not yet widely understood and appreciated. This book sets out to provide a clear description of the essentials of the subject, with comprehensive and up-to-date coverage of the most useful codes and their decoding algorithms. A practical engineering and information technology emphasis, as well as relevant background material and fundamental theoretical aspects, provides an in-depth guide to the essentials of Error-Control Coding.

Provides extensive and detailed coverage of Block, Cyclic, BCH, Reed-Solomon, Convolutional, Turbo, and Low Density Parity Check (LDPC) codes, together with relevant aspects of Information Theory
EXIT chart performance analysis for iteratively decoded error-control techniques
Heavily illustrated with tables, diagrams, graphs, worked examples, and exercises
Invaluable companion website features slides of figures, algorithm software, updates and solutions to problems&;&;&;&;&;

Offering a complete overview of Error Control Coding, this book is an indispensable resource for students, engineers and researchers in the areas of telecommunications engineering, communication networks, electronic engineering, computer science, information systems and technology, digital signal processing and applied mathematics.

"synopsis" may belong to another edition of this title.

About the Author

Jorge Castiñera Moreira is Associate Professor (Senior Lecturer) in Communication Systems in the Electronics Department, School of Engineering, Mar del Plata University, Argentina. 
He is Director of the Communications Laboratory, Director of the research project &;Open Source software applications for wireless networks&; and co-director of the research project &;Information Theory. Data Networks. Chaos and Communications&;.  Jorge is also responsible for the teaching area &;Communications&;.

Patrick G. Farrell is Visiting Professor in the Department of Communication Systems at Lancaster University, UK, where he supervises 7 research assistants, 50 PhD and 35 MSc students.  His research interests include error-control coding, coded modulation, digital communications, multi-user communications and information theory and source coding.  Patrick has over 350 publications, reports and presentations, and is Editor of two book series (Academic Press and Research Studies Press).

From the Back Cover

Provides extensive and detailed coverage of Block, Cyclic, BCH, Reed-Solomon, Convolutional, Turbo, and Low Density Parity Check (LDPC) codes, together with relevant aspects of Information Theory
 Presents EXIT chart performance analysis for iteratively decoded error-control techniques
 Heavily illustrated with tables, diagrams, graphs, worked examples, and exercises
Includes an invaluable companion website featuring slides of figures, algorithm software, updates and solutions to problems

Excerpt. � Reprinted by permission. All rights reserved.

Essentials of Error-Control Coding

By Jorge Castieira Moreira, Patrick Guy Farrell

John Wiley & Sons

Excerpt

<h2>CHAPTER 1</h2>Information and Coding Theory In his classic paper 'A Mathematical Theory of Communication', Claude Shannon introducedthe main concepts and theorems of what is known as information theory. Definitionsand models for two important elements are presented in this theory. These elements are thebinary source (BS) and the binary symmetric channel (BSC). A binary source is a device thatgenerates one of the two possible symbols '0' and '1' at a given rate r, measured in symbolsper second. These symbols are called bits (binary digits) and are generated randomly.The BSC is a medium through which it is possible to transmit one symbol per time unit.However, this channel is not reliable, and is characterized by the error probability p (0 ≤ p ≤1/2) that an output bit can be different from the corresponding input. The symmetry of thischannel comes from the fact that the error probability p is the same for both of the symbolsinvolved.Information theory attempts to analyse communication between a transmitter and a receiverthrough an unreliable channel, and in this approach performs, on the one hand, an analysis ofinformation sources, especially the amount of information produced by a given source, and, onthe other hand, states the conditions for performing reliable transmission through an unreliablechannel.There are three main concepts in this theory:1. The first one is the definition of a quantity that can be a valid measurement of information,which should be consistent with a physical understanding of its properties.2. The second concept deals with the relationship between the information and the source thatgenerates it. This concept will be referred to as source information. Well-known informationtheory techniques like compression and encryption are related to this concept.3. The third concept deals with the relationship between the information and the unreliablechannel through which it is going to be transmitted. This concept leads to the definition ofa very important parameter called the channel capacity. A well-known information theorytechnique called error-correction coding is closely related to this concept. This type ofcoding forms the main subject of this book. One of the most used techniques in information theory is a procedure called coding, which isintended to optimize transmission and to make efficient use of the capacity of a given channel.In general terms, coding is a bijective assignment between a set of messages to be transmitted,and a set of codewords that are used for transmitting these messages. Usually this procedureadopts the form of a table in which each message of the transmission is in correspondencewith the codeword that represents it (see an example in Table 1.1).Table 1.1 shows four codewords used for representing four different messages. As seen inthis simple example, the length of the codeword is not constant. One important property of acoding table is that it is constructed in such a way that every codeword is uniquely decodable.This means that in the transmission of a sequence composed of these codewords there shouldbe only one possible way of interpreting that sequence. This is necessary when variable-lengthcoding is used.If the code shown in Table 1.1 is compared with a constant-length code for the same case,constituted from four codewords of two bits, 00, 01, 10, 11, it is seen that the code in Table 1.1adds redundancy. Assuming equally likely messages, the average number of transmitted bitsper symbol is equal to 2.75. However, if for instance symbol s2 were characterized by aprobability of being transmitted of 0.76, and all other symbols in this code were characterizedby a probability of being transmitted equal to 0.08, then this source would transmit an averagenumber of bits per symbol of 2.24 bits. As seen in this simple example, a level of compression ispossible when the information source is not uniform, that is, when a source generates messagesthat are not equally likely.The source information measure, the channel capacity measure and coding are all relatedby one of the Shannon theorems, the channel coding theorem, which is stated as follows:If the information rate of a given source does not exceed the capacity of a given channel,then there exists a coding technique that makes possible transmission through this unreliablechannel with an arbitrarily low error rate. This important theorem predicts the possibility of error-free transmisssion through a noisy orunreliable channel. This is obtained by using coding. The above theorem is due to ClaudeShannon, and states the restrictions on the transmission of information through a noisychannel, stating also that the solution for overcoming those restrictions is the application ofa rrrrather sophisticated coding technique. What is not formally stated is how to implement thiscoding technique.A block diagram of a communication system as related to information theory is shown inFigure 1.1.The block diagram seen in Figure 1.1 shows two types of encoders. The channel encoderis designed to perform error correction with the aim of converting an unreliable channel intoa reliable one. On the other hand, there also exists a source encoder that is designed to makethe source information rate approach the channel capacity. The destination is also called theinformation sink.Some concepts relating to the transmission of discrete information are introduced in thefollowing sections. 1.1 Information1.1.1 A Measure of InformationFrom the point of view of information theory, information is not knowledge, as commonlyunderstood, but instead relates to the probabilities of the symbols used to send messagesbetween a source and a destination over an unreliable channel. A quantitative measure ofsymbol information is related to its probability of occurrence, either as it emerges from asource or when it arrives at its destination. The less likely the event of a symbol occurrence,the higher is the information provided by this event. This suggests that a quantitative measureof symbol information will be inversely proportional to the probability of occurrence.Assuming an arbitrary message xi which is one of the possible messages from a set a givendiscrete source can emit, and P(xi) = Pi is the probability that this message is emitted, theoutput of this information source can be modelled as a random variable X that can adopt any ofthe possible values xi, so that P(X = xi) = Pi. Shannon defined a measure of the informationfor the event xi by using a logarithmic measure operating over the base b:Ii [equivalent to] -logb Pi = logb (1/Pi) (1) The information of the event depends only on its probability of occurrence, and is notdependent on its content.The base of the logarithmic measure can be converted by usingloga(x) = logb(x) 1/logb(a) (2) If this measure is calculated to base 2, the information is said to be measured in bits. If themeasure is calculated using natural logarithms, the information is said to be measured in nats.As an example, if the event is characterized by a probability of Pi = 1/2, the correspondinginformation is Ii = 1 bit. From this point of view, a bit is the amount of information obtainedfrom one of two possible, and equally likely, events. This use of the term bit is essentiallydifferent from what has been described as the binary digit. In this sense the bit acts as the unitof the measure of information.Some properties of information are derived from its definition:Ii ≥ 0 0 ≤ Pi ≤ 1Ii -> 0 if Pi -> 1Ii > Ij if Pi < Pj For any two independent source messages xi and xj with probabilities Pi and Pj respectively,and with joint probability P(xi , xj) = Pi Pj, the information of the two messages is the additionof the information in each message:Iij = logb 1/Pi Pj = logb1/Pi + logb 1/Pj = Ii + Ij 1.2 Entropy and Information RateIn general, an information source generates any of a set of M different symbols, which areconsidered as representatives of a discrete random variable X that adopts any value in the rangeA = {x1, x2, ..., xM}. Each symbol xi has the probability Pi of being emitted and containsinformation Ii. The symbol probabilities must be in agreement with the fact that at least oneof them will be emitted, so[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)The source symbol probability distribution is stationary, and the symbols are independentand transmitted at a rate of r symbols per second. This description corresponds to a discretememoryless source (DMS), as shown in Figure 1.2.Each symbol contains the information Ii so that the set{I1, I2, ..., IM} can be seen as adiscrete random variable with average information[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)The function so defined is called the entropy of the source. When base 2 is used, the entropyis measured in bits per symbol:[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)The symbol information value when Pi = 0 is mathematically undefined. To solve thissituation, the following condition is imposed: Ii = ∞ if Pi = 0. ThereforePi log2 (1/Pi) = 0(L'Hopital's rule) if Pi = 0. On the other hand, Pi log (1/Pi) = 0 if Pi = 1. Example 1.1: Suppose that a DMS is defined over the range of X, A = {x1, x2, x3, x4}, andthe corresponding probability values for each symbol are P(X = x1) = 1/2, P(X = x2) =P(X = x3) = 1/8 and P(X = x4) = 1/4.Entropy for this DMS is evaluated as[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]Example 1.2: A source characterized in the frequency domain with a bandwidth of W =4000 Hz is sampled at the Nyquist rate, generating a sequence of values taken from the rangeA = {-2, -1, 0, 1, 2} with the following corresponding set of probabilities {1/2, 1/4, 1/8, 1/16}.Calculate the source rate in bits per second.Entropy is first evaluated as[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]The minimum sampling frequency is equal to 8000 samples per second, so that the informationrate is equal to 15 kbps.Entropy can be evaluated to a different base by usingHb(X) = H(X)/log2(b) (6) Entropy H(X) can be understood as the mean value of the information per symbol providedby the source being measured, or, equivalently, as the mean value experienced by an observerbefore knowing the source output. In another sense, entropy is a measure of the randomnessof the source being analysed. The entropy function provides an adequate quantitative measureof the parameters of a given source and is in agreement with physical understanding of theinformation emitted by a source.Another interpretation of the entropy function is seen by assuming that if n >> 1 symbolsare emitted, nH(X) bits is the total amount of information emitted. As the source generatesr symbols per second, the whole emitted sequence takes n/r seconds. Thus, information willbe transmitted at a rate ofnH(X)/(n/r) bps (7)The information rate is then equal toR = rH(X) bps (8)The Shannon theorem states that information provided by a given DMS can be coded usingbinary digits and transmitted over an equivalent noise-free channel at a rate ofrb ≥ R symbols or binary digits per secondIt is again noted here that the bit is the unit of information, whereas the symbol or binarydigit is one of the two possible symbols or signals '0' or '1', usually also called bits.Theorem 1.1: Let X be a random variable that adopts values in the range A = {x1,x2, ..., xM} and represents the output of a given source. Then it is possible to show that0 ≤ H(X) ≤ log2(M) (9)Additionally,H(X) = 0 if and only if Pi = 1 for some iH(X) = log2(M) if and only if Pi = 1/M for every i (10)The condition 0 ≤ H(X) can be verified by applying the following:Pi log2(1/Pi) -> 0 if Pi -> 0 The condition H(X) ≤ log2(M) can be verified in the following manner:Let Q1, Q2, ..., QM be arbitrary probability values that are used to replace terms 1/Pi bythe terms Qi/Pi in the expression of the entropy [equation (5)]. Then the following inequalityis used:ln(x) ≤ x - 1where equality occurs if x = 1 (see Figure 1.3).After converting entropy to its natural logarithmic form, we obtain[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]and if x = Qi/Pi,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)As the coefficients Qi are probability values, they fit the normalizing condition[summation]Mi=1 Qi ≤ 1,and it is also true that [summation]Mi=1 Pi = 1.Then[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)If now the probabilities Qi adopt equally likely values Qi = 1/M,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)In the above inequality, equality occurs when log2(1/Pi)= log2(M), which means that Pi = 1/M.The maximum value of the entropy is then log2(M), and occurs when all the symbolstransmitted by a given source are equally likely. Uniform distribution corresponds to maximumentropy.In the case of a binary source (M = 2) and assuming that the probabilities of the symbolsare the valuesP0 = α P1 = 1 - α (14)the entropy is equal toH(X) = Ω(α) = α log2(1/α)+ (1 - α) log2 (1/1 - α) (15) This expression is depicted in Figure 1.4.The maximum value of this function is given when α = 1 - α, that is, α = 1/2, so that theentropy is equal to H(X) = log2 2 = 1 bps. (This is the same as saying one bit per binary digitor binary symbol.)When α -> 1, entropy tends to zero. The function Ω(α) will be used to represent the entropyof the binary source, evaluated using logarithms to base 2. Example 1.3: A given source emits r = 3000 symbols per second from a range of foursymbols, with the probabilities given in Table 1.2.

(Continues...)

Excerpted from Essentials of Error-Control Coding by Jorge Casti�eira Moreira. Copyright � 2006 by John Wiley & Sons, Ltd. Excerpted by permission of John Wiley & Sons.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

"About this title" may belong to another edition of this title.

PublisherJohn Wiley & Sons Inc
Publication date2006
ISBN 10 0470035722
ISBN 13 9780470035726
BindingHardcover
LanguageEnglish
Number of pages360

(No Available Copies)

Search Books: Create a Want

Can't find the book you're looking for? We'll keep searching for you. If one of our booksellers adds it to AbeBooks, we'll let you know!

Create a Want

Other Popular Editions of the Same Title

9780470029206: Essentials of Error-Control Coding

Featured Edition

ISBN 10: 047002920X ISBN 13: 9780470029206
Publisher: Wiley, 2006
Hardcover

Wiley India, 2010 (Softcover)

Items related to Essentials of Error-Control Coding