伽罗瓦域算术单元在FPGA上的实现

¹LakhendraKumar,²k . l . Sudha

B。E项目学者,八世SEM、部门建设,DSCE,班加罗尔,印度
教授,部门一分为三,DSCE,班加罗尔,印度

文摘

有限域运算变得越来越是一个非常著名的解决方案计算在许多应用程序中。伽罗瓦域算术BCH的基础形式,Reed-Solomon和其他擦除编码技术从失败中保护存储系统。大多数伽罗瓦域运算的实现依赖于乘法表或离散对数来执行该操作。基于软件的伽罗瓦域实现中使用的许多存储系统的可靠性和安全性组件。不幸的是,乘法和除法操作对伽罗瓦字段是昂贵的,而增加。加速乘法和除法,大多数软件伽罗瓦域实现使用预先计算查表、接受与优化这些操作相关联的内存开销。然而,可用内存的数量限制了伽罗瓦域的大小和导致性能不一致的架构。典型的算术单元包括一个加法器和减法器,乘法器和除法器。除了操作完成一个n位XOR操作,对于乘法操作LSB首先乘方法和费马小定理用于乘法逆元的操作。这些操作是在FPGA上实现Virtex v。5 kit & simulated using Verilog on Xilinx 14.2 ISim simulator. Arithmetic unit architecture is measuredin terms of %age of device utilized and time delay.

关键字

有限域,BCH,伽罗瓦,反演、加法器、乘法器、除法器

介绍

有限域代数结构用于纠错编码、密码学和数字信号处理。有限域的许多最重要的数学结果可以追溯到19世纪,但直到1950年代引入纠错编码,他们来到任何实际使用

有限域运算是不同于标准的整数运算。有有限数量的元素在有限的领域;所有操作在有限域的结果在这一领域内一个元素。有限的字段是用于各种各样的应用程序,包括古典等线性分组码的编码理论BCH编码和里德所罗门纠错和加密算法如Rijndael加密算法

无线宽带无线传输和电脑硬盘存储应用程序的误差修正是必要的,而在编码和解码速度的需求正在增长。如果这样的系统在越来越多的极端条件下工作,必须使用有效的纠错编码,进而意味着需要更快的算术运算。

有多种方式执行有限域运算。一个方法是使用软件算法在一个处理器执行计算。这是灵活的方法,因为处理器可以为任何有限域通常被编程或字段表示。一个大缺点是计算慢,因为处理器通常不是最优设计有限域运算

明显可以实现更好的性能如果这些计算是在硬件完成。有很多优化实现特定的编码方案和固定字段表示。这意味着他们可以执行的编码和解码很有效,但他们也只局限于一个单一的应用程序

记住这些事实显然是件有意思的事情找到一个解决方案,结合硬件的速度,和软件的灵活性。这样做的方法之一是通过设计一个硬件运算器,可以用作外部硬件单元或作为一个集成的一部分而设计的信号处理器。这个运算器可以用于交流有许多来源,使用不同的编码方案

二世。相关工作

有很多工作做在有限域算术运算。很少有有限域处理器的例子,但大多数这些加密应用程序的设计有不同的要求。两个例子是哈桑和Wassal[2]和金姆和李[3]。设计一个有限域运算单元的纠错编码似乎有趣

乘法的硬件架构和反演已经由许多人多年来开发的。有限域运算是数学的一个研究分支,已经知道多年和硬件实现。许多早期的建议可以在Berlekamp [4]。第一个收缩期架构提出了在80年和进一步发展。

比特串行收缩期的实现数组的一些例子给出了乘法小王和林[5],蔡和王[6]。Digital-serial收缩因子提出了金正日,汉族和香港[7],郭和王[8]。

三世。提出工作

本文的目的是提供一种基本的代数知识,这将帮助在下列主题材料的理解。治疗主要是描述性的,没有试图让数学上严格的。对任何正整数m,可以延长'字段GF (p)的点元素,叫做一个扩展字段的GF (p)和用GF (pm)。大部分代数编码理论,代码结构和解码是建立在有限的领域。

BCH码的数学性质和RS码definedalso代表了伽罗瓦域。数学操作,比如添加,减法,乘法和除法利用有限域理论。有限域的最基本公理:

1。的所有元素在该领域形成了阿贝尔群与额外的运算符“+”。

2。非零元素的形式和乘法操作符“。”。

3所示。乘法的任何非零元素是一个加法群的自同构。

GF (24)

构建的主要原因GF(2米),他们没有两个0和1根。本节提供了一个详细的解释伽罗瓦域(24)。考虑下面的方程

从上面的方程,很明显,0和1是方程的根。所以,我们可以说,第四阶的方程(1)是GF(24)以外的领域。通过假设α作为方程的根源之一,P(α)应该等于零。这可以用下面的公式来解释

上面的方程(2)可以用来生成GF (24)。重新安排上面的方程,

可以生成高阶场元素同样乘以α其先前的权力。十五的α可以计算如下:

α15 =α14。α= 1。

这里,十五的简化订单为1,这是一个现有的元素;进一步的α总是会给现有的元素。因此,域GF(24)有以下16个元素:

0 1α,α2、α3α4,α5,α6,α7,α8,α9,α10,α11,α12,α13α14

b .伽罗瓦域算术单元——设计和架构

运算器是指单位在给定的字段执行数学运算。这一主题解释了运算器的设计和架构基于伽罗瓦域元素及其实现FPGA (Virtex 5节)。在运算器执行的计算所需的各种错误校正码的编码和解码等BCH和RS码可编程通用计算机上的轻松。

➢伽罗瓦域加法器

可以添加两个字段元素与图2所示的电路。首先,这两个元素的向量表示要添加加载到寄存器A和b的矢量和随后出现在输入寄存器答:当注册一个脉冲(或定时),和加载到注册(注册作为一个累加器)。例如,如果我们想要添加α7和α13 GF (24)。我们知道他们的向量表示(1 1 0 1)和(1 0 1 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(2米)可以执行首先形成的乘法逆元因子β然后乘以这个逆β-1股息,因此形成了商。乘法逆元的β可以通过找到事实β(2 ^ m - 1) = 1。因此,

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

四、硬件实现伪代码

在本节中,运算器的设计上实现Virtex 5节。Virtex-5设备提供专门的高性能倒装芯片BGA包优化设计提高信号的完整性和抖动。包电感是最小化的最优位置和均匀分布数量的增加以及权力和接地插脚。Xilinx XUPV5-LX110T是一个多才多艺的通用开发板的Virtex®5 FPGA。这是一个功能丰富的通用评价和开发平台,包括电路板存储器和行业标准的连接接口,并为嵌入式应用程序提供了一个通用的开发平台。

图2显示了一个运算器的框图。它包括三个主要模块即加法器、乘法器和除法器以及用于延迟时钟分频器的输出。每一块都有自己的控制信号,触发后,做相应的操作。下面的伪代码显示的信号从输入流的输出通过不同阶段的运算器。

伪代码:

步骤1。初始化输入“b”和“c”,控制信号‘开始’,‘添加’,‘mul’和‘div’,时钟信号“时钟”。

步骤2。如果= 0开始

一。如果加= 1,执行添加操作。

b。如果mul = 1,执行乘法操作。

c。如果div = 1,执行部门操作。

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

步骤4。如果开始= 1,默认的输出为0

诉仿真结果

在本节中,讨论了模拟和运算器的合成结果。单位已经模拟使用Xilinx 14.2 ISim模拟器和功能验证。合成进行了使用RTL观众示意图。此外设备利用率也总结了Virtex v。5箱。

图4显示了伽罗瓦场的仿真结果ISim运算器。在这个结果我们采取了脉冲时钟周期为10。起初时钟,设计单位重置使输出“0000”。运算器的输出如表2所示的时钟脉冲,输入和控制信号

表3显示了在FPGA硬件用于设计运算器。在FPGA即Virtex v。5,we have total of 69120 slice registers and slice LUTs out of which only 31 registers and 62 LUTs are used. Aslice LUTs contains block RAM, FFs and multiplexers. A collection of registers and flip-flop is referred to as configurable logic block (CLB). Device used for design of arithmetic unit is much less compared to its availability. So, the complexity is very less and operation is much faster.