This relatively short chapter on channel entropy describes the entropy properties of communication channels, of which I have given a generic description in Chapter 11 concerning error-correction coding. It will also serve to pave the way towards probably the most important of all Shannon's theorems, which concerns channel coding, as described in the more extensive Chapter 13. Here, we shall consider the different basic communication channels, starting with the binary symmetric channel, and continuing with nonbinary, asymmetric channel types. In each case, we analyze the channel's entropy characteristics and mutual information, given a discrete source transmitting symbols and information thereof, through the channel. This will lead us to define the symbol error rate (SER), which corresponds to the probability that symbols will be wrongly received or mistaken upon reception and decoding.

Binary symmetric channel

The concept of the communication channel was introduced in Chapter 11. To recall briefly, a communication channel is a transmission means for encoded information. Its constituents are an originator source (generating message symbols), an encoder, a transmitter, a physical transmission pipe, a receiver, a decoder, and a recipient source (restituting message symbols). The two sources (originator and recipient) may be discrete or continuous. The encoding and decoding scheme may include not only symbol-to-codeword conversion and the reverse, but also data compression and error correction, which we will not be concerned with in this chapter. Here, we shall consider binary channels.

The concept of entropy is central to information theory (IT). The name, of Greek origin (entropia, tropos), means turning point or transformation. It was first coined in 1864 by the physicist R. Clausius, who postulated the second law of thermodynamics. Among other implications, this law establishes the impossibility of perpetual motion, and also that the entropy of a thermally isolated system (such as our Universe) can only increase. Because of its universal implications and its conceptual subtlety, the word entropy has always been enshrouded in some mystery, even, as today, to large and educated audiences.

The subsequent works of L. Boltzmann, which set the grounds of statistical mechanics, made it possible to provide further clarifications of the definition of entropy, as a natural measure of disorder. The precursors and founders of the later information theory (L. Szilárd, H. Nyquist, R. Hartley, J. von Neumann, C. Shannon, E. Jaynes, and L. Brillouin) drew as many parallels between the measure of information (the uncertainty in communication-source messages) and physical entropy (the disorder or chaos within material systems). Comparing information with disorder is not at all intuitive. This is because information (as we conceive it) is pretty much the conceptual opposite of disorder! Even more striking is the fact that the respective formulations for entropy that have been successively made in physics and IT happen to match exactly. A legend has it that Shannon chose the word “entropy” from the following advice of his colleague von Neumann: “Call it entropy.

This chapter considers the continuous-channel case represented by the Gaussian channel, namely, a continuous communication channel with Gaussian additive noise. This will lead to a fundamental application of Shannon's coding theorem, referred to as the Shannon–Hartley theorem (SHT), another famous result of information theory, which also credits the earlier 1920 contribution of Ralph Hartley, who derived what remained known as the Hartley's law of communication channels. This theorem relates channel capacity to the signal and noise powers, in a most elegant and simple formula. As a recent and little-noticed development in this field, I will describe the nonlinear channel, where the noise is also a function of the transmitted signal power, owing to channel nonlinearities (an exclusive feature of certain physical transmission pipes, such as optical fibers). As we shall see, the modified SHT accounting for nonlinearity represents a major conceptual progress in information theory and its applications to optical communications, although its existence and consequences have, so far, been overlooked in textbooks. This chapter completes our description of classical information theory, as resting on Shannon's works and founding theorems. Upon completion, we will then be equipped to approach the field of quantum information theory, which represents the second part of this series of chapters.

Gaussian channel

Referring to Chapter 6, a continuous communications channel assumes a continuous originator source, X, whose symbol alphabet x1,…, xi can be viewed as representing time samples of a continuous, real variable x, which is associated with a continuous probability distribution function or PDF, p(x).

