大多数人钱包里都会有张「这个月爽了不管下个月哭」的信用卡,每张卡上都会有一串16位的卡号,这串数字是独一无二的,银行只认数字不认脸,这串数字当然不会是随机摇号给你的,它们有自己的规律。

这里是一张火星银行和煎蛋联合发行的「刷爆超载鸡」系列信用卡卡面:

[-]

开头一些数字表示的是这张卡的类型,代表你是「威士」,还是「万事达」,或者是「美国运通」……

[-]

表格左边是常见的信用卡品牌,右边是相应的数字前缀。(你可以拿出磁条刷毛的卡片对照一下)

检查位

信用卡号,经常需要被输入、扫描、传输和调取。这些过程都有出错的可能,特别是一得瑟就手潮的地球人……钱数上的事情可不敢开玩笑,所以最后一位作为校对(检查数字)。

普通的16位数字信用卡号,前15位是发卡行定的,但是最后这一位,是通过前15位,用某种算法算出来的。

[-]

这最后一位没法挑,因为它是算法确定的。这个算法是由 IBM 的工程师 Hans Peter Luhn 在1954年发明的。当时被申请为专利,现在已经公开,进入公共知识领域,成为国际标准组织的一项标准:ISO/IEC 7812-1。

很明显,就靠一个数字,是不能保证检测到所有错误的(命中的可能性是1/10),但 Luhn 算法非常智能,它能检测到任何一位的错误(输错一个数字),比如把上面这个卡号的9和6互换换成6。它也能检测到几乎所有成对交换的数字。这些都是人们输入卡号时候,经常犯的错误。所以校对码还是起到了不小的作用。

Luhn 算法

Luhn 算法是基于「模运算」和「数根法则」的。

Luhn 是 mod 10 (模10算法):

[-]

计算得到「检查位」数字的过程是这样的:

从右侧开始,偶数位数字都乘以2,如果结果是一个2位数字,则把这个两位数字相加,得到一个一位数字(这就叫数根,不可能出现19的情况)。然后加在一起得到一个结果

然后我们把所有奇数位上的数字相加,得到一个结果。

把这两个结果再相加(煎蛋卡的结果是67)。然后需要加上一个数字,使它能够被10整除,这里,我们需要加上·3·。

545762389823411 3
哒哒~ 这个 3 就是我们煎蛋卡的校对码啦 ♂( ̄▽ ̄)/

校验码的其他应用

检查位的数字,是常用的校验方法,检查输入的数字是否符合格式要求,避免简单的输入错误,或者对付一些想碰碰运气能不能猜对卡号的呆子……。

以下是一些同样编入校对码的场合(不是所有都是基于 Luhns 算法的):

车辆识别号、条形码、书刊杂志的ISBN号、澳大利亚的税号、匈牙利的社保号、美国银行的中转码……

对于好学的蛋友们,除了 Luhn 算法,世界上还有其他的校验码算法。比如 Verhoeff(1969) Damm algorithm(2004)。他们除了和 Luhn 算法一样,可以检测单位错误以外,还可以检测「任意位数成对交换」,还有一些算法可以扩展到除数字意外的文本内容的校验。

奇偶校验位

「数字校验」的概念由来已久,早年计算机刚发明不久,内存的可靠性还不如今天,计算机工程师需要一种方法来检测硬件错误。

解决之道来自于「奇偶」的概念。计算机中,一字节由8个比特组成,任何情况下,每一位上为1的总数不是偶数,就是奇数。如果是偶数,则「奇偶校验位」为0,反之则为1。

每次在硬件层面读取数值的时候,奇偶校验码就会被生成一次,如果校对发现出错,程序就会抛出一个错误。你可以很清楚的看到变动任何一位都会翻转校验码的结果。但是奇偶校验码不会告诉你,是具体哪个位置上出错了(也有可能是奇偶校验位本身错了!)。

现在 RAM 芯片的可靠性已经大大增强,大部分的 PC 机已经不支持带奇偶校验的内存条。但是高端服务器和一些关键岗位上的电脑(银行,发电厂之类)还是配备了奇偶校验的保护措施。刚才说了,奇偶校验无法告诉你是哪位错了,所以它不具备纠错能力,于是工程师在这些关键场合,开发了一种叫做 ECC(Error-Correcting-Code-memory)的技术。

ECC 内存的工作原理更加复杂。ECC 给每一块存储区的数据编码,增加的位用来重建数据。它能够检测到任何「一位」的错误,或者两个同步位的错误,更重要的是,它能纠正所有「一位」的错误,把正确的数值写回去。但是 ECC 在每一位,都需要更多的奇偶校验位(意味着更贵)。

ECC 的数学很复杂,本小编就不在这里不懂装懂了,但 ECC 更依赖冗余和排序算法。如果有好学的蛋友,请移步学习 Reed-Solomon Error Correction。 欢迎学成之后,欢迎投稿给大家讲讲呗。

现在给大家看一下 ECC 校验的基本原理,假设下图中有一个未知位,但是其他信息都是正确可靠的,而且我们知道我们在用「偶数校对」,这样我们就能恢复迷失的这位(这里应该是0)。

磁盘冗余整列(RAID)

最后一个「容错机制」例子就是RAID存储技术。

在硬盘拷数据的时候右腿乱抖腿,其他人都白眼看着你,因为计算机最脆弱的部分就是硬盘数据传输。如果你继续眼看天花板,换作左腿乱抖,只能说你这人……图样图森破,人生里还没有经历过硬盘数据崩坏的苦痛。

存储在硬盘上的数据其实是非常脆弱的,所以需要冗余技术。其中最简单的一个办法就是做一份镜像,这的确有效,但缺点是你需要一倍的硬盘。

[-]

还有一种更加经济的方法,就是用奇偶校验的办法进行数据编码。基本理论是这样的,假设说一个硬盘有出错的可能,但是两个硬盘同时出错的概率很小(这还是需要一点人品的……),如果其中一个出错了,那么你可以利用冗余机制,继续工作,同时你可以把坏掉的硬盘换掉,新硬盘上岗以后,它就可以重建数据并恢复校对码,继续工作并提供保护,而且整个过程里,你不需要宕机。

RAID 的全称是「Redundant Array of Inexpensive Disks」, 意思是硬盘比起现在来,那时候是「又贵又不靠谱的东西」,但是现在是便宜了,还是相对的不靠谱。设计的初衷,就是用相对便宜的硬盘组成阵列,拼的就是「你们不可能商量好一起挂掉的对吧?!」。虽然看上去要用很多硬盘,但总体成本还是优于单个高性能的,但也就靠谱一点点的硬盘设备。

看上去就和安全网络一样。

今天,随着可靠性和技术的进步,我们还是需要这种安保措施,但这只是最后一道防线,不是标准的安全措施。为了提醒大家注意这点,行业上已经把 RAID 的定义改为(Redundant Array of Independent Disk): 大量独立的硬盘的冗余阵列,其实吧,说成「穷人的磁盘阵列」就可以了。

本文译自 datagenetics,由 Junius 编辑发布。

[ 广告 ]
赞一个 (7)

PREV :
NEXT :