汉明码如何纠错(汉明码纠错能力)

汉明码如何纠错

TPC是“事务处理性能委员会”、“ 传输功率控制”的简称。另外，TPC应用在炼钢行业，是鱼雷罐车的意思，用于装铁水的车子。应用在船舶行业则表示每厘米吃水吨，TPC=ρA/100。

tpc是什么

02

Turbo乘积码因其具有接近香农限的译码性能和适合高速译码的并行结构,已成为纠错编码领域的研究热点。Turbo乘积码的分量码一般由扩展汉明码构造而成。当Turbo乘积码采用扩展汉明码作为子码时,随着信噪比的提高,码字的最小码重对误帧率的影响会逐步增大

汉明码纠错能力

香农提出了信道编码定理，并在其证明中引用了三个基本条件：

采用随机编码方式;

码字长度趋于无穷大;

采用最大似然译码算法。

一个随机选择的码以很高的概率为好码，对于随机码的最大似然译码，其译码复杂度G与所传输的信息比特数呈指数关系，即为G=exp（NR），随机码的误码率上限为以Pe～G-Eb（R）/R，误码率随着码长N趋于无穷大而趋向于0的同时，译码复杂度以指数增长，可见随机码在实际系统里其实并不实用。

由于信道编码定理证明的非构造性，并没有给出如何构造逼近香农容量限的编码方法，构造一个逼近香农容量限的纠错码成了众多学者争相研究的课题，并逐渐形成了信息论的一个重要分支—信道编码理论。

从构造方法上看，纠错码可分为分组码和卷积码两大类。在20世纪50年代到60年代，人们主要研究了线性分组码。这类编码以代数中的群论、域论等理论为数学基础，利用各种代数方法设计好的纠错码，并研究与之相适应的译码算法。

第一个分组码是1950年发现的能纠正单个错误的汉明（Hamming）码。1950年汉明（Hanmming ．R．W）发表的论文《检错码与纠错码》是开拓编码理论研究的第一篇论文，考虑在计算机中纠正单个错误。汉明码（7，4），码率为4/7，需要3个监督位，码率不高，同时纠错能力有限，只能纠正单一错误。

M．Golay针对汉明码的缺点提出了性能更好的格雷（Galay）码，Golay发现了两种编码，一种是二元Golay码，采用12个数据比特，11个校验比特为一组，能纠正3个错误。第二种是三元Golay码，以三进制数为运算域，6个数据符号，5个校验符号为一组，可以纠正2个错误。

这两种码基本原理相同，都是将q元符号按每k个分为一组，然后通过编码得到n-k个q元符号作为冗余校验符号，最后由校验符号和信息符号组成有n个q元符号的码子符号，编码码率为r=k/n。

Muller在1954年以布尔逻辑代数方式提出了Reed．Muller码（RM码），它比Hamming码和Golay码好的地方是它可以改变码字大小和纠错能力，是Reed在Muller基础上得到的一种新的分组码，也是继格雷码之后提出的最主要的一类分组码。

继RM码之后，Prange于1957年又提出了循环码的概念。循环码实际上也是一类分组码，但是它的码字具有循环移位特性，即码字比特经过循环移位以后仍然是码字集合中的码字。这种循环结构使码字的设计范围大大增加，同时大大的简化了编译码结构。

循环码的一个非常重要的子集就是分别由Hocquenghem在1959年以及Bose和Ray—Chuadhuri研究组在1 960年几乎同时提出的BCH（Bose Chuadhuri Hocquen曲em）码，CH码的码字长度为n=qm-1，其中m为一个整数。二元BCH码（q=2）的纠错能力限为，t《（2m-1）。

1960年Reed和Solomon将BCH码扩展到非二元（q》2）的情况，得到了RS（Reed．Solomon）码。RS码的最大优点是其非二元特性可以纠正突发错误并日．它也能纠正随机错误。

但直到1967年Berlekamp给出了一个非常有效的译码算法之后，RS码才在实际系统中崭露头角，比如在CD播放器、DVD播放器以及CDPD（Cellular Digital Packet Data）标准中都得到了很好的应用。

