标签归档：Math

Analysis and Construction of Functional Regenerating Codes with Uncoded Repair for Distributed Storage Systems

Posted on by
回复

原文

本文作者是NCCloud 作者在INFOCOMM13 上发表的短文。作为NCCloud 的理论基础，证明了n = k+2 = d+1 情况下，FMSR 的存在性，并给出了这类编码的一个确定的编码方式。NCCloud 和本文提到的FMSR 具有三点重要性质：

  1. FMSR 码存储效率和容错效率与MDS 相同
  2. FMSR 达到最小修复带宽
  3. FMSR 使用非编码修复（uncoded repair/repair-by-transfer）

继续阅读 →

一些关于矩阵的基础知识

Posted on by
回复

一、特殊矩阵

正方矩阵/方阵( Square matrix )     大小为n×n 的矩阵

单位矩阵( Identity matrix )             对角线上元素为1，其余元素为0 的方阵，常用I 表示

置换矩阵( Exchange matrix )        反对角线上元素为1，其余元素为0 的方阵，常用J 表示

对角矩阵( Diagonal matrix )          非对角线上元素全为零的方阵

对称矩阵( Symmetric matrix )       满足矩阵中元素eij = eji   的方阵

三角矩阵(Triangle matrix)             分为上三角矩阵（元素eii 以上元素为零）和下三角矩阵

正交矩阵(Orthgonal matrix)          满足MTM = I 的方阵，矩阵和矩阵转置的乘积为单位矩阵

继续阅读 →

Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions(FAST 13′)

Posted on by
回复

PDF     Slide     Video

这是FAST13 中一篇关于通过Intel SSE3 指令集加速伽罗瓦域上计算的短文。纠错码广泛用于存储系统中，可分为XOR（异或）码和Reed-solomon(RS) 码。前者（LDPC, RAID5, X-code）在编码时仅进行异或运算，速度快；后者编码运算基于伽罗瓦域/有限域GF(2w)，速度相对较慢（XOR 可看做是GF(2) 上的运算）。该文旨在提出基于处理器128 比特指令集加速编码时的乘法运算。

继续阅读 →

初探GF-Complete（伽罗瓦运算库）

Posted on by
回复

GF-Complete 是一个开源、综合性的伽罗瓦运算库，相应的文章发表在FAST13 中（见参考文献【1】）。作者是大名鼎鼎的Jim Plank 教授，作为开源纠错码库Jerasure 的开发者，在这个伽罗瓦运算库中创新地采用了SSE 指令集来加速纠错码运算的瓶颈—伽罗瓦运算中的乘法运算，并采用了其他运算方法，综合得到GF-Complete。该库可在Plank 主页中下载得到，下面就GF-Complete 库做简要分析，详细可参考文档【2】。

继续阅读 →

伽罗瓦域上的乘法

Posted on by
4

一、前言

伽罗瓦域上的乘法在包括加/解密编码和存储编码中经常使用，常见的AES 和Reed-Solomon 编码就使用了伽罗瓦域GF(28) 中的运算。以2 或者2w 形式的伽罗瓦域来说，加减法都是异或运算，乘法相对较复杂一些，本文就GF(2w) 上有限域的乘法运算和优化进行分析。现代计算机是为二进制普通运算所设计，对伽罗瓦域计算最多仅有指令集上的优化，而且仅限于某些处理器，因此在更高层次上优化伽罗瓦域上的乘法显得尤为重要。

继续阅读 →