Galois场算单元在FPGA上的实现

¹LakhendraKumar,²K. L. Sudha博士

B.E项目学者，第八SEM，建设与建设系，DSCE，班加罗尔，印度
印度班加罗尔DSCE建筑与工程学院教授

摘要

有限场算法正日益成为许多应用计算的一个非常突出的解决方案。伽罗瓦场算法形成了BCH、Reed-Solomon和其他擦除编码技术的基础，以保护存储系统不发生故障。大多数Galois场算法的实现依赖于乘法表或离散对数来执行此操作。基于软件的Galois现场实现被应用于许多存储系统的可靠性和安全性组件中。不幸的是，与加法相比，对伽罗瓦域的乘法和除法运算是昂贵的。为了加速乘法和除法，大多数软件Galois字段实现使用预先计算的查找表，接受与优化这些操作相关的内存开销。然而，可用内存的数量限制了Galois字段的大小，并导致不同体系结构之间的性能不一致。典型的算术单元包括加法器或减法器、乘数和除法器。加法运算用一个n位异或运算完成，乘法运算用LSB第一乘法法和费马小定理进行乘法逆运算。这些操作在FPGA Virtex v.5 kit上实现，并在Xilinx 14.2 ISim模拟器上使用Verilog进行模拟。 Arithmetic unit architecture is measuredin terms of %age of device utilized and time delay.

关键字

有限场，BCH，伽罗瓦场，反演，加法器，乘法器，除法器

介绍

有限域是用于纠错编码、密码学和数字信号处理的代数结构。有限域的许多最重要的数学结果可以追溯到19世纪，但是直到20世纪50年代纠错码的引入，这些结果才得到实际应用

有限域的算术不同于标准整数算术。有限域中的元素数量有限;在有限域中执行的所有操作都会在该域内生成一个元素。有限域用于各种应用，包括经典编码理论中的线性分组码，如BCH码和Reed Solomon纠错，以及密码学算法，如Rijndael加密算法

无线宽带无线电传输和计算机硬盘存储是需要纠错的应用，对编解码速度的要求也在不断增长。如果这类系统要在越来越极端的条件下工作，就必须使用有效的纠错码，这就意味着需要更快的算术运算。

有限域运算有很多种方法。一种方法是使用在处理器中执行计算的软件算法。这是一种灵活的方法，因为处理器通常可以为任何有限场或场表示进行编程。一个很大的缺点是计算很慢，因为处理器通常不是针对有限域算法进行优化设计的

如果在硬件中完成这些计算，则可以获得更好的性能。有许多具有固定字段表示的特定编码方案的优化实现。这意味着它们可以非常有效地执行编码和解码，但它们也仅限于一个单一的应用程序

考虑到这些事实，找到一种将硬件的速度和软件的灵活性结合起来的解决方案显然是很有趣的。实现这一点的一种方法是设计一个硬件算术单元，它可以作为外部硬件单元使用，也可以在设计信号处理器时作为集成部分使用。该算法单元可用于与多种编码方案的信号源通信

2相关工作

有限域运算已经做了很多工作。有限域处理器的例子很少，但大多数都是为具有不同要求的密码应用而设计的。Hasan和Wassal[2]和Kim和Lee[3]提供了两个例子。为纠错编码设计一个有限域算术单元的想法似乎很有趣

用于乘法和逆运算的硬件体系结构已经由许多人开发了很多年。有限域算法是数学中一个研究得很好的分支，其硬件实现已经存在很多年了。在Berlekamp[4]中可以找到许多早期的建议。第一个收缩结构是在80年代提出的，并得到了进一步的发展。

Wang和Lin [5]， Tsai和Wang[6]给出了用于乘法的位串行收缩阵列的一些实现示例。Kim, Han and Hong[7]和Guo and Wang[8]提出了数字串行收缩乘法器。

3提出工作

本文的目的是提供代数的基本知识，这将有助于理解以下主题的材料。这种处理基本上是描述性的，没有试图在数学上严谨。对于任意正整数m，可以将素数场GF(p)扩展为pm元素的场，称为GF(p)的扩展场，记为GF(pm)。代数编码理论、代码构造和解码的很大一部分都是围绕有限域构建的。

定义BCH码和RS码的数学性质也表示伽罗瓦场。像加法、减法、乘法和除法这样的数学运算都是使用有限场理论进行的。有限域最基本的公理是:

1.字段中的所有元素组成一个附加运算符“+”的阿贝尔群。

2.字段中的非零元素用乘法运算符“。”组成组。

3.与任何非零元素相乘是加性群的自同构。

A. gf (24)

构造一个GF (2m)的主要原因是它们没有0和1作为根。本节对伽罗瓦场(24)进行了详细的解释。考虑下面的等式

由上式可知，0和1都不是方程的根。因此，我们可以说，式(1)的四阶根在GF(24)域之外。假设α是方程的一个根，P(α)应该等于零。这可以用下面的公式来解释

以上式(2)可用于生成GF(24)。将上述方程重新排列得到:

