第4章数据链路控制改

1、第第4章章 数据链路控制数据链路控制1n4.0 分组与帧分组与帧n4.1 流控技术流控技术n4.3 差错控制差错控制n4.4 高级数据链路控制高级数据链路控制n4.2 差错检测差错检测4.0 分组分组 (Packet) 与帧与帧 (Frame)21. 什么是分组什么是分组?数据不能以任意长度的比特串连续传输，数据不能以任意长度的比特串连续传输，而必须分割成小的数据块并分开传输。这些而必须分割成小的数据块并分开传输。这些数据块被称为数据块被称为分组分组。可以处理分组的网络被。可以处理分组的网络被称为称为分组网分组网。2. 为什么需要分组为什么需要分组?3n可以在发送方和接收方之间实现协调以保证数

2、可以在发送方和接收方之间实现协调以保证数据能够正确到达目的地；据能够正确到达目的地；n可以保证网络中所有的计算机可以公平地共享可以保证网络中所有的计算机可以公平地共享底层的硬件。底层的硬件。4典型地，一个分组的长度为典型地，一个分组的长度为 65536 bytes。但是一帧的长度是各种各样的：但是一帧的长度是各种各样的：n以太网以太网:n令牌环令牌环:n令牌总线令牌总线:nFDDI:nATM:641518 bytesno limitation= 8191 bytes=4500 bytes53 bytes3. 分组和硬件帧分组和硬件帧5问：如何在指定的硬件设备上传输分组问：如何在指定的硬件设备上

3、传输分组?答：每种硬件都定义自己的帧格式，在硬件上传答：每种硬件都定义自己的帧格式，在硬件上传输的分组必须封装成正确的帧才能被硬件识输的分组必须封装成正确的帧才能被硬件识别。别。帧格式举例帧格式举例3. 分组和硬件帧分组和硬件帧4.1 流控技术流控技术4.1.1 停止停止-等待流控等待流控6捎带式捎带式控制控制特殊帧特殊帧控制控制4.1.2 滑动窗口流控滑动窗口流控7 窗口是连续帧的一个子集；窗口是连续帧的一个子集； 在发送方，只有落入发送窗口中的帧才可以在在发送方，只有落入发送窗口中的帧才可以在没有收到没有收到ACK的情况下直接被发送；的情况下直接被发送； 对于接收方，只有落入接收窗口中的帧

4、才能被对于接收方，只有落入接收窗口中的帧才能被接收；接收； 窗口可以沿着连续帧一步一步向前滑动。窗口可以沿着连续帧一步一步向前滑动。窗口窗口 (Window) 的概念：的概念：窗口是如何工作的窗口是如何工作的?8发送窗口发送窗口 (SW)大小大小 = 4接收窗口接收窗口 (RW)大小大小 = 1t1023456ACK011t206ACK123451t203456ACK124.3 差错控制差错控制4.3.1 停止停止-等待等待ARQ协议协议9假设假设:1. 没有错误发生；没有错误发生；2. 接收方具有接收方具有无限无限的的接收和处理帧接收和处理帧的能力。的能力。1. 非受限情况非受限情况4.3.

5、1 停止停止-等待等待ARQ协议协议10假设假设:1. 没有错误发生；没有错误发生；2. 接收方只有接收方只有有限有限的的接受和处理帧接受和处理帧的能力。的能力。2. 简单停止等待简单停止等待4.3.1 停止停止-等待等待ARQ协议协议11去掉所有假设去掉所有假设ARQ: Automatic Repeat reQuest3. 实际的停止等待实际的停止等待4.3.2 Go-Back-N ARQ12Sending Window = 4, Receiving Window = 113Go-Back-N ARQ步骤步骤1. 发送方发送发送方发送03号帧，但号帧，但2号帧在途中丢失；号帧在途中丢失； (

6、SW=0 3，RW=0)2. 接收方接收接收方接收0号帧，并发出号帧，并发出ACK0；(RW=1)3. 发送方接收发送方接收ACK0，并发出，并发出4号帧；号帧；(SW=1 4)4. 接收方接收接收方接收1号帧，并发出号帧，并发出ACK1； (RW=2)5. 发送方接收发送方接收ACK1，并发出，并发出5号帧；号帧； (SW=2 5)6. 接收方接收接收方接收35号帧，都丢弃；号帧，都丢弃； (RW=2)7. 发送方一段时间后未收到发送方一段时间后未收到ACK2，则认为该帧丢失，于，则认为该帧丢失，于是重发是重发25号帧；号帧；8. 接收方顺序接收接收方顺序接收25号帧，并送出号帧，并送出AC