This final chapter concerns cryptography, the principle of securing information against access or tampering by third parties. Classical cryptography refers to the manipulation of classical bits for this purpose, while quantum cryptography can be viewed as doing the same with qubits. I describe these two approaches in the same chapter, as in my view the field of cryptography should be understood as a whole and appreciated within such a broader framework, as opposed to focusing on the specific applications offered by the quantum approach. I, thus, begin by introducing the notions of message encryption, message decryption, and code breaking, the action of retrieving the message information contents without knowledge of the code's secret algorithm or secret key. I then consider the basic algorithms to achieve encryption and decryption with binary numbers, which leads to the early IBM concept of the Lucifer cryptosystem, which is the ancestor of the first data encryption standard (DES). The principle of double-key encryption, which alleviates the problem of key exchange, is first considered as an elegant solution but it is unsafe against code-breaking. Then the revolutionary principles of cryptography without key exchange and public-key cryptography (PKC) are considered, the latter also being known as RSA. The PKC–RSA cryptosystem is based on the extreme difficulty of factorizing large numbers. This is the reason for the description made earlier in Chapter 20 concerning Shor's factorization algorithm.

The previous chapter introduced the concept of coding optimality, as based on variable-length codewords. As we have learnt, an optimal code is one for which the mean codeword length closely approaches or is equal to the source entropy. There exist several families of codes that can be called optimal, as based on various types of algorithms. This chapter, and the following, will provide an overview of this rich subject, which finds many applications in communications, in particular in the domain of data compression. In this chapter, I will introduce Huffman codes, and then I will describe how they can be used to perform data compression to the limits predicted by Shannon. I will then introduce the principle of block codes, which also enable data compression.

Huffman codes

As we have learnt earlier, variable-length codes are in the general case more efficient than fixed-length ones. The most frequent source symbols are assigned the shortest codewords, and the reverse for the less frequent ones. The coding-tree method makes it possible to find some heuristic codeword assignment, according to the above rule. Despite the lack of further guidance, the result proved effective, considering that we obtained η = 96.23% with a ternary coding of the English-character source (see Fig. 8.3, Table 8.3). But we have no clue as to whether other coding trees with greater coding efficiencies may ever exist, unless we try out all the possibilities, which is impractical.

This mathematically intensive chapter takes us through our first steps in the domain of quantum computation (QC) algorithms. The simplest of them is the Deutsch algorithm, which makes it possible to determine whether or not a Boolean function is constant for any input. The key result is that this QC algorithm provides the answer at once, whereas in the classical case it would take two independent calculations. I describe next the generalization of the former algorithm to n qubits, referred to as the Deutsch–Jozsa algorithm. Although they have no specific or useful applications in quantum computing, both algorithms represent a most elegant means of introducing the concept of quantum computation parallelism. I then describe two most important QC algorithms, which nicely exploit quantum parallelism. The first is the quantum Fourier transform (QFT), for which a detailed analysis of QFT circuits and quantum-gate requirements is also provided. As will be shown in the next chapter, a key application of QFT concerns the famous Shor's algorithm, which makes it possible to factor numbers into primes in terms of polynomials. The second algorithm, no less famous than Shor's, is referred to as the Grover quantum database search, whose application is the identification of database items with a quadratic gain in speed.

Deutsch algorithm

Our exploration of quantum algorithms shall begin with the solution of a very basic problem: finding whether or not a Boolean function f(x) is a constant.

This chapter is about coding information, which is the art of packaging and formatting information into meaningful codewords. Such codewords are meant to be recognized by computing machines for efficient processing or by human beings for practical understanding. The number of possible codes and corresponding codewords is infinite, just like the number of events to which information can be associated, in Shannon's meaning. This is the point where information theory will start revealing its elegance and power. We will learn that codes can be characterized by a certain efficiency, which implies that some codes are more efficient than others. This will lead us to a description of the first of Shannon's theorems, concerning source coding. As we shall see, coding is a rich subject, with many practical consequences and applications; in particular in the way we efficiently communicate information. We will first start our exploration of information coding with numbers and then with language, which conveys some background and flavor as a preparation to approach the more formal theory leading to the abstract concept of code optimality.

Coding numbers

Consider a source made of N different events. We can label the events through a set of numbers ranging from 1 to N, which constitute a basic source code. This code represents one out of N! different possibilities. In the code, each of the numbers represents a codeword.

