错误纠正和检测代码

在本教程中，我们将学习一些常用的错误纠正和检测代码。我们将会看到数字通信中的错误，有哪些不同类型的错误，一些错误纠正和检测码，如奇偶校验，CRC，汉明码等。

Introdcution

在数字系统中，模拟信号会转换成数字序列(以位的形式)。这个位序列被称为“数据流”。单比特位置的变化也会导致数据输出的灾难性(重大)错误。几乎在所有的电子设备中，我们发现错误并使用错误检测和修正技术来获得精确或近似的输出。

什么是错误

在传输过程中(从源到接收方)数据可能被破坏。它可能会受到外部噪音或其他物理缺陷的影响。在这种情况下，输入数据与接收到的输出数据不相同。这种不匹配的数据称为“错误”。

数据错误将导致重要/安全数据的丢失。即使数据的一点变化都可能影响整个系统的性能。数字系统中的数据传输通常采用“位传输”的形式。在这种情况下，数据错误很可能在0和1的位置发生变化。

回到顶部

类型的错误

在一个数据序列中，如果将1改为0或将0改为1，则称为“误码”。

在从发射机到接收机的数据传输过程中，通常会出现三种类型的错误。他们是

•单比特错误

•多个比特错误

•突发错误

单比特数据错误

整个数据序列中一个比特的变化，称为“单比特误差”。在串行通信系统中，单比特错误的发生是非常罕见的。这种类型的错误只发生在并行通信系统中，因为数据在单线中按位传输，单线有可能有噪声。

多比特数据错误

如果发送端到接收端的数据序列中有两个或多个比特发生变化，称为“多比特误差”。这种类型的错误发生在串行类型和并行类型的数据通信网络。

突发错误

数据序列中位的变化称为“突发错误”。突发误差从第一个比特变化到最后一个比特变化计算。

在这里，我们确定了从第4位到第6位的误差。第4位和第6位之间的数字也被认为是错误的。这组比特被称为“突发错误”。这些突发比特从发射机到接收机会发生变化，这可能会导致数据序列出现重大错误。这种类型的错误发生在串行通信中，很难解决。

回到顶部

错误检测码

在数字通信系统中，误差随数据一起从一个通信系统转移到另一个通信系统。如果这些错误没有被检测和纠正，数据将会丢失。为了有效的通信，数据传输的精度应该很高，这可以通过先检测错误，然后纠正它们来实现。

错误检测是在通信系统中，检测从发射机到接收机传输的数据中存在的错误的过程。我们使用一些冗余码来检测这些错误，在数据从源(发射机)传输时添加这些冗余码。这些代码被称为“错误检测代码”。

错误检测的类型

1. 奇偶校验检查
2. 循环冗余校验(CRC)
3. 纵向冗余校验
4. 校验和

奇偶校验检查

奇偶校验位指的是在传输数据之前在发射机添加到数据中的一个额外的位。在添加奇偶校验位之前，需要计算数据中1或0的数量。在计算数据的基础上，在实际信息/数据上增加一个额外的位。数据中加入奇偶校验位会导致数据字符串大小的变化。

这意味着如果我们有一个8位的数据，然后在数据二进制字符串中添加一个奇偶校验位后，它将变成一个9位的二进制数据字符串。

奇偶校验也被称为“垂直冗余校验(VRC)”。

在错误检测中有两种奇偶校验位

• 偶同位
• 奇校验

偶同位

• 如果数据中有偶数个1，则奇偶校验位为0。例如:数据为10000001—>校验位为0
• 奇数为1，奇偶校验位为1。例如:数据为10010001—>校验位1

奇校验

• 如果数据中有奇数个1，则奇偶校验位为0。例如:数据为10011101—>校验位为0
• 偶数个1，奇偶校验位为1。例如:数据为10010101—>校验位1

请注意:数据位的计数也包括奇偶校验位。

