寻找最大容错的扁平XOR 码

Posted on 2018/09/18 by qing

参考：

[1] Finding the most fault-tolerant flat XOR-based erasure codes for storage systems [PDF]

[2] Determining fault tolerance of XOR-based erasure codes efficiently [PDF]

本文内容主要来源于上面两篇文章，主要讨论暴力搜寻方法具有最大容错能力（most fault-tolerant）的扁平（Flat）XOR 码。

XOR 码是通过异或运算（exclusive OR）进行数据编码、解码和重建的编码方法，其生成矩阵可以用1/0 二进制矩阵表示。

扁平码是一种每个节点只保存一个符号（数据块），即生成矩阵的每一行（列）对应一个节点。k 和m 分别表示原始数据块个数和校验块个数的话，扁平码的生成矩阵是一个(k+m)×k 大小的0/1 矩阵。常见的RS 码是扁平码，但不是XOR 码；CRS 码不是扁平码，是XOR 码。

暴力搜索通过遍历所有的解空间（所有可能的(k, m) 编码），通过计算每个解的性质，找到满足条件的编码。一个(k+m)×k 大小的0/1 矩阵有2^((m+k)×k) 种可能的二进制矩阵，如果将编码限制在系统码中，则有2^(m×k) 种可能的二进制矩阵。

[2] 中介绍了一种ME （Minimal Erasures）算法，是暴力搜索的关键，该算法通过找到最小失效列表（Minimal Erasure List）寻找某种编码的最大容错能力。ME 算法会用到几个术语：

汉明距离（Hamming distance）：如果一个编码的汉明矩阵是d，那么它能容忍的最大失效节点少于d 个。

失效样式（Erasure pattern）：一组失效（的数据块）使得有一个原始数据块无法被恢复。

失效列表（Erasure list）：所有失效样式的集合。

失效矢量（Erasure vector）：长度为m 的矢量，其中第i 个元素是失效列表中长度为i 的失效样式个数的总和。比如 < 0, 0, 3, 7, …> 表示有失效列表中有3 个长度为3 的失效样式，有7 个长度为4 的失效样式。失效矢量中第d 个值是第一个非零值（小于d 的失效均可恢复）。

最小失效（Minimal Erasure，ME）是一种特殊的失效样式，它的每个失效元素都是必须的，如果去掉其中之一，它就不再是失效样式。

最小失效列表（Minimal Erausre List，MEL）是一个编码的所有最小失效的集合。

最小失效矢量（Minimal Erasure Vector，MEV）是一个长度为m 的矢量，其第i 个元素是MEL 中长度为i 的ME 的个数。

ME 算法具体详见[2] ，其输入是编码的生成矩阵（或Tanner 图），输出为MEL 和MEV。下图给出了 m < 8 和 k < 8 的结果。

下图是m < 11 和 k < 21 所有扁平XOR 码的最大汉明距离。

下图是m < 11 和 k < 21 所有扁平XOR 码中具有最优容错的个数。

下图是下图是m < 11 和 k < 21 所有扁平XOR 码中能够达到最大汉明距离的个数。

[1] 还介绍了如何减少搜索的解空间等优化的方法，并指出搜索算法有部分是Python 写的，用C 能够进一步提高运算速度，并增加m 和k 的值。

遗传算法解决数学等式（续）

Posted on 2018/08/03 by qing

之前的文章（http://blog.foool.net/2017/08/用遗传算法解决简单的数学等式问题/）中介绍了过如何使用遗传算法解决数学等式问题，即寻找满足等式

(a + 2b + 3c + 4d) – 30 = 0

的一组解。适应函数确定后，影响算法好坏的主要依赖于交叉概率（crossover ratio），变异概率（mutation ratio）、初始基因组大小（即用于交叉变异的基因个数）和基因初始阈值。基因初始阈值指的是基因的取值范围，比如等式中变量a/b/c/d 的取值范围，我在实验中限定变量为大小不超过100 的整数。下面给出本文的几个结论。

一、遗传算法也可以用于寻找唯一解

之前的文章中寻找的是四元一次等式的一个解，这个解的个数是无穷的，遗传算法能够找到一个解，但每次找到的解也不相同。但如果要用遗传算法解一个包含四个等式的四元一次方程组（唯一解）也是可行的，只是时间话的需要更长。比如遗传算法解四元一次等式平均需294 次迭代，解四元一次方程组需11400 次迭代（所有参数同之前的文章）。本文使用的四元一次方程组为：

(a + 2b + 3c + 4d) – 30 = 0

(2a + 2b + 2c + 2d) – 24 = 0

(3a + 1b + 7c + 1d) – 60 = 0

