06 chapter6 Information Theory and Coding.pptx

第1页：第06章信息论与编码封面

信息论与编码：章节封面，标示本章主题与内容范围。

第2页：6.1 信源编码

Information has become the key to success (it has always been a key to success, but in today's world it is the key). And behind all this information and its exchange lie the tiny l's and 0's (the omnipresent bits) that hold information by merely theway they sit next to one another. Yet the information age thatwe live in today owes its existence, primarily, to a seminal paper published in 1948 that laid the foundation of the wonderful field of Information Theory—a theory initiated byone man, the American Electrical Engineer Claude E. Shannon, whose ideas appear ed in the article "The Mathematical Theory of Communication" in the Bell System Technical Journal (1948). In its broad est sense 2, information includes the content of any of the standard communication media, such as telegraphy, telephony, radio, or television, andthe signals of electronic com put ers, servo-mechanism syst ems, and other data-process ing devices. The theory iseven applicable to the signals of the nerve net works ofhumans and other animals

本页为英文原文段落，中文译文见本章「参考译文」部分。

第3页：6.1 信源编码

• The chief concern of information theory is to discover mathematic all aws govern ing systems designed to communicate or manipulate information. It sets up quantitative measures of information and of the capacity of various systems to transmit, store, and otherwise process information. Some of the problems treated are related to finding thebest methods of using various available communication systems andthe best methods for sep ara ting wanted information or signal
• The bound aries of information theory are quite fuzzy. The theory overlaps heavily with communication theory but is more orient ed towards the fundamental limitations on the process ing and communication of information and less towards the detailed operation of the devices employ ed

本页为英文原文段落，中文译文见本章「参考译文」部分。

第4页：6.1.2 Un certainty

• 6.1.2 Un certainty and Information
• Any information source, analog or digital, produces an output that is random in nature 3. If it were not random, i. e., the output were known exactly, there would be noneed to transmit it! We live in an analog world and most sour ces are analog sources, for example, speech, temperature fluctuations etc. The discrete sources areman-made sources, for example, a source (say, a man) that genera tes a sequence of letters from a finite alphabet (typing his e-mail)
• Before we go on to develop a mathematical measure of information, let us develop an intuitive feel for it. Readthe following sentences

本页为英文原文段落，中文译文见本章「参考译文」部分。

第5页：6.1 信源编码：Tomorrow

• (1) Tomorrow, the sun will rise from the East
• (2) The phone will ring in the next one hour
• (3) It will snow in Delhi this winter
• The three sentences carry different amounts of information. In fact, the first sentence hardly carries any information. Everybody knowsthat the sun rises in the East and the probability of this happening again is almost unity. Sentence (2) appears to carry more information than sentence (1). The phone may ring

本页为英文原文段落，中文译文见本章「参考译文」部分。

第6页：6.1 信源编码

• Sentence (1), which talks about an event which has aprob ability of occurrence very close to 1 carries almost no information. Sentence (3), which has a very low prob ability of occurrence, appears to carry a lot of information (made us read it twice to be sure we got the information right!). The other interesting thing to note isthat the length of the sentence has nothing to do with thea mount of information it conveys. In fact
• Definition 1 Consider a discrete random variable Xwith possible outcomes

本页为英文原文段落，中文译文见本章「参考译文」部分。

第7页：6.1 信源编码

• The Self-Information of the event is defined as
• (6-1)
• We note that a high probability event conveys less information than a low probability event. For an event with,. Since a lower prob ability implies a higher degree of un certainty (and vice versa), a random variable with a higher degree of uncertaintyconta ins more information. We will use this corr elation between un certainty and level of information for physical interpret ations throughout this chapter
• The units of I{x) are determined by the base of the logarithm, which is usually selected as 2 or e. When the base is 2, theunits are in bits and when the base is e, the units are in nats(natural units). Since , , i. e., self information is non-negative. The following two examples illustrate why a logarithmic measure of information is appropriate

本页为英文原文段落，中文译文见本章「参考译文」部分。

本页英文原文由图片提取，部分单词之间空格缺失，已按大小写与标点边界补回分隔，确切分词请以课件原图为准。

第8页：6.1 信源编码

• The units of I{x) are determined by the base of the logarithm, which is usually selected as 2 or e. When thebase is 2, the units are in bits and when the base is e, the units are in nats (natural units). Since , , , i. e., self information is non-negative. The following two examples illustrate why a logarithmic measure of information is appropriate
• Example 1 Consider a binary source which tosses a fair coin and outputs a 1 if a head (H) appears and a 0 if atail (T) appears. For this source, P(1)=P(0) = 0.5. The information content of each output from the source is
• (6-2)

本页为英文原文段落，中文译文见本章「参考译文」部分。

第9页：6.1 信源编码：Consider

• Indeed, we have to use only one bit to represent the output from this binary source (say, we use a 1 tore present H and a 0 to represent T)
• Now, suppose the successive outputs from this binary source are statistic ally independent 4, i. e., the source ism emory less. Consider a block ofmbits. There are pos sib lem-bit blocks, each of which is equally probable with probability
• The self-information of anm-bit block is
• (6-3)
• Again, we observe that we indeed needmbits tore present the pos sib lem-bit blocks

本页为英文原文段落，中文译文见本章「参考译文」部分。

第10页：6.1 信源编码

• Thus, this logarithmic measure of information possess es the desired additive property when a number of source outputs is considered as a block
• Example 2 Consider a discrete memory less source (DMS)(source C) that outputs two bits at a time. This source comprise stwo binary sources (sources A and B) as mentioned in Example 1, each source contrib uting one bit. The two binary sources within the source C are independent. In tui tiv ely
• (6-4)

本页为英文原文段落，中文译文见本章「参考译文」部分。

第11页：6.1 信源编码

• We have to use two bits to represent the output from this combined binary source
• Thus, the logarithmic measure of information possess est he desired additive property for independent events
• Next, consider two discrete random variables Xand Ywith possible outcomes, and, respect ively. Suppose we observe some outcome and we want to determine thea mount of information this event prov ides about thee vent,, i. e., we want to mathematic ally represent the mutual information. We note the two extreme cases
• (1) Xand Yare independent, in which case the occurrence of prov ides no information about
• (2) X and Fare fully dependent events, in which case the occurrence ofdeterm ines the occurrence of the event

本页为英文原文段落，中文译文见本章「参考译文」部分。

第12页：6.1 信源编码

• A suitable measure that satisfies these conditions is the logarithm of the ratio of the conditional probability
• (6-5)
• divided by the probability
• (6-6)
• Definition 2 The mutual information between an dis defined as
• (6-7)

本页为英文原文段落，中文译文见本章「参考译文」部分。

第13页：6.1 信源编码：Therefore

• As before, the units of I(x) are determined by the base ofthe logarithm, which is usually selected as 2 or e. Whenthe base is 2 the units are in bits. Note that
• (6-8)
• Therefore
• (6-9)
• The physical interpretation of I(xi;yj)=I(yj;xi) is asfollows. The information provided by the occurrence ofthe event Y=yjabout the event X=xjis identical to the information provided by the occurrence of the event X=xiabout the event Y=yi

本页为英文原文段落，中文译文见本章「参考译文」部分。

第14页：6.1 信源编码

• Let us now verify the two extreme cases
• (1) When the random variables Xand Yare statistic ally independent, P(xi|yj)=P(xi), it leads to I(xi;yj)=0
• (2) When the occurrence of Y=yjuniquely deter min est he occurrence of the event X=xi, P(xi|yj)=1, the mutual information becomes
• (6-10)
• This is the self-information of the event X=xi
• Thus, the logarithmic definition of mutual information confirms our intuition

本页为英文原文段落，中文译文见本章「参考译文」部分。

本页英文原文由图片提取，部分单词之间空格缺失，已按大小写与标点边界补回分隔，确切分词请以课件原图为准。

第15页：6.1.3 Average

• 6.1.3 Average Mutual Information and Entropy
• So far we have studied the mutual information associated with a pair of events and which are the possible outcomes of the two random variables Xand Y. We now want to find out the average mutual information between the two random variables. This can be obtain eds imply by weigh ting by the probability of occurrence ofthe joint event and summing over all possible joint eve nts
• Definition 3 The average mutual information between two random variables Xand Yis given by
• (6-11)

本页为英文原文段落，中文译文见本章「参考译文」部分。

第16页：6.1 信源编码

• For the case when Xand Yare statistic ally independent,, i. e., there is no average mutual information between Xand Y. An important property of the average mutual information is that where equality holds if and only if Xand Yare statistic ally independent
• Definition 4 The average self-information of a random variable Xis defined as
• (6-12)
• When Xrepresents the Alphabet of possible output lett ers from a source, H(X) represents the average information per source letter. In this case H(X) is called the entropy. The term entropy has been borrow ed from statistical mechanics, where it is used to denote the levelof disorder in a system. It is interesting to see that the Chinese character for entropy looks like ENTROPY !

本页为英文原文段落，中文译文见本章「参考译文」部分。

第17页：6.1 信源编码：Consider

• Consider a discrete binary source that emits a sequence of statistic ally independent symbols. The output is eithera 0 with prob ability por a 1 with a probability 1-p. The entropy of this binary source is
• (6-13)
• The plot of the binary entropy function versus pis givenin Figure 6.1
• We observe from Figure 6.1 that the value of the binary entropy function reaches its maximum value forp=0.5, i. e., when both 1 and 0 are equally likely. In general itcan be shown that the entropy of a discrete source is maximum when the letters from the source are equ ally probable

本页为英文原文段落，中文译文见本章「参考译文」部分。

第18页：图6.1 binary entropy

图6.1 binary entropy

本页为图示页，图中给出6.1 信源编码的结构或流程，具体图形见课件原图。

第19页：生词与短语：internet

本页为生词与短语（New words and phrases）列表，收录本节出现的专业词汇。

词条按原文「中文释义—音标—英文词条」的顺序识别，如与原件排版不符以课件原图为准。

第20页：生词与短语：probability

本页为生词与短语（New words and phrases）列表，收录本节出现的专业词汇。

词条按原文「中文释义—音标—英文词条」的顺序识别，如与原件排版不符以课件原图为准。

第21页：课文注释（6.1 信源编码）

本页为课文注释（Notes），讲解本节难句的句式与翻译处理。

• Notes
• 1.本节涉及信息论与编码领域中的信源编码部分
• 2. In its broad est sense广义地说。此句可译为：广义地说，信息包括一切标准通信媒体的内容，如电报、电话、无线电、电视以及来自电子计算机、伺服机械装置系统和其他数据处理器件的信号
• 3.句中analog or digital作any information source的同位语。此句可译为：任何信源，不管是模拟的还是数字的，都会产生本质上随机的输出
• 4. statistic ally independent统计独立的。此句可译为：现在假定该二元信源的连续输出是统计独立的，即信源是无记忆的

第22页：6.2 Channel Capacity

• 6.2 Channel Capacity 1
• 6.2.1 Introduction
• In Section 6.1, we saw that most natural sources have inherent redundancies and it is possible to compress databy re moving these redundancies using different source cod ing techniques. After efficient represent at ion of source symbols by the minimum possible number of bits, we transmit these bit-streams over channels (e. g., telephone lines, optical fibres etc.). These bits may be transmitted asthey are (for base band comm unications)

本页为英文原文段落，中文译文见本章「参考译文」部分。

第23页：6.2 信道容量

the de modulator process es the channel-corrupted waveform and reduces each waveform to a scalar or avector that represents an estimate of the transmitted data symbols. The detector, which follows thede modulator, decides whether the transmitted bit is a 0 or a 1. This is called hard decision deco ding. This decision process at the decoder is similar to a binary quantization with two levels. If there are more than 2 levels of quantization, the detector is said to perform asoft decision deco ding

本页为英文原文段落，中文译文见本章「参考译文」部分。

第24页：6.2 信道容量

The use of hard decision deco ding causes an irreversible lossof information at the receiver. Suppose the modulator sendsonly binary symbols but the de modulator has an alphabet with symbols, and as sum ing the use of quantizer as depict ed in Figure 6.2(a), we have Q=8. Such a channel is called a binary in put Q-ary output discrete memory less channel. The corresponding channel is shown in Figure 6.2(b). The dec oder performance depends on the location of the represent ationlevels of the quantize rs, which in turn depends on the signal level and the noise power. Accord ingly, the de modulator must incorporate automatic gain control 3 in order to realize an effective multilevel quantizer. It is clear that the construction ofsuch a decoder is more complicated than the hard decision dec oder. However, soft decision deco ding can provide significant improvement in performance over hard decision deco ding

本页为英文原文段落，中文译文见本章「参考译文」部分。

第25页：图6.2 Transfer

图6.2 Transfer

本页为图示页，图中给出6.2 信道容量的结构或流程，具体图形见课件原图。

第26页：6.2 信道容量

There are three balls that a digital communication engineer must juggle: (1) the transmitted signal power, (2) the channel bandwidth, and (3) the reliability of the communication system (in terms of the bit error rate). Channel coding allows us to trade-off one of these comm odities (signal power, bandwidth or reliability with respect to others). In this section, we will study how to achieve re liable communication in the presence of noise. We shall ask ourselves questions like: how many bits per second can be sent over a channel of a given bandwidth and for a given signal to noise ratio (SNR)? For that, webegin by stu dying a few channel models firs

本页为英文原文段落，中文译文见本章「参考译文」部分。

第27页：6.2.2 Channel Models

• 6.2.2 Channel Models
• We have already come across the simple st of the channel models, the binary symmetric channel (BSC), inthe previous section. If the modulator employs binary waveforms and the decoder makes hard decision, thenthe channel may be viewed as one in which a binary bit stream enters at the transmitting end and another bit stream comes out at the receiving end. This is depictedin Figure 6.3. t
• Figure 6.3 A composite discrete-input, discrete-output channel

本页为英文原文段落，中文译文见本章「参考译文」部分。

第28页：6.2 信道容量

• The composite discrete-input, discrete-output channel ischarac teri zed by 4 the set of possible inputs, the set of possible outputs and a set of conditional prob abilities that relate the possible outputs to the possible inputs. As sum ing the noise in the channel causes independent err ors in the transmitted binary sequence with average prob ability of errorp
• (6-14)

本页为英文原文段落，中文译文见本章「参考译文」部分。

第29页：6.2 信道容量

• A BSC is shown in Figure 6.4
• Figure 6.4 A binary symmetric channel (BSC)

第30页：6.2 信道容量

• The BSC is a special case of a general, discrete-input, discrete-output channel. Let the input to the channel beq-ary symbols, i. e. , and the output of the detector at the receiver consist of q-ary symbols, i. e., . We assume that the channel andthe modulation is memory less. The inputs and output scan then be related by a set ofq Qconditional prob abilities(6-15)
• where and. This channel is known as a Discrete Memory less Channel (DMC) and is depict ed in Figure 6.5

本页为英文原文段落，中文译文见本章「参考译文」部分。

本页英文原文由图片提取，部分单词之间空格缺失，已按大小写与标点边界补回分隔，确切分词请以课件原图为准。

第31页：图6.5 discrete memory

图6.5 discrete memory

本页为图示页，图中给出6.2 信道容量的结构或流程，具体图形见课件原图。

第32页：6.2 信道容量

• Definition 5 The conditional prob ability is defined as the Channel Transition Probability 5 and isdenoted by Pi, j
• Definition 6 The conditional prob abilities that characterize a DMC can be arran ged in the matrix form P=[Pi, j]. Pis called the Probability Transition Matrix forthe channel
• 6.2.3 Channel Capacity
• Consider a DMC having an input alphabet and an output alphabet. Let us denote the set of channel transition prob abilities by. The average mutual information provided by the output Yabout the input Xis given by(see Section 6.1.2)
• (6-16)

本页为英文原文段落，中文译文见本章「参考译文」部分。

本页英文原文由图片提取，部分单词之间空格缺失，已按大小写与标点边界补回分隔，确切分词请以课件原图为准。

第33页：6.2 信道容量

• The channel transition prob abilities are determined by the channel character istics (particular ly the noise inthe channel). However, the input symbol prob abilitiesare within the control of the discrete channel encoder. The value of the average mutual information, , maximized over the set of input symbol prob abilitiesis a quantity that depends only on the channel transition prob abilities . This quantity is called the capacity ofthe channel
• Definition 7 The capacity of a DMC is defined as the maximum average mutual information in any single useof the channel, where the maximization is over all possible input prob abilities. That is,(6-17)

本页为英文原文段落，中文译文见本章「参考译文」部分。

本页英文原文由图片提取，部分单词之间空格缺失，已按大小写与标点边界补回分隔，确切分词请以课件原图为准。

第34页：6.2 信道容量

• The maximization of is performed under the constr aints
• and
• The unit of channel capacity is bits per channel use(provided the base of the logarithm is 2)

本页为英文原文段落，中文译文见本章「参考译文」部分。

第35页：生词与短语：redundancy

本页为生词与短语（New words and phrases）列表，收录本节出现的专业词汇。

词条按原文「中文释义—音标—英文词条」的顺序识别，如与原件排版不符以课件原图为准。

第36页：课文注释（6.2 信道容量）

本页为课文注释（Notes），讲解本节难句的句式与翻译处理。

• Notes
• 1.本节涉及信息论与编码领域中的信道容量部分
• 2.在此句中，宾语从句that most natural…source codingtechni ques作saw的宾语，而that引导的宾语从句又由两个并列句构成。此句可译为：在第6.1节曾讲到多数自然信源都有固有的冗余度，因此通过不同信源编码技术将这些冗余去掉以实现对数据的压缩是可能的
• 3. automatic gain control自动增益控制。自动增益控制是指使放大电路的增益自动地随信号强度而调整的控制方法

第37页：课文注释（6.2 信道容量）

本页为课文注释（Notes），讲解本节难句的句式与翻译处理。

• 4. be character ized by描述为……，具有……的特征。此句可翻译为：联合的离散输入离散输出信道(discrete-input, discrete-output channel)可描述为一个可能的输入集、一个可能的输出集，以及可能输出与可能输入相关联的条件概率
• 5. channel transition probability信道转移概率
• 6. average mutual information平均互信息量；depend only on仅依赖于……。此句可翻译为：平均互信息的值在输入符号概率集上达到的最大值是仅依赖于信道转移概率的一个量，这个量称为信道容量

第38页：6.3 Channel Coding

• 6.3 Channel Coding 1
• All real-life channels are affected by noise. Noise cause sdiscrepancies (errors) between the input and the output data sequences of a digital communication system. For atypical noisy channel, the probability of bit error may beas high as . This means that, on an average, 1 bit out ofevery 100 transmitted over this channel gets flipped. Formost applications

本页为英文原文段落，中文译文见本章「参考译文」部分。

第39页：6.3 信道编码

Table 6-1 Accept able bit error rates for various applications Probability of Error Application Speech telephony Voice band data Electronic mail, Electronic newspaper Internet access Video telephony, high speed computing

本页为英文原文段落，中文译文见本章「参考译文」部分。

本页英文原文由图片提取，部分单词之间空格缺失，已按大小写与标点边界补回分隔，确切分词请以课件原图为准。

第40页：6.3 信道编码

• In order to achieve such high levels of reliability, were sort to channel formatting coding. The basic objective of channel coding is to incr ease the resistance of the digital communication system to channel noise 2. This isdone by adding redundancies in the transmitted data stream in a controlled manner
• In channel coding, we map 3 the in coming data sequence to a channel input sequence. This encoding procedure isdone by the channel encoder. The encoded sequence isthen transmitted over the noisy channel. The channel output sequence at the receiver is inverse mapped on toan output data sequence. This is called the deco ding procedure, and is carried out by the channel decoder. Both the encoder and the decoder are under thede signer's control

本页为英文原文段落，中文译文见本章「参考译文」部分。

第41页：6.3 信道编码

As already mentioned 4, the encoder intro duces redundancy in a prescribed manner. The deco derexploits this redundancy in order to reconstruct the original source sequence as accurate ly as possible. Thus, channel coding makes it possible to carry outre liable communication over unreliable (noisy) channels. Channel coding is also referred to as 5 error control cod ing, and we will use these terms interchangeably. It is interesting to note here that source coder reduces redundancy to improve efficiency, whereas, the channel coder adds redundancy in a controlled manner to improve reliability 6

本页为英文原文段落，中文译文见本章「参考译文」部分。

第42页：6.3 信道编码：Code

• We first look at a class of channel codes called block codes. In this class of codes, the in coming message sequence is first sub-divide din to sequential blocks, each of length kbits. Eachkbit long information block is mapped into annbit block by the channel coder, wheren>k. This means that for every kbits of information, (n-k) redundant bits are added. The ratio
• (6-18)
• is called the code rate. Code rate of any coding scheme is, natural ly, less than unity. A small code rate implies that more and more bitsper block axe the redundant bits corresponding to a higher cod ing overhead. This may reduce the effect of noise, but will also reduce the communication rate as we will end up transmitting more redundant bits and fewer information bits

本页为英文原文段落，中文译文见本章「参考译文」部分。

第43页：6.3 信道编码：Suppose

Let us now introduce the concept of time in our discussion. We wish to look at questions like how manybits per second can we send over a given noisy channel with arbitrarily low bit error rates? Suppose the DMS hasthe source alphabet Xand entropy bits per source symbol and the source genera tes a symbol every seconds, then, the average information rate of the source is bits per second. Let us assume that the channel can be used once every seconds and the capacity of the channel is Cbits per channel use. Then, the channel capacity per unit time is bits per second. Wenow state Shannon's second theorem known as the Channel Coding Theorem

本页为英文原文段落，中文译文见本章「参考译文」部分。

第44页：6.3 信道编码：Suppose

Let us now introduce the concept of time in our discussion. We wish to look at questions like how manybits per second can we send over a given noisy channel with arbitrarily low bit error rates? Suppose the DMS hasthe source alphabet Xand entropy bits per source symbol and the source genera tes a symbol every seconds, then, the average information rate of the source is bits per second. Let us assume thatthe channel can be used once every seconds andthe capacity of the channel is Cbits per channel use. Then, the channel capacity per unit time is bits per second. We now state Shannon's second theorem known as the Channel Coding Theorem

本页为英文原文段落，中文译文见本章「参考译文」部分。

第45页：6.3 信道编码：Theorem

• Theorem 1 Channel coding theorem (Noisy coding theorem)
• (1) Let a DMS with an alphabet Xhave entropy and produce symbols every seconds. Let a DMC have capacity C and be used once every seconds. Then, if
• (6-19)
• there exists a coding scheme for which the source output; can be transmitted over the noisy channel and be reconstructed with an arbitrarily low probability of error
• (2) Converse ly, if
• (6-20)
• it is not possible to transmit information over the channel andre construct it with an arbitrarily small probability of error
• The parameter is called the critical rate

本页为英文原文段落，中文译文见本章「参考译文」部分。

第46页：6.3 信道编码：DMS

The channel coding theorem is a very important result in information theory. The theorem specif ies the channel capacity, C, as a fundamental limit on the rate at whichre liable communication can be carried out over an unreliable (noisy) DMS channel. It should be noted thatthe channel coding theorem tells us about the existence of some codes that can achieve re liable communication in a noisy environment. Unfortunate ly, it does not give usthe recipe to construct these codes 7. Therefore, channel cod ing is still an active area of re search as the search for better and better codes is still going on

本页为英文原文段落，中文译文见本章「参考译文」部分。

第47页：生词与短语：discrepancy

本页为生词与短语（New words and phrases）列表，收录本节出现的专业词汇。

本页词条原文粘连较多，未能安全切分为词条表，建议对照原图补充。

第48页：课文注释（6.3 信道编码）

本页为课文注释（Notes），讲解本节难句的句式与翻译处理。

• Notes
• 1.本节涉及信息论与编码领域中的信道编码部分
• 2. the resistance of …to…译为……的抗……的能力。此句可翻译为：信道编码的基本目标是增加数字通信系统的抗噪声能力
• 3. map映射、转换。此句可翻译为：在信道编码中，我们把进来的数据序列映射到信道输入序列
• 4. As already mentioned正如已经提到的、正如前面所述。此句可翻译为：正如已经提到的，编码器以预先设计好的方式引进冗余度，译码器利用这个冗余度以便尽可能精确地恢复原来的信源序列
• 5. be referred to as称为、被称为。此句可翻译为：信道编码又称为错误控制编码(error control coding)这些术语可互换使用
• 6.句中whereas表示语义转折，译为“然而”。此句可翻译为：可以注意到，信源编码通过减少冗余度来提高效率，而信道编码则通过在控制下添加冗余度来提高可靠性
• 7. unfortunate ly为副词，翻译时译为“遗憾的是”。此句可翻译为：但遗憾的是它没给出构造这些码的方法

第49页：6.1 信源编码

• 参考译文
• 第6章信息论与编码
• 6.1信源编码
• 6.1.1信息论简介
• 今天，我们生活在信息时代，因特网(Internet)已经成为我们生活中不可缺少的一部分，这使得太阳系第三大行星成为一个地球村。人们通过手机交谈已经是一件很平常的事。电影可以以DVD碟片的形式租回家欣赏。名片上印上电子邮箱和网址也很正常。许多人更愿意给朋友发送电子邮件和电子贺卡而不去发普通信件。股票行情也可以通过手机来査看

第50页：译文 6.1 信源编码

• 信息已成为成功的关键(它一直是成功的关键，但在当今的世界上它是最关键的)
• 在所有这些信息的背后，信息的交换却依靠小小的1和0 (即无所不在的比特)，通过它们一个接一个地排在一起来表达信息
• 我们今天所生活的信息时代的存在主要归功于发表于1948年的一篇精辟的论文，这篇论文为奇妙的信息论奠定了基础
• 信息论的创始人是美国电子工程师Claude E. Shannon,他在发表在Bell system technical Journal(1948)中的论文The Mathematical Theory of Communication(通信的数学理论)中阐述了自己的思想
• 广义地说，信息包括一切标准通信媒体的内容，如电报、电话、无线电、电视以及来自电子计算机、伺服机械装置系统和其他数据处理器件的信号
• 该理论甚至适用于人体和其他动物神经网络的信号

第51页：译文 6.1 信源编码

• 信息论最关注的是发现为通信和处理信息而设计的控制系统中存在的数学定律。它通过建立量化指标来度量信息以及不同系统在传输、存储和处理信息时的容量。有些要解决的问题与发现使用各种已有通信系统的最好方法相关，也和将有用的信息或信号同无用的信息或噪声分开的最好方法有关。另一个问题就是对给定的信息载体(通常称为信道)给出容量上界。尽管对那些结果感兴趣的主要是通信工程师，但有些概念也已被诸如心理学和语言学等领域采用并且被验证很有用
• 信息论的界限非常模糊。这种理论与通信理论有很大的重叠，但它主要面向信息处理和通信方面的基本界限，而较少涉及所用元器件的详细运作情况

第52页：6.1.2 不确定性和信息

• 6.1.2不确定性和信息
• 任何信源，不管是模拟的还是数字的，都会产生本质上随机的输出。假若不是随机，即能准确地确定其输出，那么就没必要传输它！信源存在模拟信源和离散信源两种。人们生活在一个模拟世界里，多数信源都是模拟信源，例如语音、温度波动等。离散信源都是人造的信源，例如从有限字母集中产生一连串字母(如写电子邮件)的信源(如人)
• 在进一步介绍信息的数学度量方法之前，下面先给出直观的度量。阅读下面的句子
• (1)明天太阳将从东方升起
• (2)一小时后电话会响
• (3)今年冬天德里将下雪

第53页：译文 6.1 信源编码：第一个句

• 这3个句子含有不同的信息量
• 事实上，第一个句子几乎不含任何信息，因为每个人都知道太阳从东方升起，也就是说这件事再次发生的概率几乎为1 ( N. Bohr说道：“作预言是有风险的，特别是在涉及将来的时候
• ”)
• 第二个句子看起来比第一个句子包含的信息多，因为电话可能响，也可能不响
• 电话在一小时后响的概率是有限值(除非在维修)
• 最后一个句子可能要读两遍，因为德里从来没下过雪，因此德里下雪的概率非常低
• 有趣的是，上述句子所携带的信息量与句子中所陈述的事件发生的概率有关，而且也可以观察到相反的关系
• 第一个句子讲的是发生概率几乎为1的事件，它几乎没携带什么信息

第54页：译文 6.1 信源编码

• 下面将给出信息的数学度量方法
• 定义1考虑可能的输出为，，，的离散随机变量X，则事件的自信息(self-information)定义为
• (6-1)
• 由以上内容可知，高概率事件没有低概率事件所携带的信息多。对于的事件，有。因为低概率事件意味着高度的不确定性(反之亦然)，具有高度不确定性的随机变量带有更多的信息。本章将一直用不确定性和信息量的这种相关性进行解释
• 的单位取决于对数的底数，通常取为2或e。当以2为底数时，单位为比特(bit)，而当以e为底数时，单位为奈特(nat,自然单位)。由于，故，即自信息是非负的。下面用两个例子说明为什么用对数来度量信息是合适的

第55页：译文 6.1 信源编码

• 例1考虑一个掷硬币的二元信源：若正面(H)出现则输出1，若反面(T)出现则输出0。对于该信源，有P(1)=P(0)=0.5。来自该信源的每一个输出所含的信息量为
• (6-2)
• 事实上，只能用1比特来表示这个二元信源的输出(例如，用1代表H，用0代表T)
• 现在假定该二元信源的连续输出是统计独立的，即信源是无记忆的。考虑一个mbit的数组，则共有个可能的m比特组，每一个都具有概率。一个m比特组的自信息为
• (6-3)
• 由此可知确实需要m个比特来表示可能的m比特组
• 因此，当信源的一些输出被看作一个组的时候，这种信息的对数度量公式具有所期望的可加性

第56页：译文 6.1 信源编码

• 例2考虑一个离散无记忆信源(DMS)(信源C)，它每次输出两个比特。该信源由例1中提到的两个二元信源(信源A和B)构成，每个信源贡献一个比特。信源C中的这两个二元信源是独立的。从表面上看，组合信源(信源C)的信息量应该是组成该信源的两个独立信源的输出所含有的信息量之和。下面分析一下信源C的输出所含的信息量。有4种可能的情况{00，01,10，11}，每种情况都具有概率P(C)=P(A) P(B)=0.5×0.5=0.25，这是因为信源A和B是独立的。信源C的每个输出所含的信息量为
• (6-4)
• 因此必须用两比特来表示这个组合的二元信源的输出
• 因此，信息的对数度量公式对独立事件具有可加性

第57页：译文 6.1 信源编码

• 下面考虑两个离散随机变量X和Y,其可能的输出分别为,和,。假设观察到输出，想由此确定该事件所提供的关于事件,的信息量，也就是说想用数学方式表示出它们的互信息。有两种极端的情况
• (1) X和Y独立，在此情况下，的发生未提供任何关于的信息
• (2) X和Y为完全依赖的事件，在此情况下，的发生决定了的发生。满足此条件的一种合适的度量是对条件概率
• (6-5)
• 除以概率
• (6-6)
• 所得的商取对数

第58页：译文 6.1 信源编码

• 定义2定义之间的互信息为
• (6-7)
• 同前面一样，的单位取决于对数的底数，通常为2或e。当底数为2时，单位为比特
• 注意
• (6-8)
• 因此
• (6-9)
• 对的自然解释如下：事件的发生所提供的关于的信息完全等同于事件的发生所提供的关于的信息

第59页：译文 6.1 信源编码

• 现在来看两种极端情况
• (1)当随机变量X与Y统计独立时，有，它导致
• (2)当事件的发生唯一决定事件的发生时，有,因而互信息为(6-10)
• 这就是事件的自信息。因此，互信息的对数定义证实了我们的直觉

第60页：6.1.3 平均互信息和熵

• 6.1.3平均互信息和熵
• 到现在为止已经介绍了与事件对和相关的互信息，它们是两个随机变量X和Y的可能输出。现在要找到这两个随机变量之间的平均互信息，这可以通过用关联事件的发生概率为加权，然后再求和得到
• 定义3两个随机变量X和Y的平均互信息为(6-11)
• 对于X和Y统计独立的情况，有，即X和Y之间没有平均互信息。平均互信息的一个重要性质是，其中当且仅当X和Y统计独立时，等号才成立

第61页：译文 6.1 信源编码：代表每个信源字母

• 定义4随机变量X的平均自信息定义为
• (6-12)
• 其中，X代表信源可能输出的字母符号，H(X)代表每个信源字母的平均信息。在这种情况下，称H(X)为熵(entropy)。术语“熵”取自统计力学，在该学科中用来表示一个系统的无序程度
• 考虑一个产生统计独立的符号序列的离散二元信源，其输出为0的概率为p，输出为1的概率为1-p。该二元信源的熵为
• (6-13)

第62页：译文 6.1 信源编码

• 该二元熵函数相对于p的平面图如图6.1所示。图6.1二元熵函数
• 从图6.1中可以看出，该二元熵函数在p=0.5时，即当0和1出现的几率相同时达到最大值。在一般情况下可以证明，一个离散信源在其字母出现的概率相同时，熵的值达到最大

第63页：6.2 信道容量

• 6.2信道容量
• 6.2.1引言
• 在6.1节中曾讲到多数自然信源都有固有的冗余度，因此通过不同的信源编码技术将这些冗余去掉以实现对数据的压缩是可能的。当信源符号可以用尽量少的比特数来有效地表示以后，即可通过信道(如电话线、光纤等)来传输这些比特流。这些比特可能被原样传输(基带通信)，或经过调制后传输(通带通信)。令人遗憾的是，现实生活中的所有信道都有噪声。噪声这个术语是指那些对传输和处理通信系统中的有用信号造成干扰的无用波。噪声的来源可能是外界的(如大气噪声、人工噪声等)，也可能是内在的(如热噪声、放射噪声等)。结果是在接收端得到的比特流很可能与原来传输的不一样。在通带通信中，由解调器处理信道弄损的波形，再将这些波形化简为一个矢量或向量来近似表示传输的数据符号

第64页：译文 6.2 信道容量

• 检波器会在解调器解调之后判决原来传输的比特是0还是1，这种方法叫做硬判决译码(hard decision deco ding)。译码器上的这种判决过程与两个等级的二元量化很相似。如果在量化中有多于两个的等级，则检波器实施的方法称为软判决译码(soft decision deco ding)
• 使用硬判决译码会在接收端造成不可挽回的信息损失。假设调制器发送的只是二元信号，而解调器接收到Q个符号的字符，再假定量化器的使用方法如图6.2(a)所示，这里有Q=8，这样的信道称为二元输入Q元输出离散无记忆信道(discrete memory less channel, DMC)，对应的信道如图6.2(b)所示。译码器的性能取决于量化器表示级数的位置，而量化器的表示级数又取决于信号水平和噪声功率。相应地，为了实现一个多级量化器，解调器必须采用自动增益控制技术。很明显构造这样的译码器比硬判决译码器要复杂得多，但是软判决译码在性能上比硬判决译码具有明显的改善

第65页：译文 6.2 信道容量：传输信号

• 图6.2多级量化器的传输特征和信道转移概率图
• 数字通信工程师们必须考虑3个因素：传输信号的功率、信道带宽以及通信系统的可靠性(在比特误差率方面)。信道编码允许牺牲其中的一种因素(信号功率、带宽或可靠性)。本章将介绍在有噪声的情况下如何实现可靠的通信。人们会问类似如下的问题：在一个给定带宽和信噪比(SNR)的信道上每秒钟能传输多少比特？为此下面首先介绍几个信道模型

第66页：6.2.2 信道模型前面介绍了最

• 6.2.2信道模型前面介绍了最简单的信道模型——二元对称信道(binary symmetric channel, BSC)。若调制器采用的是二元波形，而检波器进行硬判决，那么信道可以看成是在发送端输入一个二元比特流，在接收端输出另一个比特流。图6.3表示出了这种模型
• 图6.3一种联合的离散输入离散输出信道

第67页：译文 6.2 信道容量

• 图6.4—个二元对称信道(BSC)
• 联合的离散输入离散输出信道(discrete-input, discrete-output channel)可描述为一个可能的输入集、一个可能的输出集，以及将可能的输出与可能的输入相关联的条件概率集合。假设信道中的噪声以错误概率p在二元序列的传输中产生独立错误，则
• (6-14)
• 图6.4所示的就是一个BSC

第68页：译文 6.2 信道容量：假定信道

• BSC是离散输入离散输出信道的一种特殊情况。设信道输入是q元符号，即，在接收端检波器的输出为Q元符号，即。假定信道和调制过程都是无记忆的，那么输入和输出之间可以通过q Q元条件概率集合相关联
• (6-15)
• 其中，且
• 这种信道称为离散无记忆信道(DMC)，如图6.5所示

第69页：译文 6.2 信道容量

• 图6.5一个具有q元输入Q元输出的离散无记忆信道(DMC)
• 定义5条件概率P(yi|xj)为信道转移概率，并记为Pi, j
• 定义6描述一个DMC的条件概率可以用矩阵形式P=Pi, j给出。P称为信道的概率转移矩阵(probability transition matrix)

第70页：6.2.3 信道容量

• 6.2.3信道容量
• 考虑一个DMC，它的输入字符集为，输出字符集为，这里用{P(yi|xj)}表示信道转移概率的集合。输出字符集Y关于输入字符集X的平均互信息为(见6.1.2节)(6-16)
• 信道转移概率由信道的特征(特别是信道中的噪声)决定。但是输入符号的概率受离散信道编码器的控制。平均互信息的值在输入符号概率集上达到的最大值是仅依赖于信道转移概率的一个量，这个量称为信道容量
• 定义7一个DMC的容量定义为每次使用该信道时的最大平均互信息，其中最大值是在所有可能的输入概率上求得的，即
• (6-17)

第71页：6.3 信道编码

• 的最大值是在下列约束条件下求得的
• 并且
• 信道容量的单位是每个信道使用的比特数(只要对数的底数为2)
• 6.3信道编码
• 所有现实生活中的信道都将受到噪声的影响。噪声会造成数字通信系统中的输入和输出数据序列间不一致(错误)。一个典型噪声信道的比特错误概率可以高达，这表明在这个信道上平均每传输100比特，就有一比特被改变了。对大多数应用来说，这样的可靠程度远不能满足要求。不同应用对可靠程度(服务质量的一项内容)的要求也不同。表6-1列出了不同应用可接受的比特错误率

第72页：表6-1 不同应用可接受的比特错误率错误

表6-1不同应用可接受的比特错误率错误概率应用语音电话声乐数据电子邮件、电子报纸因特网访问可视电话、高速计算

本页提及表6-1，原表以图片形式给出、行列数据粘连，未做自动切分，建议对照原图人工还原。

第73页：译文 6.3 信道编码：可以借助信道格式

• 为了获得较高的可靠性，可以借助信道格式编码。信道编码的基本目标是增强数字通信系统的抗噪声能力，这可以通过在传输的数据流中以可控的方式加入冗余度来实现
• 在信道编码中，把进来的数据序列映射为信道输入序列，这一编码过程由信道编码器完成。然后将编码后的序列通过有噪信道传输出去。在接收端信道输出序列被反过来映射到输出数据序列，这称为译码过程，由信道译码器完成。编码器和译码器都受设计者控制
• 正如已经提到的，编码器以预先设计好的方式引进冗余度，译码器借助冗余度来尽可能精确地恢复原来的信源序列，因此通过信道编码在不可靠(有噪声)的信道中实现可靠通信就变得可能了。信道编码又称为错误控制编码(error control coding)，这些术语可互换使用。可以看出信源编码是通过减少冗余度来提高效率的，而信道编码则通过可控的方式添加冗余度来提高可靠性

第74页：译文 6.3 信道编码

• 下面首先介绍的一类信道码称为分组码(block code)。在这类码中，进入的消息序列首先被分成一系列的组，每个组的长度为k比特。每个k比特长信息组再由信道编码器对应到一个n比特组，其中，这表明对任意k比特的信息，有冗余的比特被添加进来。比率(6-18)
• 称为码率(code rate)。任何编码方案的码率自然要小于1。小的码率意味着每个组有更多的冗余比特，相应地有更高的编码负载，这样可能会减小噪声的影响，但同时也会降低通信率，因为最终要传输更多的冗余比特和更少的信息比特。这里所面临的问题是是否存在一种编码方案使消息比特发生错误的概率可以任意小，而码率又不会太小。答案是肯定的，这首先由Shannon在他的信道容量的第二个定理中给出。后面就将给出这个定理

第75页：译文 6.3 信道编码：通过有噪信道

• 现在引入时间的概念考虑这样的问题：通过有噪信道一秒钟传输多少比特可以使比特错误率达到任意低？假设DMS有信源字符集X、每信源符号H(X) bit的熵,而且信源每Ts秒产生一个符号。信源的平均信息率为每秒H(X)/Tsbit。假设信道可以每Tc秒使用一次，而信道容量为每次信道使用的C比特。单位时间的信道容量为每秒钟C/Tcbit。下面给出Shannon的第二定理“有噪编码定理”，又称为信道编码定理
• 定理1信道编码定理(有噪编码定理)
• (1)设一个DMS信源字符集X的熵为每信源符号H(X)比特，而且信源每Ts秒产生一个符号。设一个离散无记忆信道的容量为C，且每隔Tc秒使用一次。若
• (6-19)
• 则存在一个编码方案，使信源输出可以通过该有噪信道传输并以任意低的错误概率恢复

第76页：译文 6.3 信道编码：则通过该信道

• (2)相反地，若
• (6-20)
• 则通过该信道传输的信息不可能以任意小的错误概率恢复
• 参数C/Tc称为临界率(critical rate)
• 信道编码定理是信息论中一个非常重要的研究结果。该定理说明了信道容量C是通过有噪DMS信道实现可靠通信的基本界限。由信道编码定理可知存在一些在有噪环境下实现可靠通信的码。但遗憾的是它没给出构造这些码的方法，因此信道编码仍然是一个很活跃的研究领域，人们仍然在搜寻着越来越好的码