在发射机上给数据加一个奇偶校验位的电路称为“奇偶校验发生器”。奇偶校验位被传输，并在接收端进行校验。如果发送端发送的奇偶校验位与接收端接收的奇偶校验位不相等，则检测到错误。校验接收端奇偶校验的电路称为奇偶校验器。

具有偶数奇偶校验和奇数奇偶校验的消息

回到顶部

循环冗余校验(CRC)

循环码是一种线性(n, k)分组码，其特性是一个码字的每一次循环移位都会产生另一个码字。这里k表示发送端消息的长度(信息比特数)。N为添加校验位后的消息总长度。(实际数据和校验位)。N k是校验位的个数。
用于错误检测的循环冗余校验码称为CRC码(循环冗余校验码)。循环冗余校验码是一种缩短的循环码。这些类型的代码用于错误检测和编码。它们很容易使用带有反馈连接的移位寄存器实现。这就是为什么它们被广泛用于数字通信的错误检测。CRC规则将提供有效和高水平的保护。

CRC生成代码

根据所需的位检查次数，我们将在实际数据中添加一些0(0)。这个新的二进制数据序列除以一个长度为n + 1的新单词，其中n是要添加的校验位的个数。由这种模2除法得到的提醒符被加到红利位序列中形成循环码。生成的码字完全可以被用于生成代码的除数整除。这是通过发射机传送的。

例子

在接收端，我们将接收到的码字用相同的除数除，得到实际的码字。对于没有错误的数据接收，提醒为0。如果提醒是非零的，这意味着在接收到的代码/数据序列中有错误。错误检测的概率取决于用于构造循环码的检查比特数(n)。对于单比特和双比特错误，概率为100%。

对于长度为n - 1的突发误差，误差检测的概率为100%。

长度为n + 1的突发误差，检测误差的概率降低到1 - (1/2)^{n - 1}．

长度大于n - 1的突发误差，检测误差的概率为1 - (1/2)ⁿ．

回到顶部

纵向冗余校验

在纵向冗余方法中，一个比特块以表格的形式排列(行和列)，我们将分别计算每一列的奇偶校验位。这些奇偶校验位的集合也和我们的原始数据位一起发送。

纵向冗余校验是一点一点的奇偶校验计算，因为我们分别计算每个列的奇偶校验。

该方法可以很容易地检测出突发错误和单比特错误，而不能检测出同一垂直切片上发生的2比特错误。

回到顶部

校验和

校验和类似于奇偶校验位，不同的是，校验和中的比特数大于奇偶校验位，并且校验结果总是被限制为零。这意味着如果校验和为零，就会检测到错误。消息的校验和是具有一定长度的码字的算术和。总和以1的互补表示，并作为实际码字的码扩展存储或传输。在接收端，通过接收发射机的比特序列计算新的校验和。

校验和方法包括校验位、校验位和纵向冗余校验(LRC)。例如，如果我们必须传输和检测一个长数据序列(也称为数据字符串)的错误，那么我们将其划分为较短的单词，我们可以使用相同宽度的单词存储数据。对于每一个传入的位，我们将它们添加到已经存储的数据中。在每个实例中，新添加的单词被称为“校验和”。

在接收端，接收到的比特校验和与发送端校验和相同，没有发现错误。

我们还可以通过将所有数据位相加来求校验和。例如，如果我们有4个字节的数据，分别是25h、62h、3fh、52h。

然后，将所有字节相加，得到118H

去掉carry Nibble，我们有18H

求咬痕的2的补数，即E8H

这是传输的4位数据的校验和。

在接收端，为了检查数据是否接收无误，只需将校验和加到实际数据位上(我们将得到200H)。通过放弃carry蚕食，我们得到00H。这意味着校验和被限制为零。所以数据没有错误。

一般来说，有5种校验和方法

• 整数加法校验和
• 补充的校验和
• 弗莱彻校验和
• 阿德勒校验和
• ATN校验和(一个/ 466)