(4a + 3b + 2c + 1d) – 30 = 0

二、增加初始基因组大小有可能加速算法速度

增加基因组中基因数量，那么每次迭代/循环中的基因数量更多，可能出现解的概率增大。在以四元一次等式为例的实验中，增加基因组大小的确显著减少了迭代的次数，即使考虑了增加基因数目而带来的增量计算，算法仍减少了程序的整体运行时间。

三、增加初始基因组大小也有可能不能加速算法速度

有点调皮了，这个结论是和第二点结论是相左的，如在其他参数相同情况下，随着基因组大小增大，遗传算法在解四元一次方程组需要迭代的次数增加。

四、对于特定问题，参数大小影响算法性能大

下图是在基因组大小为18 时, 遗传算法1000 次测试四元一次等式求解所需要迭代次数的热力图，横坐标是变异率，从5% 到43%，纵坐标是交叉率，从5% 到70% 。热力图颜色范围是0-300，最深颜色表示300 次或300次以上迭代（比如在交叉率是70%，变异率是43%，实际迭代次数是9268次）。

综上，1.借助于适应函数，交叉、变异过程，遗传算法给出了一个在较大解空间快速求解的途径，但具体设计交叉、变异过程需要考虑特定问题；2.选取合适的参数极大影响了遗传算法性能，一般可以通过相似问题（复杂度更低）的参数选择作为参考（但是这种参考也不一定可靠，比如上面例子中，四元一次方程中增大基因组个数可以减少迭代次数，但在四元方程组中增加基因组个数却增加了迭代次数）。

自循环字符串/周期性字符串的判别和概率

Posted on 2018/07/06 by qing

问题来源：需要判断一个长度为N 的0/1 二进制字符串是自循环的概率是多少？自循环指的是一个字符串循环移位s 位仍然可以得到其本身，s 小于字符串长度。比如，010010 是自循环的，因为将这个字符串循环右移三个bits 字符串还是其本身。

通过自循环字符串特征很容易推导出：自循环字符串是周期性字符串，即字符串完全由若干个相同子串拼接得到，上面例子中重复的子串是 010。并且，自循环字符串移位得到其本身需要的最少步数s 和最小子串长度相同，也就是说，计算得到字符串最小重复子串也就得到了其自循环需要移位数s。

那么问题归结为如何找到一个周期性字符串的最小重复子串？

算法：令周期性字符串为S，那么SS 是两个S 的拼接，从SS 第二个字符开始，利用字符串匹配寻找S，如果SS 从第c 个字符开始包含了S 字符串，则S 的最小周期子串长度为c。下面是两个例子：

例子一：S = 010010

SS = 010010010010

0 1 0 0 1 0 0 1 0 0 1 0 不是S
0 1 0 0 1 0 0 1 0 0 1 0 不是S
0 1 0 0 1 0 0 1 0 0 1 0 是S

结束，最小子串长度为3，即010 。

例子二：S = abaaabaaabaa

SS = abaaabaaabaaabaaabaaabaa

a b a a a b a a a b a a a b a a a b a a a b a a
a b a a a b a a a b a a a b a a a b a a a b a a
a b a a a b a a a b a a a b a a a b a a a b a a
a b a a a b a a a b a a a b a a a b a a a b a a

结束，最小子串长度为4，即abaa 。

接着统计了下二进制字符长度（X轴）和周期性字符串个数/概率（Y轴）关系。

可见，自循环字符串个数和概率与其字符串长度有关，总的来说：

长度越长，包含的自循环的字符串个数越多，呈指数增加
长度越长，字符串可能是自循环的概率降低，呈指数下降
素数只有两个自循环字符串（全0，全1）
包含分解因子越多，越可能包含更多自循环字符串

Clay Codes — 从生成矩阵的角度来看

Posted on 2018/05/22 by qing

Clay Codes ( Clay Codes: Moulding MDS Codes to Yield an MSR Code ) 是FAST18 上提出的一种编码方法，文章地址，Clay 码能够将一般的MDS 码（最优容错）转化为具有最优修复的编码方法，具有以下性质：

Minimum Storage （最小存储开销，同经典RS码和最小存储再生码，MSR）
Maximum Failure Tolerance（最大容错，即 (n,k)-Clay 码可以容任意n-k 失效）
Optimal Repair Bandwidth （最优修复开销，能够达到理论最优值）
All-Node Optimal Repair （最小开销修复所有节点的数据，包括原始数据和校验数据）
Disk Read Optimal （最优磁盘读）
Low Sub-packetization （低分包数，即码字长度短）

首先介绍下Clay 码的设计思想，第二部分从生成矩阵的角度来看看Clay 码如何实现。

