This chapter introduces the notion of noisy quantum channels, and the different types of “quantum noise” that affect qubit messages passed through such channels. The main types of noisy channel reviewed here are the depolarizing, bit-flip, phase-flip, and bit-phase-flip channels. Then the quantum channel capacity χ is defined through the Holevo–Schumacher–Westmoreland (HSW) theorem. Such a theorem can conceptually be viewed as the elegant quantum counterpart of Shannon's (noisy) channel coding theorem, which was described in Chapter 13. Here, I shall not venture into the complex proof of the HSW theorem but only provide a background illustrating the similarity with its classical counterpart. The resemblance with the channel capacity χ and the Holevo bound, as described in Chapter 21, and with the classical mutual information H(X; Y), as described in Chapter 5, are both discussed. For advanced reference, a hint is provided as to the meaning of the still not fully explored concept of quantum coherent information. Several examples of quantum channel capacity, derived from direct applications of the HSW theorem, along with the solution of the maximization problem, are provided.

Noisy quantum channels

The notion of “noisiness” in a classical communication channel was first introduced in Chapter 12, when describing channel entropy. Such a channel can be viewed schematically as a probabilistic relation between two random sources, X for the originator, and Y for the recipient.

This chapter makes us walk a few preliminary, but decisive, steps towards quantum information theory (QIT), which will be the focus of the rest of this book. Here, we shall remain in the classical world, yet getting a hint that it is possible to think of a different world where computations may be reversible, namely, without any loss of information. One key realization through this paradigm shift is that “information is physical.” As we shall see, such a nonintuitive and striking conclusion actually results from the age-long paradox of Maxwell's demon in thermodynamics, which eventually found an elegant conclusion in Landauer's principle. This principle states that the erasure of a single bit of information requires one to provide an energy that is proportional to log 2, which, as we know from Shannon's theory, is the measure of information and also the entropy of a two-level system with a uniformly distributed source. This consideration brings up the issue of irreversible computation. Logic gates, used at the heart of the CPU in modern computers, are based on such computation irreversibility. I shall then describe the computers' von Newman's architecture, the intimate workings of the ALU processing network, and the elementary logic gates on which the ALU is based. This will also provide some basics of Boolean logic, expanding on Chapter 1, which is the key to the following logic-gate concepts.

This chapter is concerned with a remarkable type of code, whose purpose is to ensure that any errors occurring during the transmission of data can be identified and automatically corrected. These codes are referred to as error-correcting codes (ECC). The field of error-correcting codes is rather involved and diverse; therefore, this chapter will only constitute a first exposure and a basic introduction of the key principles and algorithms. The two main families of ECC, linear block codes and cyclic codes, will be considered. I will then describe in further detail some specifics concerning the most popular ECC types used in both telecommunications and information technology. The last section concerns the evaluation of corrected bit-error-rates (BER), or BER improvement, after information reception and ECC decoding.

Communication channel

The communication of information through a message sequence is made over what we shall now call a communication channel or, in Shannon's terminology, a channel. This channel first comprises a source, which generates the message symbols from some alphabet. Next to the source comes an encoder, which transforms the symbols or symbol arrangements into codewords, using one of the many possible coding algorithms reviewed in Chapters 9 and 10, whose purpose is to compress the information into the smallest number of bits. Next is a transmitter, which converts the codewords into physical waveforms or signals. These signals are then propagated through a physical transmission pipe, which can be made of vacuum, air, copper wire, coaxial wire, or optical fiber.

This second chapter concludes our exploration tour of coding and data compression. We shall first consider integer coding, which represents another family branch of optimal codes (next to Shannon–Fano and Huffman coding). Integer coding applies to the case where the source symbols are fully known, but the probability distribution is only partially known (thus, the previous optimal codes cannot be implemented). Three main integer codes, called Elias, Fibonacci, and Golomb–Rice, will then be described. Together with the previous chapter, this description will complete our inventory of static codes, namely codes that apply to cases where the source symbols are known, and the matter is to assign the optimal code type. In the most general case, the source symbols and their distribution are unknown, or the distribution may change according to the amount of symbols being collected. Then, we must find new algorithms to assign optimal codes without such knowledge; this is referred to as dynamic coding. The three main algorithms for dynamic coding to be considered here are referred to as arithmetic coding, adaptive Huffman coding, and Lempel–Ziv coding.

Integer coding

