基于查找表的有限域乘法器复杂度分析.docVIP

 基于查找表的有限域乘法器复杂度分析 张学茹，寿国础** （北京邮电大学信息与通信工程学院，北京 100876） 5 10 15 20 25 30 35 40 摘要：有限域乘法器广泛应用于数字信号处理、编码理论、信息安全等领域。随着低碳通信 概念深入人心，针对有限域乘法器复杂度的优化成为业界研究重点。目前对有限域乘法器复 杂度的衡量是基于二输入与门和二输入异或门的数量，即是基于逻辑门的。而随着基于查找 表的 FPGA 技术的流行和广泛应用，基于逻辑门分析达到最优的实现方案，在 FPGA 中可能由 于不能充分利用查找表达不到最佳效果。对此，提出了一种基于查找表的复杂度分析方法， 并且选取了传统乘法器和 KOM 乘法器作了具体分析，分别基于逻辑门、基于四输入、六输入 查找表作了分析并进行了对比，结果显示不同条件下复杂度最优化结构存在明显差异。因此， 在 FPGA 具体实现中，使用本文提出的基于查找表的复杂度分析，将能降低乘法器空间复杂 度，减少资源消耗。 关键词：有限域乘法器；空间复杂度；查找表 中图分类号：TN92 Complexity Analysis of Finite Field Multiplier Based on LUT Zhang Xueru, Shou Guochu (Information and Communication Engineering School, Beijing University of Posts and Telecommunications, Beijing 100876) Abstract: Finite field multipliers are widely used in digital signal processing, coding theory and informationsecurity. With the low-carbon communication being hot, the low complexity finite field multiplier attract more attention. The current way to measure complexity of multipliers measure is based on gates.With the FPGA widely used, which is based on LUT, the current optimal structurei based on gates may can not reach owing to not full-used of LUT. The paper propose a method to mutiplier complexity based on LUT. And the traditional multiplier , KOM multiplier are analysisand respectively, based on gates, 4-LUT,6-LUT.The results is differ from each other with gates-based and LUT based.The conclusion is in FPGA implementation, whichi is wideused ,the LUT-based complexity analysis,should be taken into account to reduce complexity. Keywords: Finite field multiplier; complexity; LUT 0 引言 有限域运算的基本运算是加法和乘法，其中加法实现代价小，硬件上是异或门实现的； 而乘法的实现复杂度高，资源消耗大，经常是决定系统性能的关键。经典乘法器的实现复杂 2 m 上基于 KOM 的次平方复杂度乘法器，如文献[1-3]。 而目前对有限域乘法器的实现复杂度的分析都是基于逻辑门的，即用消耗的二输入与门 和二输入异或门的数量衡量空间复杂度大小。这种分析方式对于早期基于 ASIC 确定最佳实 现方案是适用的。而近些年来， FPGA 在硬件实现领域得到越来越广泛的应用。FPGA 由 于其基于 RAM 的快速可擦除功能而在安全领域得到广泛应用，比如在算法敏捷性、算法上 传和成本效益中表现出明显优势。现有的 FPGA 是基于查找表技术，例如 vertix-4 是基于 4 输入查找表的[