🈁 🏙️ 👰🏾 编码消息时纠正多个错误 🎾 👨🏼 🙆🏾

在信息系统中，通信或计算网络中消息的交换伴随着环境或入侵者的干扰影响，这导致出现信号失真和数字传输期间的符号错误。使用纠正代码可以对付这种现象。早些时候，我描述了汉明代码，并展示了如何解决代码字中的单个错误。自然地，出现了关于存在大量错误的情况的问题。今天，我们将考虑一个码字中两个错误（多重错误）的情况。一方面，理论上的一切或多或少都是简单易懂的，但另一方面，它一点也不明显。该材料的介绍基于E. Berlekamp的作品。

理论规定

在消息中使用有组织的冗余的想法使R.汉明开始构建此处描述的纠正代码。线性校正（n，k）码的特征是校验（m×n）矩阵H.矩阵的要求很简单：行数与校验符号数一致，其列数必须不为零，并且所有列均应不同。此外，列值通过作为最终字段元素的单词字符描述了码字中所占据的位置编号。

通常，解码器使用针对该单词计算的校正子计算来确定发送的单词是否有错误。校正子等于此矩阵的列之和乘以误差向量的成分。如果H包含m行，并且该代码允许您纠正单个错误，则块（代码字）的长度不超过

n \leq 2^{m} - 1

$n≤2^m-1$ 。同样重要的是码字彼此之间所需距离的可行性。

汉明码达到此限制。汉明码字的每个位置都可以用与矩阵H的对应列重合的二进制向量编号。在这种情况下，校正子将直接与发生错误的位置编号（如果只有一个错误）或与数字的二进制和（如果有多个错误）相一致。

向量编号是一个非常富有成果的想法。此外，我们将假设

n \leq 2^{m} - 1

$n≤2^m-1$ 及该字的第i个位置的编号我。

二进制编号（即这种表示）称为位置定位器。假设您要修复所有双重和单一错误。显然，这将需要大量的代码冗余，即矩阵H必须具有更多的行（两倍）。因此，我们将形成一个具有2m行和

列，并且是合理的选择不同的列。对于前m行，我们将采用汉明码的前一个矩阵。这些是词空间的基本词向量。例1 令m = 5且n =31。奇偶校验矩阵H的形式为：获得校正双错误的（n，k）码：对于矩阵中指示的函数fj（ξ），希望有一个映射本身的5维向量集。当且仅当函数f为双射（置换）时，矩阵的最后5行才会定义汉明码。如果前5行和后5行分别允许您更正单个错误，那么也许它们可以一起使您更正两个错误。

n \leq 2^{m} - 1

$n≤2^m-1$

为了找到所需的函数fj（ξ），我们必须学会加，减，乘和除以二进制5维向量，并用度为4的多项式表示它们。

示例2

00000←→0

00010←→1

00011←→x

...

此类多项式的和与差对应于矢量的和与差： 0±0 = 0、0±1 = 1、1±0 = 1、1±1 = 0，±符号具有在二进制情况下，含义相同。乘法不是这样，乘法结果的指数可以超过4。示例3

11011 \leftarrow\to х^{4} + х^{3} + х + 1

$11011 ←→ ^4 +^3++1$

(х^{3} + х + 1) х^{4} + х^{3} + х + 1) = х^{7} + х^{6} + х^{5} + 3 х^{4} + 2 х^{3} + х^{2} + 2 х + 1 =

$(^3++1)^4+^3++1)=^7+^6+^5+3^4+2^3+^2+2+1=$

= х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1

$=^7+^6+^5+^4+^2+1$ 。

需要一种降低大于4

的次数的方法，这种方法被称为（减少）以5的不可约多项式M（x）为模的残差的构造。该方法包括除以除法后的乘积从多项式到余数的转换

M (x) = x^{5} + x^{2} + 1

$M(x)=x^5+x^2 + 1$

所以

或

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 = (х^{2} + х + 1) (х^{5} + х^{2} + 1) + х^{3} + х^{2} + х

$^7+^6+^5+^4+^2+1 =(^2+ + 1)(^5 +^2 +1) +^3 +^2 +$

≡符号显示为“ comparable to”。通常，A（x）≡a（x）mod M（x）当且仅当存在多项式C（x）使得 A（x）= M（x）C（x）+ a（x）多项式的系数以模2的形式减少： A（x）≡a（x）mod（2，M（x））。

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 \equiv (х^{3} + х^{2} + x) m o d (х^{5} + х^{2} + 1) .

$^7+^6+^5+^4+^2+1 ≡(^3+^2 + x)mod(^5 +^2 +1).$

比较的重要属性

如果a（x）≡A（x）mod M（x）和b（x）≡B（x）mod M（x），则

a（x）±b（x）≡A（x）±B（x ）mod M（x）和

（x）b（x）（x）B（x）mod M（x）。

而且，如果多项式a（x）和A（x）的次数小于M（x）的次数，则从公式

a（x）≡A（x）mod（2，M（x））得出a（x） = A（x）。

度数degM（x）有2种不同的残基类别-即，与小于m的不同多项式一样多，即可以有多少个不同的划分残基。划分更加困难。

除法算法

对于数字。

对于给定的a和M，存在唯一定义的数字q和A，使得a = qM + A，0≤A≤M，

