计算机网络 错误纠正码 – 汉明码




错误纠正码 – 汉明码

错误和错误纠正码

当比特在计算机网络上传输时,由于干扰和网络问题,它们容易受到损坏。损坏的比特导致接收方接收到伪数据,即错误。

错误纠正码 (ECC)是由特定算法生成的一系列数字,用于检测和纠正在嘈杂信道上传输的数据中的错误。错误纠正码确定已损坏的比特数量以及在算法限制内已损坏的比特位置。

ECC可以广泛分为两种类型−



  • 块码 − 将消息分成固定大小的比特块,为了错误检测或纠正,在块中添加冗余比特。

  • 卷积码 − 消息包括任意长度的数据流,通过对数据流应用滑动的布尔函数生成奇偶符号。

汉明码

汉明码是一种块码,能够检测两个同时出现的比特错误并纠正单个比特错误。它由R.W. Hamming开发用于错误纠正。

在这种编码方法中,源将冗余比特插入消息中。这些冗余比特是额外生成并插入到消息中特定位置的比特,以实现错误检测和纠正。当目标接收到该消息时,它将进行重新计算以检测错误并找到出错的比特位置。

用汉明码编码消息

发送方用于编码消息的过程包括以下步骤−

  • 步骤1 − 计算冗余比特的数量。

  • 步骤2 − 定位冗余比特。

  • 步骤3 − 计算每个冗余比特的值。

一旦冗余比特嵌入消息中,就会发送给用户。

步骤1 − 计算冗余比特的数量。

如果消息包含 m M个数据位, r r个冗余位被添加到它上面,以便 m r能够表示至少( m + r + 1)个不同的状态。这里,( m + r )表示(𝑚 + 𝑟)位位置中的一个错误位置,而一个额外的状态表示没有错误。因为, r r位可以表示2 r r个状态,而2 r r必须至少等于( m + r + 1)。因此以下方程式应成立 2 r ≥ m+r+1

第2步-定位冗余位。

即放置在2的幂位的r个冗余位,即1, 2, 4, 8, 16等处。在本文的其余部分中称为 _r 1 _ (位于位置1), _r 2 _ (位于位置2), _r 3 _ (位于位置4), _r 4 _ (位于位置8)等等。

第3步-计算每个冗余位的值。

冗余位是奇偶校验位。奇偶校验位是一个额外的位,使得1的数量要么是偶数,要么是奇数。两种类型的奇偶校验位是−



  • 偶校验 - 此时消息中的位数变为偶数。

  • 奇校验 - 此时消息中的位数变为奇数。

每个冗余位r i ,通常是根据其位位置计算奇偶校验位(通常为偶校验位)。它涵盖了其二进制表示中包含第i位为1的所有位位置,除了r i 位的位置。因此−

  • 1 位是所有二进制表示中,最低位排除 1 后包含 1 的数据位的奇偶校验位(3、5、7、9、11 等)

  • 2 位是从右边算起,位置为 2 的二进制表示中排除 2 的数据位的奇偶校验位(3、6、7、10、11 等)

  • 3 位是从右边算起,位置为 3 的二进制表示中排除 4 的数据位的奇偶校验位(5-7、12-15、20-23 等)

解码汉明码消息

接收器接收到传入消息后,执行重新计算以检测并纠正错误。重新计算的步骤如下:

  • 第一步 − 计算冗余位的数量。

  • 第二步 − 定位冗余位。

  • 第三步 − 奇偶校验。

  • 第四步 − 错误检测和纠正

第一步 − 计算冗余位的数量

使用与编码中相同的公式确定冗余位的数量。

2 r ≥ m + r + 1,其中 m 是数据位的数量,而 r 是冗余位的数量。

第二步 − 定位冗余位

冗余位放在 2 的幂位置,即 1、2、4、8、16 等。

第三步 − 奇偶校验

奇偶校验位是根据数据位和冗余位使用与生成码中的 c 的相同规则计算的。



c = parity(1, 3, 5, 7, 9, 11 等)

c = parity(2, 3, 6, 7, 10, 11 等)