一 Clay 码的设计思想

1.1 术语

首先文章介绍了一些基础概念：

纠删码：纠删码将一段原始数据等分为k 份，进而编码为m 份，共计n=k+m 份，通过将这n 份数据分别存储在n 个不同的存储节点上，达到抵御数据丢失的风险。

标量码/向量码（Scalar code/Vector code）：标量码每个码字在每个节点上包含一个字节，向量码在每个节点上包含若干个字节，共同组合为一个超字节（superbyte），不同节点上超字节共同组成一个码字。

上图表示标量码，下图表示向量码。在磁盘阵列中，每个条带（stripe）也是横跨n 个节点，对应的一个码字，而码字中一个字节（标量码）或者超字节（向量码）则对应着条带中的一个数据块。一个(n,k) 标量码和向量码在生成矩阵中对应的是一个n×k 和nw×kw 矩阵，其中一个超字节包含w 个字节。

MDS 码：最大距离可分（Maximum Distance ）码是一种最优容错编码方法，即编码后的n 份数据最大可容忍任意m 份数据失效，原始数据也不会丢失。常见的RS、CRS、Evenodd、RDP 码都是MDS 码。

修复开销：修复开销指的是重建一个节点数据或单个数据块所需要的数据量（从磁盘读取、从网络传输的数据量）。在存储系统中，单点失效是常态，因此研究更注意单点失效的修复开销。

MSR 码：最小存储再生码（Minimum Storage Regenerating codes，MSR 码）是一类具有最小存储开销下的再生码。再生码是一类能够减少修复开销的纠删码。

原始数据量为M，再生码在每个节点存储的数据量为α。如果每个节点存储量最小，即α=M/k，那么这个再生码是MSR 码，和其他经典(n,k)-MDS 码存储开销相同。当一个节点失效，需要从剩余d<(n-1) 个节点中每个取β<α 数据完成修复，修复开销为dβ。当n-1 时，修复开销最小，为(n-1)α/m。

磁盘开销：再生码是网络编码研究者提出的，在数据修复时在网络上传输的数据量能够达到理论最小，但需要在磁盘上读取大量数据，进而计算得到少量修复数据进行数据修复，因此需要额外的磁盘访问和计算。Clay 码能够减少磁盘开销，即在网络上传输的数据就是从磁盘哦读取的数据。

系统码：系统码编码后保留了原始数据，非系统码编码后只有校验数据。实际存储系统中常见的是系统码，这样数据读取不用解码。

1.2 编码方法

下面以(n=4,k=2) 来介绍Clay 码，一种将一般MDS 码转化为MSR 码的方法。

Clay 是Coupled Layer 的结合，包含了Clay 码的两个特点：1 将MDS 码分层处理；2 分层之间耦合数据。

一个(4,2)-MDS 码编码后的数据有4 份，可以摆放成一个正方形。

四个(4,2)-MDS 码编码后的数据可以形成一个四层的棱柱，四棱柱的四个边对应着四个存储节点，边上的四个点所代表的数据存储于同一个节点。（下图a_0/b_0/c_o/d_0 都存在同一个节点）

耦合是将分层中不同数据进行线性组合，以实现最小修复开销。

图中被耦合的数据块用黄色表示，没有参与耦合的数据块用红色表示，两两耦合对应的数据块如上右图所示。如何选择耦合的数据块对文章中有也介绍，但为什么这样选择文章未提及。

下面谈谈什么是耦合，耦合即通过线性组合两个数据块，不管这两个数据块是原始数据块还是校验数据块。然后再将两个线性组合后的数据块（Coupled）取代两个原来未耦合的数据块（Uncoupled）。下图中(a_0, b_0)，[a_0,b_0] 表示的就是数据块a_0 和b_0 的线性组合。注意：实际中Clay 码在节点上存储的是耦合后的数据，这样才能保证Clay 码的最优修复。

两个数据块的线性组合可以表示为数据块的乘法，解耦同理，如果用C(p) C*(p)表示两个耦合的数据块，解耦即乘以解耦矩阵，

γ 为不等于0的值，使得矩阵（在对应的有限域）满秩即可，比如2。

1.3 最优修复单点失效

下面以一个节点的修复来展示Clay 的最小修复开销，(4,2) 编码最小修复开销为(n-1)α/m = 3α/2 = 6，这也是其他MSR 的最小理论修复开销。下图给出了原a_2 数据块所在节点的修复过程。

Clay 修复该节点失效只需要第二层和第三层的剩余数据块（如上图（中）所示），修复步骤如下：

