笔记
1. 字节填充：确保数据帧的完整性
字节填充是数据链路层使用的一种技术，主要用于区分数据帧的边界和避免数据中的特殊字符被误解为控制字符。
工作原理
- 使用特殊字符（通常是FLAG字符，如0x7E）标记帧的开始和结束。
- 在数据中，如果出现与FLAG相同的字符，在其前面插入一个转义字符（通常是ESC字符，如0x7D）。
- 接收方在处理数据时，如果遇到ESC字符，就删除它并保留其后的字符。
正确的示例
假设FLAG是01111110，ESC是01111101：
原始数据：
01111110 00000001 01111101 00000010 01111110
正确的填充后数据：
01111110 (开始FLAG)
01111101 01111110 00000001 01111101 00000010 01111101 01111110
01111110 (结束FLAG)
注意：只有当数据中出现与FLAG相同的模式时，才在其前插入ESC。原始数据中的ESC (01111101) 不需要特殊处理。
字节填充的效率考量
字节填充确保了数据帧的完整性，但可能导致数据膨胀。在最坏情况下（数据中频繁出现FLAG模式），填充后的数据可能接近原始数据的两倍大小。这种潜在的效率问题促使我们思考：是否存在更高效的帧定界方法？
2. 奇偶校验：简单但局限
奇偶校验是最基本的错误检测方法之一。
核心原理
- 奇校验：确保数据中1的总数（包括校验位）为奇数。
- 偶校验：确保数据中1的总数为偶数。
局限性分析
- 无法检测偶数个位的错误。
- 无法检测位置互换的错误。
例如，数据"1100"变成"0011"，奇偶校验无法检测到这个错误。这种局限性使得奇偶校验在需要高可靠性的现代系统中几乎不再使用。
3. 校验和（Checksum）：改进但仍不完美
校验和是奇偶校验的一种改进，通常涉及将数据视为数值并进行数学运算。
简单加法校验和的问题
最基本的校验和方法——简单加法，存在明显缺陷：
例如：[50, 50, 50, 50] 和 [100, 25, 25, 25] 的校验和相同。
这个例子清楚地表明，简单的加法校验和无法检测数据重排或某些类型的修改。
加权校验和
为了改进，引入了加权校验和：
Σ(i * a_i)，其中 i 是位置，a_i 是数据值
这种方法提高了对数据顺序变化的敏感性，但仍然存在局限。
4. 循环冗余校验（CRC）：强大而高效
CRC是一种更复杂但更强大的错误检测方法。它基于多项式除法的概念，但在实现中使用XOR操作来模拟这种"除法"。
CRC的核心原理
- 将数据视为一个大的二进制多项式。
- 用一个预定义的生成多项式"除"这个数据多项式。
- 余数作为CRC值。
XOR "除法"示例
被除数： 1101001
除数： 1011
步骤1: 1101001
1011 (XOR)
----
0110001
步骤2: 0110001
1011 (XOR)
----
0011001
步骤3: 0011001
1011 (XOR)
----
0000101 (余数)
这个过程看似复杂，但在硬件层面上可以高效实现。
为什么使用XOR？
在二进制多项式算术中，加法和减法等同于XOR操作。这一特性使得CRC既数学严谨又计算高效。
CRC的优势
- 能检测所有单比特和双比特错误。
- 能检测所有奇数个比特的错误。
- 能检测大多数突发错误。
CRC的效率问题
尽管CRC在错误检测方面非常有效，但它的计算复杂度乍看之下似乎是O(n^2)，这可能引发对其效率的质疑。然而，通过使用查找表和位操作，CRC的实际实现可以达到接近O(n)的复杂度。这种优化使CRC在实际应用中既高效又可靠。
评论区