例子

到目前为止，我们讨论了错误检测代码。但要获得准确而完美的数据序列而不产生任何错误，仅通过检测数据中发生的错误是不够的。但我们也需要通过消除错误来纠正数据，如果有的话。为此，我们使用一些其他代码。

回到顶部

错误校正码

用于检错和纠错的代码称为“纠错码”。误差校正技术有两种。他们是谁,

• 单比特纠错
• 破裂纠错

纠正单比特错误的过程或方法称为“单比特错误纠正”。对数据序列中的突发错误进行检测和校正的方法称为“突发错误校正”。

汉明码或汉明距离码是我们在大多数通信网络和数字系统中使用的最好的纠错码。

回到顶部

汉明码

这种错误检测和纠错码技术是由r.w.汉明开发的。这段代码不仅能识别整个数据序列中的错误位，还能纠正它。此代码使用位于码字中某些位置的若干奇偶校验位。奇偶校验位的数目取决于信息位的数目。汉明码利用冗余位和数据位之间的关系，这种编码可以应用于任意数量的数据位。

何谓冗余位?

冗余是指“实际数据序列的位数与传输位数之间的差值”。这些冗余位在通信系统中用于检测和纠正错误。

汉明码是如何纠正错误的?

在汉明码中，冗余位被放置在特定的计算位置以消除错误。两个冗余位之间的距离称为“汉明距离”。

为了了解汉明码的工作原理和数据纠错检测机制，我们来看看下面几个阶段。

奇偶校验位数

如前所述，添加到数据串中的奇偶校验位的数量取决于要传输的数据串中的信息位的数量。奇偶校验位的数目将通过使用数据位来计算。关系如下。

2^P>= n + P +1

这里，n表示数据串中的位数。

P表示奇偶校验位的个数。

例如，如果我们有4位的数据串，即n = 4，那么通过试错法可以找到要添加的奇偶校验位的个数。我们取P = 2

2^P= 2²n + P + 1 = 4 + 2 + 1 = 7

这违背了实际的表达式。

那么我们试试P = 3

2^P= 2^3.= 8, n + P + 1 = 4 + 3 + 1 = 8

因此我们可以说，需要3个奇偶校验位来传输4位数据，并进行单位纠错。

在哪里放置这些奇偶校验位?

在计算出所需奇偶校验位的数目后，我们应该知道将它们放置在信息串中的适当位置，以提供单比特纠错。

在上面考虑的例子中，我们有4个数据位和3个奇偶校验位。因此，要传输的总码字为7比特(4 + 3)。我们一般从右到左表示数据序列，如下图所示。

位7，位6，位5，位4，位3，位2，位1，位0

奇偶校验位必须位于2的幂位。也就是1 2 4 8 16等等。因此，包含奇偶校验位后的码字是这样的

D7 d6 d5 p4 d3 p2 p1

这里P1、P2和P3是奇偶校验位。D1 - D7是数据位。

构造位位置表

在汉明码中，每个奇偶校验位检查并帮助查找整个码字中的错误。所以我们必须找到奇偶校验位的值来给它们赋一个位值。

通过计算并在数据位中插入奇偶校验位，通过汉明码实现纠错。

让我们通过看一个例子来清楚地理解这一点。

例:

使用汉明码对数据1101进行偶校验编码。

步骤1

计算所需的奇偶校验位数。

则设P = 2

2^P= 2²n + P + 1 = 4 + 2 + 1 = 7。

2个奇偶校验位对4位数据是不够的。

那么我们试试P = 3

2^P= 2^3.= 8, n + P + 1 = 4 + 3 + 1 = 8

因此，3个奇偶校验位对于4位数据是足够的。

码字的总位数是4 + 3 = 7

步骤2

构建位定位表

步骤3

确定奇偶校验位。

P1: 3 5 7位有3个1所以对于偶数奇偶校验，P1 = 1。