两个耦合的数据块(b_3,d_1) 和[b_3, d_1] 解耦得到b3 和d1，如上图（右）
第二层通过b1，b3 的MDS 解码得到b_0, b_2，第四层MDS 解码得到d_0，d_2
利用第二层中[a_2, b_0] 和步骤2 得到的b_0 得到a_2，同理得到c_2；

简单推导可以发现其他三个节点也可以以最小开销完成数据修复。

1.4 系统码

需要注意的是Clay 码这时虽然满足了所有节点的最优修复，但耦合的过程中某些数据已经不再是系统码，因为某些原始数据已经线性组合为校验数据。作者因此提出了一种“耦合-编码-再解耦”的方式来保证Clay 码的系统性（systematic），如下图所示。

首先对原始数据进行耦合，经过MDS 编码后再解耦，这样原始数据还是原始数据，但校验数据不再是MDS 编码后的校验数据了。

但如果是这样理解的话，会存在一个问题：MDS 编码前，耦合的校验数据为空，导致一个原始数据和空数据耦合，那么解耦后的数据能延续刚才的最优修复么？

换个角度，如果耦合的两个数据块中有一个是原始数据，是不是可以选课合适的耦合方程来保证原始数据不发生变化，即数据块a，b 耦合后可以是a，xa+yb（a 是原始数据）或xa+yb，b（b是原始数据）的形式么？但如果需耦合数据都是校验数据块呢？

这几个问题可以通过生成矩阵的方法来解释。

二 Clay 码的生成矩阵

本节用生成矩阵这个工具来展示如何实现Clay 码，即生成(4,2)-Clay 码的生成矩阵并验证其最优修复性质。

首先利用Clay 码“耦合 – MDS编码 – 解耦” 的变换过程构建其生成矩阵。因为三个变换都是线性变换，所以可以用三个矩阵来代替。

注意：前面我们提到解耦矩阵和耦合矩阵是互逆的，这是针对两个需要耦合/解耦数据块而言的，本节所讲的耦合、解耦矩阵是针对所有数据块，且需要在中建添加MDS 编码过程，所以本节耦合、结构矩阵大小不同，更不互逆。

|G| 是Clay 码的生成矩阵，那么

|G| = |U|×|GM|×|C|

|U|是解耦矩阵，|GM| 是MDS编码的生成矩阵，|C| 是耦合矩阵。

首先从最简单的MDS 编码矩阵 |GM| 开始，一层MDS 编码生成矩阵是一个2×2 单位矩阵和2×2 校验矩阵组合得到的4×2 的生成矩阵（如下左图所示）。四层的MDS 编码矩阵如下右图（在生成矩阵右边标出了该行向量对应的数据块）。

为了使得一个码字中原始数据部分放在一起，可以进行一个对齐操作，即将单位矩阵放在上面，新的生成矩阵为|GM|。

根据所对应数据块位置和耦合规则，可以得到解耦矩阵 |U|，如下图所示。

因为MDS 编码后，有16个数据块，所以解耦矩阵|U| 大小为16×16。

耦合矩阵是一个8×8 大小的矩阵（因为四层MDS码有8 个原始数据块，|GM| 大小是16×8）。那么利用|G| 矩阵上半部分是单位矩阵可解出耦合矩阵|C|

|G| = [I P] = |U|×|GM|×|C| → |C| = |I+L×GP|^{-1}

耦合矩阵|C| 是 |I+L×GP| 的逆矩阵，L 是解耦矩阵|U| 右上分块矩阵，GP是MDS 编码生成矩阵|GM| 下半部分的校验部分。

下面介绍程序验证过程。首先是测试当λ=2 时，两个数据块的耦合和解耦矩阵。

当λ=2 时，计算得到的耦合矩阵|C| = |I+L×GP|^{-1} 为

MDS 码采用RS码，|GM| 为

耦合矩阵乘积为 |GM|×|C| 为

最终(4,2)-Clay 码生成矩阵|G|为

最后，用程序验证了这个矩阵的最优修复性质，具体而言，首先将该矩阵等分为4×8 的4个子矩阵，依次失效每个子矩阵，从失效子矩阵以外的矩阵中选取行向量重建该失效子矩阵，所需要选取的子矩阵的行向量个数即需要重建数据块的数量，验证发现所有子矩阵修复都只需要6 个行向量，达到了最小修复开销。

基于FPGA SoC 的内存系统中的纠错码

Posted on 2017/12/16 by qing

原文地址：https://www.altera.com/en_US/pdfs/literature/wp/wp-01179-ecc-embedded.pdf

原文名称：Error Correction Code in SoC FPGA-Based Memory Systems

下载地址：wp-01179-ecc-embedded