The principle of integer coding is to assign an optimal (and predefined) codeword to a list of n known symbols, which we may call {1,2,3,…, n}. In such a list, the symbols are ranked in order of decreasing frequency or probability, or mathematically speaking, in order of “nonincreasing” frequency or probability.

It is always a great opportunity and pleasure for a professor to introduce a new textbook. This one is especially unusual, in a sense that, first of all, it concerns two fields, namely, classical and quantum information theories, which are rarely taught altogether with the same reach and depth. Second, as its subtitle indicates, this textbook primarily addresses the telecom scientist. Being myself a quantum-mechanics teacher but not being conversant with the current Telecoms paradigm and its community expectations, the task of introducing such a textbook is quite a challenge. Furthermore, both subjects in information theory can be regarded by physicists and engineers from all horizons, including in telecoms, as essentially academic in scope and rather difficult to reconcile in their applications. How then do we proceed from there?

I shall state, firsthand, that there is no need to convince the reader (telecom or physicist or both) about the benefits of Shannon's classical theory. Generally unbeknown to millions of telecom and computer users, Shannon's principles pervade all applications concerning data storage and computer files, digital music and video, wireline and wireless broadband communications altogether. The point here is that classical information theory is not only a must to know from any academic standpoint; it is also a key to understanding the mathematical principles underlying our information society.

Shannon's theory being reputed for its completeness and societal impact, the telecom engineer (and physicist within!) may, therefore, wonder about the benefits of quantum mechanics (QM), when it comes to information.

This appendix provides a brief overview of common data compression standards used for sounds, texts, files, images, and videos. The description is just meant to be introductory and makes no pretense of comprehensively defining the actual standards and their current updated versions. The list of selected standards is also indicative, and does not reflect the full diversity of those available in the market, as freeware, shareware, or under license. It is a tricky endeavor to attempt a description here in a few pages of a subject that would fill entire bookshelves. The hope is that the reader will get a flavor and will be enticed to learn more about this seemingly endless, yet fascinating subject. Why put this whole matter into an appendix, and not a fully fledged chapter? This is because this set of chapters is primarily focused on information theory, not on information standards. While the first provides a universal and slowly evolving background reference, like science, the second represents practically all the reverse. As we shall see through this appendix, however, information standards are extremely sophisticated and “intellectually smart,” despite being just an application field for the former. And there are no telecom engineers or scientists who may ignore or will not benefit from this essential fact and truth!

This chapter marks a key turning point in our journey in information-theory land. Heretofore, we have just covered some very basic notions of IT, which have led us, nonetheless, to grasp the subtle concepts of information and entropy. Here, we are going to make significant steps into the depths of Shannon's theory, and hopefully begin to appreciate its power and elegance. This chapter is going to be somewhat more mathematically demanding, but it is guaranteed to be not significantly more complex than the preceding materials. Let's say that there is more ink involved in the equations and the derivation of the key results. But this light investment will turn out well worth it to appreciate the forthcoming chapters!

I will first introduce two more entropy definitions: joint and conditional entropies, just as there are joint and conditional probabilities. This leads to a new fundamental notion, that of mutual information, which is central to IT and the various Shannon's laws. Then I introduce relative entropy, based on the concept of “distance” between two PDFs. Relative entropy broadens the perspective beyond this chapter, in particular with an (optional) appendix exploration of the second law of thermodynamics, as analyzed in the light of information theory.

Joint and conditional entropies

So far, in this book, the notions of probability distribution and entropy have been associated with single, independent events x, as selected from a discrete source X = {x}.

Chapter 1 enabled us to familiarize ourselves (say to revisit, or to brush up?) the concept of probability. As we have seen, any probability is associated with a given event xi from a given event space S = {x1, x2,…, xN}. The discrete set {p(x1), p(x2),…, p(xN)} represents the probability distribution function or PDF, which will be the focus of this second chapter.

So far, we have considered single events that can be numbered. These are called discrete events, which correspond to event spaces having a finite size N (no matter how big N may be!). At this stage, we are ready to expand our perspective in order to consider event spaces having unbounded or infinite sizes (N → ∞). In this case, we can still allocate an integer number to each discrete event, while the PDF, p(xi), remains a function of the discrete variable xi. But we can conceive as well that the event corresponds to a real number, for instance, in the physical measurement of a quantity, such as length, angle, speed, or mass. This is another infinity of events that can be tagged by a real number x. In this case, the PDF, p(x), is a function of the continuous variable x.

This chapter is an opportunity to look at the properties of both discrete and continuous PDFs, as well as to acquire a wealth of new conceptual tools!