上述讨论的这些都是分组码，分组码存在一些不足，应用受限。首先，必须是按帧传输、按帧译码，这样在帧长较长时会带来一定的时延。其次，要求准确的帧同步，这样才能准确译码。多数分组码要求解调器的硬判决输出，这样又会带来一些判决误差，影响性能。此外，分组码的译码方法通常都采用大数逻辑译码和捕错译码，其译码复杂度与码长成指数关系，码长越长，译码复杂度越大，而且上升趋势很快，所以基本上不实用。

1955年，Elias等人首先提出了卷积码。卷积码不是将数据分割成不同的分组，而是通过移位寄存器将校验比特加入输入数据流中。每n比特输出是当前k比特输入和寄存器中的m比特的线性组合，每次输出总的比特数与约束长度k有关，其码率为存一次编码间隔中数据比特k与输出比特数n之比。

卷积码与分组码不同在于它在编码的过程中引入了寄存器，增加了码元之间的相关性，在相同的复杂度下可以获得比分组码更高的编码增益，但是这种相关性同时也增加了分析和设计卷积码的复杂性。

随着人们对卷积码研究的深入，在卷积码的译码算法方面出现了序列译码算法、门限译码算法和维特比（Viterbi）译码算法。

维特比（Viterbi）译码算法的出现，使卷积码逐渐成为研究和应用的重点，以后出现的TCM（栅格编码调制）技术进一步确立了卷积码在纠错码应用中的主导地位，特别是在通信系统中得到了极为广泛的应用。

汉明码纠错过程解析

FSK 信号：S(t)=cos(ω0t+2πfi·t)

在通信信道FSK 模式的基带信号中传号采用fH 频率，空号采用fL 频率。在FSK 模式下，不采用汉明纠错编译码技术。调制器提供的数据源有：

1、外部数据输入：可来自同步数据接口、异步数据接口和m序列；

FSK正交调制器结构

2、全1码：可测试传号时的发送频率（高）；

3、全0码：可测试空号时的发送频率（低）；

4、0/1 码：0101．．交替码型，用作一般测试；

5、特殊码序列：周期为7的码序列，以便于常规示波器进行观察；

6、m序列：用于对通道性能进行测试；

汉明码纠错代码

是一样的，都是同一种纠错码。

纠错码(error correcting code)，在传输过程中发生错误后能在收端自行发现或纠正的码。仅用来发现错误的码一般常称为检错码。为使一种码具有检错或纠错能力，须对原码字增加多余的码元，以扩大码字之间的差别 ，即把原码字按某种规则变成有一定剩余度（见信源编码）的码字，并使每个码字的码之间有一定的关系。

汉明码纠错原理

图灵奖（Turing Award），全称A.M.图灵奖（ACM A.M Turing Award），是由美国计算机协会（ACM）于1966年设立的计算机奖项，名称取自艾伦·麦席森·图灵（Alan M. Turing），旨在奖励对计算机事业作出重要贡献的个人 。图灵奖对获奖条件要求极高，评奖程序极严，一般每年仅授予一名计算机科学家。图灵奖是计算机领域的国际最高奖项，被誉为“计算机界的诺贝尔奖”。

图灵奖一般在每年3月下旬颁发。从1966年至2020年，图灵奖共授予74名获奖者，以美国、欧洲科学家为主。2000年，华人科学家姚期智获图灵奖，是华人第一次也是唯一一次获得图灵奖。

图灵奖获得者

1966年艾伦·佩利高级程序设计技巧，编译器构造。

1967年莫里斯·威尔克斯存储程序式计算机EDSAC，EDSAC 2，程序库。

1968年理查德·卫斯里·汉明数值方法，自动编码系统，错误检测和纠错码。

1969年马文·闵斯基人工智能。

1970年詹姆斯·维尔金森数值分析，线性代数，倒退错误分析。

1971年约翰·麦卡锡人工智能。

1972年艾兹格·迪科斯彻程序设计语言的科学与艺术。

1973年查理士·巴赫曼数据库技术。

1974年高德纳算法分析、程序设计语言的设计、程序设计。

1975年艾伦·纽厄尔, 赫伯特·西蒙人工智能，人类认知心理学和列表处理（list processing）。

1976年迈克尔·拉宾, 达纳·斯科特非确定性自动机。

1977年约翰·巴克斯高级编程系统，程序设计语言规范的形式化定义1978年罗伯特·弗洛伊德设计高效可靠软件的方法学