备注：本文是Altera 和Micron 科技的共同编写的技术白皮书。

本文分析了1. 软错误的潜在原因和影响；2. Altera 和Micron 提出的一种错误检测和纠错方法，能够使得嵌入式系统能够容忍这类软差错。

引言

不断进步的半导体工艺技术使得嵌入式系统集成度、功能和性能都在增加。然而，性能的增长也带了巨大的开销，高性能系统的一个负面影响就是必须花费更多精力去处理软差错。随着集成电路供应电压的下降，使得它更容易受到电磁和颗粒辐射的影响。随着嵌入式系统内存大小增大到百兆量级，自然界alpha 粒子导致的软差错可能会超出可接受的限度。另外，现代接口速度超过Gb 每秒，大量的噪声和抖动会造成数据在传输线上写入/读出外部内存时发生错误。

内存比特错误来源

1. 比特单元软错误

通常，被写入数据的比特单位都以电荷值表示其编程值。当向某比特单位写入新值时，将重新编程和强制电荷值变为新值。一般来说，只要基本要求满足，如供电正常，对于动态内存刷新方法有效，内存比特单元内的编程值总是确定的。

但是，存储的电荷值会受到射入内存系统外部电荷的负面影响。宇宙粒子和大气中的原子碰撞产生能量射线可能会影响到存储的电荷值。要使得内存比特单元值跳变，必须向其注入足够多的电荷才能使得其表示为一个错误的逻辑值。

宇宙射线中百分之十以上由高能alpha 粒子组成，它们能够穿透几米厚的混凝土。芯片封装材料在衰减过程中会释放出低能alpha 粒子，因为能量小，其传播的距离和影响也小。类似地，gamma 射线也是表现为宇宙射线的一种高能粒子，由自然界衰减造成。地球的大气环境对于宇宙射线和粒子是一个天然、有重要意义的屏障，但绝不是天衣无缝的。结果就是，在高海拔，如山顶上、航空系统，大气环境能够提供的保护更少，发生软错误的几率更高。

这类因为外来能量注入无意地修改内存比特单位中数值叫做单粒子翻转（single event upset， SEU）。这类错误是软错误，这类错误的原因不是因为设备的缺陷造成的，而是由于设备所在环境的外部干扰造成。一旦正确的数据因此发生重写，几乎不可能再次经历SEU而翻转回来。这类事件的可能性极小，并且随着内存容量增加而增大。

2. 硬件错误

硬件错误被被归类为功能性错误。这类错误往往是可重复的、持续性的。一个包含了内存设备的系统被制造出后，应该是没有故障的，但随着系统寿命的增加，这种状况可能发生改变。各种因素，如频繁的温度变化、电压、高湿度和物理压力，都可能会引起系统中部件的失效。这类错误可能会表现为一个内存单元或一个印制线缺陷导致的比特卡顿（bit stuck，某位比特单位读出、传输结果总是1或0）。

3. 传输错误

传输错误发生在内存比特单位和功能性单元之间的读写数据路径上。这类错误一般是因为系统中短暂地超过系统设计余量的抖动和噪声造成，因此它们与设计余量、使用系统部件质量和系统对所在环境的电能敏感度有关。

物理连接到外部内存的电感、电容数量和导线长度比片上系统（System-on-Chip，SoC）或者内存系统中的内部布线要高出几个数量级。不过，部件内部还是可能发生传输错误。Alpha 粒子和gamma 射线能够影响感应放大器和内存比特线，导致获取到错误的数据值。

图一：传输错误

4. 数据错误的影响

内存数据的损坏对于嵌入式系统的运行通常是致命的。在基于处理器的系统中，内存错误会导致指令或数据流中的值不正确。现代处理器会检测到非法指令，通常会迫使系统重新启动。数据流中的错误可能会导致程序流出轨，往往会导致非法访问受保护的内存。这些事件在桌面系统中表现为“死亡蓝屏”或“core dump”。

尽管在嵌入式系统中崩溃是令人讨厌的，但是想要有个替代方法也不是那么简单。没有立即检测出的错误可能会长时间滞留在系统中。由于错误的数据用于计算新数据，未检测到的内存错误可能会倍增。而一旦检测到错误的数据，错误的起点以及造成的后续影响将很难确定。

嵌入式系统通常运行时间较长，并不像在台式计算机那样频繁地重新启动。这给嵌入式系统带来了额外的缺点：错误将随着时间推移而累积。数据错误和系统崩溃的负面影响很多：异常行为的系统会令用户烦恼，让顾客感到不快；维护成本可能会增加，因为客户的投诉会触发对不可重现错误来源进行昂贵的调查；突然的系统故障可能会造成重型机器周围的不安全环境，而且安全系统中的错误可能会导致意外的系统访问后门。