对于具有来自给定字段的系数的多项式。

对于给定的（x）和M（x），存在唯一定义的多项式q（x）和A（x），使得a（x）= q（x）M（x）+ A（x），degA（x ）<deg M（x）。

欧几里得算法提供了多项式除法的可能性。

对于数字，此处描述了扩展GCD的示例。

对于给定的a和b，存在数字A和B，使得aA + bB =（a，b），其中（a，b）是数字a和b的GCD。

对于具有给定字段系数的多项式。

对于给定的a（x）和b（x），存在多项式A（x）和B（x）使得

a（x）A（x）+ b（x）B（x）=（a（x），b （X）），

其中（a（x），b（x））是最大程度的a（x）和b（x）的归一化公因数。

如果a（x）和M（x）的公因数d（x）≠1，则除以（x）mod M（x）并不总是可能的。

显然，被（x）除等于与A（x）相乘。

由于如果（a（x），b（x））= 1 = GCD，则根据Euclid算法，存在A（x）和B（x）使得a（x）A（x）+ b（x） B（x）= 1，因此a（x）A（x）≡1mod b（x）。检查二进制多项式在场GF（

2^{5}

$2^5$ ），是通过所有小于deg M（x）的可能除数的直接除法来执行的。

例子4。

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ 除以x和（x + 1）

由线性除数。除法结果不为零。除以平方除数

..他们给出非零余额。度数≥3的除数不存在，因为它们的乘积等于度数≥6。因此，可以对多项式进行模加，减，乘和除

х^{2}, х^{2} + х = х (х + 1), х^{2} + 1, х^{2} + 2 х + 1 = (х + 1)^{2}, х^{2} + х + 1.

$^2 , ^2 +=( +1),^2 +1, ^2 +2 +1= ( +1)^2, ^2 + + 1.$

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ 。

我们转向寻找奇偶校验矩阵H的函数，该函数指定块长度为31，比率为21/31的双纠错码；31-21 = 10 = 2t-校验符号=10。此函数的根必须是代码字中错误位置的数量，即将位置编号替换为该函数后，它将变为零。

搜索功能

假设β1和β2是单词变形的字符（位置）的数字。使用数字β1和β2的二进制表示法，这些数字可以表示为模M（x）的残基类别，即建立度<5的对应关系βi→β ^（i）（x） -二进制多项式，

前5个测试条件确定β1+β2；第二组测试方程式必须确定f（β1）+ f（β2）。

解码器必须根据给定系统确定β1和β2：

函数f（x）应该是什么？

最简单的函数是与常数f（β）≡αβ（）modM（x）相乘。

但是ξ2=αξ1，即该系统的方程是相关的。新的五个测试条件不会给解码器任何新的东西。

类似地，函数f（β）=β+α不会改变这种情况，因为ξ2=ξ1。

尝试电源功能：先取

f (β) = β^{2}

$f(β) = β^2$ ... 此外，

这些方程式也是相关的，因为

ξ 1^{2} = (β 1 + β 2)^{2} = β 1^{2} + 2 β 1 β 2 + β 2^{2} = β 1^{2} + β 2^{2} = ξ 2

$ξ1^2 =(β1 + β2)^2=β1^2 + 2β1β2 + β2^2 = β1^2 + β2^2 =ξ2$

因此，第二个方程是第一个方程的平方。

试

f (β) = β^{3}

$f(β) = β^3$ ... 更改解码器方程式：

位置

ξ 2 = β 1^{3} + β 2^{3} = (β 1 + β 2) (β 1^{2} - β 1 β 2 + β 2^{2}) = ξ 1 (β 1 β 2 - ξ 1^{2}) .

$ξ2 =β1^3 + β2^3=(β1 + β2)(β1^2 -β1β2+ β2^2)=ξ1(β1β2-ξ1^2).$

因此，对于ξ1≠0，我们有

：β1和β2满足方程式。

因此，如果恰好发生两个错误，则它们的定位符满足该方程式。

由于给定的方程在模M（x）的二进制多项式字段中具有2个根，因此解码器始终可以找到两个所需的定位符。

如果仅发生一个错误，则β1=ξ1并且 $β1^2 = ξ2$ ...因此，在这种情况下，唯一的误差满足等式β+ξ1= 0或1+ξ1β ^-1 = 0。

最后，如果没有发生错误，则解码器始终执行解码，在这种情况下ξ1+ξ2= 0。

在实践中，不直接使用以误差定位符为根的多项式，而是直接使用以误差定位符为根的多项式，会更方便（实际上）。那些。是他们的乘法倒数。

显然，在不超过两个错误的情况下，解码器可以确定错误编号。如果三个或更多符号失真，则将发生解码错误或解码失败。

所以功能

f (x) = x^{3}

$f(x) = x^3$ 适用于构造二进制码的校验矩阵H的低五行，二进制码的码字长度为31，校验码为10，并纠正所有双精度错误。

前五个检查指定错误号的总和（S1）；后五项检查是错误号多维数据集的总和（S3）。

解码过程包括三个主要步骤：

检查每个接收到的码字，并计算S1和S3。
在σ（z）中找到错误定位符多项式；
计算根σ（z）的互取值，并更改结果单词对应位置的符号。

编码消息时纠正多个错误

理论规定

比较的重要属性

除法算法

搜索功能

More articles: