这是一篇旧文，点击以旧主题模式浏览。北邮通信原理讲义下册_大学生考试网
北邮通信原理讲义下册
通信原理II第一讲Feb. 27, 20071信源的描述信源或者是连续时间的，或者是离散时间的。如果是连续时间的，则总可以通 过抽样使其变成离散时间的，因此以下只考虑离散时间的信源。 信源的输出当然是随机的，故可以把信源输出建模为一个随机序列{Xi }。 随机序列有千千万万，我们只考虑简单的一种：广义平稳随机序列。即序列 中的任何一个Xi ,不论时间坐标i是多少，它们的概率分布都相同，而且自相关 函数E [Xi Xj ]只与i ? j 有关。 一个信源所表达的信息当然是由整个序列贡献的，正如我这个讲稿所要表达 的意思是由全体字符串构成的。先来考虑简单的情形，即序列{Xi }中的某一个 单个符号。{Xi }是平稳序列，具体选哪一个都是一样的。为了省事，我们略去 代表时间的下标i，这样，要研究的就是单个随机变量X 。 随机变量的取值范围是实数或者实数构成的集合。例如Gaussian随机变量的 取值范围是(?∞, ∞), Rayleigh随机变量的取值范围是[0, ∞), 载波相位的取值 范围是(0, 2π )，《通信原理II》成绩的取值范围是整数{0, 1, ? ? ? , 99}D也是实数 的子集。考虑简单的情形，假设X的取值x的范围是M 个实数： X = x ∈ {x1 , x2 , ? ? ? , xj , ? ? ? , xM } 实际信源的输出也许是连续取值的实数，但我们总可以通过足够精细的量化使 它只有有限个取值。 现在，我们要研究的就是一个离散随机变量X ，其取值范围是{x1 , x2 , ? ? ? , xM }。 X 取值等于x1 ，或者x2 ，或者其他的概率很可能是不一样的，记其取xj , j = 1, ? ? ? , M 的 概 率 为Pj ， 即Pj = P {X = xj }。 注 意 ， 有 时 我 们 也 用P (X )或 者P (xj )这样的记号。 对于离散随机变量，只要枚举出所有可能结果的出现概率，就完全描述了其 概率统计特性。因此可以用下面的方法来表述这个事情： X P (X = xj ) = x1 P1 x2 P2 ? ? ? xM ? ? ? PM (1)当然了，如果X 是连续随机变量（有无限多种取值），我们也可以将其用类 似的方法表述为 X x ∈ (a, b) = (2) p (x) p (x) 再来看随机序列。随机序列是无限多个随机变量。先从两个随机变量X1 和X2 说 起。掷两个筛子的结果可以当作是掷一个有6 × 6 = 36面的筛子。由此类推，1两个随机变量X1 和X2 可以理解为一个随机的Y，它的结果是向量(xi , xj ), 其 中xi 是X1 的结果，xj 是X2 的结果。因而，仿照式(1), 可以将其描述为 X2 P (x) = (x1 , x1 ) (x1 , x2 ) ? ? ? (xM , xM ) P11 P12 ??? PM M (3)这个结果显然可以推广到任意L个随机变量构成的序列{X1 , X2 , ? ? ? , XL }。这个 序列的每一种出现结果是一个向量(xi1 , xi2 , ? ? ? , xiL )，其中 xik ∈ {x1 , x2 , ? ? ? , xM }。这样的向量有M L 个可能结果。于是，整个序列可以描 述为 XL P (x) = x1 P1 x2 P2 ? ? ? xM L ? ? ? PM L (4)要点 :把L长的序列看成一个更大的单个符号。 当我们用式(4)来描述随机序列时，一个关键就是如何写出每一种总结果的 出现概率。如果这L个随机变量是相互独立的，那么总结果的出现概率就是各 个随机变量出现概率的乘积。比如课本上的式(7.2.10)。这种情况称为无记忆 信源。是说，信源每次输出的结果都与先前的输出无关，其随机性完全是单独 的。 如果序列是相关的，那么写出第i种向量结果xi 的出现概率就不能用各自概 率的乘积，而要用链式规则: P (X L = x) = P (X1 = xi1 , X2 = xi2 , ? ? ? , XL = xiL ) = P (X1 )P (X2 |X1 )P (X3 |X2 , X1 ) ? ? ? P (XL |XL?1 ? ? ? X1 )(5)其中P (X1 )是P (X1 = xi1 )的简记，其他类似。 对式(5)的理解是：X2 的结果是随机的，但其结果和X1 是有关系的。如果已 知X1 的具体结果之后再来看X2 ，虽然它还是不确定的，但此时的不确定性 （随机性）是X1 之外的原因造成的，这个原因和造成X1 随机性的原因是独立 的，因此就可以进行概率相乘了，即P (X1 , X2 ) = P (X1 )P (X2 |X1 )。P (X2 |X1 )是 已经知道X1 的条件下，X2 还具有的随机性。2信息量信源发送随机变量X 给信宿。因为信宿不能预见到X 具体是多少，所以在信宿 看来，X 是随机的。而信宿所获得的信息量也是和这种随机性关联在一起的。 假如信宿早就能料到X 会是什么，那么信源发送X 给信宿这个行为没有使信宿 得到任何信息。 X 有M 种 不 同 的 取 值 ， 每 种 的 可 能 性 都 不 同 。 就 是 说 ， 信 宿 未 见 到 发 送 内 容 之 前 ， 它 对 信 源 发 送 的X 的 预 料 是 ： 有P1 的 机 会 是x1 、 有P2 的 机 会 是x2 ，……。当信宿确实观察到X 之后，事先的种种猜测已经变成现实。 若有一个事情，你不确定其具体结果是什么，只能猜测的话，这个事情对你 来说就存在着“不确定性”。有人告诉了你结果，将使你消除不确定性，也就 是说你获得了信息。因此，所谓“信息”其实就是“不确定性”。 如果X 的内容越是预料之外，信息量也就越大。完全在料定之中的事情如果 发生，和别人不告诉你结果是一样的，因而是没有信息量的（别人不告诉你结 果，并没有改变你对这个事情的认识）。举例来说，某生参加《通信原理II》 2考试，依其自我判断，他认为考试成绩X 取值于(99, 100)范围的概率大于0.99， 考试成绩在[60, 99)的概率是0.009。如果同学查分后告诉他考了99分，这个消息 对他没有多少信息量。但如果同学告诉他说他考了12分，那么这可是个重大消 息，足以使他产生多种常见的狂躁情绪。 以西洋科学为特征的“现代科学”的基本原则是要把所研究的问题数学 化，一般就是数量化。为了研究“信息”这个东西，我们先试图将其量化。 若信息的量是I , 那么依前面的讨论，I 的大小是和X 的具体实现有关系的， 不同的X 的实现，其随机性（概率）不同，因此信息量也不同，因此可记 为I [P (xj )], 即I 是概率P (X = xj )的函数。这个函数应该满足: I是概率的减函 数，概率越大，信息量越小（概率越大，就越在预料之中）。若概率为0则I是 无穷；若概率为1，则I应该是0。另外，两个独立事件组成的事件（比如通 原II考试得99，食堂吃饭发现蟑螂肉也很好吃。没有迹象表明这两件事情有因 果联系，故此可认为它们独立）的信息量应该是各自信息量之和。你同学告诉 你这两件事情，你所获得的信息的数量应该就是相加的关系。但在概率论中， 这两个事件的概率是相乘的关系。这就是说I作为概率的函数，乘积的函数必须 是函数的和：I (p1 ? p2 ) = I (p1 ) + I (p2 )。Shannon等先驱经过苦苦思索后，发现 这个函数应该是 I (p) = ? log(p) (6) 对数取什么底无关紧要。如果以2为底，则I的单位叫bit；如果是以e为第，则 称奈特(nat); 若以10为底，则称为Det（笛特）。 如果随机变量X 有两种可能，机会各占一半，则无论哪一个发生，信息量都 是? log2 (1/2) = 1bit。因此，“1bit”的意思就是，在两个等可能的不确定的 结果中，确定了其一发生，便是得到了1bit的信息量。 要 点：信息的多少就是不可预料性的大小，它是概率的函数，取值于[0, ∞),满 足可加性和递减这两个关键特征。这样的函数只能是log函数。 信息量是概率的函数，条件概率和联合概率自然也有相应的信息量。条件 概率P (Y = yj |X = xi )所算出的信息量是指，已经知道X = xi 的情况下，继续 告诉信宿Y = yj 所能带给信宿的信息量。如果X与Y不独立，那么I [P (Y |X )]将 不见得会等于I [P (Y )]。比如说，若X代表升高，Y代表体重。那么X的随机性 和Y的随机性是高度相关的。尽管高度相关，即使已经知道了身高，你还是 不能断定体重是多少。Y |X 表示给定身高条件下Y的随机结果，相同身高条件 下，造成体重随机性的因素已经和造成身高的随机性因素无关了。所以相应概 率，例如P (Y = 10kg |X = 180m)的信息量I [P (Y = 10kg |X = 180m)]是在你 已知身高为180m的条件下，继续告诉你身高只有10kg, 这个消息带给你的信息 量。 注意，条件信息可能比无条件的信息量大或小。（信息量的大小就是你的意 外程度）。 联合概率P (X, Y )的信息量容易理解。我们前面已经说过，可以把(X, Y )整 体当作一个事件，因此联合概率的信息量就是这个整体事件的发生结果所带来 的信息量。3熵把随机变量X 的每一种结果xj 通过函数y = f (x)映射为yj = f (xj )，我们就定义 了另外一个随机变量Y = f (X )。 现在，X 的每个结果xj 都通过其发生概率Pj 映射为一个实数Ij = ? log(Pj ), 因此I也是一个随机变量。也就是说，因为发生哪个是不确定的，所以信宿得到 3的信息量也是不确定的。 信源X 的平均信息量称为其熵(entropy)，记为H (X )：M MH (X ) = E [I ] =j =1(Pj × Ij ) = ?j =1(Pj log Pj )(7)熵作为信息量的数学期望，其单位自然也和信息量一样，是bit或者nat，取 决于对数的底是多少。如果我们谈论的是随机序列{Xi }中某一个符号的熵，则 习惯把单位写成“bit/symbol”。 二元熵函数：如果X是二进制随机变量，其可能取值只是x1 , x2 , 对应的概率 是p, 1 ? p。那么X的熵是 h2 (p) = H (X ) = ?p log(p) ? (1 ? p) log(1 ? p) 其图见课本296页。 联 合 熵 : 两个随机变量X、Y有联和概率，因此有联合的信息I [P (X, Y )]， 这个I的大小与具体的(X, Y )取值有关，是依赖于X、Y的随机量，对它求数学 期望就是联合熵： H (X, Y ) = E [? log P (X, Y )]M M ?(8)=?i=1 j =1P (X = xi , Y = yj ) log P (X = xi , Y = yj )(9)条件 熵: 条件概率P (Y |X )对应有条件信息I [P (X, Y )]，它也是与具体的(X, Y )取 值有关的，对其求数学期望就是条件熵： H (Y |X ) = E [? log P (Y |X )]M M=?i=1 j =1P (X = xi , Y = yj ) log P (Y = yj |X = xi )(10)利用前面提到的的链式法则：P (X, Y ) = P (X )P (Y |X )，可得 H (X, Y ) = E [? log P (X, Y )] = E [? log P (X ) ? log P (Y |X )] = H (X )+ H (Y |X ) (11) 同样可以得到 H (X, Y ) = H (Y ) + H (X |Y ) (12) 这些结果是很好理解的：注意熵就是平均的信息量。得知X，Y这两个结果 平均获得的信息量是：先知道X所获得的信息量，再加上又知道Y所新增加的 信息量。条件熵H (Y |X )就是已知X之后，继续知道Y所新增加的平均信息量。 关于熵有下面的不等式： H (X ) ≤ log M (13)1 ）时成立，此即“等概的信源熵最大”。 等号在X等概出现（P (X = Xi ) = M 如果信源等概，我们对它是什么最没有把握。假如我们知道某种结果要比另外4一种出现机会大一些，那么我们实际上已经有了一点信息，在出现可能性判断 上已经能有所偏向。因此，等概熵最大是很合理的事情。 证明: H (X ) ? ln M = E [? ln P (X ) ? ln M ] = E [ln M P1(X ) ]，由ln(x) ≤ x ? 1得 H (X ) ? ln M ≤ E [ # 用类似方法还可以证明 H (X |Y ) ≤ H (X ) (14) 1 1 ? 1] = E ?1 = M P (X ) M P (X )MP (xi )i=11 ?1 = 0 M P (xi )等式在独立时成立。这个结果的意思是说，如果两个随机变量有关系，那么已 知第一个随机变量的结果时，再告诉你第二个随机变量的结果所带给你的平均 信息量将比单纯告诉你第二个结果要来的小一些。（但不排除个别情况下，已 知第一个事情后可，第二个事情的结果更让你吃惊，条件信息量I (P (Y |X ))可 能比I [P (Y )]大或者小，条件熵H (Y |X )一定不会比H (Y )更大）。5通信原理II第二讲March 6, 20071互信息信息量是不确定性，就是你不可能猜出来的那些东西。对于随机变量X，平均 信息量是H (X )。 对于两个随机变量，已经知道X后，对于Y我们仍然有一些猜不出来的地 方。平均猜不出的程度就是条件熵H (Y |X )，它必然小于等于H (Y )。也就是 说，如果不知道X的具体内容，猜Y猜不出的程度会更大一些。 换言之，已知X使我们对Y多少知道了一些，这个程度是H (Y ) ? H (Y |X ), 它 叫 互 信 息 （mutal information,MI） ， 记 为I(X;Y)。 因 此 ， 互 信 息 就 是 已 知X后，我们能依据X而猜出的关于Y的信息。 注意记号，我们有时候把自信息I [P (X = xi )]写成I (X ), 如同我们会把概 率P (X = xi )写成P (X )一样。因此需要注意自信息和互信息的符号差别，I (X, Y )是 自信息，它是I [P (X = x, Y = y )]的简写。互信息是I (X ; Y )。这里一个是分 号“;”，一个是逗号“, ”。 有如下关系： I (X ; Y ) = I (Y ; X ) = H (X ) ? H (X |Y ) = H (Y ) ? H (Y |X ) = H (X ) + H (Y ) ? H (X, Y )(1)证明：若A、B独立，则P (A, B ) = P (A)P (B )，H (A, B ) = H (A) + H (B )。由 于P (X, Y ) = P (X )P (Y |X ) = P (Y )P (X |Y )，因此，Y 和X |Y 是独立的，X 和Y |X 是 独立的。因此H (X, Y ) = H (X ) + H (Y |X ) = H (Y ) + H (X |Y )，代入上式即可 得证。# 式(1)表明，已知X猜Y能猜出多少，已知Y猜X也能猜出同样多。课本301页 的图7.4.1以文式图（Venn diagram）的方式示出了有关量值的关系。两个圆分 别表示H (X ), H (Y )，是我们对单独的X、Y而言所不知道的东西；X、Y之间 有一些共同的东西，这就是互信息I (X ; Y )。如果知道了X，那么Y中与X共同 的这部分信息就知道了，余下的就是条件熵H (Y |X )。就整体而言，我们不确 定的程度不是H (X ) + H (Y )，因为这两个不确定中有共同的部分，所以总的不 确定程度是H (X, Y ) = H (X ) + H (Y ) ? I (X ; Y )。12信源的表达方式、信源的效率同样的信息可以有不同的表达方式，比如母亲对孩子说“看我不揍你”，其含 义是“我要揍你”；某个小伙子A 听B说了某句话后，愤怒地说“你再说一遍 试试”，意思是禁止B再这样说。再比如，传送掷筛子的结果{6 6 4 1 2}时，如 果改变为{000 000 111 101 110}并无不妥，只要收发都约定好：000 → 6, 111 → 4, ? ? ? ,即可。 通信中，要把信源的输出{X1 , X2 , ? ? ? , XL }传递到信宿，我们也有多种表达 方式可选。当然要选最有效率的方式。因此，实际传送的可能是另外一个序 列{Y1 , Y2 , ? ? ? , YM }。比方说Y是二进制符号，则传送它需要M个bit。 若序列{Xi }是n进制，则{X1 , X2 , ? ? ? , XL }有nL 种不同结果。顺序编号为 0, 1, ? ? ? , nL ?1，再转为二进制，则需要log2 nL = L log2 n bit。若序列{Yi }是m进 制，则{Y1 , Y2 , ? ? ? , YM }有mM 种不同结果，顺序编号为0, 1, ? ? ? , mM ? 1，再转 为二进制，则需要M log2 m bit。只要M log2 m & L log2 n，那么传送（或存 储）序列{Yk }显然更有效率。这就是信源编码的基本思想。 乍一看，这个思想是有问题的：如果nL & mM ，那么序列{Yi }的全部结 果只能表示序列{Xi }的一部分结果。正如：原序列是6次掷筛子的结果，总共 有66 = 46656种不同的结果，而我们打算用7张不同花色的扑克牌来表达原序 列，后者只能表达47 = 16384种结果。 奥妙就在于熵这个概念。Shannon说，别看序列{X1 , ? ? ? , XL }有nL 种不同 的结果，但因为符号不等概、序列也可能前后相关，所以它的全部信息量只 L 有H (X1 , X2 , ? ? ? , XL ) & i=1 H (Xi ) = LH (X ) & L log2 n，其中H (X )是单个 符号的熵（假设平稳，则每个符号的熵都一样大）。设H (X1 , X2 , ? ? ? , XL )的 数值为a bit，那么用a个YES/No问题就能确定出具体{X1 , ? ? ? , XL }的结果，因 此实际只需要传a个bit(a个YES/NO问题的答案)，它要比L log2 n小得多。 这里的原因在于“典型”“非典型”序列这样的概念。Shannon说，如 果L → ∞，那么所有{Xi }的结果可分为两类，“典型序列”和“非典型序 列”，根本不用考虑非典型序列，而典型序列只有2H (X1 ,??? ,XL ) 个。 例如：考虑1万个掷硬币的结果。所有可能结果有210000 种。如果正反面出 现机会不等，比如反面出现机会是2/3，如果你设计的系统压根不打算传送某 些结果，比如正面占90%的结果，那么你的系统基本上不会有什么风险。因为 正面出现的机会少，所以1万个硬币有9000个正面这种情况虽然有可能，但比 起其他“典型”结果来说，可能性可以忽略。信息论对这种风险有具体的估算 办法，如课本上的例7.6.2。我们对此不作特别要求，只是再次重申一下信息论 的观点： 传输（或存储）序列{X1 , X2 , ? ? ? , XL }（L非常大）所需要的比特数最少 是H (X1 , X2 , ? ? ? , XL )，折合到每个符号仅为: H∞ (X ) lim H (X1 , X2 , ? ? ? , XL ) L (2)L→∞对于序列{Xi }，传送X1 的信息量是H (X1 ) = H (X )，是单符号的熵；再 传送X2 时，只需传送新增的不确定性H (X2 |X1 )。依此类推，传送第L个符 号XL 时，只需传送H (XL |XL?1 , ? ? ? , X1 )。当L非常大时，以后每出现的一个 符号新增的信息量limL→∞ H (XL |XL?1 , ? ? ? , X1 )并不大。这个增量自然就是序 列的总信息量平均到每个符号的结果：2L→∞lim H (XL |XL?1 , ? ? ? , X1 ) = limL→∞H (X1 , X2 , ? ? ? , XL ) LH∞ (X )(3)这个结果不仅符合直觉，也是可以证明的。首先 limL→∞ = ≥ = H (X1 ) + H (X2 |X1 ) ? ? ? H (XL |XL?1 , ? ? ? , X1 ) H (X1 , X2 , ? ? ? , XL ) = lim L→∞ L L H (XL ) + H (XL |XL?1 ), ? ? ? , H (XL |XL?1 , ? ? ? , X1 ) lim L→∞ L H (XL |XL?1 , ? ? ? , X1 ) + H (XL |XL?1 , ? ? ? , X1 ), ? ? ? , H (XL |XL?1 , ? ? ? , X1 ) lim L→∞ L 1 lim H (XL |XL?1 , ? ? ? , X1 ) L→∞ L1 即H∞ (X ) ≥ limL→∞ L H (XL |XL?1 , ? ? ? , X1 )。上面用到了平稳性和增加条件 将使熵变小这两个性质。其次= ≤ =H (X1 ) + H (X2 |X1 ) ? ? ? H (XL |XL?1 ? ? ? X1 ) H (X1 , X2 , ? ? ? , XL ) = L L H (X1 ) + ? ? ? + H (XM |XM ?1 ? ? ? X1 ) + H (XM +1 |XM ? ? ? X1 ) + ? ? ? + H (XL |XL?1 ? ? ? X1 ) L H (X1 ) ? ? ? H (XM |XM ?1 ? ? ? X1 ) + H (XM +1 |XM ? ? ? X2 ) + ? ? ? + H (XL |XL?1 ? ? ? XL?M +1 ) L H (X1 ) + ? ? ? + H (XM ?1 |XM ?2 ? ? ? X1 ) + (L ? M + 1)H (XM |XM ?1 ? ? ? X1 ) L1 先固定M ,令L → ∞，再令M → ∞，上式结果就是H∞ (X ) ≤ limL→∞ L H (XL |XL?1 , ? ? ? , X1 )。 1 因此必然有H∞ (X ) = limL→∞ L H (XL |XL?1 , ? ? ? , X1 ) 综上所述，对于信源{Xi }，如果不采用任何压缩技术，平均每个符号需 要log2 n H0 (X )比特。如果采用高效的压缩技术，最好情况下有望每个符号 ∞ (X ) 平均只需要H∞ (X )比特。压缩比极限可达到 H H0 (X ) 。这个比值也叫信源的效 率η ，相应定义信源的冗余度为R=1?η =H0 (X ) ? H∞ (X ) H∞ (X ) =1? H0 (X ) H0 (X )实际信源的特征往往是：符号不等概，符号之间有很强的相关性。因此它 一定可以压缩，具体方法的压缩能力或许有区别，最大的压缩程度可由η 或R衡 量。计算H∞ (X )需要用到无限维的概率分布（因为计算熵H (X1 , ? ? ? , XL )或者 条件熵H (XL |XL?1 , ? ? ? , X1 )都需要L维概率P (X1 , X2 , ? ? ? , XL )）。这些概率 可以用统计方法获得。表7.3.4是统计得到的H∞ 。 上述最好的方法充分利用了信源序列的相关性。对于第L个符号，它充分 扣除了过去所有符号在XL 上的贡献，只传送纯新的增量信息。如果我们只考 虑A个符号，即对于第L个输出符号，只扣除前A ? 1个符号的贡献，那么效率就 会低一些，平均每符号最少需要的比特数将是HA (X ) H (XL |XL?1 , ? ? ? , XL?A+1 )。 3H2 (X ) = H (XL |XL?1 )只考虑前一个符号的贡献；H1 (X ) H (X )只考虑单个 符号，不考虑相关性，但考虑了不等概特性；H0 (X )则连不等概都不考虑，即 不进行压缩。下面的不等式是显而易见的 0 ≤ H∞ (X ) ≤ ? ? ? ≤ H2 (X ) ≤ H1 (X ) ≤ H0 (X ) = log2 n (4)3信源编码上面我们已经看到，信息论的基本意思是，对于信源我们只需要传送它的熵就 可以了。信息论对此有更为严格和精确的表述。我们略讲一二。3.1等长无失真编码对于不等概的独立序列信源，每符号最少可以压缩到H1 (X )（因为独立，所以 没有相关性可利用，H∞ = H1 ）。一种做法是：将信源序列分为等长的组，每 组长度比如是L。每组的可能结果有nL 种，扣除非典型序列，对剩下的进行编 码（就是进行二进制整数编号）。虽着L趋于无限长，这种方法可以趋向极限 的效率: 每符号所用的比特数仅为H (X )。 无失真的意思是，用编码结果{Yi }能够完全复原出原序列{Xi }(不能复原出 非典型序列结果，但这个概率可以忽略)。也思就是说I (X ; Y ) = I (X )。3.2变长无失真编码如上的方法实际上是不现实的，经过一番计算我们发现，要使这种编码是保险 的，分组长度必须非常长。保险的意思是，非典型序列的概率确实可以忽略。 课本例7.6.2就是这种计算的一例，虽然如何计算不在我们的要求之内，但从这 个例子的结果能看到分组长度到底需要多长。 一种简单，而且有效的方法是采用变长编码。其思想是，出现频率高的符号 用短码，出现概率低的用长码。理想状态下，这样做效果非常不错。 变长编码的一个经典例子是Hu?man编码。3.3限失真信源编码前面谈论的是离散信源。对于连续信源，要想精确表达信源，熵是无穷大， 这当然是做不到的。例如，对于均匀分布在[0, 1]内的X , 如果按间隔0.1量化， 结果有10种，熵是1Det = log2 10bit；如果量化间隔是0.01，熵就是lg 100 = 2Det。可见，真要想无限精确地传送X 的话，信源的熵将是无限大。 好 在 对 许 多 应 用 来 说 ， 我 们 没 有 必 要 无 限 精 确 。 比 如 一 个 听MP3的 学 生 不 可 能 抱 怨 说 ， 它 听 到 的 某 个 歌 的 某 个 抽 样 值 比 原 音 的 电 压 值3.04V 低 了0.000001V ，人类的耳朵不可能有这么高的分辨率。因此，我们退而寻求 这样的编码，它把原始信息X 映射成Y ，虽然I (X ; Y ) & H (Y )（就是说，我们 得知Y并不能完全精确的复原X，否则就是I (X ; Y ) = I (X )），但由Y复原的结 果和X相比，“失真”完全可以满意。失真的意思是Y = X ，失真的程度D是 一个数，我们用它来说X 和Y 不相等的程度。一般用均方失真（但也可以用其 他定义）：D = E [(Y ? X )2 ]。4对于可允许的失真度D，存在许多将X 映射为Y 的方法，其中的互信息I (X ; Y )就 是该种方法所需要的传输量，也称为信息率（单位一般是每符号多少bit）。如 果数学模型齐备的话，信息论能算出所有这些失真符合要求的方法最小的互信 息，这个值定义为“率失真函数”，记为R(D)，它是给定可允许的失真为D的 条件下，最少需要传送的信息量。它是一个函数，自变量是失真程度D，函数 值是信息率R，所以叫率失真函数。4利用序列的相关性实际信源都是有相关性的，如前所述，如果能够理性地扣除随机变量之间的关 联，信源实际的熵要比看上去小得多。因此，实际应用中的压缩技术都在这方 面花费了很大力气。 一种方法是预测编码，在发送样值XL 之前，它先预测一下这个值可能是多 少，预测的结果当然不可能绝对准确(XL 毕竟会有新的信息)，我们再把预测误 ?L 传过去。因为误差毕竟比较小，所以传它的时候，量化比特就可以 差XL ? X 少一些。 另一种方法是变换编码。一个随机向量经过适当线性变换后，可以变得彼此 不相关。这使我们能把相关信源改造成不相关信源。因为熵不大，所以变换后 的表现是，某些值可能非常小，以致于忽略它影响不大。这样我们就能大大减 少传输量。5通信原理II第三讲March 13, 20071量化连续随机变量X 的熵是无穷大，量化器把它映射到M 进制的离散随机变量Y ， 传输Y 最多只需要log2 M bits/symbol，如果Y 的这M 个量化电平不是等概出现 的话，还能更少。 对于通常的量化设计，如果已知X ，那么Y 就是确定的，但已知Y 并不能 确定X ，即I (X ; Y ) = H (Y ) & H (X )。因此Y 和X 之间的失真D必不为零。 给定D的情况下，理论上最好的量化器所需要的传输速率是R(D)（率失真函 数）。 对于一些具体的量化器，它的速率也是失真的函数。比如，若Y 均匀分布， S 那么均匀量化器的量化信噪比是 N = M 2 。不妨假设信号功率S = E [X 2 ] = q √ √ 1(即X 在[? 3, + 3]内均匀分布)。量化噪声Nq E [(Y ? X )2 ]就是均方失 真D。而传输速率R是每样值（即每符号） log2 M bit，此情形下速率与失真的 √ 函数关系是R(D) = ? log2 D，其曲线与图7.7.1类似。若要求D = 0，则R就 得无穷大（因为M 无限大）；如果允许D = 1的话，R = 0，说明不用传就可 以。这种方案是，无论Y 是多少，收端始终输出X = 0。 注意，信息论讲的是我们最好能做到什么程度（理论上的可能性）。7.9C 7.11节讲的是一些具体做法（真实存在的技术），前面的Hu?man编码也是一 种具体技术。假如我们通过适当的数学模型能算出7.8节给出的R(D)，那么任 何实际的量化系统都不可能做到比它更好。 7.9.3讲的是标量量化，均匀量化是这种量化的一种最简单形式。就一般而 言，量化的设计包括两点： 1. 把X 的取值范围(?∞, +∞)或者(?A, +A)分割成M 个不重叠的子区间（量 化区间）； 2. 对每个区间设计一个代表此区间的点：量化电平。 发送端传给接收端的是子区间的编号。收端只要知道X 在那个子区间就够了。 接收端知道每个区间的量化电平是多少，因为这是事先设计的。 均匀量化只是一种简单的量化方式。给定M 时，能使D最小的量化方法见课 本326页。它的思路是，把失真D表达成多元函数，其自变量是分界点和代表点 （量化电平）。再用数学中求多元函数极值的方法得到最佳的设计。其主要结 论是 1. 边界必须是代表点的等距分界点； 2. 代表点必须是概率质心，或者说是条件数学期望。 1上述量化是对标量X 进行的，也可以扩展到矢量，即把(X1 , X2 , ? ? ? , XN )当 作一个整体，将它进行空间划分，再把矢量所在的区域编号传给收端。收端得 到这个编号后，用预先为该区域所设计的代表点(Y1 , Y2 , ? ? ? , YN )来近似信源端 的矢量(X1 , X2 , ? ? ? , XN )。这些代表点的集合叫做码本(codebook) 。发端储存 着划分空间的方法，收端储存着码本。 比如说，(X1 , X2 )的取值范围是平面上的一个正方形，这个正方形的左 下角的坐标是(?A, ?A)，右上角的坐标是(A, A) 。采用笛卡儿积的记号方 法，(X1 , X2 )的取值范围就是(?A, A) × (?A, A)。M = 8的矢量量化就是把这 个正方形分割成8个区域，并为每个区域设计一个代表点。如下图所示 如果X1 , X2 落在某个区域中，就把这个编号告诉收端。这样做的传输速率 28 是R = log = 1.5bits/symbol，相应的失真度取决于区域的划分方法和代表点 2 的选择。对于最佳的设计，边界线是代表点之间的等距线，代表点是该区域的 概率质心（条件数学期望）。2相关信源如果信源序列之间有相关性，表明它们之间的互信息不为0，每一个符号单独新 增的信息并不一定很大。预测编码和变换编码的原理都是一样的，就是先把信 源改造成不相关序列。改变相关性的常用做法是进行线性变换。 预测编码中，我们不是直接传送第L个信源符号XL （对语音信号，就是抽 ? L 的差：YL = XL ? X ? L 。整体看，等于是把序 样值），而是传送它和预测值X 列{Xi }变换成了序列{Yi }。理想的情况下，{Yi }应该是个独立序列，表明预测 值完全包含了过去符号的贡献，使得扣除预测值后的预测误差只包含新增的信 ? L = XL ，除非H∞ (X ) = 0，否则这是不可能的。 息。注意，理想情况不是X ? L = f (X1 , X2 , ? ? ? , XL?1 )。 预测器用过去的结果计算出预测值，可记为X ? 这个f 一般用线性函数，即XL 是X1 , X2 , ? ? ? , XL?1 的线性组合。这样，YL = ? L 自然也是X1 , X2 , ? ? ? , XL?1 的线性组合。因此，把信源{Xi }映射为{Yi }的 XL ?X 过程就是经过了一个因果的滤波器（线性系统）。这个例子中的规则是：得 到YL 不得利用未来的符号{XL+1 , XL+2 , ? ? ? }（因果性）。 在另外一些应用中，信源{X1 , ? ? ? , XL }不一定表示按时间顺序先后到达的 符号（也许是空间次序，比如图片）。或者虽然是时间顺序，但我们可以批量 处理，一次处理L个，下次再处理L个。它和刚才的差别是，得到Yk 时，我们可 以用它后面的Xk+1 。对于固定长度为L的序列，能去除相关性的线性变换就是 一个矩阵变换：[Y1 , Y2 , ? ? ? , XL ]T = A[X1 , X2 , ? ? ? , XL ]T 。 总而言之，相关信源中的相关性是一种冗余，去除相关性就能提高传输效 率。预测编码和变换编码都是借助线性变换来改变相关性，只不过一个是因果2滤波器，一个是矩阵变换。它们的实质是相同的。实际的技术或许出于复杂性 或其他原因不能完全消除相关性，但至少能使它显著变弱。3信道信道是一个抽象的概念，指所研究问题中从发送端到接收端之间的一切环节。 不同的情景下，“发送端”和“接收端”所指不同，因而信道的含义也不同。例 如： 1. 在无线通信中，发送天线到接收天线之间的电波传播空间是一种信道， 这个信道也叫“狭义信道”或者“传输媒质”； 2. 从调制器的输出端到解调器的输入端的一切环节是一种信道，它的内部 包含了上下变频器、放大器、收发滤波器、收发天线、传输媒质等； 3. 从A律十三折线编码器的输出端到接收机中A律十三折线译码器的输入端 之间的一切环节也是一种信道，它的内部包括了调制解调器以及前面所 提到的信道。 再比如，下图是一个BPSK系统的框图。图中的“编码器”和“译码器”指的 是第九章要讲的信道编码，目的是为了纠正BPSK解调后仍然存在的误码。对 于不同的研究，信道可能是A → B （无线传输媒质）、C → D（BPSK调制 的带通信道）、I → J （BPSK调制的等效基带信道）、G → H （离散时间 的BPSK等效信道）、E → F （二元数字信道）等等。 无论是哪一种情况，总Figure 1: 某BPSK系统Figure 2: 信道模型 可以把问题抽象为Figure. 2：信道的输入或者是连续时间的随机过程X (t)，或 者是离散时间的随机序列{Xi }。信道的输出也可能是随机过程Y (t)或者随机序 列{Yi }。信道所起的作用就是把输入的随机过程或序列映射为另外一个随机过 程或者序列。这种映射其本身往往具有随机性。也就是说，观察到输出Y ，并 不能确定发送的X ，也即I (X ; Y ) & H (X )。4无线多径信道考虑图1中的信道A → B ，如果信道的输入是X (t)，输出Y (t)必然会包括噪声 和干扰的影响。除此之外，无线传播环境也会带来许多复杂的影响。由于后者 3是无线通信信道最具特征的东西，所以在无线信道建模时，我们关键是要搞清 楚信道传播对信号带来的影响。故此，我们忽略噪声和干扰，先来看传播过程 造成的影响。 设想手机中藏有一个观察者，那么在这个观察者看来 1. 接收信号的强度在随机变化。此现象叫做衰落(fading) 2. 接收信号的频率在变化。此现象叫多普勒频移（Doppler shift）。 他观察到这些的原因在于：(1)用户在移动；(2)到达手机的无线信号是经由 多个路径到达的。 Doppler的原理在于，波的相位是时间和空间的函数。如果频率是f0 ，那 t 么在静止的地点，经过?t时间后观察到相位变化是 ? T0 × 2π = 2πf0 ?t(T0 是 周期)。如果用户同时还在以速度v 移动，那么经过?t时间后空间相位的变化 ×v × 2π （λ是波长）。藏在手机中的观察者不知道这两种相位变化的区 是 ?tλ ×v 别，他看到的只是，经过?t时间后，到达手机的信号的相位变化了 ?tλ × 2π + 2πf0 ?t = 2π (f0 + v/λ)?t。于是，他以为发送信号的频率是f0 + v/λ，因为他 不知道手机在移动（想象一下，他只能看示波器之类的仪表，不许他看手机外 面的风景）。或者说，在他看来这和发送频率就是f0 + v/λ没有区别。如果考 虑到移动方向θ，上述v 应改为v cos θ。v/λ cos θ叫做方向θ上的Doppler频移，其 最大值v/λ叫最大多普勒频移。 接收信号所呈现出的衰落还可分为平衰落和频率选择性衰落。假设发送一个 复包络为b(t) 的带通信号，这个信号将经过许多路径到达手机。每一径所经历 的幅度衰减?i ，相移?i 、时延τi 都可能不同，并且它们可能会随时间变化（因 为手机在移动）。通常，手机移动造成的某一径上的时延变化不大。因为电磁 波以光速传播，时延变化1?s意味着位置相隔300m。在短时间内，手机位置不 可能发生这么大的变化。因此一般可以忽略τi 随时间的变化。因而第i径在t时刻 接收到的带通信号的复包络是?i (t)ej?i (t) b(t ? τi )。总接收信号是 r(t) = Rei?i (t)ej?i (t) b(t ? τi )ejωc t(1)如果各路径之间的时延差相对于b(t)来说非常小，比如，各路径的时延的差别 在?s数量级，而b(t)是速率为1kbps的双极性NRZ信号（BPSK的复包络），那 么式(1)就可以近似成 r(t) ≈ Re b(t ? τ ?)i?i (t)ej?i (t) ejωc t(2)相当于让复包络乘上了一个时变的复数h(t) = i ?i (t)ej?i (t) 。这种情形叫平衰 落。如果手机不动，则?i 和?i 都不是时间的函数，因而h是个复常数。如果信 号所经过的系统只是乘了复常数，这个系统的传递函数在所有频率上都一样， 即其频域特性是平的。平衰落在任何一个瞬时都是一个频域特性为常数的线性 系统。它不会对发送的信号造成波形失真（假设h(t)的变化比b(t)的变化慢得 多），但不同瞬时的信噪比是随机变化的。 注意，以上讨论中，我们假设信道的时变性仅由于手机移动。实际上，发送 端的移动，以及周边环境中物体的移动也会产生同样的效果。4通信原理II第四讲March 20, 20071信道信道可分为连续时间信道和离散时间信道两类。连续时间信道一般可以用 图8.4.1来描述。它表示，发送信号s(t)先经过了一个信号系统变换为ft [s(t)]， 记号ft 代表这个信号系统所做的变换，之后叠加了噪声n(t)。描述信道的关键 在描述ft ，即信道对发送的信号进行了怎样的变换。因此，许多文献在描述信 道时略去噪声，只谈论ft 。但注意这绝不表示没有噪声。 ft 经常是线性系统，并且经常是随机时变的线性系统。所谓时变线性系统， 是说在一个局部时间它是线性时不变系统，有明确的冲激响应h(τ )及传递函 数H (f )。但在不同的局部时间（比如1小时前的若干ms内，和现在的若干ms时 间内），这两个线性时不变系统是不相同的（h(τ )，也即H (f )不相同）。这种 不相同一般具有随机性，因此有时也称为“随参”信道，意思是说，线性时不 变系统的参数（如冲激响应）在随机变化。相应的，不随时间变化的信道就是 “恒参”信道。更常见的说法是“时不变信道”或者“静态信道”。 有 些 系 统 可 能 有 多 个 发 送 端 ， 多 个 接 收 端 。 这 样 的 系 统 叫MIMO系 统 （mutilple input multiple output）。例如基站有可能通过4根发送天线向某 个终端发送信号，这个终端（比如笔记本电脑）也可能配备了2根接收天线来接 收信号。 总之，连续信道一般可以描述为线性时变系统，然后叠加了噪声和干扰。后 者一般可以建模为平稳高斯过程。 时间离散的信道则是用转移概率描述。对于无记忆信道，可用一维转移 概率P (Y |X )来描述。如果信道输入X 和Y 是有限取值的，还可以用图8.4.3、 图8.4.4这样的图示方式来描述。注意，X ，特别是Y 有无限种取值是很平常 的。例如，若信道的输入端是BPSK发送数据冲激的点（根升余弦脉冲成形 的输入），信道输出端定义为接收端匹配滤波器采样输出的点，那么X ∈ {+1, ?1}，Y ∈ (?∞, ∞)。适当控制接收端匹配滤波器的增益，可以使采样结 果中的信号分量也取值于{+1, ?1}。若噪声方差是σ 2 ，则Y = X + Z ，Z 是抽 样中的噪声成分。信道的转移概率是 P (Y |X ) = √ 1 2πσ 2 e?(Y ?X )2 2σ 2(1)在不同的研究问题中，“信道”物理所指可能不同。一个离散时间的信道其 内核可能就是一个连续时间的无线信道。比如刚才这个BPSK信道X → Y 是离 散时间信道，但该系统中的BPSK已调信号sBP SK (t) = b(t) cos(ωc t + θ)必然要 经过连续时间的无线信道到达接收端。12连 续时 间信 道 ―无 失真 信道r(t) = as(t ? τ0 ) (2)发送s(t)，若接收信号是 其中a, τ0 是确定的常量，则我们认为r(t)相比于s(t)是无失真的。因为已知的常 数a可以消去（除以a），固定的小时延对通信质量没有关系（手机通话时，如 果有几十毫秒的延迟当然无所谓了）。 [r (t)] ?j 2πf τ0 ， 如果一个线性系统满足式(2)，其传递函数必然是H (f ) = F F [s(t)] = ae ?1 冲激响应必然是h(τ ) = F [H (f )] = δ (τ ? τ0 )。传递函数的特征是: 1. 幅频特性|H (f )|是常数， 2. 相频特性?(f ) ∠H (f ) = ?2πf τ0 是过原点的直线。如果信道满足这样的特征，称为“理想无失真信道”。 无线信道传输的是带通信号，带通信号的信息完全包含在复包络中。即便发 送的信号s(t)和接收信号r(t) 之间不满足r(t) = as(t ? τ0 )的关系，也有可能复包 络是无失真的。比如对于QPSK信号sQP SK (t) = bI (t) cos ωc t ? bQ (t) sin ωc t， 如果接收信号是r(t) = 2bI (t ? τ0 ) sin ωc t + 2bQ (t ? τ0 ) cos ωc t，那么对于任 意的τ0 ，r(t)和sQP SK (t) 的波形并不相同，即r(t)不是sQP SK (t)延迟后再进行 幅度缩放。但从复包络看，发送信号的复包络是sl (t) = bI (t) + jbQ (t)，接 收信号的复包络是rl (t) = 2bQ (t ? τ0 ) ? 2jbI (t ? τ0 ) = 2j × sl (t ? τ0 )，符合 式(2)所定义的无失真，只不过系数a是复数2j 。这就是说，对于带通信号， 如果复包络符合式(2) 的关系，就可以认为信道是无失真的，虽然此时的带 通信号自身实际上可能有失真。由于谈论的是复包罗，此时(2)所描述的是 带通信道的等效基带信道Heq (f ) = ae?j 2πf τ0 ，它和带通信道H (f )是平移关 系，H (f ) = Heq (f ? fc )（f 在fc 附近）。因此满足复包络无失真的带通系统的 特征是： 1. 幅频特性|H (f )|在fc 附近是常数， 2. 相频特性?(f ) 过原点）。 ∠H (f ) = ?2πf τ0 + 2πfc τ0 + θ在fc 附近是直线（不要求其中θ是复系数a的相位。 对于频率为f 的信号来说，周期是1/f ，相移2π 就是延迟1/f 。如果线性系统 (f ) ?(f ) 1 的相位特性是?(f )，那么频率为f 的分量的延迟将是τ (f ) = ?2 π × f = 2πf 。 如果不同频率成分的延迟不一样，叠加后的波形自然就会有变化，出现失 真。为了无失真，必须所有频率分量有相同的延迟τ0 ，每个频率的相移就必须 是?2πf τ0 ，即过原点的直线。 如果?(f ) = ?0 是常数，那么每个频率分量的延迟都不一样，时域信号比然 有失真。比如说模拟基带信号m(t)的Hilbert变换m ? (t) 就是对所有频率分量移 相90? （对负频率是前移），结果和m(t)比，通常都是有失真的。 但如果是对带通信号的所有频率成分都经历一个固定相移?0 （负频率前 移），在等效基带模型中就是对(2)的系数a增加了一个因子e?j?0 ，它还满足无 失真条件。就是说，对带通系统，在复包络无失真的意义下，等效基带的相位 特性可以是?j 2πf τ0 再加上任意的常数相位?0 （对正负频率是同一个常数相 位，不是负频率反极性）也是可以的。也即，相频特性必须是直线，但不一定 非得过原点。比如说，将DSB信号s(t) = m(t) cos ωc t经过一个Hilbert变换期，2输出是s ?(t) = m(t) sin ωc t，s(t)和s ?(t)比当然有失真（波形不一样），但它们的 复包络m(t)和?jm(t)相比是无失真的。 如果已知带通系统相频特性为?(f )，那么复包络所经历的时延由直线部分 决定，与常数相位?0 无关，就是直线部分的斜率。因此时延可以写成 τG (f ) = d?(f ) 2πf (3)这个结果叫“群时延特性”（群指复包络），理想情况下它应该是与f 无关的 常数。实际系统的特性当然不会完全理想。可以用专门的仪器来测量幅频特性 和群时延特性，这样的仪表叫矢量网络分析仪。如果测量结果的幅频特性和群 时延特性都近似是常数，信道就是近似无失真的。33.1连续 时间 信道 ―多 径 衰落 信道平衰落与频率选择性衰落连续时间信道最简单的情形就是式(2)，即信道对信号的作用只是延迟和复数增 益。式(2)这个模型在频域看，H (f )是平的（与f 无关）。 对于无线信道，式(2)中的复数增益a一般来说是在随时间随机变化的，可以 写成a(t)。此时的情形可以理解成：在任何一个局部时间，信道在频域还是平 的，只是幅度增益和相移在不同的时间不一样。这样的信道叫平衰落信道。平 是指与f 无关，衰落是指随机时变性。引入时变性后，(2)可写成 r(t) = a(t)s(t ? τ0 ) 比(2)更复杂一些的线性时不变系统的输入输出关系是 r(t) = s(t ? τ )h(τ )dτ (5) (4)一般来说，此时信道传递函数H (f ) = F [h(τ )]是和f 有关系的，这种信道叫 “频率选择性信道”，与刚才说的“平”对应。如果信道还在随机时变，就是 有“频率选择性衰落”。 在无线信道中，平衰落和频率选择性衰落的成因都是多径传播。如果发送信 号的复包络是s(t)，则接收信号的复包络是 r(t) =iai (t)s(t ? τi )(6)如 果 各 径 时 延 的 差 别 很 小 ， 则r(t) ≈ s(t ? τ ?) i ai (t)， 和 式(4)一 样 （τ ?对 应τ0 ， i ai (t)对应a(t)），因此就是平衰落信道。如果各径时延的差别不能 忽略，那么(6)中的发送信号就不能从求和中提处理，此时若不考虑时变性就 和(5)一样，其中的冲激响应是h(τ ) = i ai δ (τ ? τi )。 总之，在局部时间看，信道是一个线性时不变系统，若它是无失真的（平坦 的幅频特性和群时延特性），就是平衰落。否则就是频率选择性衰落。3.2时延扩展与相干带宽无论是时变信道还是时不变信道，如果发送一个时域的冲激脉冲δ (t ? τ )，经由 多个路径传播，每个路径因为路径长度总归不完全相同，所以收端将观察到一 3串冲激。实际当中不可能存在宽度为0，无限高的冲激脉冲。它必定有一定的 宽度（脉冲宽度大致等于信号带宽的倒数）。这些有一定宽度的脉冲串前后叠 加，在接收端看来就是一个更宽的脉冲。发送的窄脉冲到收端宽度被扩宽了， 此现象叫时间弥散，或者叫时延扩展。 假设最先到达的脉冲延迟了τ1 (到达时间是t = τ + τ1 )，最后到达的延迟 了τmax ，那么脉冲将被展宽为τmax ? τ1 。如果以第一个脉冲的到达时刻为时间 原点（即令τ1 = 0），则展宽程度就是τmax 。 如果脉冲没有被展宽，接收端观察到的还是发送的脉冲，只是有一个时变的 复增益，这就是平衰落。如果脉冲被展宽，接收脉冲就不可能说成是发送脉冲 乘上了复增益，因此必然是频率选择性衰落。可见，时域的冲激响应如果有展 宽的现象，频域必然能观察到选择性。 如果信道存在频率选择性，通信系统设计时就必须要采取相应的应对措施， 例如均衡、多载波传输等。如果只是平衰落，采取这些措施是毫无意义的。设 计人员需要判断是否存在频率选择性。为此提出了“相干带宽”和“时延扩 展”这样两个数量指标以进行大致判断。相干带宽Bc 是这样一种概念，如果信 号带宽显著小于Bc ，就可以认为不会有频率选择性。从时域看，如果多发送 信号的脉冲宽度远大于时延扩展，脉冲被展宽的问题就可以忽略，因而也没有 频率选择性。根据时频域关系，时延扩展和相干带宽是倒数关系。对于这些量 的精确定义，文献中存在不同的版本。注意一点，这些量只具有数量级的意义 （我们比较的时候是看是否远大于或远小于），所以这些不同的定义没有实质 差别。3.3多普勒扩展与相干时间无论是平衰落信道还是频率选择性信道，如果发送一个频域冲激δ (f ? fc )（即 单频信号），那么收端在频域看到的是被展宽的脉冲。即发送信号带宽是0， 但接收信号有一定带宽，这种现象叫Doppler扩展（频率弥散，见图8.6.4）。 它是时变性造成的。时变是移动的结果（发射机、接收机或者环境中物体的 移动），移动意味着有Doppler频移。当电波从四面八方到达时，每个方向 v 的Doppler是不相同的（Doppler shift= λ cos θ），使接收端看到许多频率分量 同时存在。 与前相似，我们定义了两个数量“相干时间”和“多普勒扩展”来作为时变 性的判断。某些技术需要知道在它所关心的时间范围内，信道是否可以当作时 不变来对待。这些数量指标能提供一个大致的判断。多普勒扩展的数量定义为 v 最大的多普勒频移fD = λ ，相干时间Tc 定义为其倒数。实际上，移动速度v 决 定了信道随时间变化的程度，v 的大小决定着Doppler的大小。 总结：信道可能是时间选择性（时变信道）的或者频率选择性（频变信道） 的，或者兼而有之。沿f 的变化程度大致可用相干带宽Bc 反映，对应时域冲激 响应的展宽程度；沿t的变化程度大致可用相干时间Tc 反映，对应频域的多普勒 扩展。3.4Rayleigh fading and Rician fading对于平衰落信道，中心极限定律（Central Limit Theorem）表明式(4)中的时变 复增益a(t) = i ai (t)近似是一个复高斯过程，一般假设它是广义平稳的。于 是，作为复包络，a(t)代表的带通信号Re{a(t)ej 2πfc t }就是一个窄带平稳高斯过 程。根据课本57页的知识，其包络（复包络的模）服从瑞利分布。因此，这样 的信道称为瑞利信道，或者叫瑞利衰落信道。4实际上，仅从概率论的知识就可以知道这一点。若X = Xc + jXs 是复高斯 2 + X 2 服从瑞利分 随机变量，实部虚部均值为0，独立同分布，那么|X | = Xc s 布。 在某些环境中，到达手机的多径中某一径可能显著比其他径强。此时复增 益a(t)可以写成a(t) = K + i ai (t)，K 可以是复数，代表这个强径过来的信 号， i ai (t)是其余径的合成物。复包络中的K = ρej? 对应到带通信号是正弦 波Re{ρej? × ej 2πfc t } = ρ cos(2πfc t + ?)。根据课本58页(3.8节)，|a(t)|当服从莱 斯分布。这样的信道叫莱斯信道，或莱斯衰落信道。 瑞利或莱斯这些名称涉及的是随机过程a(t)的一维概率特性（一阶特性）。 无线信道中还存在其他的衰落分布。相同的传输技术在不同的衰落分布下其性 能表现会有很大差别，因此研究人员需要知道他所面对的信道是什么类型的分 布。4分集一般来说，衰落对无线通信是一个坏事情，因此必须要想办法对付它。方法很 多，其中之一是分集(diversity)。 分集的基本思想是：将相同的信息通过不同的“渠道”送达。这些渠道经历 独立的衰落，于是某个渠道被衰落破坏的时候，我们还有另一个。衰落独立是 必须的，否则，一个信道出问题的时候，另一个可能也会出问题。 制造出独立信道的方法很多，比如用多个天线来接收。如果天线间距足够 大，它们所经历的衰落就是近似独立的。这种方式叫空间分集。为了保证独 立，采用定向天线时，天线间距一般需要大于10倍波长。如果是全向天线（如 手机或者笔记本电脑），天线间距一般需大于半个波长。 也可以用不同的载波频率、不同的电磁波极化方式、不同的发送时间、或者 不同的天线指向来实现分集，分别叫做频率分集、极化分集、时间分集和角度 分集。 接收端收到多个信号后，有许多后处理的方式。其中之一是选择最好的一 个。假设有两个信道，每个信道当接收信号幅度在u0 之上时可正常通信。由 于衰落的原因，这两个信道瞬时接收的信号包络v1 , v2 是随机的。若每一个低 于u0 的概率是P (v1 & u0 ) = P (v2 & u0 ) = 10?3 ，那么分集系统不能正常通信的 概率是P (v1 & u0 , v2 & u0 ) = 10?3 × 10?3 = 10?6 ，显著低于单信道工作时的 概率10?3 。 从多个接收信号中选出最强信号这种策略叫“选择分集”，还存在性能比它 更好的策略（但也更复杂）。5通信原理II第五讲March 27, 20071信道容量对于信道X → Y ，如果转移概率P (Y |X )给定，这个信道就已经给定。我们关 心的是，通过这个信道最多可以传送多少信息。 发送X ，接收方观察到Y 。接收方依据Y 去猜测X ，所能猜出的程度是互信 息I (X ; Y ) = H (X ) ? H (X |Y ) = H (Y ) ? H (Y |X )。因此，给定信道时，接收端 所能获得的信息将不会超过I (X ; Y )。如果信道是理想的，I (X ; Y ) = H (X )， 收端依据Y 可以完全猜出X 是什么；如果信道不理想，则I (X ; Y ) & H (X )，表 明由于信道引入了一些不确定性，使得我们观察到Y 后，不能完全说出X 是什 么，但能猜出一些东西来（比如说出一个范围）。例如BPSK信道，发送1万个 二进制符号，总共有210000 种不同的可能性，如果信道的互信息是I (X ; Y ) = 0.5bits/symbol， 那 么 观 察 到1万 个Y 后 获 得 的 信 息 量 是5000bit。 每1bit信 息 能使我们排除一半的可能性。5000bit的信息将使我们能够把全部210000 种发 送序列(X1 , X2 , ? ? ? , X10000 )的可能结果划分成25000 个小范围，然后排除其中 的25000 ? 1个小范围，指出发送序列具体在哪一个小范围内，但不能进一步 说出是这个小范围内的具体哪一个。假如发送的时候并不是210000 种可能结 果都有机会发，而是挑出其中的M = 25000 个。所有发送向量必然是这M 个 中的一个。收端知道这M 个可能的发送向量都是些什么，只是不知道每次发 送的具体是哪个。那么依刚才的讨论，收端观察到一万个Y 后应该能够准确 地猜出发送的是M 个可能性中的哪一个。这种情况下就发端来说，发送的信 息量是log2 M = 5000bits，实际发送的符号数是1万个，平均每个符号携带 了0.5bit 的信息。把原始信息加载到信道符号序列{Xi }上的技术，以及从观察 结果{Yi }识别出发送内容的技术属于“信道编码”的范畴（第9章）。 上面这个例子显示出，能够通过信道传送的信息量是I (X ; Y )(bits/symbol)。 不过，“给定信道”（即给定P (Y |X )）这个条件并没有给定互信息I (X ; Y )， 它还与P (X )有关： I (X ; Y ) = H (Y ) ? H (Y |X ) = ?YP (Y ) ln P (Y ) +X,YP (X, Y ) ln P (Y |X )其中的P (Y, X ) = P (Y |X )P (X )，P (Y ) = X P (X, Y ) = X P (Y |X )P (X )， 可见I (X ; Y )的值还与信道符号X 的分布特性有关。既然我们关心的是“给定信 道时，最多能传多少”，那么这个量就应该是 C = max I (X ; Y )P (X )这个结果叫做“信道容量”或者仙农容量（Shannon Capacity）。12Binary symmetrical channel二元对称信道（BSC）的输入X ∈ {0, 1}，输出Y ∈ {0, 1}，信道转移概率具有 对称性P (Y = 1|X = 1) = P (Y = 0|X = 0)，P (Y = 1|X = 0) = P (Y = 0|X = 1) = ?，?就是这个二元信道的误比特率。根据作业，此信道的容量是 C = 1 ? h2 (?) = 1 + ? log2 ? + (1 ? ?) log2 (1 ? ?) bits/symbol 达到这个容量时，信道输入X 必须是等概的。3Gaussian channel高斯信道也叫做AWGN信道，其信道输出y 是信道输入x叠加了0均值的高斯噪 声z ：y = x + n (我们会混用大小写来表示随机变量，并无特别的意思，只 是习惯而已)。x和n相互独立。假设发送功率是S = E [x2 ]，信噪比是SNR = E [x2 ] S E [n2 ] = σ 2 。信道的转移概率是 p(y |x) = √ 1 2πσ 2 e?(y ?x)2 2σ 2若v 是连续随机变量，其熵定义为H (v ) = ?E [ln p(v )]，这个定义严格说叫“差 分熵”。因为连续随机变量真正的熵是无穷大：熵的定义是?E [log P ]，连 续随机变量的概率是P (v ) = p(v )dv ，而? ln P = ? ln p(v ) ? ln dv = ∞。但 为了使问题变得有意义，我们使用了定义H (v ) = ?E [ln p(v )]。dv 这个无限 小在计算互信息时将被约去：I (u; v ) = H (u) ? H (u|v ) = E [? ln p(u)du] ? E [? ln p(u|v )du] = E [? ln p(u)] ? E [?p(u|v )]。 高斯信道的互信息是I (x; y ) = E [√ ? ln p(y )]?E [? ln p (y |x)]。其中? ln p(y |x) = √ 1 n2 2 2 + 1 = ln 2πeσ 2 。 因 此I (x; y ) = ln 2 πσ + ， 其 数 学 期 望 是 ln 2 πσ 2 2 2 √ 2σ H (y ) + ln 2πeσ 2 。欲互信息最大，必须H (y )最大。y 是两个独立随机变量 的和，由于噪声的均值为0，所以y 的功率Sy 是x和n的功率之和：Sy = S + σ 2 。 有 办 法 证 明 ， 给 定 平 均 功 率E [v 2 ]时 ，0均 值 正 态 随 机 变 量 的 熵 最 大 。 因 此 使H (y )最大的y 必然是0均值的高斯随机变量，其熵为ln 2πe(S + σ 2 )。因此 信道容量（最大的互信息）是（转换为bit单位）： C = log2 2πe(S + σ 2 ) ? log2 √ 2πeσ 2 = 1 log2 (1 + SNR) bits/symbol (1) 2达到这个容量的信道输入也必然是0均值的高斯随机变量。4限 带的 AWGN信道对于连续时间的AWGN信道，信道输入是x(t)，输出是y (t) = x(t) + n(t)。如 果信道带宽是B ，那么噪声n(t)就是一个带限白噪声，其功率谱密度在?B ≤ 2 0 f ≤ B 范围内是常数 N 2 ，噪声总功率是σ = N0 B 。x(t)和y (t)也都是带宽限制 S 在|f | ≤ B 的随机过程。y (t)中的信噪比是SNR = σ 2。 给 定 带 宽 为B 时 ， 最 高 的 无ISI传 输 速 率 是Rs = 2B ， 码 元 间 隔 是Ts = t?kTs t?kTs 1 1 k xk sinc( Ts )。由于sinc( Ts )的 Rs = 2B 。发送信号可表示为x(t) = 能量是Ts ，且两两正交，故发送信号的每符号能量是Es = E [x2 k ]Ts ，又因 t 1 为Es = STs ，所以E [x2 ] = S 。接收端用匹配滤波器 h ( t ) = MF k Ts sinc( Ts )接 2收后，最佳采样时刻的输出是yk = xk + nk ，其中噪声分量nk 的均值为0， E [x2 N0 S 2 k] 方差是 2 Ts = N0 B = σ 。yk 中的信噪比是 E [n2 ] = σ 2 。根据前面的结果，S 信道xk → yk 的容量是 1 2 ln(1 + σ 2 )。就是说平均每个xk 可以携带的信息量 1 S 是 2 ln(1 + σ2 )，而每秒钟时间内可以传2B 个符号，于是每秒钟内可传输的 S 信息量就是2B × 1 2 ln(1 + σ 2 )，这就是著名的仙农公式：kC = B log2 (1 + SNR)bps(2)注意式(1)的单位是bits/symbol，式(2)的单位是bits/second。这两个单位 都可称之为“速率”。它们都是单位时间内的信息量，前者的单位时间 是symbol，后者是秒。5信道复用对于时间连续的信道，利用它同时传送多个用户的信号的技术属于信道复用。 考虑两个用户，在0 ≤ t & T 时间内用户1 和用户2各自需要传送一个符号， 分别是b1 和b2 （它们可能是有限状态的数字符号，也可能是模拟信号的采样 值）。若用户1发送信号b1 s1 (t)，用户2发送信号b2 s2 (t)，于是叠加后的信道输 入为x(t) = b1 s1 (t) + b2 s2 (t)。我们现在首要关心的是如何从混合信号x(t)中分 离出各自的信息，故暂且不考虑噪声。 s1 (t), s2 (t)是事先设计的，因此收端知道它是什么，收端不知道的只是b1 , b2 。 为了分离数据，一种方法是将收到的x(t)分别对s1 (t)和s2 (t)做相关：Tr1 r2T 0=0 Tx(t)s1 (t)dt = b1 E1 + b2 E12 x(t)s2 (t)dt = b2 E2 + b1 E210 T 0=其中E1 =T 0s2 1 (t)dt和E2 =s2 2 (t)dt分别是s1 (t)和s2 (t)的能量，E12 = E21 =RT s (t)s (t)dt1 2 0 √ 有关。 s1 (t)s2 (t)dt与两信号的相关系数ρ E1 E2 从r1 , r2 复原出b1 , b2 是一个求解线性方程组的问题。只要s1 (t)和s2 (t)线性不 相关（即排除s1 (t) = Ks2 (t)的情形，K 是任意常数），根据r1 , r2 就能唯一复 T 原出b1 , b2 。实际当中人们更为喜欢的设计是正交设计（ 0 s1 (t)s2 (t) = 0）， 它在性能、复杂度等方面都有好处。此时r1 = b1 E1 只和b1 有关，r2 = b2 E2 只 和b2 有关。 推广到任意N 个用户的情形就是：用任意N 个线性不相关的脉冲si (t), i = 1 ? ? ? N 作为各用户的成形脉冲，就可以让它们在同一信道上传输而保证收端可 以将其分离。线性不相关的意思是：任何一个si (t)都不是其他sj (t), j = i 的线 性组合。实际当中常用的是正交复用，即{si (t)}两两正交。 有无穷多种构造两两正交信号集的方法。最为常用的方法是：(1)频率正 交，FDM；(2)时间正交，TDM。此外还有码正交CDM（第十章讲）。3通信原理II第六讲April 3, 20071信道编码的概念相同的信息可以有不同的表达方式，在信源编码中，我们致力于寻求更为简洁 的表达方式，使编码后的数据率最小。信源编码的奥秘在于原始信源中的冗余 信息，这些信息可以从其他信息中获得，因此完全没有必要传它。 在信道编码中，我们致力于寻求最安全的表达方式，它能有效抵抗信道造成 误码。信道编码的原理也在于冗余信息。因为有冗余，所以当信道破坏了某个 比特的时候，我们可以指望借助其他比特上的冗余信息复原出被破坏的比特。 通信系统一般是先对原始信源进行信源编码以压缩冗余，再通过信道编码增 加冗余，然后通过信道传输。2分组码信道编码中最基本的概念是分组码。发送端把输入的数据流按k比特为一组进 行分组。对于每个分组，编码器改用另外n个比特来表达这个分组的数据内 容。经常的做法是，在这k个信息比特后面加上一些特别设计的比特，这些增 加的比特叫校验比特。编码器输出的这n个比特叫一个码字(codeword)。n比特 的码字经过二元对称信道（BSC）传输，接收到的n个比特中，有可能部分比 特出现错误。译码器利用编码规则来猜测原来发送的是什么，或者判断是否发 生了错误，以便采取相应措施（如后面要提到的ARQ技术）。Figure 1: 分组码k Fig.1所示的情形叫(n, k )分组码。称 n 为其编码率，编码率的单位是bits/symbol， 也可以说它没有单位。33.1简单的分组码重复码重 复 码 的 分 组 长 度 是k = 1， 编 码 器 把 这 个 比 特 重 复n遍 。 这 样 的 编 码 记 为(n, 1)重复码。编码率是1/n。例如：在(3,1)重复码中，发送信息1的码字 是111，发送信息0的码字是000。 1假设码长n是奇数，则当错误个数不超过一半时，接收端根据收到的n个 比特中多数是1还是0就能正确判断出发送的信息是什么。如果信道的误码率 n n i n?i 是p，那么这样译码后仍然错的概率是q = 。一般来 i= n+1 i p (1 ? p) 2 说q 要比p小得多，说明重复码可以显著提高传输的可靠性。3.2偶校验码偶校验码把k 比特分组uk?1 , uk?2 , ? ? ? , u0 编码为n = k + 1个比特。编码规则是 在k 个信息比特之后附加r = 1个“校验比特”p，形成码字uk?1 , uk?2 , ? ? ? , u0 , p。 这个校验比特p的取值由k 个信息比特决定，如果信息比特中1的个数是偶数 个，那么p = 1，否则p = 0。如果经过信道传输后，n个比特中发生了奇数个 错，则接收端一定可以知道发生了错误。 k?1 偶校验码的这个校验比特可以看成是用信息比特算出来的：p = i=0 ui ， 其中的求和是模二和。前面提到的重复码也可以理解成是k = 1个信息比特u后 面缀了r = n ? k 个校验比特形成码字(u, pr?1 , pr?2 , ? ? ? , p0 )。校验比特的计算 规则是pi = u, i = 0, 1, ? ? ? , r ? 1。 对于任意的分组码，一般情形是在k 个信息比特(uk?1 , uk?2 , ? ? ? , u0 )后面缀 了r = n ? k 个校验比特，形成码字 (cn?1 , cn?2 , ? ? ? , c0 ) = (uk?1 , uk?2 , ? ? ? , u0 , pr?1 , pr?2 , ? ? ? , p0 ) 校验比特是按某种规则，根据信息比特的内容计算出的。3.3汉明码汉明（Hamming）码的数据分组长度是k = 4。编码器对每个信息分组(u3 , u2 , u1 , u0 ) 添加了r = 3个校验比特(p2 , p1 , p0 )，使得Fig.2中每个圆内始终有偶数个1。发 送的码字是7比特的(u3 , u2 , u1 , u0 , p2 , p1 , p0 )。Figure 2: 汉明码图示 可以验证：如果接收到的7比特码字中有1比特出错，则可以根据编码规则 猜出错在哪里。但如果错误数多于1个，则译码后一定会有至少3比特错误。 即：译码器所以为的发送的码字和真正发送的码字之间至少有3处不一样。 4 上述Hamming码是一个编码率为 7 的(7, 4)分组码。它是Hamming码家族中的一 员。4随机错与突发错如果传输的一个码字中，每个位置上出错的机会是统计独立的，这种错误类 2型叫独立随机错，简称随机错。如果传输的一个码字中，错误只出现在连续 的L个位置上(未必个个都错)，其它地方不出错（或者出错的机会非常小），这 种错叫突发错。注意突发错只表示错误集中在一个范围内，不表示这L个比特 都错。若无特别说明，我们缺省假设错误类型是随机错。 一个接收码字中具体哪个位置对、哪个位置错的描述叫错误图案。Fig.3中 的两种描述都表示在一个7比特的码字发生了2比特错，错误位置是第5和第3比 特。注意右起第1位编为第 √ 0比特，不过如何编号（左起或右起，0起或1起）无 关紧要。Fig.3(a)中用 表示对，用×表示错，Fig.3(b)中用0表示对，用1表示 错。我们将采用Fig.3(b)中的方法来表示错误图案，此时错误图样是一个7比特 的向量e = (0101000)。Figure 3: 错误图案5汉明距及汉明重量一个n长的二进制向量就是一个码字。任意两个码字c1 , c2 之间的码距dH (c1 , c2 )是 两者不相同的位置的个数，此处的下标H 表示是汉明距离。 码字c的码重WH (c)是c中1的个数。下标H 表示它是汉明重量。码字和码重 之间的关系是d(c1 , c2 ) = W (c1 + c2 )，其中+表示逐比特模二加。 对于给定的编码，编码器的输出虽然长为n，但它只有2k 种不同的输出，称 这些输出是此编码的合法码字（许用码字）。任意两个合法码字之间有一个汉 明距离，所有合法码字之间最小的距离称为此码的最小码距，记为dmin (请对 照调制星座图中的dmin )。 对于任意的(n, k )分组码，如果n = k （即没有冗余），则最小码距是1；如 果有一个校验位（n ? k = 1），dmin 可以达到2，如偶校验码。每增加一个校 验比特，dmin 最多增加1。因此(n, k )分组码的最小码距绝不可能超过n ? k +1。 和调制星座的dmin 一样，分组码的最小码距也直接关系到码的性能。因此，如 何设计出dmin 最大的码便是一个重要的问题。66.1差错控制方式FECFEC（Forward Error Correction）就是前向纠错。前向是指发送端到接收端这 个方向。发送端把k 长的信息比特向量u编成一个n长的码字向量c，到接收端成 为n长的向量x，接收端根据x推测发送的c或u是什么。 FEC的设计强调纠错能力。假设n长的码字发生了m个比特错误，采用不同 的设计时，有些能够纠正这些错误，有些就不能。“纠错能力”可以体现为 保证可纠的最大错误数：在n长的码字中，如果错误个数m ≤ t的所有错误图 样都可以纠正，则t就能说明这种FEC编码的能力怎么样。比如对于(7, 1)重复 3码，t = 3。对于(7, 4)汉明码，t = 1；对于(7, 6)偶校验码，t = 0。一般来说， k 纠错能力t和编码效率 n 是相互矛盾的指标。 一个二进制的(n, k )线性分组码总共有2k 个可能的码字(合法码字)：C = {c0 c1 , ? ? ? , c2k ?1 }。其中任意两个之间都有距离dH (ci , cj )。最大似然（ML） 译码将把接收的码字x译为C 中的离它最近的那个合法码字。因此，在ML译 码准则下，如果某个分组码的纠错能力是t，那么发送某个ci ∈ C ，错误可能 使收到的码字x离开ci 有t远。纠错能力是t说明x将被译为原发的ci ，说明?j = i, dH (x, ci ) & dH (x, cj )。因此C 中任意两个不同码字的距离至少是2t + 1。这 就是说，如果要求一个FEC编码具有纠t个错的能力，必须要求dmin ≥ 2t + 1。6.2ARQARQ（Automatic ReQuest）的意思是收端发现错误后，要求发端重新发送。ARQ对 编码的要求是：能使收端知道，它接收的码字中是否存在错误。偶校验码是一 种简单的检错码。常用的检错编码是CRC（后面要讲）。检错的原理很简单： 如果接收端发现接收码字x并不是一个合法码字，即x ∈ / C ，就知道x中一定有 错。 如果C 的最小码距是dmin ，那么当x中存在m ≤ e = dmin ? 1个错时，这 样的错误一定能被发现。不过这样判断检错能力过分保守。比如对于偶校验 码，dmin = 2，故此它能发现所有单比特错。不过，偶校验码可检出的错误 类型远不止这些。例如(8, 7)偶校验码，它能检出所有奇数错的错误图样，共 8 8 8 有 8 1 + 3 + 5 + 7 = 128种，其中单比特错误图样有8种。 由于只需要判断是否有错，不需要判断哪个比特错（以进行纠正）， 因此用于ARQ目的的编码（如CRC）一般都很简单。和目前常用的FEC， 如Turbo码、LDPC码相比，其复杂度完全可以忽略不计。不过ARQ系统需要 有一个后向（也叫反向，与前向相对）的信道来告诉发送端刚才的发送是否成 功。这是FEC系统不需要的。6.3HARQHybrid ARQ是FEC与ARQ二者的结合。其思想是，发送一个编码，收端先进 行FEC译码，如果能译对（靠CRC或者其他方法判断），就OK，否则请求重 传。 与纯FEC相比，它可以应付超过FEC纠错能力的误码；与纯ARQ比，它可 以降低重传的频度。大量重传毕竟不是一件好事，起码它要占用反向信道的资 源（速率、功率等）。7信道编码定理对于BSC信道，如果信道误比特率是?，那么信道容量是ρ = 1 + h2 (?) = 1 + ? log2 (?)+(1??) log2 (1??)bits/symbol。信道编码定理指出，对于(n, k )编码， k 若其编码率 n ≤ ρ，那么一定存在某一种具体的编码方法，使得收端在ML译 码（即译为离接收结果最近的合法码字）之后的误比特率能随n → ∞而趋 于0。Shannon之所以敢这么说，不是因为他发现了某个具体的编码具有如此优 异的性能。而是他证明了：所有可能的编码的平均性能就这么好，因此至少有 一个性能很好。 信道编码定理所考虑的信道不限于BSC信道。不过作为初学，本章主要考 虑BSC信道中的编码问题。4通信原理II第七讲April 10, 200711.1Preliminaries关于位置编号的约定位置编号是一个容易让初学者感到混乱的问题。 编码器的输出是n个比特，比如(1000111)。对于不同的输入信息，编码结果 也不同。为了分析研究，我们自然会想到用代数的方法，引入变量符号来记述 这7个比特值，比如(u, v, w, a, b, c, x)。也可以用一个单字母符号配上不同的下 标：(ba , bb , bu , bx , by , bw , bz )。用数字做下标当然更为便利，此时也有许多标记 方法，如：(b1 , b2 , ? ? ? , b7 ), (b6 , b5 , ? ? ? , b0 ), (b7 , b6 , ? ? ? , b1 ) 等等。由于这些下标 仅仅是一个label，所以写成(b3 , b2 , b1 , b6 , b4 , b5 , b0 ) 也无不可。 总之，如何对比特位置进行编号只是我们自己如何描述它的问题，与被研究 的问题无关。任何人都可以按照自己的偏好来标记。不同的文献对此也没有共 识。本课约定，在线性分组码中，默认的编号规则是从左到右对应位置编号从 大到小，最右的那个比特编为0。这种规则也就是MSB(Most Sigmi?cant Bit， 最高有效位)在左。如果你更习惯其他编号的话，也完全可以。不过在考试中， 如果不使用默认编号的话，必须加以注明，以避免误解。 实际当中，这n个比特发送的时间次序有可能是从左到右、从右到左或者其 他。如果信道没有差异的话，任何次序都是无关紧要的。1.2Galois Field我们日常所用的加减乘除都是二元运算的一个特例，也即二元函数。对于集 合?，如果任取两个元素a, b ∈ ?，将(a, b)对应到某个c ∈ ?，即c = f (a, b)， 就是定义了一种二元运算。我们可以随意设计一个记号来标记这种运算，比 如a b = c，也可以给它起一个名字，比如叫“*法”。我们平常所用的算术 中，1 + 2 = 3是把(1, 2)对应给了3，+是我们为了标记这个二元运算所设计的符 号，我们还将其名之为“加法”。 实数以及加减乘除这些算术规则构成了我们非常熟悉的算术系统。对于任 意集合?，同样也可以建立一个算术系统，只须定义出相应的二元运算规则即 可。 设有集合?，在这个范围内定义了oA ，oB 这样两种二元运算。不妨将其命 名为“加法”和“乘法”，并分别使用记号+和×，约定a × b可以简写成ab。 这样做不光是为了复用这些符号和术语（以降低记号成本），更因为我们所熟 悉的算术只是一个特例。 对于集合?中的元素，可以采用任何一种自认为方便的方式来标记，比 如a, b, ? ? ? 。如果?是有限的，或者可数的，也可以用ωi 这样的方式来标记其元 素，其中i是整数。当然也可以直接用整数来标记，即3这个符号代表?中的某 一个元素，4则是另一个符号。如同用学号来标记学生。这里的3,4都只是些符 1号，除非对运算、排序等进行了定义，否则它们不具有我们平常所说的“数” 的意义。 根据本课的需要，我们需要简要学习一种叫做域（?eld）的数学系统，它有 如下规则（其中的某些规则可以用其它规则导出） 1. 存在唯一一个特定的元素a ∈ ?，使得对于任何b ∈ ?，有a + b = b。我们 用“0”这个符号来标记这个特殊的元素。 2. 存在唯一一个特定的元素x ∈ ?，使得对于任何b ∈ ?，有x × b = b。我们 用“1”这个符号来标记这个特殊的元素。 3. 对于任意的a ∈ ?，存在唯一一个元素b ∈ ?，使得a + b = 0，称此b为a的 负数。如果必要的话，我们用记号?a来表示它。 4. 对于任意的a ∈ ?，存在唯一一个元素c ∈ ?，使得a + c = 0，称此c为a的 逆。如果必要的话，我们用记号a?1 来表示它。 5. 所定义的加法和乘法满足交换律：即对于a, b ∈ ?，a + b = b + a，ab = ba； 6. 所定义的加法和乘法满足结合律：即对于a, b, c ∈ ?，(a + b) + c = a + (b + c)，(ab)c = a(bc)； 7. 所定义的乘法对加法有分布律：即对于a, b, c ∈ ?，(a + b)c = ac + bc； 若?是实数R，那么我们日常使用的加减乘除四则运算构成了实数域。如 果?只有有限个元素，即|?| = q & ∞，这样的域就是伽罗华域，记为GF(q )。 对于GF(2)，? = 0, 1，加法定义为逻辑异或，乘法定义为逻辑与。1.3线性代数N 长实数向量x = (x1 , x2 , ? ? ? , xN )的每个元素都属于实数集合R。x属于实数的 扩展域RN 。两个向量的加法是逐元素相加。向量x ∈ RN 和标量α ∈ R的乘积 定义为x的每个元素乘以α：αx = (αx1 , αx2 , ? ? ? , αxN )。两个向量x1 , x2 的线 性组合是α1 x1 + α2 x2 ，其中α1 , α2 ∈ R。 现在考虑n长的二进制向量b = bn?1 , bn?2 , ? ? ? , b0 ，其元素属于GF(2)，b属 于扩展二元域GF(2n )。标量a ∈GF(2)和向量b ∈ GF(2n )的积定义为b的每个 元素都乘上a：若a = 0, 则ab = (0, 0, ? ? ? , 0)，若a = 1，则ab = b。两个向 量b1 , b2 的线性组合是a1 b1 + a2 b2 ，其中a1 , a2 ∈ GF(2)。 将k 个向量g1 , g2 , ? ? ? , gk ∈ GF(2n )做线性组合，得到向量c = uk?1 g1 + uk?2 g2 + ? ? ? + u0 gN 。对于不同的组合系数uk?1 , uk?2 , ? ? ? , u0 ，组合结果有 可能不同。将所有可能的组合结果装入一个集合C ，则C ? GF(2n )。称C 是 由g1 , g2 , ? ? ? , gk 张成的，称g1 , g2 , ? ? ? , gk 是C 的一组基。C 至多有2k 个元素， 且必然包括全零向量(0, 0, ? ? ? , 0)。如果g1 , g2 , ? ? ? , gk ∈ GF(2n )线性不相关， 则C 中的元素个数是2k 个。线性不相关的意思是说，g1 , g2 , ? ? ? , gk 中的任何一 个都不可能是其他向量的线性组合。对于我们所考虑的二进制情形，两个向量 线性不相关=两个向量不相同，k 个向量线性不相关=任何一个都不是其它若干 个的和。22线性分组码分组码的编码器的输入是k 个比特u = (uk?1 , uk?2 , ? ? ? , u0 )，输出是n个比特c = (cn?1 , cn?2 , ? ? ? , c0 )。从数学角度看，编码器的功能就是一个函数c = f (u)。 如果这个函数是线性函数，这样的编码器就是“线性分组码”的编码器。所 谓线性函数是指，对于任意的u1 , u2 ，总有f (u1 + u2 ) = f (u1 ) + f (u2 )，即和 的编码结果等于编码结果之和。也可以等价地说成是“c中的任何一个比特都 是(uk?1 , uk?2 , ? ? ? , u0 )中某些比特之和”，或者“c是u的线性变换”。因此， 编码关系可以写成矩阵形式： c = uG (1) 其中的G是一个k × n的矩阵，其元素属于GF(2)。给定G便给定了函数f ，便给 定了编码器。此矩阵称作该编码器的“生成矩阵”：c是通过G 产生的。 记G的k 个行为向量g1 , g2 , ? ? ? , gk ，那么(1)可以写成c = uk?1 g1 + uk?2 g2 + ? ? ? + u0 gk ，即c是G的某些行的和。比如，对于(7,4)线性分组码，G有4行，每 行是一个长为7的行向量，信息u = (1100)的编码结果是G的第一行和第二行之 和。 对于正常的编码，G的各行是线性不相关的，这一点保证不同的信息分 组u的编码结果不同。由于u 有2k 种不同，因此c也有2k 种不同，其中包括n长 的全零向量0 = (0, 0, ? ? ? , 0)G。记C 为所有c的集合，则C 是G的行所张成的线 性空间。很明显G的各行一定在C 中。 从C 中任意选出k 个线性不相关，都可以张成C ，因此，用C 中任意k 个线性 不相关的行作为编码器的生成矩阵，编码结果的集合都是相同的（但信息到码 字的对应关系不同）。若不同编码器所生成的码字集合相同，就说它们是等价 的。由于序号的编号次序并不重要，因此若两个编码器的结果的差别只是次序 交换的话，它们也是等价的。 可对照第6章信号星座的概念来理解：8PSK有8个点，每个点对应3个比 特。无论比特和点之间怎么对应（比如格雷映射或者自然映射），它们都 是8PSK，其符号错误率是一样的。在线性分组码中，如果集合C 相同，译码后 码字的错误率就是相同的。 如果原始信息u能够原样出现在c中，这样的编码叫“系统码”，直接出现 在c中原始信息位叫“系统位”，其余叫“校验位”。由于次序并不重要， 所以我们默认假设系统码的系统位出现在左边（高位）。即编码结果一定可 以写成(u, p)的形式，其中p = (pr?1 , pr?2 , ? ? ? , p0 )是校验位，校验比特的个数 是r = n ? k 。从uG = (u, p)可知，系统码的G一定具有(I, Q)的形式，其中I 是 单位阵。 任意给定一个G，如果它不是系统码的生成矩阵，一般可以通过初等行变换 将其变换为系统码形式，如果这样不行的话，再配合列交换总是可以的。具体 操作的示例见课本391页。如果是只通过初等行变换得到的，那么结果是唯一 的。 线性分组码编码器的实现是一个矩阵乘法，见课本395页的图9.2.1和图9.2.2。 线性分组码的最小码距是非全零码字中最小的码重。对于任意的(n,k)分组 码，得到dmin 需要对所有2k 个码字进行两两比较，需要比较(2k ? 1)!次。对于 线性分组码，只需要判断2k ? 1个非全零码字的码重就能得知dmin 。3通信原理II第八讲April 17, 20071编码问题线 性 分 组 码 是 分 组 码 的 一 种 。 就 一 般 来 说 ， 任 何 一 种 将k 比 特 信 息u映 射 到n比特码字c 的做法就是一种编码设计，比如将00、01、10、11 分别映射 到 、0100 、1001 就构成了一种(4,2)分组码。 对于任意的(n,k)分组码，实现编码器的一种通用方法是查表法：用一个存 储器存储所有2k 个码字，设计地址线宽是k bit，数据线宽是nbit。然后用u作为 地址线来读存储器。这种方法需要的存储量随k 指数增长，是2k × nbit。 采用线性分组码时，编码器是向量和矩阵相乘：c = uG。特别对于系统 码，c = (u, p) = u(I, Q)，只需要实现矩阵乘法uQ。实现这样的乘法需要的是 一些异或门，门数不超过k (n ? k )个，硬件复杂度大大低于查表法。2译码发送某个码字c = (cn?1 , cn?2 , ? ? ? , c0 ) ∈ C ，经过BSC信道后成为y。信道可能 会使c中的某些比特出错。如果某个比特发生错误，相当于这个比特加上了1。 因此信道输出可以写成 y=c+e (1)其中的e = (en?1 , en?2 , ? ? ? , e0 )是错误图样。如果ei = 1就表示ci 发生了错误。 接收端看到的是y，它想知道的是c。因为接收端不知道e，所以发送的是什 么没有确定的答案。在收端看来，最可能的发送码字是C 中离y最近的码字。 因此译码器的通用设计可以是：把全部码字C 存储在一个存储器中，用y逐个 和C 中的码字进行比较，每次比较包括的操作是：从C 中读出一个码字，与y 异 或，数出异或结果中1的个数（汉明重量）。通过这些比较找出最近的那个码字 作为判决结果。这就是ML译码。 对于线性分组码，我们也可以避免这种通用的方法，同时等达到相同的效 果。能做到这一点的关键是因为线性分组码的码字一定满足 H cT = 0 1 (2)其中0是一个长为r = n ? k 的全零列向量，H 是一个r × n的矩阵，称为监督矩 阵或者校验矩阵（parity check matrix）。 式(2)能够成立的原因是这样的。对于任意的线性分组码，我们总能把它 转换成系统码的形式。故此不妨考虑系统码，c = (u, p)，G = (I, Q)，因 此p = uQ。对于GF(2)上的运算，若a = b则a + b = 0，因此uQ + p = 0，写成 Q 矩阵形式就是(u, p) = 0，转置后就是(QT , I )cT = 0，即(2)。 I 由于G的各行线性无关，所以方阵Q是满秩的，所以H 的各行线性无关。 接收端已知H ，用接收到的y去乘H 能得到一个长为r = n ? k 的向量s = yH T ，这个向量叫伴随式(syndrome)。根据式(1)和式(2)可得 H eT = sT (3)说明信道中发生的错误图样是线性方程组(3)的解，只要解出这个线性方程组， 就知道了e，再与y相加，结果就是(c) + e + e = c。不过，式(3)有r = n ? k 个 方程，而e有n个变量，因此方程组(3)有多解。任意给定e中的k 个比特，就能得 到一个解，这样我们将得到2k 种可能的错误图样。接收端不可能知道真正发生 的错误是哪一个，只能猜。如果猜错也没办法。根据ML检测的精神，应该猜 码重最小的解（即错误个数最少者）。 实际的译码电路实现时，倒不需要每收到一个y，就忙着去解方程组(3)， 再选择码重最小的错误图样。这个过程可以事先做，把结果存起来用就行了。 比如(7,4)码，伴随式s = (s2 s1 s0 )有3个比特，共8种。事先对于每一种s，解方 程组(3)，再选出码重最小的（如果最小的有多个，就随便选一个），称这个 为“可纠正错误图样”（意思是：如果信道中实际发生的错误图样确实是它的 话，就搞定了。否则只好译错）。然后把每个s纪录下来。电路实现的构成包括 三部分：(1)计算s，这是一个矩阵乘法；(2)查表，即用s为输入，输出相应的可 ?相加 纠正错误图样，一般可化为适当的逻辑电路；(3)将y与所认为的错误图样e ?。图9.2.4是一个例子。 得到译码结果c3H两个向量的内积为零称为正交。比如a = (01100)和b=(01111)的内积是abT = 0 × 0 + 1 × 1 + 1 × 1 + 0 × 1 + 0 × 1 = 0，故此它们是正交的。式(2)表明H 的每 一行都和C 中的任何一个码字正交。 将H 进行初等行变换得到H ，那么H 的任何一行是H 的行的线性组合，因 此任何一个c ∈ C 也必然和H 正交，即方程组(2)可以改写成H cT = 0。表明给 定G时（即给定了C ），校验矩阵并不唯一。即便给定的G是系统码的生成矩 阵，H 也同样不唯一。不过，如果要求H 具有“典型形式”H = (P, I )，则结果 是唯一的。2H 有k = n ? k 行，各行线性无关，因此它也符合成为生成矩阵的条件。 若以G = H 为生成矩阵，将得到一个(n, k )线性分组码，称为原码的对偶码。 若C 是对偶码的码字集合，则?c ∈ C , c ∈ C ，有c cT = 0。即对偶码和原码正 交。 注意到H cT 的结果是H 的某些列之和，这些列的位置对应c中1的位置。 若c的 码 重 是d， 则 标 明H 一 定 有d列 ， 其 和 为0， 即H 一 定 有d列 是 线 性 相 关 的。若c = 0，则其码重最小是dmin ，因此H 的任意dmin ? 1列必然是线性无 关的。利用这个特性，可以根据H 来求解码的最小码距。如果我们发现H 的 任何d列线性无关，则dmin ≥ d + 1。对于式(9.2.12)给出的H ，任何两列都 不相同，因此dmin ≥ 2 + 1 = 3。再注意到任何1列都不可能是其它两列之 和，因此dmin ≥ 4。再注意到左起第1列是第4、5、6列之和，因此得知该码 的dmin = 4，它可保证纠1位错。如果发生2位错，有些或许能纠，但不保证能 纠所有2位错。4汉明码不论是否线性，任意(n, k )码的码字集合C 都是在2n 个n长的向量中挑出了2k 个。 假设这个码能保证纠t个错，那么C 中任何两个码字之间的距离至少是2t + 1。如 果以任意一个c ∈ C 为球心做一个球，让它囊括GF(2n )中所有距离c不超过t的 向量，那么这个球内的点数是V =t i=0 i 。对C 中的所有码字都做这样的 Cn球，那么它们必然不相交。这些球大小相同，它们所包括的总点数是2k V ，这 个数值必然不会超过2n ，因此有如下不等式t i Cn ≤ 2n?k i=0(4)给定n, k ，若tmax 是满足上述不等式的最大t值，则表明我们不可能设计出一个 二进制分组码，它的纠错能力竟然比tmax 还大。这个上界叫Hamming界。 能使(4)等式成立的码叫完备码。能在t = 1的条件下等式成立的就是汉明 码。此时1 + n = 2n?k 。若校验位个数是r = n ? k ，则码长是n = 2r ? 1，信息 位个数是k = n ? r = 2r ? 1 ? r。最小码距是dmin = 2t + 1 = 3。因此其H 的任 意两列线性无关（即任意两列不相同）。Hamming码的校验矩阵很容易写出： 将r个比特的所有可能结果写出，除去全零的一个，把剩下的作为H 的各个列即 可。 顺便指出：我们把生成矩阵写成G是因为Generator，把校验矩阵写成H 是 因为Hamming。3通信原理II第九讲April 24, 2007我们所说的循环码是：循环+线性。首先它是线性分组码，任何两个合法码 字之和还是合法码字；其次，任何一个码字的循环移位也是码字。因此循环码 是线性分组码的一个子集。 在线性分组码中，我们用向量来描述码字，使得可以用线性代数的数学工具 来研究它。对于循环码，还可以用多项式这样的数学工具。1多项式可以把一个码字用多项式来描述：例如1101可以描述为x3 + x2 + 1，0101则 是x2 + 1。长为n的码字将对应一个次数不超过n ? 1的多项式：n?1c(x) = cn?1 xn?1 + cn?2 xn?2 + ? ? ? + c1 x + c0 =i=0ci xi(1)约定码字向量c = (cn?1 , cn?2 , ? ? ? , c0 )中从左到右的比特对应多项式中次数从 高到低的项。当然这只是约定的一种，有些研究人员更喜欢相反的次序，比如 将1101表达为1 + x + x3 。 式(1)中多项式的系数取值于GF(2)，称这个多项式是系数在GF(2)上的多项 式。类比我们以前所学的多项式知识：如果多项式的系数规定只能是整数，就 叫整系数多项式，如2x4 + x ? 1；如果系数只能是实数，就叫实系数多项式， 如3x4 +2 3 √ x 5+ 1。两个多项式相加是系数相加，因此x3 + x2 + 1加x4 + 1得x4 + x3 + x2 ，对 应=11100。 两个多项式相乘也如我们熟悉的多项式乘法，只不过系数运算是在GF(2)上。 例如 (x3 + x + 1)(x + 1) = (x3 + x + 1)x + (x3 + x + 1)= x4 + x2 + x + x3 + x + 1 = x4 + x3 + x2 + 1 1Figure 1: 竖式乘法 手算时，可以按竖式乘法来做，如Fig.1所示。 若有多项式a(x), b(x)，其次数分别为n, m，且m & n。根据带余除法定理， a(x) = q (x)b(x) + r(x) (2)其中q (x)是用b(x)去除a(x)得到的商，r(x)是余。q (x)的次数是n ? m，r(x)的 次数小于m。例如6次多项式x6 + x3 除以3次多项式x3 + x + 1得商x3 + x，得 余x2 + x。这样的计算过程可按Fig.2所示的竖式除法进行。Figure 2: 竖式除法 对多项式a(x)模b(x)的结果就是将a(x)除以b(x)所得的余式，记为[a(x)]k mod b(x)=r(x)。特别地，a(x)模x 的结果就是截去a(x)中次数大于等于k 的项。例如f (x) = x6 + x3 + 1模x4 的结果是x3 + 1，f (x)模x3 的结果是1。 对于任意的多项式a(x)、b(x)及p(x)，有如下关系（课本402页） b(x) a(x)mod p(x) mod p(x)= [a(x)b(x)]mod p(x)(3)这 是 因 为 ， 将a(x)除 以p(x)， 若 商 为q (x)， 余 为r(x)， 则a(x) = q (x)p(x) + r(x)。于是(3)左边是{b(x)r(x)} {b(x)r(x)}mod p(x) ，右边是{b(x)q (x)p(x)+b(x)r (x)} mod p(x)=mod p(x) ，两边相等。设n比 特 长 的 码 字c对 应 的 多 项 式 为c(x) = cn?1 xn?1 + cn?2 cn?2 + ? ? ? + c0 。xc(x)就是将其左移一位，[xc(x)]mod xn 就是舍去移出的比特。例如c=(1000101)2的多项式表示是c(x) = x6 + x2 + 1，xc(x) = x7 + x3 + x代表，是c左 移一位，右边补0。xc(x) 比特。 再来考虑[xc(x)] xc(x)mod (xn +1) ，由于 mod x6= x2 + 1代表0001010，是c左移后舍去移出的= cn?1 xn + cn?2 xn?1 + ? ? ? + c1 x2 + c0 x = cn?1 xn + cn?1 + cn?1 + cn?2 xn?1 + ? ? ? + c1 x2 + c0 x = cn?1 (xn + 1) + (cn?2 xn?1 + ? ? ? + c1 x2 + c0 x + cn?1 )故此， [xc(