计算机网络 第三章 课后题答案_what is the remainder obtained by dividing x7 + x5

英文版教材第三章 1、2、3、4、6、7、9、11、14、15、16, 补充题1

1. 一个上层分组（数据包）被分为 10 帧，每帧有 80%可能无损到达。如果在数据链路层没有差错控制，该报文要平均传送多少次才能正确交付？

   考点：概率中的乘法和加法原理

   答：整个报文无差错的到达接受端的概率$A=0.8^{10}=0.107$，因此成功发送1个报文平均需要传输的概率$=\frac{1}{0.107}=9.3$
   正规解法：假设第 k 帧发送成功，前面 k-1 帧全部失败，则平均传输次数$={\Sigma }_{k=0}^{\infty }kA(1-A{)}^{k-1}=9.3$

2. 在一个数据流中有下列数据片段： A B ESC C ESC FLAG FLAG D，使用字节填充方法，填充之后的结果是什么？

   考点：字节填充法

   答：A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D

3. 试问字节填充算法的最大开销是多少？

   考点：字节填充法中转义字符的处理

   答：如果数据部分只有 FLAG 和 ESC 字符，则经过填充之后，原数据字符数和转义字符个数相同，因此开销 = 转义字符数/数据字符数 = 100%

4. 使用位填充时，是否可能出现单比特差错（丢失、插入或者修改等），而通过校验和无法查出？如果不会，为什么？如果会，什么情况下会出现？校验和长度对此是否有影响？

   考点：校验和概念和能力的理解

   答：有可能。当使用位填充时，如果有单比特数据在传输的过程中发生改变，对于 n 位校验和，有 $\frac{1}{2^n}$ 的概率无法查出错误，即被判断为校验和字段的 n 位数据的值恰好是使得对数据部分校验正确的值。校验和的位数越长，错误被忽略的概率越低。

5. 为增强单比特校验的可靠性，一个差错检测编码使用一个校验位来检查所有奇数位，使用第二个校验位来检查所有偶数位。此编码的汉明距离是多少？

   考点：海明距离的理解

   答：增加了 2 位校验位后，编码的汉明距离是 2（数据中 1 个不同，则校验中 1 个不同）

6. 假定利用海明码传送 16bit 报文，则需要添加多少 bit 的检查位才能确保接受方能够检测并纠正单个 bit 错误？如果传送 1101001100110101 的报文，在使用偶数校验方式，请给出传送的位模式。

   考点：纠错码（海明码）

   答：根据公式 $m+r+1\le 2^r$，当 $m=16$ 时，r 最小为 5。因此需要添加 5bit 的检查位。
   
   利用编码简便法有：码字中为1的位号为 b3, b5, b7, b11, b12, b15, b17, b19, b21，表示为二进制码并按模2求和，得到校验码 $P_5{P}_4{P}_3{P}_2{P}_1=01011$，因此发送的位模式为 111010110011001010101

7. 一种检测差错的方法是把数据分成 n 行 k 列的数据块来传输，每行一个校验位，每列一个校验位，右下角的校验位对其所在行和列进行校验。这种方法可以检查出所有单比特差错吗？能检查出所有双比特差错吗？三比特差错呢？证明这种方法不能检查出某些四比特差错。

   考点：行列同时校验方法的原理

   答：可检查出所有单比特差错，一个单比特差错导致所在行列都出现校验错误。也可以检查出所有双比特差错，即使出错的两个比特在同行或者同列，也能查出。对于 3 比特差错， 如果在同行或同列，则该行或列的奇偶校验将检测出错误。 如果同行中有两个错误，则至少其中一个的列奇偶校验将检测到错误。 同列中有2个错误同理。对于 4 比特差错，如果出错的四个点正好位于矩形的 4 个顶点，则无法检查出差错。

8. 假定数据以 1000 比特成块发送，可能发生 1 比特差错，出错的概率是独立的且重传不出错。误码率为多少时，采用奇偶校验检错并重传的方法要好于汉明码直接纠错？

   考点：两种差错控制方法的理解及其开销的计算

   答：若采用海明码直接纠错，根据不等式 $m+r+1\le 2^r$ 可得到海明码校验位长度为 10，共需传输 1010 位；若采用奇偶校验并重传的方式，只需 1 位校验位，但需要计算重传开销。假设出错率为 p，采用检测重传的方式的开销$=1001+1000p\times 1001＜1010$，解得 $p＜8.99\times 10^{-6}$

9. What is the remainder obtained by dividing $x^7+x^5+1$ by the generator polynomial $x^3+1$?
   考点：检错码(CRC)
   答：将 $M(x)=x^7+x^5+1$ 表示为2进制为 10100001，由题意知 $r=3$，将 $M(x)$ 左移 3 位得到：10100001000，$R(x)=10100001000\%G(x)=111$

10. 位流 10011101 使用教材中描述的标准 CRC 方法来进行校验。生成多项式是 x 3 + 1 x^3+1