c = parity(4-7, 12-15, 20-23 等)

第四步 − 错误检测和纠正

计算奇偶校验位的二进制值的十进制等价值。如果为0,则没有错误。否则,十进制值表示出现错误的位位置。例如,如果c 1 c 2 c 3 c 4 = 1001,则表示在位置9上的数据位(十进制等价值为1001)出现错误。将该位翻转以获取正确的消息。



计算机网络 精选笔记
计算机网络 IP地址格式和IP地址表计算机网络 总线拓扑与环形拓扑的区别计算机网络 总线拓扑与星形拓扑的区别计算机网络 电路交换和分组交换之间的区别计算机网络 星型与环拓扑之间的区别计算机网络 路由器与桥接器的区别计算机网络 ISDN综合数字网服务计算机网络 TCP连接终止流程计算机网络 ASA自适应安全设备功能计算机网络 Relabel-to-front算法计算机网络 服务器虚拟化类型计算机网络 ACL访问列表计算机网络 DSL数字用户线路计算机 基于操作系统的虚拟化计算机网络 CBAC基于上下文的访问控制计算机网络 克里斯蒂安算法计算机网络 SSID服务集标识符计算机网络 VoIP互联网语音传输协议计算机网络 CRAM挑战响应认证机制计算机网络 ACL扩展访问列表计算机网络 Li-fi与Wi-fi区别计算机网络 自反访问列表计算机网络 SONET同步光传输网络计算机网络 WPA Wifi保护访问计算机网络 WPS计算机网络 ACL标准访问列表计算机网络 时间访问列表BCD到七段数码管解码器计算机网络 以太网帧格式计算机网络 AAA认证授权和计费计算机网络 AD管理距离和AS自治系统计算机网络 什么是3D互联网计算机网络 4G移动通信技术计算机网络 无线传输媒介的类型计算机网络 数据表示计算机网络 网络标准计算机网络 经典寻址 vs 无类别编址计算机网络 BOOTP和RARP之间的区别计算机网络 传输失真是什么计算机网络 WiFi和互联网的区别计算机网络 链路状态路由是什么计算机网络 层设计问题计算机网络 无线局域网是什么计算机网络 中继器是什么计算机网络 数据链路层的设计问题是什么计算机网络 TCP和UDP之间的区别计算机网络 SAN存储区域网络的组成部分计算机网络 漏桶算法是什么计算机网络 IEEE 802.11无线局域网标准是什么计算机网络 密码学是什么计算机网络 奇偶校验位是什么计算机 主存储器是什么计算机网络 数据链路层中的帧封装计算机网络 错误纠正码 - 汉明码计算机网络 网关是什么计算机网络 纯Aloha和分槽Aloha的区别计算机网络 PPP 点对点协议计算机网络 路由器是什么计算机网络 令牌桶算法是什么计算机网络 Hub和Switch是什么计算机网络 组件计算机网络 OSI参考模型计算机网络 NIC网络接口卡是什么计算机网络 TCP/IP参考模型计算机网络 互联网的优点和缺点计算机网络 数据链路层中的错误检测和纠正计算机网络 交换机是什么计算机网络 ALOHA协议计算机网络 DAN概述计算机网络 应用交付网络ADN概述计算机网络 室外移动性模型高斯-马尔可夫计算机网络 OSPF开放最短路径优先协议计算机网络 DAN桌面区域网络概述计算机网络 ADN应用交付网络概述计算机网络 室外移动性模型高斯-马尔可夫计算机网络 OSPF开放最短路径优先协议计算机 RAM与ROM的区别计算机网络 OSI、TCP/IP和混合模型计算机网络 TCP报文首部中的选项字段计算机 基于操作系统的虚拟化计算机网络 IPv4头部的选项字段计算机网络 USB和Ethernet的区别计算机网络 Firewire和Thunderbolt的区别计算机网络 RSTP和PVST的区别计算机网络 DMZ和端口转发的区别计算机网络 CAT6和CAT6A之间的区别计算机网络 放大和重传之间的区别