对于P2: 3,6和7位有两个1，所以对于偶数奇偶校验，P2 = 0。
对于P3: 5、6和7位有两个1，所以对于偶数奇偶校验，P3 = 0。

通过在各自的位置输入/插入奇偶校验位，就可以形成码字并传输。它是1100101。

注意:如果码字都是零(例如:0000000)，那么汉明码没有错误。

为了用字母和数字表示二进制数据，我们使用字母数字代码。

回到顶部

字母数字代码

字母数字代码基本上是用来表示字母数字数据的二进制代码。由于这些代码用字符来表示数据，字母数字代码也被称为“字符代码”。

这些代码可以以计算机可接受的形式表示所有类型的数据，包括字母、数字、标点符号和数学符号。这些代码在I/O设备中实现，如键盘、显示器、打印机等。
在早期，打孔卡被用来表示字母数字代码。

他们是

• 摩尔斯电码
• 博多码
• 霍尔瑞斯代码
• ASCII代码
• EBCDI代码
• UNICODE

摩尔斯电码

在计算机和数字电子时代的起步阶段，莫尔斯电码是最受欢迎和使用最多的电码。这是塞缪尔·f·b·莫尔斯在1837年发明的。这是第一个用于电信的电报代码。主要用于电报信道、无线电信道和空中交通管制单位。

BOUDOT代码

这个密码是法国工程师埃米尔·鲍多在1870年发明的。它是一个5单位的代码，意思是它用5个元素来代表一个字母表。电报网络也使用它来传输罗马数字。

霍尔瑞斯代码

这个代码是由Herman Hollerith在1896年创立的公司开发的。根据传输的信息进行穿孔的12位码称为“霍勒瑞斯码”。

ASCII代码

ASCII是指美国信息交换标准码。它是世界上最受欢迎和广泛使用的字母数字代码。该代码是在1967年开发并首次发布的。ASCII码是7位的代码，这意味着该代码使用27 = 128个字符。这包括

26个小写字母(a - z)， 26个大写字母(a - z)， 33个特殊字符和符号(如!@ # $ etc)， 33个控制字符(* - + /和%等)和10个数字(0 - 9)。

在这个7位的代码中，我们有两部分，最左边的3位和右边的4位。最左边的3位称为“区域位”，右边的4位称为“数字位”。

8位ASCII码可以代表256(28)个字符。它被称为USACC - II或ASCII - 8码。

例子:

如果我们想打印名字伦敦，ASCII码是?

ASCII-7相当于L = 100 1100

ASCII-7的等效函数O = 100 1111

ASCII-7中的N = 100 1110

ASCII-7中的D = 100100

ASCII-7相当于A = 1000001

ASCII-7中的N = 100 1110

LONDAN ASCII代码的输出是1 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0。

UNICODE

ASCII码和EBCDI码的缺点是它们不能兼容所有语言，而且它们没有足够的字符集来表示所有类型的数据。为了克服这些缺点，开发了这个UNICODE。
UNICODE是所有数字编码技术的新概念。我们用不同的字符来表示每个数字。它是最先进、最复杂的语言，能够表示任何类型的数据。这就是所谓的“通用代码”。它是一个16位的代码，我们可以用它表示216 = 65536个不同的字符。
统一码是由统一码联盟和ISO(国际标准化组织)共同开发的。

EBCDI代码

EBCDI表示扩展二进十进制交换码。此代码是由IBM公司开发的。它是一个8位的代码，所以我们可以用EBCDI代码表示28 = 256个字符。这包括所有的字母和符号，如26个小写字母(a - z)， 26个大写字母(a - z)， 33个特殊字符和符号(如!@ # $ etc)， 33个控制字符(* - + /和%等)和10个数字(0 - 9)。

在EBCDI代码中，8位代码的数字由前面加1111的8421 BCD代码表示。

回到顶部