Открытый доступ Открытый доступ  Ограниченный доступ Доступ по подписке
Временные диаграммы входов и выхода модифицированного умножителя Карацубы

Модифицированный умножитель Карацубы для устройства решения уравнений в коде Рида-Соломона

Джаганат Саманта, Джайдеб Бхаумик, С. Барман

Аннотация


Арифметики конечных полей широко используются в линейных блочных кодах, таких как код БЧХ и код Рида–Соломона, а также в криптографических алгоритмах. Умножители конечных полей играют важную роль и занимают значительную часть площади в конструкции СБИС. В работе представлен улучшенный обобщенный умножитель Карацубы. Оптимизация алгоритма умножения Карацубы осуществлена путем разделения сомножителей на две альтернативные формы и выражения всех членов с помощью повторяющейся процедуры. Выполнено сравнение аппаратных требований предложенного умножителя со стандартным умножителем Карацубы. Предложенный умножитель требует меньшего количества сложений по сравнению с традиционным и общая площадь сокращается на 53,75% (без редукции) и на 52,08% (с редукцией). Кроме того, предложенный умножитель обладает быстродействием на 3,63% (без редукции) и 3,91% (с редукцией) выше, чем у традиционного умножителя Карацубы. Предложенный модифицированный умножитель Карацубы использован для расчета ключевого уравнения в декодере RS(47, 41), который находит применение в интеллектуальных домашних сетях. Все работы по моделированию выполнены с использованием моделирующей системы Xilinx 14.3 ISE и реализованы на семействе устройств Vertex 5 FPGA.

Ключевые слова


конечные поля; алгоритм Карацубы; умножитель полей Галуа; решающее устройство уравнения; код Рида-Соломона; СБИС; ПЛИС; программируемая логическая интегральная схема

Полный текст:

PDF

Литература


Berlekamp E. R. Bit-serial Reed-Solomon encoders / E. R. Berlekamp // IEEE Trans. Inf. Theory. — Nov. 1982. — Vol. 28, No. 6. — P. 869–874. — DOI : http://dx.doi.org/10.1109/TIT.1982.1056591.

Zhang T. Systematic design of original and modified Mastrovito multipliers for general irreducible polynomials / Tong Zhang, K. K. Parhi // IEEE Trans. Comput. — Jul. 2001. — Vol. 50, No. 7. — P. 734–749. — DOI : http://dx.doi.org/10.1109/12.936239.

Reyhani-Masoleh R. A new construction of Massey-Omura parallel multiplier over GF(2m) / R. Reyhani-Masoleh, M. A. Hasan // IEEE Trans. Comput. — May 2002. — Vol. 51, No. 5. — P. 511–520. — DOI : http://dx.doi.org/10.1109/TC.2002.1004590.

VLSI architectures for computing multiplications and inverses in GF(2m) / C. C. Wang, T. K. Truong, H. M. Shao, L. J. Deutsch, J. K. Omura, I. S. Reed // IEEE Trans. Comput. — Aug. 1985. — Vol. C-34, No. 8. — P. 709– 717. — DOI : http://dx.doi.org/10.1109/TC.1985.1676616.

Shi Z. J. Software implementations of elliptic curve cryptography / Zhijie Jerry Shi, Hai Yun // Int. J. Network Security. — 2008. — Vol. 7, No. 1. — P. 141–150. — URL : http://ijns.jalaxy.com.tw/download_paper.jsp?PaperID=IJNS-2006-09-13-3&PaperName=ijns-v7-n1/ijns-2008-v7-n1-p141-150.pdf.

Low complexity digit-serial multiplier over GF(2^m) using Karatsuba technology / Trong-Yen Lee, Min-Jea Liu, Chia-Chen Fan, Chia-Chun Tsai, Haixia Wu // Complex, Intelligent, and Software Intensive Systems : Seven Int. Conf. CISIS, 3–5 July 2013, Taichung : proc. — IEEE, 2013. — P. 461–466. — DOI : http://dx.doi.org/10.1109/CISIS.2013.84.