7、K2ACK5。14 数据帧和应答帧都有编号；数据帧和应答帧都有编号； 接收端总是期望按帧的编号顺序接收帧，若收接收端总是期望按帧的编号顺序接收帧，若收到失序帧，则丢弃；到失序帧，则丢弃； 发送方将窗口中的所有帧缓存起来，以备重发，发送方将窗口中的所有帧缓存起来，以备重发，若得到确认，则可以删除；若得到确认，则可以删除； 发送方若在一定时间内未收到发送方若在一定时间内未收到ACK，则认为，则认为帧丢失，帧丢失，发方将重发该时间内发送过的所有帧发方将重发该时间内发送过的所有帧。Go-Back-N ARQ的特点的特点3. 窗口大小可以是任意值吗窗口大小可以是任意值吗?15 如果窗口很大，则已发送但未

8、被确认的帧就会如果窗口很大，则已发送但未被确认的帧就会很多；如果有错误发生，则需要重传窗口内的很多；如果有错误发生，则需要重传窗口内的所有帧，这增加了网络的发送成本。所有帧，这增加了网络的发送成本。 窗口是连续帧的一个子集，窗口内的帧都需要窗口是连续帧的一个子集，窗口内的帧都需要编号，如果窗口很大，将会需要更多的比特来编号，如果窗口很大，将会需要更多的比特来为帧进行编号，这也增加了通信的开销，降低为帧进行编号，这也增加了通信的开销，降低了发送效率。了发送效率。窗口可以多大窗口可以多大?16如果帧的编号从如果帧的编号从 02k -1.01234567.SenderReceiver01234567

9、Resend0New 0 orold 0?Therefore, 窗口大小窗口大小 HP n相同性能条件下，站距越大，相同性能条件下，站距越大，HP越优于越优于 RPn站距小，通信量大，站距小，通信量大，HP的优越性不明显的优越性不明显 n实现难度：实现难度：RP t，则按检错方式工作，则按检错方式工作） 1min ed12min td1min etd572. 检错和纠错的原理检错和纠错的原理编码效率：编码效率：Rk / nk：信息位长度信息位长度n：码元总长码元总长nk：监督位长度监督位长度检错和纠错能力是用信息量的冗余度来换取检错和纠错能力是用信息量的冗余度来换取的的584.2.3 简单的差

10、错编码方法简单的差错编码方法 设码组长度为设码组长度为n，表示为（表示为（an-1 an-2 a1 a0），），其其中前中前n-1位为信息位，位为信息位，a0为校验位，则为校验位，则: :偶校验时有：偶校验时有：奇校验时有：奇校验时有：（ ：模模2相加，等同于相加，等同于“异或异或”运算运算）只能发现单个或奇数个错误，适合于检测随机差错。只能发现单个或奇数个错误，适合于检测随机差错。0.110 naaa1.110 naaa即偶校验：即偶校验： 奇校验：奇校验：1210. naaaa1.1210 naaaa 1. 奇偶校验码奇偶校验码单比特错误检测单比特错误检测:591. 奇偶校验码奇偶校验码两

11、比特错误检测两比特错误检测01101000010111101001偶偶校校验验可检出可检出信息位信息位校验位校验位602. 行列监督码行列监督码0110110001011101100101010101110 1 1 0 11 0 0 0 10 1 1 1 01 1 0 0 10 1 0 1 01 0 1 1 1信息组信息组101100监督监督纵向纵向：010101;101110;101001;001011;发送发送 110101;1011000 1 1 1 11 0 0 1 10 1 1 0 01 1 0 1 10 1 0 0 01 0 1 0 1101100监监督督信信息息组组突发错误突发错

