由于在计算机中和通讯系统中信号传递非常频繁与广泛,因此如何防止传输错误是一件很重要的事情。当然,要解决这个问题可以有不同的途径。
其中的一个途径就是采用纠错码(ErrorCorrectingCode),即从编码上下功夫,使得二进制数码一旦在传递过程中出错,接收端的纠错码装置就能立即发现错误,并将其纠正。当二进制信号串从发送端发出时,需要按规定具有干扰能力的纠错码,然后才能发送出去。在接收端,当接收到二进制信号串后立即对收到的纠错码进行检查,检查是否失真,若失真则要负责纠正。这就是在计算机和数据通讯系统中被广泛采用的方法。
我们先举一个日常生活中的实例。如果你发出一个通知:“明天14:00--16:00开会”,但在通知过程中由于某种原因产生了错误,变成“明天10:00--16:00开会”。别人收到这个错误通知后由于无法判断其正确与否,就会按这个错误时间去行动。为了使收者能判断正误,可以在发通知内容中增加“下午”两个字,即改为:“明天下午14:00--16:00开会”,这时,如果仍错为:“明天下午10:00--16:00开会”,则收到此通知后根据“下午”两字即可判断出其中“10:00”发生了错误。但仍不能纠正其错误,因为无法判断“10:00”错在何处,即无法判断原来到底是几点钟。这时,收者可以告诉发端再发一次通知,这就是检错重发。为了实现不但能判断正误(检错),同时还能改正错误(纠错),可以把发的通知内容再增加“两个小时”四个字,即改为:“明天下午14:00—16:00两个小时开会”。这样,如果其中“14:00”错为“10:00”,不但能判断出错误,同时还能纠正错误,因为其中增加的“两个小时”四个字可以判断出正确的时间为14:00—16:00。
通过上例可以说明,为了能判断传送的信息是否有误,可以在传送时增加必要的附加判断数据;如果又能纠正错误,则需要增加更多的附加判断数据。这些附加数据在不发生误码的情况之下是完全多余的,但如果发生误码,即可利用被传信息数据与附加数据之间的特定关系来检出错误和纠正错误。具体地讲就是:为了使信源代码具有检错和纠错能力,应当按一定的规则在信源编码的基础上增加一些冗余码元(又称监督码),使这些冗余码元与被传送信息码元之间建立一定的关系,发送端完成这个任务的过程就称为误码控制编码;在接收端,根据信息码元与监督码元的特定关系,实现检错或纠错,输出原信息码元,完成这个任务的过程就称误码控制译码(或解码)。另外,无论检错和纠错,都有一定的误别范围,如上例中,若开会时间错为“16:00—18:00”,则无法实现检错与纠错,因为这个时间也同样满足附加数据的约束条件,这就应当增加更多的附加数据(即冗余码元)。我们已知,信源编码的中心任务是消去冗余,可是为了检错与纠错,又不得不增加冗余,这又必然导致传输效率降低,显然这是个矛盾。我们分析误码控制编码的目的,正是为了寻求较好的编码方式,能在增加冗余不太多的前提下来实现检错和纠错。
设信息以字(Word)为单位进行传输,每个字是一个m二进制数,每个二进制位称为码元(CodeLetter)。BG大游娱乐平台现在选择整数nm,构造一个一对一函数e:BB(其中B={0,1},B是所有的m位二进制数集,B是所有的n位二进制数集)。称e为(m,n)编码函数,通过它我们用一个n位二进制数代表一个m位二进制数。若bB,则称e(b)是代表b的码字(codeword),e(b)中的冗余码元将有助于检出或纠正传输过程中产生的误码。
其中z=x+y(k=1,2,…,n)(即是n位二进制数的按位模2加法)。则(B;)是一个群,00…0是运算*的单位元,每个元素的逆元是它本身(每个非单位元的阶是2)。同样(B;)也是一个群。
在计算机中经常使用的汉明码(HammingCode)就是一种群码。它就利用群的性质实现纠错。