5. 嵌入式系统中错误的可能性

硬错误率和传输错误率是许多变量的函数。在较大系统中对于这类错误的研究比较成熟，但研究结果并不能直接将应用于其他系统。另一方面，已有很多研究发布了软错误率（Soft Error Rate，SER）结果。举一个实际例子，一个有1GB 内存的嵌入式系统的平均故障间隔时间的范围在一年几次和几年一次。

MTBF 还应该考虑到该领域系统数量。系统供应商则应该考虑一个给定时间段内可能发生失效设备的总数。假设10000 台设备的MTBF 是十年，那么意味着平均每年都将有1000 台设备遭受一次单比特错误。

这种错误率的可接受性取决于应用领域。在高海拔使用的应用开发人员将关注由于宇宙射线造成的较高的SER。军事，汽车，高性能计算，通信和工业客户将更关注错误率导致的安全性和可靠性的下降。在消费领域，一年的MTBF 则有时可以被接受。然而在许多情况下，错误率造成增加维护成本和不满意的客户数量是推动解决方案的关键因素。

提高容错能力

1. 传输错误

Altera®SoC FPGA 支持高达533 MHz（1066 Gbps）的DDR3。 DDR3 接口规范以及SoC FPGA 与外部存储器器件中实现的方式保证了错误率可以忽略不计，因为于DDR 规范所限定的范围内具有可靠的电路板设计和抖动和噪声控制。

谷歌与多伦多大学合作进行的大规模研究以及斯坦福大学的另一项研究表明，被分析的所有系统中大部分错误仅是由系统的一个设备子集造成。这些错误很可能是由过度的抖动或噪声引起的，或可能与系统及其组件的质量不合格有关。

传输错误发生的概率会随着接口速度的增加而增大，比如DDR4 或更高。随着功耗降低和接口速度提高，电源层面的电压和信号电平也随之缩小，抖动和噪声越来越难以控制。

随着更高的接口速度而增加，例如为DDR4及更高版本所定义。随着功耗降低和接口速度提高，电源层面的电压和信号电平也随之缩小，抖动和噪声越来越难以控制。 JEDEC 指出，对于DDR4 和GDDR5 的下一代存储器规范，抖动和噪声的影响已经促使该规范允许在一定的误码率和简化设计，特性和鉴定之间权衡。任何需要容忍的误码率都将用一种有效的方法来纠正发生的错误。

2. 软错误

因为软错误是不可避免的，所以已研发出了一些方法能够使得系统对这些错误具有抵抗力。也就是说，当一个错误发生时，它能够被检测、校正并传输校正后的值，因此系统可不中断地运行。这个壮举是通过向内存数据段中添加字节实现的，那么加宽的数据段携带了足够的信息来检测和校正错误。数据字段中增加的比特越多，能够被校正的错误也就越多。这使得纠错成为成本和期望可靠性的函数。能够修正一个错误和检验出两个错误的纠错方法即具有成本效益，又被证明在嵌入式系统中提供了出色的错误恢复能力。这种在工业界被广泛应用的技术叫做纠错码（Error Correction Code，ECC）。

3. ECC 的基本实现

通过增加内存容量，并在进出额外的外部内存的通道上增加有限的组合逻辑可以实现ECC。逻辑部分用于ECC 编码，采用非常成熟的多项式汉明（Hamming）算法。一个ECC 比特产生器可以为正在存储的数据生成ECC 数据，并将ECC 数据和普通数据一起存储。ECC 检测和校正逻辑函数被插入在内存的输出端，当从内存读取数据，这个函数将检验ECC 数据和普通数据的组合。如果没有检测到错误，则直接传输普通数据而不做任何改变。如果检测到一个错误，它将纠正普通数据内的错误比特位，并返回纠正后的数据，可选择性地抛出一个异常标志。当检测到两个错误时，则抛出一个异常标识，让系统因地制宜地去响应这个事件。

图2：ECC 内存容量更大且增加额外的逻辑部件

4. ECC 优势

能够纠单错和检测出双错具有很多好处。虽然ECC 是由大内存的SER 问题推动的，但它也增加了抵御其他类型错误的能力。一个硬件单错，比如内存中的比特卡顿或印刷电路板上的不稳定连接，都能够被ECC 完全掩盖，同样单比特传输错误也同样能被解决。核心是ECC 可以校正一个数据段中的错误比特。也就是说，ECC 可以正确地处理系统中的多个错误，只要任意一个数据段中发生不超过一个比特的错误。

另一个好处ECC 逻辑能够指出系统的健康状态。当ECC 逻辑纠正了一个数据段中的单错，它还可以向处理器发送一个故障状态信号，以利于处理器采去与系统所需的可靠性相关的措施。这一手段将系统降级转化为可调度的维护任务，而不是响应意外的、致命的系统错误状况。基于启发式概率，附表分析了有ECC 和没有ECC 的系统的估计软错误模型，表明ECC 有效地增加了MBTF，使其从短于系统寿命增加到比宇宙寿命更长。

表1：ECC 使得容单错能力大大提高

图3：外部DDR 内存没有错误校正的软错误MTBF

Altera 和Micron ECC 解决方案

1. 外部DRAM 的ECC

为Altera SoC FPGA 的外部内存添加ECC 功能只需要增加内存数据带宽。生成ECC 比特、错误检测和校正的功能都已经内置到SoC FPGA 的内存控制器中，这样的话，虽然带宽变大，但内存具备了ECC 功能。此外，在SoC FPGA 和外部内存之间的数据通道上已经布置了ECC，因此在数据通道上也可以恢复某些传输错误。

具有16-bit 或32-bit 宽的数据通道的外部内存系统在SoC FPGA 和外存之间分别需要存储额外的6 或7 个ECC 存储位。对于这两种情况，Altera 架构简化为定义一个额外的1 字节的ECC 内存存储位。

2. ECC DRAM 的典型架构

一个由SoC FPGA 和外部存储器组成的现代嵌入式系统可能需要包含1 GB 的DRAM。为了实现这种系统的高性价比的32 位宽内存接口，一个典型的DRAM 可以包括并行配置的一个8位宽器件和两个16位宽器件的组合。

图4：典型的外部DDR 内存架构

3. ECC NAND 闪存

外部的NAND 闪存可以连接到SoC FPGA 器件，既可以作为一个存储引导配置的内存，也可以作为存储应用程序的文件系统。NAND 闪存对软错误非常敏感，并且经常需要ECC 保护。不同于外部DDR 内存将数据段带宽变宽，NAND 闪存提供额外的存储缓冲区来保存ECC 数据。ECC 所编码的数据块也更大，如512 或1024 字节，那么SoC FPGA 设备则能够校正高达24 比特的错误。尽管实现方式被调整为更适应NAND 闪存的一般错误模式，但恢复方法还是类似于常规的SRAM 和DRAM。

4. Altera SoC FPGA 的错误恢复

ECC功能内置于SoC FPGA器件中，用于大量片上内存实例。L2 缓存，临时RAM，FPGA 结构内部的内存和外围上作为数据缓存的内存都带宽加宽并装备上了ECC 产生器和逻辑校正器件。由于这些是内置的，使用ECC 功能不需要额外的成本。同样地，外部内存和NAND 闪存的ECC 也内置在SoC FPGA 中。数据和指令缓存在物理大小上相对较小，因此不容易发生软错误。因为它们需要高速运行，也为了读取L1 缓存时避免额外的延迟，系统使用更简单的奇偶校验方法。

FPGA 架构内的配置数据不是以增宽的数据段来组织的，因此也没有用ECC 校验。FPGA 架构内部有一个内置的硬件引擎，允许循环地检查配置数据的正确性，当检测到一个错误时会抛出一个异常标志。这种错误校正方法称作“擦洗（scrubbing）”，也是这类设备的一种工业标准方法。Altera SoC FPGA 具有支持系统级的错误恢复所需要的逻辑器件，并集成到设备中。通过仅扩展外部DDR 内存，可以获得对软错误和传输错误具有恢复能力的通用综合系统级方法。

图5：SoC FPGA 系统级的容错能力

总结

嵌入式系统中的内存可能受到宇宙射线的注入而导致比特位翻转，而过度的噪声和抖动也会导致传输错误，从而使得传输的数据不正确。虽然这种错误可能性很小，但随着内存容量、接口频率和带宽的增大，这类事件的可能性越来越成为挑战。系统级错误恢复能力日益成为高性能嵌入系统设计的考虑因素。Altera SoC FPGA 设备通过擦除（scrubbing）、奇偶校验和ECC 技术实现高容错能力。它能够很方便地为外部内存增加ECC 功能，特别是兼容了高性能系统中32-bit 位宽的外部DRAM 内存。增加ECC 实际上消除了内存对这些错误的敏感性，为系统级别的容错做出了重要贡献。

扩展阅读

“A Second Look at Jitter: Calculating Bit Error Rates,” Justin Redd, Maxim Integrated Products:
www.eetimes.com/electronics-news/4164171/A-second-look-at-jitter-Calculating-bit-error-rates
■ “Understanding the New Bit Error Rate DRAM Timing Specifications,” Perry Kelly, Agilent Technologies:
www.jedec.org/sites/default/files/Understanding%20BER%20based%20timing%20specifications%20Agilent%202011_1101.pdf
■ “DRAM Errors in the Wild: A Large-Scale Field Study,” Bianca Schroeder, University of Toronto, Eduardo Pinheiro and Wolf-Dietrich Weber, Google Inc.:
www.cs.toronto.edu/~bianca/papers/sigmetrics09.pdf
■ “Hard Data on Soft Errors: A Large-Scale Assessment of Real-World Error Rates in GPGPU,” Imran S. Haque, Vijay S. Pande, Stanford University:
http://cs.stanford.edu/people/ihaque/papers/gpuser.pdf
■ White Paper: Enhancing Robust SEU Mitigation with 28-nm FPGAs , Altera Corporation:
www.altera.com/literature/wp/wp-01135-stxv-seu-mitigation.pdf
■ On the Need to Use Error-correcting Memory,” Berke Durak:
http://lambda-diode.com/opinion/ecc-memory

Vim 常见问题（StackOverflow 高票问题）

Posted on 2017/08/23 by qing

问：如何退出Vim 编辑器？

答：点击 Esc 键，然后 :q 退出编辑器（或 :q! 不保存退出编辑器，或:q! 退出编辑器不保存，或 :x 等同于:wq 退出编辑器并保存)）。

问：如何快速缩进多行？

答：利用 > 命令， >5> 或者 5>> 缩进五行， >% 缩进一个block（需要将光标放在括号上）。

问：如何在Vim 中符号替换为换行符，:%s/,/\n/g 将会插入^@ 字符？

答：用/r 代替 /n 。在Vim 中，/r 和 /n 分别插入0X00 和0X0A 字符。

问：Vim 如何高亮搜索？

答：set nohlsearch 关闭高亮， set hlsearch! 打开高亮。

问：如何设置搜索大小写不敏感？

答： /letter\c搜索letter 且大小写不敏感，/letter\C 大小写敏感（默认）；或:set ignorecase 设置大小写不敏感。

问：如何复制一行？

答：yy 复制一行，dd 剪切一行，p 粘贴内容在本行下一行，P 粘贴内容在本行上一行。

问：w !sudo tee % 如何实现sudo （root 权限）保存的功能？

答：% 表示当前文件，tee 将即输出到% 还输出到屏幕。

问：如何设置Tab 为4 个空格，并自动缩进？

答：在vimrc 中添加

filetype plugin indent on
" show existing tab with 4 spaces width
set tabstop=4
" when indenting with '>', use 4 spaces width
set shiftwidth=4
" On pressing tab, insert 4 spaces
set expandtab

问：如何移动到一行的最后？

答：A 移动到本行最后并进入插入模式或 $ 移动到最后（普通模式，normal mode）

问：如何编辑多个文件？

答：使用tabs（Vim7 中引入），:tabe <filepath> 在新tab 中打开文件，:tabn 和 :tabp 在文件之间切换。还可以通过:sp <filepath> 进行分屏，ctrl+w 在屏幕之前切换。

问：remap/map/noremap 命令

答：remap 是使得映射命令能够递归地映射。系统默认是开启的（建议）。map/noremapd 都是映射命令。:map 和 :noremap 是递归映射（recursive）和非递归映射（no-recursive）。

:map j gg
:map Q j
:noremap W j

j 映射为 gg。Q 递归地映射为 gg。 W 将不会映射到 gg 而只会映射到 j ，因为它使用非递归映射。考虑到还有普通模式（normal）可视模式（visual），还有对应的映射命令（:nmap 和 :nnoremap）与（:vmap 和 :vnoremap）。

问：如何关闭粘贴时的自动缩进？

答：:set paste 进入插入粘贴模式（显示-- INSERT (paste) --），粘贴后取消 -:set nopast。可以将<F3> 键进行映射，从而快速切换模式：:set pastetoggle=<F3> 。

问：如何使用寄存器（registers）？

答：Vim 中寄存器可以用于暂时存储文本、宏命令等，以备后面使用。

:reg a b c 打印出 a b c 寄存器中内容；"a 表示寄存器a，"ayy 复制一行到寄存器a，"ap复制到当前位置；"Ayy 将内容增添在寄存器a；"+ 是一个特殊寄存器指向系统剪切板（clipboard），"+p 将系统剪切板中的内容粘贴到当前位置； "0 – "9 是九个数字寄存器，"0 寄存器保存复制（yank）的内容，"1 – "9 按时间分别保存删除（dd）的内容。