[科普中国]-编码错误检测

简介

编码错误检测是指检测编码过程或编码传输过程中出现的错误。在程序设计中，编码错误检测也称为程序测试，即查找编写代码阶段的错误。在通信中，编码错误检测是指检测编码传输过程中的错误，通常使用适合的散列函数（或校验和 算法）实现。

编码编码是信息从一种形式或格式转换为另一种形式的过程。用预先规定的方法将文字、数字或其它对象编成数码，或将信息、数据转换成规定的电脉冲信号。编码在电子计算机、电视、遥控和通讯等方面广泛使用。编码是信息从一种形式或格式转换为另一种形式的过程。编码也可以是指用规定的一组代码表示计算机程序的指令或信息的过程，即为计算机编写程序2。

程序测试程序测试(program testing)是指对一个完成了全部或部分功能、模块的计算机程序在正式使用前的检测，以确保该程序能按预定的方式正确地运行。软件的正确性尚未得到根本的解决，软件测试仍是发现软件错误和缺陷的主要手段。为了发现系统中的错误，应竭力设计能暴露错误的测试用例。测试用例是有测试数据和预期结果构成的。一个好的测试用例是极有可能发现至今为止尚未发现的错误的测试用例。测试方法有灰盒测试、白盒测试、黑盒测试。

灰盒测试灰盒测试，确实是介于白盒测试与黑盒测试之间的，可以这 样理解，灰盒测试关注输出对于输入的正确性，同时也关注内部表现，但这种关注不象白盒那样详细、完整，只是通过一些表征性的现象、事件、标志来判断内部的运行状态，有时候输出是正确的，但内部其实已经错误了，这种情况非常多，如果每次都通过白盒测试来操作，效率会很低，因此需要采取这样的一种灰盒的方法。

白盒测试白盒测试，又称结构测试。他的前提是可以把程序看成在一个透明的白盒子里，测试者完全知道程序的结构和处理算法。这种方法按照程序内部逻辑设计测试用例，检测程序中的主要执行通路是否能按照预定要求正确工作。白盒测试根据软件的内部逻辑设计设施用例，常用的技术是逻辑覆盖，即考察用测试数据运行被测程序是对程序逻辑的覆盖程度。主要的覆盖标准有：语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、组合条件覆盖和路径覆盖。

黑盒测试黑盒测试根据关键需求说明书所规定的功能来设计测试用例，它不考虑软件的内部结构和处理算法。常用的黑盒测试技术包括等价类划分、边值分析、错误推测和因果图等。

通信中编码错误检测错误检测通常使用适合的散列函数（或校验和算法）实现。散列算法添加定长的标签到消息，从而使接收者能通过计算标签并与所提供的标签比较来验证传递的消息。散列函数存在多种多样的设计。其中一部分因其简单性或适合检测某些类型的错误（例如循环冗余校验的性能优势 为检测突发错误而使用）而被广泛使用。

一个随机前向纠错基于最小距离编码的可以对可检测误差的数量提供严格保证，但它可能不能防御原像攻击。下面章节中描述的重复编码就是纠错码的一种特殊案例。虽然相当低效，但由于其简单性，重复编码适合部分纠错与检测的应用。

重复编码重复编码是在信道上重复比特信息以实现无差错通信的编码方案。首先将要发送的数据流划分为比特块，然后将每个传输预定的次数。例如，要发送比特“1011”，四比特块{{what}}则再重复三次而产生“1011 1011 1011”。但是，如果此例中收到12位信息为“1010 1011 1011”，其中第一个块不同于其他两个，则可以确定已经发生错误。重复编码非常低效，并且如果错误在每个组的完全相同的地方发生，则很容易出现问题（例如上例中正巧错误为“1010 1010 1010”，将被检测为传输无误）。重复编码的优点是它非常简单，并实际上用于某些数字电台的传输。

奇偶校验位奇偶校验位（parity bit）是一种非常简单的方案，可以用于检测任何奇数个错误的发生。但如果发生的错误数量为偶数，则奇偶效验位看上去是正确的。对奇偶效验位的扩展和改变有纵向冗余校验、垂直冗余检查，以及双或对角奇偶（在RAID-DP中使用）。

校验和消息的校验和是固定字长（例如字节值）的字节码的模算数和。和可能在传输前用一补数以检测全零消息出现的错误。

校验和方案包括奇偶校验位、校验码和纵向冗余校验。部分校验和方案如Damm算法、Luhn算法和Verhoeff算法在设计上是专门用于检测人类书写或记录数字时常出现的错误。

循环冗余校验（CRC）循环冗余校验（CRC）是一个非安全的散列函数，旨在检测计算机网络中数字数据的意外变化。因此，它不适合检测恶意引入的错误。

循环码有着非常适合检测突发错误的有利特性。CRC尤其容易在硬件中实现，兵器因此常用在数字网络和诸如硬盘等存储设备中。

奇偶校验是循环冗余校验的特殊案例，其中单比特CRC由除数x + 1生成。