算法实现/校验和
< 算法实现
有些人将校验和视为一种散列，但碰撞（不同的输入，相同的结果）的可能性很大。校验和用于检测不可恢复的错误，以防止系统中进一步的数据损坏。如果需要校正，则需要ECC（纠错码，例如汉明码、里德-所罗门码或BCH码）。
碰撞率是大小和计算速度之间的折衷。n位校验和检测失败的概率是2^-n。此大小的选择取决于应用程序的要求和预期的错误模型（错误的类型和概率）。16位校验和字段很小，但每65536个随机输入就会出现一个误报（充其量），因此它用于数据块较小、后果良性且/或损坏不太可能的情况。32位校验和的开销是其大小的两倍，但碰撞的概率只有40亿分之一，因此它常用于存储或传输大型文件，如果这些文件可能会被修改。
编写校验和算法的程序员可以使用反码加法，如果愿意为了非常高的速度而牺牲错误检测的有效性（例如EXE文件或IP报头数据包），可以使用Fletcher-32校验和来平衡速度和错误检测（尽管它无法区分0xFFFF和0x0000），可以使用CRC-32来获得更好的错误检测，但在需要性能时实现更复杂。[1]程序员应该使用MAC或数字签名——通常涉及加密安全的散列，例如SHA-256或SHA-3——如果愿意运行速度更慢并分配256位或更多以检测对数据的恶意更改。此类散列在后面的章节中介绍，散列。
- PEAC（带进位的皮萨诺算法）与Fletcher和Adler校验和一样快，并且具有更好的错误检测能力（几乎与CRC一样好）[2]，方法是在皮萨诺（截断斐波那契）结构中使用反码加法（也称为进位）。一对16位寄存器可以生成与CRC32相当的校验和，并且编码复杂度要低得多。对于仅16位的校验和，可以将两个16位寄存器相加。
- Verhoeff算法
- Damm算法
- CRC16 CCITT
- CRC16 XModem
- CRC32 / FCS32 - 通常用于以太网和与PKZip兼容的归档
- ↑ Theresa C. Maxino。"嵌入式网络校验和的有效性"比较了常用校验和的错误检测有效性：异或（XOR）、二进制补码加法、一进制补码加法、Fletcher校验和、Adler校验和和循环冗余码（CRC）…简要提到“加权和码”在错误检测方面可能与CRC一样好，但计算成本更低…讨论了关于错误检查码的常见误解。
- ↑ Yann Guidon / YGDES。"PEAC 带进位的皮萨诺算法"。