12、误突发错误检测：突发错误检测：110100每一行依每一行依然可用偶然可用偶校验检验校验检验61将连续信息划分成小块将连续信息划分成小块2. 行列监督码行列监督码序列：0111001 0010101 0101011 10101010 1 1 1 0 0 10 0 1 0 1 0 10 1 0 1 0 1 11 0 1 0 1 0 1信信息息组组水平监督水平监督0100垂直监督垂直监督1 0 1 0 0 1 0 1随机错随机错: :能检能检突发错突发错: :能检能检不能检不能检混合错误检测混合错误检测水平垂直奇偶校验：水平垂直奇偶校验：624.2.4 线性分组码线性分组码代数码代数码：编码算法利用

13、了代数方程式以产生奇偶：编码算法利用了代数方程式以产生奇偶校验比特。校验比特。线性分组码线性分组码：是一种分组码，特点是奇偶校验比：是一种分组码，特点是奇偶校验比特和信息比特之间的关系由线性代数方程式确定。特和信息比特之间的关系由线性代数方程式确定。最典型的线性分组码是汉明码最典型的线性分组码是汉明码 (Hamming codes)。1. 概概念和特点：念和特点：631. 概念和特点概念和特点矢量空间：矢量空间：所有二进制所有二进制n元组组成的集合元组组成的集合Vn，称为称为0和和1的二进制域的。的二进制域的。n这个空间中仅有两个运这个空间中仅有两个运算：算：“加加 ( (简写简写+)+)”和

14、和“乘乘 ( (简写简写 ) )”；n所有的运算结果都包含所有的运算结果都包含在这两个元素的同一个集合中。在这两个元素的同一个集合中。642. 线性分组码的原理线性分组码的原理n封闭性：任意两个许用码组之和封闭性：任意两个许用码组之和( )仍为许用仍为许用码组；码组； n码的最小码距等于非零码的最小重量（码距码的最小码距等于非零码的最小重量（码距最小码重，最小码重，0码组除外）。码组除外）。 652. 线性分组码的原理线性分组码的原理发送时偶校验应有：发送时偶校验应有：接收时设校正子：接收时设校正子： , ,则则若监督位有若监督位有r 位，则校正子有位，则校正子有r 位：位：S1Sr，可指示可