1979年肯尼斯·艾佛森程序设计语言和数学符号，互动系统的设计，运用APL进行教学，程序设计语言的理论与实践。

1980年东尼·霍尔程序设计语言的定义与设计。

1981年埃德加·科德数据库系统，尤其是关系型数据库。

1982年史提芬·古克计算复杂度。1983年肯·汤普逊, 丹尼斯·里奇UNIX操作系统和C语言。

1984年尼克劳斯·维尔特程序设计语言设计、程序设计。

1985年理查德·卡普算法理论，尤其是NP-完全性理论。

1986年约翰·霍普克洛夫特, 罗伯特·塔扬算法和数据结构的设计与分析。

1987年约翰·科克编译理论，大型系统的体系结构，及精简指令集（RISC）计算机的开发。

1988年伊凡·苏泽兰计算机图形学。1989年威廉·卡韩数值分析。

1990年费尔南多·考巴托CTSS和Multics。

1991年罗宾·米尔纳LCF，ML语言，CCS。

1992年巴特勒·兰普森分布式，个人计算环境。

1993年尤里斯·哈特马尼斯, 理查德·斯特恩斯计算复杂度理论。

1994年爱德华·费根鲍姆, 拉吉·瑞迪大规模人工智能系统。

1995年曼纽尔·布卢姆计算复杂度理论，及其在密码学和程序校验上的应用。

1996年阿米尔·伯努利时序逻辑，程序与系统验证。

1997年道格拉斯·恩格尔巴特互动计算。

1998年詹姆斯·尼古拉·格雷数据库与事务处理。

1999年弗雷德里克·布鲁克斯计算机体系结构，操作系统，软件工程。

2000年姚期智计算理论，包括伪随机数生成，密码学与通信复杂度。

2001年奥利-约翰·达尔, 克利斯登·奈加特面向对象编程。

2002年罗纳德·李维斯特, 阿迪·萨莫尔, 伦纳德·阿德曼公钥密码学（RSA加密算法）。

2003年艾伦·凯面向对象编程。

2004年文特·瑟夫, 罗伯特·卡恩TCP/IP协议。

2005年彼得·诺尔Algol 60语言。

2006年法兰西斯·艾伦优化编译器。

2007年爱德蒙·克拉克, 艾伦·爱默生, 约瑟夫·斯发基斯开发自动化方法检测计算机硬件和软件中的设计错误。

2008年芭芭拉·利斯科夫编程语言和系统设计的实践与理论。

2009年查尔斯·萨克尔帮助设计、制造第一款现代PC。

2010年莱斯利·瓦伦特对众多计算理论所做的变革性的贡献。

2011年朱迪亚·珀尔通过概率论和因果推理对人工智能领域作出的根本性贡献。

2012年莎菲·戈德瓦塞尔, 希尔维奥·米卡利在密码科学领域里，于复杂理论的基础之上，做出变革性工作；并领先发展出新的具有数学可证明性的有效验证机制。

2013年莱斯利·兰波特对于分布式及并形系统的理论与实践具有基础性贡献，尤其是诸如因果逻辑时序（causality and logical clocks）、安全性与存活度（safety and liveness）、复制状态机（replicated state machines）及循序一致性（sequential consistency）等理论概念的发明。

2014年迈克尔·斯通布雷克对现代数据库的概念和实践作出的根本性贡献。

2015年惠特菲尔德·迪菲, 马丁·赫尔曼发明迪菲-赫尔曼密钥交换，对公开密钥加密技术有重大贡献。

2016年蒂姆·伯纳斯-李发明了万维网、第一个浏览器和使得万维网得以扩展的基础协议及算法。

2017年约翰·轩尼诗, 大卫·帕特森开创了一种系统的、定量的方法来设计和评价计算机体系结构，并对微处理器行业产生了持久的影响。

2018年约书亚·本希奥, 杰弗里·辛顿, 杨立昆深度学习。

2019年艾德文·卡特姆, 帕特里克·汉拉恩对于3D计算机图形学的基本贡献，以及这些技术对电影制作和其他应用中的计算机生成图像（CGI）的革命性影响。

2020年阿尔佛雷德·艾侯,杰弗瑞·乌尔曼对程序语言实现的基础性算法和理论的贡献。