高阶场元可以类似地通过将α乘以其前一次幂来生成。α的15次方可计算如下:

α15 = α14。α = 1。

这里，第十五阶的简化给出了1，这是一个存在的元素;α的进一步幂总是会给出现有的元素。因此场GF(24)有以下16个元素:

2 0 1α,α,α,α,α,α,α,α,α,α,α,α,α,α14

B.伽罗瓦场算单元-设计和结构

算术单元是指对给定字段执行数学运算的单元。本课题介绍了基于Galois场元的算术单元的设计、结构及其在FPGA上的实现。在算术单元上进行的计算需要编码和解码各种纠错码，如BCH和RS码，这些码可以很容易地在通用计算机上编程。

(六)伽罗瓦野外加法器

在图2所示的电路中可以添加两个场元。首先，要添加的两个元素的向量表示被加载到寄存器A和b中。然后，它们的向量和出现在寄存器A的输入处。当寄存器A被脉冲(或时钟)时，和被加载到寄存器A中(寄存器A用作累加器)。例如，如果我们想加入GF(24)的α7和α13。我们知道它们的向量表示分别是(11 0 1)和(10 0 11 1)它们的向量和是(1 1 0 1)+(1 0 1 1)=(0 1 1 0)，这就是α5的向量表示。

(六)伽罗瓦场倍增器

接下来，我们考虑将两个任意字段元素相乘，如图3所示。同样，我们使用GF(24)进行说明。设β和γ为GF(24)中的两种元素。用多项式形式表示这两个元素:

产物βγ的表达形式如下:

本产品可按以下步骤进行:

1.c3β乘以α，将产物与c2β相加。

2.(c3β)α + c2β乘以α，将产物与c1β相加。

3.(c3β)α + c2β)α + c1β乘以α，将产物与c0β相加。

(六)伽罗瓦田野分隔器

除数对GF (2m)的算术运算可以这样进行:首先形成除数β的乘法逆，然后将这个逆β-1乘以除数，从而形成商。利用β(2^m-1)=1，可以求出β的乘法逆。因此,

β-1= β(2^m-2) (3)

四、硬件实现及伪代码

在本节中，算法单元的设计是在Virtex v.5上实现的。Virtex-5器件专门提供高性能倒装芯片BGA封装，该封装经过优化设计，可提高信号完整性和抖动。由于最佳位置和均匀分布以及电源和GND引脚数量的增加，封装电感被最小化。Xilinx XUPV5-LX110T是一款多功能通用开发板，由Virtex®-5 FPGA供电。它是一个功能丰富的通用评估和开发平台，包括板载内存和行业标准连接接口，为嵌入式应用程序提供了一个多功能的开发平台。

图2显示了算术单元的框图。它由三个主要模块组成，即加法器、乘法器和分法器，以及用于延迟输出的时钟分法器。每个块都有自己的控制信号，当被触发时，执行相应的操作。下面的伪代码显示了通过算术单元的不同阶段从输入到输出的信号流。

伪代码:

步骤1。初始化输入' b '和' c '，控制信号' start '， ' add '， ' mul '和' div '，以及时钟信号' clk '。

步骤2。如果start = 0

a.如果add = 1，执行添加操作。

b.如果mul = 1，执行乘法运算。

c.如果div = 1，执行除法运算。

步骤3。在' a '处给出各自的输出

步骤4。如果start = 1，将默认输出设为0

五、仿真结果

本节讨论了算法单元的仿真和综合结果。该单元已使用Xilinx 14.2 ISim模拟器进行了模拟，并验证了功能。利用RTL原理图查看器进行了综合。此外，还总结了Virtex v.5试剂盒的器件利用情况。

图4为Galois场算单元在ISim上的仿真结果。这里，在这个结果中，我们取了一个周期为10us的脉冲时钟。在第一个时钟，设计的单元被重置，给出输出“0000”。算术单元按脉冲时钟、输入和控制信号输出如表2所示

表3给出了在FPGA上设计算法单元所用的硬件。在FPGA即Virtex v.5中，我们总共有69120个片寄存器和片lut，其中只有31个寄存器和62个lut被使用。Aslice LUTs包含块RAM, ff和多路复用器。寄存器和触发器的集合称为可配置逻辑块(CLB)。用于计算单元设计的设备远远少于其可用性。因此，复杂性大大降低，操作速度大大加快。

(一)高级HDL合成报告

图5为FPGA上Galois场算单元的RTL原理图。详细说明了在建筑设计中使用了多少逻辑门、触发器、计数器等。这里使用了一个27位的上计数器进行时钟划分，因此在Virtex v.5的LED上可以看到输出。计时摘要给出了运算单元的延迟和最大运算频率的详细信息。这里的最大频率是381.876 MHz以下，该设备可以操作。

宏观统计数据

#筹码:1个

27位上升计数器:1

#寄存器:4

人字拖:4双

# Xors: 34

1-bit xor2: 18

1-bit xor3: 4

1-bit xor4: 4

1-bit xor5: 8