This chapter describes the principle of compression in quantum communication channels. The underlying concept is that it is possible to convey “faithfully” a quantum message with a large number of qubits, while transmitting a compressed version of this message with a reduced number of qubits through the channel. Beyond the mere notion of fidelity, which characterizes the quality of quantum message transmission, the description brings the new concept of typicality in the space defined by all possible “quantum codewords.” The theorem of Schumacher's quantum compression states that for a qubit source with von Neumann entropy S, the message compression factor R has S − ε for the lower bound, where ε is any nonnegative parameter that can be made arbitrarily small for sufficiently long messages (hence, R ≈ S is the best possible compression factor). An original graphical and numerical illustration of the effect of Schumacher's quantum compression and the evolution of the typical quantum-codeword subspace with increasing message length is provided.

Quantum data compression and fidelity

In this chapter, we have reached the stage where it is possible to start addressing the issues that are central to information theory, namely, “How efficiently can we code information in a quantum communication channel?” both in terms of economy of means – the concept of data compression – and accuracy of transmission – the concept of message integrity or minimal data error, referred to here as fidelity.

In effect, the concept of information is obvious to anyone in life. Yet the word captures so much that we may doubt that any real definition satisfactory to a large majority of either educated or lay people may ever exist. Etymology may then help to give the word some skeleton. Information comes from the Latin informatio and the related verb informare meaning: to conceive, to explain, to sketch, to make something understood or known, to get someone knowledgeable about something. Thus, informatio is the action and art of shaping or packaging this piece of knowledge into some sensible form, hopefully complete, intelligible, and unambiguous to the recipient.

With this background in mind, we can conceive of information as taking different forms: a sensory input, an identification pattern, a game or process rule, a set of facts or instructions meant to guide choices or actions, a record for future reference, a message for immediate feedback. So information is diversified and conceptually intractable. Let us clarify here from the inception and quite frankly: a theory of information is unable to tell what information actually is or may represent in terms of objective value to any of its recipients! As we shall learn through this series of chapters, however, it is possible to measure information scientifically. The information measure does not concern value or usefulness of information, which remains the ultimate recipient's paradigm.

This chapter is concerned with the measure of information contained in qubits. This can be done only through quantum measurement, an operation that has no counterpart in the classical domain. I shall first describe in detail the case of single qubit measurements, which shows under which measurement conditions “classical” bits can be retrieved. Next, we consider the measurements of higher-order or n-qubits. Particular attention is given to the Einstein–Podolsky–Rosen (EPR) or Bell states, which, unlike other joint tensor states, are shown being entangled. The various single-qubit measurement outcomes from the EPR–Bell states illustrate an effect of causality in the information concerning the other qubit. We then focus on the technique of Bell measurement, which makes it possible to know which Bell state is being measured, yielding two classical bits as the outcome. The property of EPR–Bell state entanglement is exploited in the principle of quantum superdense coding, which makes it possible to transmit classical bits at twice the classical rate, namely through the generation and measurement of a single qubit. Another key application concerns quantum teleportation. It consists of the transmission of quantum states over arbitrary distances, by means of a common EPR–Bell state resource shared by the two channel ends. While quantum teleportation of a qubit is instantaneous, owing to the effect of quantum-state collapse, it is shown that its completion does require the communication of two classical bits, which is itself limited by the speed of light.

This chapter will take us into a world very different from all that we have seen so far concerning Shannon's information theory. As we shall see, it is a strange world made of virtual computers (universal Turing machines) and abstract axioms that can be demonstrated without mathematics merely by the force of logic, as well as relatively involved formalism. If the mere evocation of Shannon, of information theory, or of entropy may raise eyebrows in one's professional circle, how much more so that of Kolmogorov complexity! This chapter will remove some of the mystery surrounding “complexity,” also called “algorithmic entropy,” without pretending to uncover it all. Why address such a subject right here, in the middle of our description of Shannon's information theory? Because, as we shall see, algorithmic entropy and Shannon entropy meet conceptually at some point, to the extent of being asymptotically bounded, even if they come from totally uncorrelated basic assumptions! This remarkable convergence between fields must make integral part of our IT culture, even if this chapter will only provide a flavor. It may be perceived as being somewhat more difficult or demanding than the preceding chapters, but the extra investment, as we believe, is well worth it. In any case, this chapter can be revisited later on, should the reader prefer to keep focused on Shannon's theory and move directly to the next stage, without venturing into the intriguing sidetracks of algorithmic information theory.