公开/公告号CN103853523A
专利类型发明专利
公开/公告日2014-06-11
原文格式PDF
申请/专利权人 北京兆易创新科技股份有限公司;
申请/专利号CN201210506535.7
申请日2012-11-30
分类号G06F7/50;G06F7/52;
代理机构北京安信方达知识产权代理有限公司;
代理人栗若木
地址 100083 北京市海淀区学院路30号科大天工大厦A座12层
入库时间 2024-02-20 00:07:10
法律状态公告日
法律状态信息
法律状态
2022-09-16
专利权人的姓名或者名称、地址的变更 IPC(主分类):G06F 7/50 专利号:ZL2012105065357 变更事项:专利权人 变更前:北京兆易创新科技股份有限公司 变更后:兆易创新科技集团股份有限公司 变更事项:地址 变更前:100083 北京市海淀区学院路30号科大天工大厦A座12层 变更后:100094 北京市海淀区丰豪东路9号院8号楼1至5层101
专利权人的姓名或者名称、地址的变更
2017-05-31
授权
授权
2014-07-09
实质审查的生效 IPC(主分类):G06F7/50 申请日:20121130
实质审查的生效
2014-06-11
公开
公开
技术领域
本发明涉及计算机领域,尤其涉及一种伽罗瓦域的加法乘法器。
背景技术
伽罗瓦域理论是编码和译码学的理论基础。伽罗瓦中多项式的加法和乘 法运算在编码和译码中经常被用到。
伽罗瓦域中的元素可以用多项式来表示,例如一个伽罗瓦域为GF(2m), 则其伽罗瓦域中的元素可以用含有m个元素的多项式来表示,为了计算方便, 该多项式用只含系数的行矩阵形式表达,如当m=3时,[001]可用来表示伽 罗瓦域中的某个对应元素。故在做加法或乘法时,便可用这种行矩阵形式的 多项式进行相关的直接运算。
而伽罗瓦域中多项式的加法运算和乘法运算和实数域中多项式的加法运 算和乘法运算是不同的。一个伽罗瓦域的乘法器包含两部分,一部分是实数 域中的乘法器,另一部分是转换器。当多项式的计算既包括乘法又包含加法 时,利用传统的伽罗瓦域乘法器和加法器已不能实现加法乘法运算,而且当 多项式的元素个数变动时,普通的加法乘法器也不能满足需要。
发明内容
本发明要解决的技术问题是如何实现伽罗瓦域中既包括加法也包括乘法 时的多项式运算。
为了解决上述问题,本发明提供了一种伽罗瓦域的加法乘法器,包括: 伽罗瓦域转换器;
一或多个乘法器组,每个乘法器组各包括第一、第二实数域乘法器;所 述第一、第二实数域乘法器分别用于进行两个伽罗瓦域多项式在实数域中的 乘法运算,各得到一个实数域多项式;
一个或多个伽罗瓦域加法器,与所述乘法器组一一对应;
所述伽罗瓦域加法器用于对所对应的乘法器组中第一、第二实数域乘法 器得到的实数域多项式进行伽罗瓦域加法运算,得到加法结果多项式;
所述伽罗瓦域转换器用于将加法结果多项式转换为伽罗瓦域多项式。
进一步地,所述的加法乘法器还包括:
总加法器,用于将所有所述伽罗瓦域加法器得到的加法结果多项式相加, 将相加结果作为输入给所述伽罗瓦域转换器的加法结果多项式。
进一步地,所述伽罗瓦域加法器为自适应的伽罗瓦域加法器。
进一步地,所述自适应的伽罗瓦域加法器包括:
第一、第二元素个数运算单元,分别接收第一、第二实数域乘法器得到 的实数域多项式,用于计算所接收的实数域多项式各自的元素个数,分别得 到第一个数值和第二个数值;
加法元素个数控制单元,用于将所述第一个数值和第二个数值中较小的 一个作为相加位数x;如果第一、第二个数值相同,则将其中任意一个作为 相加位数x;
模2加法运算单元,用于接收第一、第二实数域乘法器得到的实数域多 项式,将所接收的两个实数域多项式中的低x位做模2相加,相加后的和作 为加法结果多项式的相应位,此处加法无进位,未参与模2相加的位保留原 值,作为加法结果多项式的相应位。
本发明的技术方案提出一种伽罗瓦域的加法乘法器,首先将乘法器和加 法器结合,通过调整乘法器、加法器和转换器的顺序来实现加法乘法器;本 发明的优化方案将加法器调整为自适应加法器,在加法器的输入位数变动时, 可以通用此加法器,而不需要再重新设计加法器。
附图说明
图1是实施例一的结构示意图;
图2是实施例一的例子的结构示意图;
图3是实施例一中自适应伽罗瓦域加法器的结构示意图。
具体实施方式
下面将结合附图及实施例对本发明的技术方案进行更详细的说明。
实施例一,一种伽罗瓦域的加法乘法器,如图1所示,包括:
一或多个乘法器组,每个乘法器组各包括第一、第二实数域乘法器;所 述第一、第二实数域乘法器分别用于进行两个伽罗瓦域多项式在实数域中的 乘法运算,各得到一个作为乘积的实数域多项式;
一个或多个伽罗瓦域加法器,与所述乘法器组一一对应;
各所述伽罗瓦域加法器用于对所对应的乘法器组中第一、第二实数域乘 法器得到的实数域多项式进行伽罗瓦域加法运算,得到一个加法结果多项式;
伽罗瓦域转换器,用于将加法结果多项式转换为伽罗瓦域多项式;此处 的转换将根据伽罗瓦域固有特性来转换,可参照现有技术进行转换。最终得 到正确的计算结果。
本实施例中,实数域乘法器的计算方法与实数多项式的乘法无异,例如 (x+1)×(x2+1),表示成行矩阵的形式为[1 1]×[1 0 1],二者的乘积为: x3+x2+x+1,表示为行矩阵的形式为[1 1 1 1]。
本实施例的一个备选方案中,所述加法乘法器还可以包括:
总加法器,用于将所有所述伽罗瓦域加法器得到的加法结果多项式相加, 将相加结果作为输入给所述伽罗瓦域转换器的加法结果多项式。
当所述伽罗瓦域加法器和乘法器组均为一个时,也可以不包括所述总加 法器;不包括总加法器时所述伽罗瓦域转换器所要转换的加法结果多项式为 伽罗瓦域加法器所得到的加法结果多项式。
如果包括该总加法器,由于参与相加的多项式只有一个,因此该总加法 器输出的结果就是这一个伽罗瓦域加法器加法运算所得到的多项式。包括总 加法器的情况下,所述伽罗瓦域转换器所要转换的加法结果多项式为总加法 器得到的相加结果。
本实施例中,输入到伽罗瓦域加法器中的两个实数域多项式的元素个数 可能不定,而且位数也可能互不相同,本实施例的一个备选方案中,所述伽 罗瓦域加法器为自适应的伽罗瓦域加法器。
本实施例中,当伽罗瓦域的运算涉及到先做乘法再做加法时,伽罗瓦域 中用m个元素表示的行矩阵多项式的乘法优先级较高,其次是伽罗瓦域加法, 再次是伽罗瓦域的转换。先将多项式做实数域乘法,则得到的乘积的最高次 数小于或等于2(m-1),且次数参差不齐。此时需要利用自适应的伽罗瓦 域加法器对乘积做加法运算,直到加法计算完毕后得到最终的加法结果,最 后做伽罗瓦域多项式的简化转换。
本实施例的一个例子中,如图2所示,共有2n(n为大于或等于2的正 偶数)个伽罗瓦域多项式,即图1中的多项式1、多项式2、多项式3、多项 式4、......、多项式2n-3、多项式2n-2、多项式2n-1、多项式2n;该例 子中的加法乘法器包括n个实数域乘法器,即图1中的实数域乘法器1、实数 域乘法器2、......、实数域乘法器n-1、实数域乘法器n,它们两两一组,共 分成n/2个乘法器组,分别与n/2个自适应的伽罗瓦域加法器(即图1中的伽 罗瓦域加法器1、......、伽罗瓦域加法器n/2)一一对应。
每个实数域乘法器对两个伽罗瓦域多项式进行实数域的乘法运算,比如 实数域乘法器1对多项式1和多项式2进行乘法运算,实数域乘法器2对多 项式3和多项式4进行乘法运算,......,实数域乘法器n-1对多项式2n-3 和多项式2n-2进行乘法运算,实数域乘法器n对多项式2n-1和多项式2n 进行乘法运算。
实数域乘法器将得到的实数域多项式输入给本组对应的自适应伽罗瓦域 加法器,比如实数域乘法器1和实数域乘法器2输入给伽罗瓦域加法器 1,......,实数域乘法器n-1和实数域乘法器n输入给伽罗瓦域加法器n/2; 各自适应伽罗瓦域加法器将收到的两个实数域多项式相加,将得到的多项式 输入给总加法器,由总加法器得到一个总和,输入给伽罗瓦域转换器,转换 为伽罗瓦域多项式。
本实施例的备选方案中,所述自适应的伽罗瓦域加法器的结构如图3所 示,其中虚线框中为所述自适应的伽罗瓦域加法器,包括:
第一、第二元素个数运算单元,分别接收第一、第二实数域乘法器得到 的实数域多项式,用于计算所接收的实数域多项式各自的元素个数,分别得 到第一个数值和第二个数值;
加法元素个数控制单元,用于将所述第一个数值和第二个数值中较小的 一个作为相加位数x;如果第一、第二个数值相同,则将其中任意一个作为 相加位数x;
模2加法运算单元,用于接收第一、第二实数域乘法器得到的实数域多 项式,将所接收的两个实数域多项式中的低x位做模2相加,相加后的和作 为加法结果多项式的相应位,此处加法无进位,未参与模2相加的位保留原 值,作为加法结果多项式的相应位。
例如:计算[0 1 0]+[1 1 1 0],则整个过程描述如下:计算出两个实数域多 项式的元素的个数分别为3(第一个数值)和4(第二个数值),则确定相加 位数x为3,[0 1 0]和[1 1 1 0]的低3位将参与无进位的模2运算,其中[1 1 1 0] 中的最高位“1”保留在加法结果多项式中,则加法结果多项式为[1 1 0 0]。 可见,参与模2运算的元素个数取决于元素个数较少的实数域多项式,而得 出的加法结果多项式的位数取决于元素个数较多的实数域多项式。
当然,本发明还可有其他多种实施例,在不背离本发明精神及其实质的 情况下,熟悉本领域的技术人员当可根据本发明作出各种相应的改变和变形, 但这些相应的改变和变形都应属于本发明的权利要求的保护范围。
机译: 用于伽罗瓦域的位串行乘法器并行化的方法以及使用该方法的位串行并行乘法器
机译: 用于伽罗瓦域的位串行乘法器并行化的方法以及使用该方法的位串行并行乘法器
机译: 参数伽罗瓦-身体-乘法器-加法器及其在数字信号处理器中的使用。