Erdem S. S. A less recursive variant of Karatsuba-Ofman algorithm for multiplying operands of size a power of two / S. S. Erdem, C. K. Koc // Computer Arithmetic : 16th IEEE Symp., 15-18 June 2003 : proc. — IEEE, 2003. — P. 28–35. — DOI : DOI: http://dx.doi.org/10.1109/ARITH.2003.1207657.

Cenk M. Improved polynomial multiplication formulas over F2 using chinese remainder theorem / M. Cenk, F. Ozbudak // IEEE Trans. Comput. — Apr. 2009. — Vol. 58, No. 4. — P. 572–576. — DOI : http://dx.doi.org/10.1109/TC.2008.207.

Zhou G. Complexity analysis and efficient implementations of bit parallel finite field multipliers based on Karatsuba-Ofman algorithm on FPGAs / Gang Zhou, H. Michalik, L. Hinsenkamp // IEEE Trans. Very Large Scale Integration (VLSI) Systems. — Jul. 2010. — Vol. 18, No. 7. — P. 1057–1066. — DOI : http://dx.doi.org/10.1109/TVLSI.2009.2020088.

Paar C. Efficient multiplier architectures for Galois fields GF(24n) / C. Paar, P. Fleischmann, P. Roeise // IEEE Trans. Comput. — Feb. 1998. — Vol. 47, No. 2. — P. 162–170. — DOI : http://dx.doi.org/10.1109/12.663762.

Weimerskirch A. Generalizations of the Karatsuba algorithm for efficient implementations / A. Weimerskirch, C. Paar // 2010. — URL : http://www.ei.rub.de/media/crypto/veroeffentlichungen/2010/08/08/kaweb.pdf.

Xie X. N. Novel bit-parallel multiplier for GF(2m) defined by all-one polynomial using generalized Karatsuba algorithm / Xiao-Ning Xie, Gong-Liang Chen, Yin Li // Inform. Process. Lett. — Mar. 2014. — Vol. 114, No. 3. — P. 140–146. — DOI : http://dx.doi.org/10.1016/j.ipl.2013.10.009.

Dyka Z. Combining multiplication methods with optimized processing sequence for polynomial multiplier in GF(2k) / Zoya Dyka, Peter Langendoerfer, Frank Vater // Research in Cryptology. Lect. Notes Comput. Sci. — 2011. — Vol. 7242. — P. 137–150. — DOI : http://dx.doi.org/10.1007/978-3-642-34159-5_10.

Samanta J. FPGA based modified Karatsuba multiplier / Jagannath Samanta, Razia Sultana, Jaydeb Bhaumik // VLSI and Signal Processing : Int. Conf. ICVSP14, 10–12 Jan. 2014, IIT Kharagpur : proc. — 2014.

Wicker S. B. Reed-Solomon codes and their applications / Ed. by Stephen B. Wicker, V. K. Bhargava. — New York : Wiley-IEEE Press, 1999. — ISBN : 978-0-7803-5391-6.

Sarwate D. V. High-speed architectures for Reed-Solomon decoders / D. V. Sarwate, N. R. Shanbhag // IEEE Trans. Very Large Scale Integration (VLSI) Systems. — Oct. 2001. — Vol. 9, No. 5. — P. 641–655. — DOI : http://dx.doi.org/10.1109/92.953498.

Jin I. S. Design and implementation of efficient Reed-Solomon decoder for intelligent home networking / Ik Soo Jin // Communication and Networking. — Berlin Heidelberg : Springer, 2012. — P. 261–268. — DOI : http://dx.doi.org/10.1007/978-3-642-27192-2_31.

Karatsuba A. Multiplication of many-digital numbers by automatic computers / A. Karatsuba, Y. Ofman // Doklady Physics. — 1963. — No. 7. — P. 595–596.




DOI: https://doi.org/10.20535/S0021347015100039

Метрики статей

Загрузка метрик ...

Metrics powered by PLOS ALM

Ссылки

  • На текущий момент ссылки отсутствуют.





© Известия высших учебных заведений. Радиоэлектроника, 2004–2017
При копировании активная ссылка на материал обязательна
ISSN 2307-6011 (Online), ISSN 0021-3470 (Print)
т./ф. +38044 204-82-31, 204-90-41
Условия использования сайта