2023-05-24 15:24:59
总长度：n=k+r，k是数据字的长度，r是冗余位长度。即有\(2^k\)个数据字组合，\(2^n\)个码字组合，\(2^n-2^k\)个未使用码字
正式定义需要抽象代数
简单奇偶校验编码是一种最简单、最常用的校验码，用来检测数据传输过程中是否发生错误。它的基本方法是：在n位有效信息位上增加一个二进制位作为校验位P，构成n+1位的奇偶校验码。它有两种校验方法：奇校验和偶校验。
它的检错能力是：可以检出1位错或奇数位错，无纠错能力。它的一个常见的应用场合是ASCII码，ASCII码占用一个字节，低7位是有效位，最高位用作奇偶校验。
汉明编码是一种线性纠错码，它具有一位纠错能力。它的基本方法是：在n位有效信息位上增加k位校验位，构成n+k位的汉明编码。
2^(k-1)位，其余位置是数据位。循环编码是一种线性分组码，满足循环特性，即任意码字的循环移位仍然是该编码中的一个码字。循环编码可以用多项式表示法，即将每个码字看作一个多项式的系数向量，例如(1100101)对应于x^6+x^5+x^2+1。
循环编码可以用模运算来进行编码和译码，即将多项式除以一个n次多项式N(x)，得到商式和余式，其中余式就是循环码的一个码字。
g(x)，它是N(x)的一个首1因子，且常数项不为0，它决定了循环码的结构和性质。h(x)，它是N(x)除以g(x)得到的商式，它可以用来检测和纠正传输过程中的错误。循环冗余校验-CRC是一种数据通信领域常用的一种数据传输检错技术，它通过在发送端对数据按照某种多项式算法计算出校验码，并将得到的校验码附在数据帧的后面，一起发送到接收端。接收端对收到的数据和校验码按照相同的多项式算法进行验证，以此判断接收到的数据是否正确、完整。如果没有余数，说明数据没有出错，否则说明有错误。
CRC的计算方法有多种，不同的方法有不同的生成多项式、初始值、结果异或值、输入输出反转等参数，这些参数决定了CRC的检错能力和效率。
CRC的优点是计算简单、速度快、占用资源少，能够检测出大部分随机错误和突发错误，缺点是无法检测出所有的错误，比如两个位同时发生错误并互换位置等。
CRC计算方法就是模2除法。首先根据生成多项式位数-1来在要处理的数据后边补同等数量的0，然后再用它除以生成多项式，除时不借位，直接异或运算得到商和余数。此时，要发送的数据就是商和余数了。接收方得到数据后，进行同样的操作（补0，模2除法），如果没有余数，则说明数据完好无损，否则数据有差错。
生成多项式，是一个N次多项式。比如，\(X^4+X+1\)。它对应的二进制表示的生成多项式就是\(10011\)，因为四次项、一次项和零次项系数非零。
它将被校验的数据按位或按字节进行累加，并舍弃累加溢出的位，得到一个或多个字节的结果。它可以用来检测数据在传输或存储过程中是否发生错误，通常将校验和附加在数据后面，接收方可以通过重新计算校验和并与原始校验和比较来判断数据是否完整。
数据链路层功能：
将位组合成帧，并添加首尾使其和其他帧区分开。成帧有两种协议：面向字符协议和面向位协议。它们的区别主要是转义符添加的方案。前者添加一个ESC字节，后者遇到011111就添加一个0来转义。
帧结构是：标记+头部+转义后数据+尾部+标记
也叫数据链路控制功能。
接收确认前协调发送的数据数量。它高速发送方受到接收确认信息前能传输多少数据。任何设备都有处理进入数据的速度、容量等限制。在达到限制之前，必须提示发送设备，减少发送量/暂停发送。进入的数据必须经过经验和处理才能使用。
差错检测和纠正。任何时刻，检测到帧缺失/帧破坏，协调发送方重新发送帧。这称为自动重发请求（ARQ, automatic repeat request）。
分为两类：
是一种假想的不会丢失帧、复制帧、损坏帧的理想通道。
它没有流量控制、差错控制，且和其他协议一样是单向的：帧从发送方到接收方单向传输。
它是事件驱动型程序，发送方伪代码如下：
while(true){
WaitForEvent();
if(Event(RequestToSend)){
GetData();
MakeFrame();
SendFrame();
}
}接收方伪代码：
while(true){
WaitForEvent();
if(Event(ArrivalNotification)){
ReceiveData();
ExtractData();
DeliverData();
}
}发送方发送一个帧后，必须得到ACK后才能继续发送下一个帧。此处数据帧还是单向的，除了ACK能反向通过。发送方算法如下（很简单，不用多说）：
while(true){
canSend=true
{
WaitForEvent();
if(Event(RequesToSend) AND canSend){
GetData();
MakeFrame();
SendFrame();
canSend=false;
}
if(Event(ArrivalNotification)){
ReceiveFrame();
canSend=true;
}
}
}接收方：
while(true){
WaitForEvent();
if(Event(ArrivalNotification)){
ReveiceFrame();
ExtractData();
DeliverData();
SendACKFrame();
}
}是在上面的停止等得协议加入了简单的差错控制。首先这个协议一次发送一个帧，所以相对简单。发送方发送一个帧后启动定时器，若没有收到ACK，则重发此帧。因此，帧需要编号来让双方知道应该重发哪个帧。另外，ACK帧也是帧，也会丢失。所以ACK帧也需要编号。
由于只有两个帧，所以序号使用0和1即可。接收方收到序列号后，返回当前数据序列号的取反。意思是可以接收下一个帧了。
数据发送失败，超时，发送方重发。
ACK发送失败，超时，发送方重发，接收方检测到重复数据，抛弃，回复ACK。
发送方算法：
Sn=0;
canSend=true;
while(true){
WaitForEvent();
if(Event(RequestToSend) AND canSend){
GetData();
MakeFrame(Sn);
StoreFrame(Sn)
StartTimer();
Sn=Sn + 1;
canSend=false;
}
WaitForEvent();
if(Event(ArrivalNotification)){
ReceiveFrame(ackNo);
if(not corrputed AND ackNo == Sn){
StopTimer();
PurgeFrame(Sn-1);
canSend=true;
}
}
if(Event(TimeOut)){
StartTimer();
ResendFrame(Sn-1);
}
}接收方算法：
Rn=0;
while(true){
WaitForEvent();
if(Event(ArrivalNotification)){
ReceiveFrame();
if(corrupted(frame)) sleep();
if(seqNo == Rn){
ExtractData();
DeliverData();
Rn = Rn + 1;
}
SendFrame(Rn);
}
}
由上图可以看出，停止等待ARQ大量浪费了带宽；如果上面的协议中，我们能在发送了15帧后再停止等待，则利用率可以上升到\(15000/20000\)，即\(75\%\)。同时，在停止等待ARQ中不存在流水线操作，因为单帧发送后存在阻塞操作。
它是上面的协议应用了流水线原理的版本。最主要的改动就是序列号设计，以及滑动窗口。
假设帧头部允许序列号有\(m\)位，序列号范围就是0到\(2^m-1\)。
然后发送方开始发送数据，先发第一帧， 接收方收到，回传ACK1 ，这时有了一个叫做发送方窗口的东西：
如上图，帧有四部分：已确认的帧、发送但未确认的帧、能被发送但还没收到上层数据的帧、不能发送的帧（窗口大小以外的帧）。窗口大小在这个协议中是\(S_{size}=2^m-1\)。还有两个变量\(S_f\)和\(S_n\)，分别是第一个待处理的帧、下一个要发送的帧。
当收到确认帧时，发送窗口右划；一个ACK帧可以确认一个以上的帧，这加快了传输效率。但是当第一帧没有收到，之后收到的很多帧都需要作废重传，非常浪费时间。
各种ARQ协议的利用率计算是一个经常考察的点，其实答案基本很固定。首先是思路，ARQ协议利用率计算时，假设收发时间相等，然后计算所有发送的帧中，数据帧的占比即可得到。
可在一个帧被损坏时，不必重发N个帧。它主要是针对接收方的更改。
HDLC（High-level Data Link Control）是一个实际应用的面向比特的数据链路协议，支持点到点链路和多点链路。具体实现了本章讨论的各种ARQ协议。具有两种通用传输模式：
配置方式有非平衡/平衡两种。第一种是主从配置方式，第二种是对等方式。
主站与从站：一组结点根据在通信过程中的地位分为主站与从站，由主站来控制数据链路的工作过程。主站发出命令，从站接受命令，发出响应，配合主站工作。
点对点方式与多点方式：分为点对点方式与多点方式两种类型，在多点方式的链路中，主站与每个从站之间分别建立数据链路。
正常响应模式与异步响应模式：分为正常响应模式与异步响应模式两种数据传输方式。在正常响应模式中，主站可随时向从站传输数据帧。只有在主站向从站发送命令帧探询，从站响应后才可以向主站发送数据帧。在异步响应模式中，主站和从站可以随时相互传输数据帧，从站不需要等待主站发出探询就可以发送数据帧，但是主站仍然负责数据链路的初始化、建立、释放与差错恢复等功能。
如图所示，上面是三种帧结构，分别是信息帧，管理帧，无编号帧。它的控制字段如下所示：
其中，管理帧的控制字段如下：
无编号帧的指令和响应更加复杂：
一般来讲，HDLC中常用的是对等异步控制模式。这种模式下，链接的建立和拆除如下图所示。使用4个U-frame帧来建立和断开连接。
而进行数据通信时，基本使用I-frame信息帧捎带指令。如果发生数据丢失等情况，则未接收到的一方使用S-frame来告知另一方重发。
高级数据链路控制协议是点到点和点到多点都能使用的一个通用协议，但最通用的协议还是点到点协议（Point-to-Point Protocol，PPP），使用面向字节的方式。
它的帧格式如下图所示：
特点如下：
PPP是面向字节的协议，通过转义字节01111101进行透明插入和删除。
•用于实现PPP在以太网上的传输。 •是为了满足越来越多的宽带上网设备（如ADSL—最初是静态IP 、无线、有线电视等）和越来越快的网络之间的通信而指定开发的标准，它给出了两个广泛的接受的标准：以太网和PPP拨号协议。 •PPPoE就是将PPP数据承载到以太网上，实质是在共享介质的网络中提供一条逻辑上的点到点链路（Session ID）。 •PPPoE主要协议标准：RFC2516
它广泛利用在ADSL接入方式中。通过它，可以实现高速宽带网的个人身份验证访问，为每个用户创建虚拟拨号连接，来高速连接到Internet。
数据链路层分为逻辑链路控制子层LLC和介质访问控制子层MAC。后者的协议可以分为以下几类：
没有一个站点是优于其它站点的，也不能控制其它站点。没有站点有权力允许或不允许其它站点发送或不发送数据。有数据要发送的站通过自身的协议决定发送还是不发送数据。
在链路中，为了让多方向的通信不至于冲突，因此有了底下几个协议。
在这种传输过程中，无冲突相关的计算：
它的吞吐量是\(S=G\times e^{-2G}\)，当\(G=1/2\)时，取到最大值\(S_{max}=0.184\)。
此外，还存在时隙ALOHA：
它可能的冲突时间等于帧传播时间。它的
三种坚持型方法的流程如下所示：
带冲突检测的载波监听多路访问CSMA/CD (Carrier Sense Multiple Access with Collision Detection)规定了冲突处理的算法。
任意站点都可以发送帧，之后监控介质查看传送是否成功。如果成功，站点完成发送；如果不成功，说明存在冲突，需要重新发送此帧。