15、指示2r1种误码图样种误码图样；若只有一位误码，则可指示若只有一位误码，则可指示n( (n = 2r1)个误个误码位置。码位置。 设码组长度为设码组长度为n，信息位信息位k，监督位监督位r = n - k，记为记为( (n, ,k)码，若码，若2r1 n，则有可能构造出纠正一位或一位以上错则有可能构造出纠正一位或一位以上错误的线性码。误的线性码。0.110 naaa1210. naaaaSa0a0663. 线性分组码的描述方法线性分组码的描述方法 设分组线性码设分组线性码( (n，k)中，中，k4，为能纠正一位误码，为能纠正一位误码，要求要求2 r 1rk，取取r3，得得( (7，4) )线性

16、分组码。线性分组码。a61 1 1a21 0 0无错无错0 0 0a30 1 1a51 1 0a10 1 0a41 0 1a00 0 1误码位置误码位置S1S2S3误码位置误码位置S1S2S3例如，设计校正子与误码关系如下：例如，设计校正子与误码关系如下：校正子校正子(syndrome)与误码与误码(errors)67校正子与误码（续）校正子与误码（续） 依上表有：依上表有：S1 = a6 + a5 + a4 + a2 S2 = a6 + a5 + a3 + a1 （式式1） S3 = a6 + a4 + a3 + a0无错时有：无错时有： a6 + a5 + a4 + a2 = 0a2 =

17、a6 + a5 + a4 a6 + a5 + a3 + a1 = 0即：即： a1 = a6 + a5 + a3 （式式2） a6 + a4 + a3 + a0 = 0a0 = a6 + a4 + a368校正子与误码（续）校正子与误码（续）信息位信息位监督位监督位a6 a5 a4 a3a2 a1 a010001111001100101001010110011100001110101011101001111111 根据根据( (式式2) )可可得：得：信息位信息位监督位监督位a6 a5 a4 a3a2 a1 a000000000001011001010100111100100110010110

18、101100110111000694. 监督矩阵监督矩阵H (parity-check matrix) 计算计算根据根据( (式式2) )可得：可得：1a6 + 1a5 + 1a4 + 0a3 + 1a2 + 0a1 + 0a0 = 01a6 + 1a5 + 0a4 + 1a3 + 0a2 + 1a1 + 0a0 = 01a6 + 0a5 + 1a4 + 1a3 + 0a2 + 0a1 + 1a0 = 0用矩阵形式表示为：用矩阵形式表示为：记为：记为：HAT = OT或或AHT = O704. 监督矩阵监督矩阵H特点特点nH =rn阶阶nH = P Ir监督矩阵的监督矩阵的典型形式典型形式，非

19、非典型形式可经过运算转化为典型形式。典型形式可经过运算转化为典型形式。P：rk阶，阶， Ir：rr阶阶715. 生成矩阵生成矩阵G (generator matrix) 计算计算（式（式2）可以改写为：）可以改写为： 34563456012110110110111aaaaPaaaaaaa或：或：Q = PT（式（式3）725. 生成矩阵生成矩阵G 计算计算 (续续)可见：可见：Q = PT = 110101011111735. 生成矩阵生成矩阵G 特点特点n G =kn阶阶n G =Ik Q生成矩阵的生成矩阵的典型形式典型形式，非非典型形式可经过运算转化为典型形式。典型形式可经过运算转化为典型

20、形式。Q=PT ：kr阶，阶， Ik：kk阶阶745. 生成矩阵生成矩阵G 全码组的计算全码组的计算 G为生成矩阵的典型形式，整个码组为生成矩阵的典型形式，整个码组A可以由可以由G生成：生成： A = G = 3456aaaa 0123456aaaaaaa756. 校正子与误码的关系校正子与误码的关系 76设：发送码组设：发送码组A = 接收码组接收码组B = 021.aaann 021.bbbnn 则收发码组之差：则收发码组之差：E = B + A = 021.eeenn B = A + E 6. 校正子与误码的关系校正子与误码的关系 77发端：发端：O = AHT 收端：收端：S = BH

21、T = (A + E)HT = AHT + EHT = EHT 可见：可见：S只与只与E有关，即错误图样与校正有关，即错误图样与校正子有确定关系，与发送码组无关。子有确定关系，与发送码组无关。 7. 汉明码汉明码Hamming codes用生成矩阵构造的能纠正单个错误的线性分用生成矩阵构造的能纠正单个错误的线性分组码。组码。（1）码长）码长 n = 2m1（2）监督码位监督码位 r = m（3）信息码位信息码位 k = nr = 2mm 1（4）纠错能力纠错能力 t = 1（5）最小码距）最小码距 d = 3 (n, k) 汉明码汉明码78(7,4) Hamming code/decodede

22、signS1S2S3误码位置误码位置S1S2S3误码位置误码位置001a0110a4010a1111a5100a2101a6011a3000无错无错设校正子与误码的关系为：设校正子与误码的关系为： 79(7,4) Hamming code/decodedesign 依上表有：依上表有：S1 = a6 + a5 + a4 + a2 S2 = a5 + a4 + a3 + a1 (式式4) S3 = a6 + a5 + a3 + a0无错时有：无错时有： a6 + a5 + a4 + a2 = 0a2 = a6 + a5 + a4 a5 + a4 + a3 + a1 = 0即：即： a1 = a5

23、 + a4 + a3 (式式5) a6 + a5 + a3 + a0 = 0a0 = a6 + a5 + a380(7,4) Hamming codes codingcircuit81(7,4) Hamming codes decodingcircuit (error correction)824.2.5 循环码循环码循环码循环码：设：设C为某为某(n, k)线性分组码的码组集合，如果对于线性分组码的码组集合，如果对于C中任意一个码组中任意一个码组c = ( an-1 an-2 a1 a0 )，它的循环移位，它的循环移位c(1) = ( an-2 an-3 a1 a0 an-1 )也属于也属于

24、C，则称该，则称该(n, k)码为循码为循环码，其中环码，其中c(i )表示表示c码组循环移位码组循环移位 i 次。次。循环码是线性分组码中最主要、最有用的一种码，与循环码是线性分组码中最主要、最有用的一种码，与一般的线性分组码相比，循环码具有循环特性，一般的线性分组码相比，循环码具有循环特性，易用带反易用带反馈的移位寄存器实现其硬件，且性能较好，既能纠正随机馈的移位寄存器实现其硬件，且性能较好，既能纠正随机错误，也能纠正突发错误。错误，也能纠正突发错误。概念：概念：83特点特点n封闭性封闭性：任意两个许用码组之和：任意两个许用码组之和( )仍为许用码仍为许用码组。由此性质可以得到：组。由此性

25、质可以得到：线性码都包含全零码，线性码都包含全零码，非零码的最小码重就是最小码距非零码的最小码重就是最小码距。n循环性循环性：任何许用的码组循环移位后的码组还：任何许用的码组循环移位后的码组还是许用码组。即：是许用码组。即：若若(an-1 an-2 a1 a0)为循环码组，则为循环码组，则(an-2 a1 a0 an-1)，(an-3 a0 an-1 an-2)都是许用码组。都是许用码组。 84举例举例一种一种(7, 3)循环码的全部码字循环码的全部码字序序号号码字码字序序号号码字码字信息位信息位a6 a5 a4监督位监督位a3 a2 a1 a0信息位信息位a6 a5 a4监督位监督位a3 a

26、2 a1 a010 0 00 0 0 051 0 01 0 1 120 0 10 1 1 161 0 11 1 0 030 1 01 1 1 071 1 00 1 0 140 1 11 0 0 181 1 10 0 1 085数学变量的含义数学变量的含义nA = (an-1 an-2 a1 a0)：循环码组：循环码组nA(D)：循环码多项式：循环码多项式ng(D)：生成多项式：生成多项式nG：生成矩阵：生成矩阵nM(D)：信息码多项式：信息码多项式nr(D)：监督码多项式：监督码多项式nh(D)：监督多项式：监督多项式nH：监督矩阵：监督矩阵86数学运算基础数学运算基础)( ,npnpnpQn

27、m 取模运算：取模运算：例：例：m1 = 4, m2 = 10, 求以求以n = 3为模时为模时, m1? m2?结论：在模结论：在模n运算下，一个整数运算下，一个整数m等价于其被等价于其被n除后除后的余数。的余数。解：解：4 1 mod 3, 10 1 mod 3在模在模3时，时，4 10即即mp (模模n)，或，或 m p mod nQ：商；：商；p：余数。：余数。871. 循环码表示规则循环码表示规则n用码多项式表示码组用码多项式表示码组 A = (an-1 an-2 a1 a0)A(D) = an-1Dn-1 + an-2Dn-2 + + a1D + a0D：实变量，是码元位置的标记。

28、：实变量，是码元位置的标记。n当左移一位时当左移一位时，A = (an-2 a1 a0 an-1)，表示为：，表示为：A(1)(D) = an-2Dn-1 + an-3 Dn-2 + + a1D2 + a0D + an-1A(i)(D) = an-i-1Dn-1 + an-i-2Dn-2 + + an-i+1D + an-i n左移左移i位时位时:881. 循环码表示规则循环码表示规则n下面下面考察考察DA(D)与与A(1)(D) 之间的关系。之间的关系。A(1)(D) = an-2Dn-1 + an-3 Dn-2 + + a1D2 + a0D + an-1DA(D) = an-1Dn + a

29、n-2Dn-1 + + a1D2 + a0Dn用用Dn + 1除除DA(D)得得 := A(1)(D)DA(D) = an-1(Dn + 1) + A(1)(D)891. 循环码表示规则循环码表示规则因此因此可推知，可推知，A(i)(D)可由下式求得：可由下式求得：DiA(D) = Q(D) (Dn + 1) + A(i)(D)（式（式6）其中，其中，Q(D)：DiA(D)除以除以(Dn + 1)的商；的商； A(i)(D)：DiA(D)除以除以(Dn + 1)的余数。的余数。用等价形式表示：用等价形式表示：DiA(D) A(i)(D) mod (Dn + 1)（式（式7）90Example

30、1某循环码组为某循环码组为1100101，写出，写出A(D)及及A(1)(D)。 解：解：A(D) = D6 + D5 + D2 +1左移一位左移一位: DA(D) = D7 + D6 + D3 +D = Q(D) (D7 + 1) + A(1)(D) 列成长除直式：列成长除直式： 余式为：余式为：A(1)(D) = D6 + D3 +D + 1 其对应码组为其对应码组为1001011，显然与直接移位的结果相同。，显然与直接移位的结果相同。 91 g(D)是一个能除尽是一个能除尽Dn + 1的的nk阶多项式，阶多项式，循环码完全由码组长度循环码完全由码组长度n及及g(D)所决定。阶数所决定。阶

31、数 n且能被且能被g(D)除尽的每个多项式都是许用码组，它除尽的每个多项式都是许用码组，它们构成一个们构成一个(n, k)循环码。循环码。 A(D) = M(D)g(D) A(D)：许用码组：许用码组M(D)：多项式，阶数：多项式，阶数k1，共有，共有2k个个2. 生成多项式生成多项式g(D)和生成矩阵和生成矩阵G 92Example 2令令n = 7，g(D) = D4 + D3 + D2 + 1, 请构造请构造(7, 3)循环码。循环码。 解：解：g(D) 是是D7 + 1的一个因式，因式分解可知，共有的一个因式，因式分解可知，共有8个阶次不个阶次不大于大于6的多项式是的多项式是g(D)的

32、倍式：的倍式：这这8个多项式个多项式是一个是一个(7, 3)循循环码，由于有环码，由于有8个码组，个码组，k = 3, nk = 4为为g(D)的阶次。的阶次。 D4 + D3 + D2 + 1 = g(D) 1 0 = g(D) 0 D5 + D4 + D3 + D = g(D) D D6 + D5 + D4 + D2 = g(D) D2 D5 + D2 + D + 1 = g(D) (D + 1) D6 + D3 + D2 + 1 = g(D) (D2 + D ) D6 + D5 + D3 + 1 = g(D) (D2 + 1 ) D6 + D4 + D + 1 = g(D) (D2 +

33、D + 1) 93典型的典型的g(D) 任取任取n，有，有Dn + 1 = (D + 1) (Dn-1 + Dn-2 + + D + 1) 特殊情况：特殊情况： ng(D) = D + 1n g(D) = Dn-1 + Dn-2 + + D + 1为了寻找为了寻找g(D)，必须对，必须对Dn + 1进行因式分解。进行因式分解。计算机完成计算机完成 偶监督码偶监督码(n, n1) (可证明可证明, D + 1的任何倍式的码重都为偶数的任何倍式的码重都为偶数)，dmin = 2；重复码重复码(n, 1)，全全0或全或全1，dmin = n。94G(D)和和G (非系统循环码非系统循环码)非系统码：

34、信息码元编码前后发生改变。非系统码：信息码元编码前后发生改变。 g(D)为为nk阶多项式，作为阶多项式，作为G(D)的一行，则的一行，则g(D)，Dg(D)，D2g(D)，Dk-1g(D)必线性必线性无关。无关。 )(.)()()(21DgDgDDgDDGkk G(D)可以表示为：可以表示为：95G(D)和和G (非系统循环码非系统循环码)当输入信息码元为当输入信息码元为(mk-1 mk-2 m0)时：时： 结论：码多项式必为结论：码多项式必为g(D)的倍式。的倍式。 A(D) = (mk-1 mk-2 m0) G(D) = (mk-1Dk-1 + mk-2 Dk-2 + +m1D + m0)

35、g(D)= M(D) g(D) 96G(D)和和G (非系统循环码非系统循环码)Example 3已知已知(7, 4)循环码的生成多项式循环码的生成多项式 ，求生，求生成矩阵成矩阵G。 解：解： n7，k4 11)1()1()1()(.)()()(2334245356232323223321DDDDDDDDDDDDDDDDDDDDDDDgDgDDgDDGkk 1011000010110000101100001011G1)(23 DDDg97G(D)和和G (系统循环码系统循环码) r(D)的计算的计算系统码：信息码元编码前后保持不变。系统码：信息码元编码前后保持不变。 A = (mk-1 mk

36、-2 m0 rn-k-1 rn-k-2 r0) A(D) = mk-1Dn-1 + mk-2Dn-2 + + m0Dn-k + rn-k-1Dn-k-1 + + r0 信息位信息位 (k) 监督位监督位 (n - k) = (mk-1Dk-1 + mk-2 Dk-2 + + m0)Dn-k + r(D)= M(D)Dn-k + r(D)98G(D)和和G (系统循环码系统循环码) r(D)的计算的计算M(D)：信息码多项式；：信息码多项式；r(D)：监督码多项式：监督码多项式 r(D) = A(D) + M(D)Dn-k = M(D) g(D) + M(D)Dn-k 根据模运算规则有：根据模运

37、算规则有： )()()()()()()()()()(DgDDMDMDgDDMDgDgDMDgDrknkn r(D) M(D)Dn-k mod g(D)99G(D)和和G (系统循环码系统循环码) 构造方法构造方法结论：结论：构造系统循环码时，只需要将信息码构造系统循环码时，只需要将信息码多项式升多项式升(n - k)阶，即乘以阶，即乘以Dn-k，然后以，然后以g(D)为模，即除以为模，即除以g(D)，所得余式即为监督码元。，所得余式即为监督码元。所以系统循环码的编码过程就变成用除法求所以系统循环码的编码过程就变成用除法求余数。余数。 非常重要非常重要 100G(D)和和G (系统循环码系统循环

38、码) 系统码的生成矩阵必为典型形式系统码的生成矩阵必为典型形式G = Ik Q 与单位矩阵与单位矩阵Ik每行对应的信息多项式为：每行对应的信息多项式为： mi (D) = mi Dk-i = Dk-ii = 1, 2, , k ri (D) mi (D)Dn-k mod g(D) Dn-i mod g(D)i = 1, 2, , k Dk-iDn-k mod g(D) 由由r (D) m(D)Dn-k mod g(D)得：得：101G(D)和和G (系统循环码系统循环码)G(D)的计算的计算 生成矩阵中每行的码多项式为：生成矩阵中每行的码多项式为： Ci (D) = Dn-i + ri (D)

39、 i = 1, 2, , k = 信息多项式升信息多项式升(nk)次幂监督多项式次幂监督多项式因此，系统循环码的因此，系统循环码的G(D)一般表示为：一般表示为： )(.)()()(.)()()(221121DrDDrDDrDDCDCDCDGkknnnk102G(D)和和G (系统循环码系统循环码)Example 41)(23 DDDg已知已知(7, 4)系统循环码的生成多项式为系统循环码的生成多项式为 ，求典型形式的，求典型形式的G。 列成长除直式：列成长除直式： r1(D) D6 mod g(D) (D2 + D) mod g(D) 解：解： n7，k4， 由由ri(D) Dn-i mod

40、 g(D)得：得：r1(D) D7-1 mod g(D) D6 mod g(D) 103G(D)和和G (系统循环码系统循环码)Example 4同理：同理：r2(D) D5 mod g(D) (D +1) mod g(D)r3(D) D4 mod g(D) (D2 + D +1) mod g(D)r4(D) D3 mod g(D) (D2 +1) mod g(D)因此，系统生成矩阵为：因此，系统生成矩阵为： 111)()()()()(232452643342516DDDDDDDDDDDrDDrDDrDDrDDGG(D)和和G (系统循环码系统循环码)Example 4表示成矩阵形式，得到：表

41、示成矩阵形式，得到： QIG41011000111010011000100110001 105依定义，依定义，g(D)能除尽能除尽Dn +1，即：，即：Dn +1 = g(D) h(D) (式式8)其中：其中：g(D) = gn-kDn-k + + g1D + g0生成多项式生成多项式h(D) = hkDk + + h1D + h0监督多项式监督多项式由由(式式8)知：知： 3. 监督多项式监督多项式h(D)和监督矩阵和监督矩阵H 106监督矩阵监督矩阵H0.0.0.001111102110110021120011000 kknkknknknknknknknkknhghghghghghghghghghghghghghghg107监督矩阵监督矩阵H 如果生成矩阵为：如果生成矩阵为： nkknknknggggggG 000.0.00.则监督矩阵为：则监督矩阵为： (式式9) nknkkkhhhhhhH )(000.0.0.0.00.0.nk1 k1 H完全由完全由h(D)的系数确定，的系数确定，可以验证可以验证: GHT = Ok(n-k)108Example 5已知已知 (7, 3) 循环码的生成多项式为循环码的生成多项式为 , 求生成矩