二维码纠错原理

/ 0评 / 0

前言:今天坐车的时候看到座位上有个被污染二维码,然后发现依然被识别,心里纳闷这二维码究竟是一个什么纠错原理?

Reed-solomon codes

在网上搜寻一番,发现二维码通过RS码进行纠错。关于RS码,维基百科是这么定义的:

里德-所罗门码(里所码,Reed-solomon codes,简称RS codes)是一种前向错误更正的信道编码,对由校正过采样数据所产生的有效多项式。编码过程首先在多个点上对这些多项式求冗余,然后将其传输或者存储。对多项式的这种超出必要值得采样使得多项式超定(过限定)。当接收器正确的收到足够的点后,它就可以恢复原来的多项式,即使接收到的多项式上有很多点被噪声干扰失真。

好了,说人话:任意k个确定点可以表示一个阶数至少为k-1的多项式,比如我们只需要16个点就可以确定这个多项式,但是可以发送25个点的数据,所以我们可以在其它点对这个多项式求冗余,哪怕25个点里有几个点缺失了,也可以通过剩余的点去反推出最初的多项式。

二维码纠错能力

二维码纠错分为四个级别:

纠错能力越高,所占用的数据量越大,二维码尺寸越大。

至于纠错比例是如何计算的呢,我们举个例子:
例如,需要编码的码字数据有100个,并且想对其中的一半,也就是50个码字进行纠错,则计算方法如下。纠错需要相当于码字2倍的符号(RS编码),因此在这种情况下的数量为50个×2=100码字。因此,全部码字数量为200个,其中用作纠错的码字为50个,所以计算得出,相对于全部码字的纠错率就是25%。这一比率相当于QR码纠错级别中的“Q”级别。

《二维码的生成细节和原理》是左耳朵耗子陈皓大大的文章,写的非常棒。关于二维码的生成细节可以看这篇文章,我这里就不献丑了。

评论已关闭。