Модулярная арифметика - Вклад участника [ru]

Полезная литература

2014-08-04T11:00:06Z

Ssapra:

== Доступ к большим он-лайн библиотекам ==
* [http://www.sciencedirect.com Издательство Elsevier] - более 2000 научных журналов с полными текстами
* [http://www.springerlink.com Издательство Springer] - более 1200 научных журналов с полными текстами
* [http://iopscience.iop.org/journals Издательство IOP Publishing]

== Базовая литература ==
* [http://www.amazon.com/Residue-Number-Systems-Implementation-Engineering/dp/1860948669 Residue Number Systems: Theory and Implementation]

== Журналы для публикаций ==

* [http://www.sciencedirect.com/science/journal/00963003 Applied Mathematics and Computation]
* [http://www.sciencedirect.com/science/journal/08981221 Computers & Mathematics with Applications]
* [http://www.sciencedirect.com/science/journal/03770427 Journal of Computational and Applied Mathematics]
* [http://www.sciencedirect.com/science/journal/0022314X Journal of Number Theory]
* [http://www.sciencedirect.com/science/journal/13837621 Journal of Systems Architecture]
* [http://www.sciencedirect.com/science/journal/01679260 Integration, the VLSI Journal]
* [http://www.sciencedirect.com/science/journal/01651684 Signal Processing]
* [http://www.sciencedirect.com/science/journal/01656074 Microprocessing and Microprogramming]
* [http://www.sciencedirect.com/science/journal/00457906 Computers & Electrical Engineering]
* [http://www.sciencedirect.com/science/journal/03043975 Theoretical Computer Science]
* [http://www.sciencedirect.com/science/journal/00200190 Information Processing Letters ]
* [http://www.sciencedirect.com/science/journal/00200255 Information Sciences]

== Статьи ==

=== DSP ===
* [http://www.researchgate.net/publication/4034620_RDSP_a_RISC_DSP_based_on_residue_number_system/file/9fcfd50a916e3578e8.pdf RDSP: A RISC DSP based on Residue Number System] (2003) - показывает что применение RNS для проектирования 32-битного ЦОС, дает преимущества как по скорости (15%), так и по площади (30%) и по мощности (22%). Используется специальный набор модулей (2n-1, 22n, 2n+1), который при n=8 покрывает 32-битный диапазон.

=== Подбор базисов ===
* [http://arxiv.org/pdf/1211.5248v1 Design Of A Reconfigurable DSP Processor With Bit Efficient Residue Number System] (2012) - Бит-эффективный подбор модулей для заданной размерности данных. Основан на специальных наборах вида (2n). Подбор ведется для заданного количества модулей в базисе от 3 до 6.

=== Специальные модули ===
* [https://www.jstage.jst.go.jp/article/elex/8/12/8_12_897/_pdf Fully parallel comparator for the moduli set {2^n,2^n-1,2^n+1}] (2011) - быстрое сравнение чисел для базиса вида {2n-1, 2n, 2n+1}, основанный на операции вычитания.
* [http://etd.lsu.edu/docs/available/etd-11052010-141445/unrestricted/Report_Nov2.pdf OPTIMIZATION OF NEW CHINESE REMAINDER THEOREMS USING SPECIAL MODULI SETS] - новые версии Китайской теоремы об остатках для эффективной реализации немодульных операций на "не классических" специальных наборах модулей.
* [http://www.iis.ee.ethz.ch/~zimmi/publications/modulo_arith.pdf Efficient VLSI implementation of modulo (2n±1) addition and multiplication] (R Zimmermann, 1999) - эффективное умножение по модулю 2n±1
* [http://www2.lirmm.fr/arith18/papers/Sousa-RNS.pdf Efﬁcient Method for Magnitude Comparison in RNS Based on Two Pairs of Conjugate Moduli] (Leonel Sousa, 2007) - Интересный набор из 4-х спец-модулей. Эффективная реализация прямых/обратных преобразователей. Эффективная реализация сравнения по величине. Использование для проектирования SAD-процессора.
* [http://ijcsi.org/papers/IJCSI-8-3-1-407-414.pdf Fast Overflow Detection in Moduli Set {2n – 1, 2n, 2n + 1}] (Mehrin Rouhifar, Mehdi Hosseinzadeh Saeid Bahanfar and Mohammad Teshnehlab, 2011) - определение переполнения для спецсистемы модулей
* [https://www2.lirmm.fr/lirmm/interne/BIBLI/CDROM/MIC/2011/ISCAS_2011/Papers/B2L-D-3-1130.pdf A new RNS scaler for {2n – 1, 2n, 2n + 1}] (JYS Low, CH Chang, 2011)

=== Округление, масштабирование, деление в модулярной арифметике ===
* [http://mod.stavsu.ru/articles/sokcon36.pdf МЕТОДЫ И АЛГОРИТМЫ ОКРУГЛЕНИЯ, МАСШТАБИРОВАНИЯ И ДЕЛЕНИЯ ЧИСЕЛ В МОДУЛЯРНОЙ АРИФМЕТИКЕ] - В статье рассмотрены методы и алгоритмы деления числа в модулярном коде на одно из оснований или их произведение.

=== Логические функции ===
* [http://www.blif.org/~satrajit/pubs/thesis-ds.pdf On Algorithms for Technology Mapping] (2001) - предложены алгоритмы для натягивания логической функции на заданную библиотеку логических элементов.

=== Помехоустойчивость и сбоеустойчивость ===
* [http://eprints.soton.ac.uk/257134/1/lly-lh-vtcfall-2001-2.pdf REDUNDANT RESIDUE NUMBER SYSTEM BASED ERROR CORRECTION CODES (2001, Lie-Liang Yang and Lajos Hanzo)] - основные формулы для коррекции ошибок на базе RRNS (Избыточной системы остаточных классов).
* [http://venus.ece.ndsu.nodak.edu/~katti/pdf/j09.pdf A new residue arithmetic error correction scheme] - предложен метод нахождения и коррекции ошибок на основе RNS, в которой система модулей не является взаимнопростой.
* [http://jtec.utem.edu.my/index2.php?option=com_docman&task=doc_view&gid=86&Itemid=49 Using RRNS Codes for Cluster Faults Tolerance in Hybrid Memories] - использование RNS для локализации ошибок в гибридной памяти
===== Помехоустойчивая булева логика =====
* [http://vscripts.ru/res/pdf/boolean%20logic%20with%20fault%20tolerant%20coding.pdf Boolean logic with fault tolerant coding] - помехоустойчивое кодирование при реализации булевых функций
* [http://www.swsys.ru/index.php?page=article&id=2602 Исследование архитектурной чувствительности к сбоям с использованием метода статистического внесения сбоев] - методология моделирования схем со случайными ошибками
* [http://ofinko.ru/files/pdf/RID/article_Finko2004aRUS.pdf Реализация систем булевых функций большой размерности методами модулярной арифметики] - принцип реализация булевых функций методами модулярной арифметики

=== КИХ-фильтры (FIR-filters) ===
* [http://www.comm.utoronto.ca/~dkundur/course_info/real-time-DSP/notes/8_Kundur_Overlap_Save_Add.pdf Overlap-Save and Overlap-Add (Dr. Deepa Kundur)] - доступным языком объяснены методы фильтрации длинных сигналов: Overlap-Add и Overlap-Save.
* [http://www.researchgate.net/publication/224254503_Fast_and_energy-efficient_constant-coefficient_FIR_filters_using_residue_number_system/file/9fcfd510a99ff86bd7.pdf Fast and energy-efficient constant-coefficient FIR filters using residue number system, 2011]
* [http://orbit.dtu.dk/fedora/objects/orbit:117124/datastreams/file_94b457b9-1f5f-42f0-8f16-98b195a5efe3/content Power Efficient Design of Parallel/Serial FIR Filters in RNS, 2012]

=== Криптография ===
* [http://hal.archives-ouvertes.fr/docs/00/09/03/66/PDF/D8.PDF A Full RNS Implementation of RSA (2002)] - реализация RNS с помощью системы остаточных классов
* [http://link.springer.com/article/10.1007%2Fs12209-012-1902-7 Hardware architecture for RSA cryptography based on residue number system (2012)]
* [http://www.ddt.cs.vsu.ru/?q=system/files/09.pdf Криптография с использованием эллиптических кривых]
* [http://www.ccs.asia.edu.tw/ezfiles/2/1002/img/370/1203-3.pdf Elliptic Curve Point Multiplication by Generalized Mersenne Numbers] - реализация модулярного умножения Монтгомери для вычислений на эллиптических кривых, базирующаяся на обобщенных числах Мерсена

== Книги ==
=== Математика ===
* [http://ftfsite.ru/wp-content/files/mmf_tfkp_LavrentevShabat1965ru_2.2.pdf Методы теории функций комплексного переменного] (М.А. Лаврентьев Б.В. Шабат)
* [http://topology.math.csu.ru/library/posob/terch/VINOGRADOV_NUMBER_THEORY.PDF Основы теории чисел (Виноградов И.М.)]
* [http://bookinist.net/books/bookid-320879.html Непозиционные представления в многомерных числовых системах] (Синьков М.В., Губарени Н.М. (1979))

== Сайты со статьями по модулярной арифметике ==
* [http://ofinko.ru/index.php/rid Официальный сайт ученого Финько Олега Анатольевича]

== Разное ==
* [http://amath.colorado.edu/documentation/LaTeX/Symbols.pdf Символы Latex]

Полезная литература

2014-08-04T07:19:12Z

Ssapra:

== Доступ к большим он-лайн библиотекам ==
* [http://www.sciencedirect.com Издательство Elsevier] - более 2000 научных журналов с полными текстами
* [http://www.springerlink.com Издательство Springer] - более 1200 научных журналов с полными текстами
* [http://iopscience.iop.org/journals Издательство IOP Publishing]

== Базовая литература ==
* [http://www.amazon.com/Residue-Number-Systems-Implementation-Engineering/dp/1860948669 Residue Number Systems: Theory and Implementation]

== Журналы для публикаций ==

* [http://www.sciencedirect.com/science/journal/00963003 Applied Mathematics and Computation]
* [http://www.sciencedirect.com/science/journal/08981221 Computers & Mathematics with Applications]
* [http://www.sciencedirect.com/science/journal/03770427 Journal of Computational and Applied Mathematics]
* [http://www.sciencedirect.com/science/journal/0022314X Journal of Number Theory]
* [http://www.sciencedirect.com/science/journal/13837621 Journal of Systems Architecture]
* [http://www.sciencedirect.com/science/journal/01679260 Integration, the VLSI Journal]
* [http://www.sciencedirect.com/science/journal/01651684 Signal Processing]
* [http://www.sciencedirect.com/science/journal/01656074 Microprocessing and Microprogramming]
* [http://www.sciencedirect.com/science/journal/00457906 Computers & Electrical Engineering]
* [http://www.sciencedirect.com/science/journal/03043975 Theoretical Computer Science]
* [http://www.sciencedirect.com/science/journal/00200190 Information Processing Letters ]
* [http://www.sciencedirect.com/science/journal/00200255 Information Sciences]

== Статьи ==

=== DSP ===
* [http://www.researchgate.net/publication/4034620_RDSP_a_RISC_DSP_based_on_residue_number_system/file/9fcfd50a916e3578e8.pdf RDSP: A RISC DSP based on Residue Number System] (2003) - показывает что применение RNS для проектирования 32-битного ЦОС, дает преимущества как по скорости (15%), так и по площади (30%) и по мощности (22%). Используется специальный набор модулей (2n-1, 22n, 2n+1), который при n=8 покрывает 32-битный диапазон.

=== Подбор базисов ===
* [http://arxiv.org/pdf/1211.5248v1 Design Of A Reconfigurable DSP Processor With Bit Efficient Residue Number System] (2012) - Бит-эффективный подбор модулей для заданной размерности данных. Основан на специальных наборах вида (2n). Подбор ведется для заданного количества модулей в базисе от 3 до 6.

=== Специальные модули ===
* [https://www.jstage.jst.go.jp/article/elex/8/12/8_12_897/_pdf Fully parallel comparator for the moduli set {2^n,2^n-1,2^n+1}] (2011) - быстрое сравнение чисел для базиса вида {2n-1, 2n, 2n+1}, основанный на операции вычитания.
* [http://etd.lsu.edu/docs/available/etd-11052010-141445/unrestricted/Report_Nov2.pdf OPTIMIZATION OF NEW CHINESE REMAINDER THEOREMS USING SPECIAL MODULI SETS] - новые версии Китайской теоремы об остатках для эффективной реализации немодульных операций на "не классических" специальных наборах модулей.
* [http://www.iis.ee.ethz.ch/~zimmi/publications/modulo_arith.pdf Efficient VLSI implementation of modulo (2n±1) addition and multiplication] (R Zimmermann, 1999) - эффективное умножение по модулю 2n±1
* [http://www2.lirmm.fr/arith18/papers/Sousa-RNS.pdf Efﬁcient Method for Magnitude Comparison in RNS Based on Two Pairs of Conjugate Moduli] (Leonel Sousa, 2007) - Интересный набор из 4-х спец-модулей. Эффективная реализация прямых/обратных преобразователей. Эффективная реализация сравнения по величине. Использование для проектирования SAD-процессора.
* [http://ijcsi.org/papers/IJCSI-8-3-1-407-414.pdf Fast Overflow Detection in Moduli Set {2n – 1, 2n, 2n + 1}] (Mehrin Rouhifar, Mehdi Hosseinzadeh Saeid Bahanfar and Mohammad Teshnehlab, 2011) - определение переполнения для спецсистемы модулей
* [https://www2.lirmm.fr/lirmm/interne/BIBLI/CDROM/MIC/2011/ISCAS_2011/Papers/B2L-D-3-1130.pdf A new RNS scaler for {2n – 1, 2n, 2n + 1}] (JYS Low, CH Chang, 2011)

=== Округление, масштабирование, деление в модулярной арифметике ===
* [http://mod.stavsu.ru/articles/sokcon36.pdf МЕТОДЫ И АЛГОРИТМЫ ОКРУГЛЕНИЯ, МАСШТАБИРОВАНИЯ И ДЕЛЕНИЯ ЧИСЕЛ В МОДУЛЯРНОЙ АРИФМЕТИКЕ] - В статье рассмотрены методы и алгоритмы деления числа в модулярном коде на одно из оснований или их произведение.

=== Логические функции ===
* [http://www.blif.org/~satrajit/pubs/thesis-ds.pdf On Algorithms for Technology Mapping] (2001) - предложены алгоритмы для натягивания логической функции на заданную библиотеку логических элементов.

=== Помехоустойчивость и сбоеустойчивость ===
* [http://eprints.soton.ac.uk/257134/1/lly-lh-vtcfall-2001-2.pdf REDUNDANT RESIDUE NUMBER SYSTEM BASED ERROR CORRECTION CODES (2001, Lie-Liang Yang and Lajos Hanzo)] - основные формулы для коррекции ошибок на базе RRNS (Избыточной системы остаточных классов).
* [http://venus.ece.ndsu.nodak.edu/~katti/pdf/j09.pdf A new residue arithmetic error correction scheme] - предложен метод нахождения и коррекции ошибок на основе RNS, в которой система модулей не является взаимнопростой.
* [http://jtec.utem.edu.my/index2.php?option=com_docman&task=doc_view&gid=86&Itemid=49 Using RRNS Codes for Cluster Faults Tolerance in Hybrid Memories] - использование RNS для локализации ошибок в гибридной памяти
===== Помехоустойчивая булева логика =====
* [http://vscripts.ru/res/pdf/boolean%20logic%20with%20fault%20tolerant%20coding.pdf Boolean logic with fault tolerant coding] - помехоустойчивое кодирование при реализации булевых функций
* [http://www.swsys.ru/index.php?page=article&id=2602 Исследование архитектурной чувствительности к сбоям с использованием метода статистического внесения сбоев] - методология моделирования схем со случайными ошибками
* [http://ofinko.ru/files/pdf/RID/article_Finko2004aRUS.pdf Реализация систем булевых функций большой размерности методами модулярной арифметики] - принцип реализация булевых функций методами модулярной арифметики

=== КИХ-фильтры (FIR-filters) ===
* [http://www.comm.utoronto.ca/~dkundur/course_info/real-time-DSP/notes/8_Kundur_Overlap_Save_Add.pdf Overlap-Save and Overlap-Add (Dr. Deepa Kundur)] - доступным языком объяснены методы фильтрации длинных сигналов: Overlap-Add и Overlap-Save.
* [http://www.researchgate.net/publication/224254503_Fast_and_energy-efficient_constant-coefficient_FIR_filters_using_residue_number_system/file/9fcfd510a99ff86bd7.pdf Fast and energy-efficient constant-coefficient FIR filters using residue number system, 2011]
* [http://orbit.dtu.dk/fedora/objects/orbit:117124/datastreams/file_94b457b9-1f5f-42f0-8f16-98b195a5efe3/content Power Efficient Design of Parallel/Serial FIR Filters in RNS, 2012]

=== Криптография ===
* [http://hal.archives-ouvertes.fr/docs/00/09/03/66/PDF/D8.PDF A Full RNS Implementation of RSA (2002)] - реализация RNS с помощью системы остаточных классов
* [http://link.springer.com/article/10.1007%2Fs12209-012-1902-7 Hardware architecture for RSA cryptography based on residue number system (2012)]
* [http://www.ccs.asia.edu.tw/ezfiles/2/1002/img/370/1203-3.pdf Elliptic Curve Point Multiplication by Generalized Mersenne Numbers] - реализация модулярного умножения Монтгомери для вычислений на эллиптических кривых, базирующаяся на обобщенных числах Мерсена

== Книги ==
=== Математика ===
* [http://ftfsite.ru/wp-content/files/mmf_tfkp_LavrentevShabat1965ru_2.2.pdf Методы теории функций комплексного переменного] (М.А. Лаврентьев Б.В. Шабат)
* [http://topology.math.csu.ru/library/posob/terch/VINOGRADOV_NUMBER_THEORY.PDF Основы теории чисел (Виноградов И.М.)]
* [http://bookinist.net/books/bookid-320879.html Непозиционные представления в многомерных числовых системах] (Синьков М.В., Губарени Н.М. (1979))

== Сайты со статьями по модулярной арифметике ==
* [http://ofinko.ru/index.php/rid Официальный сайт ученого Финько Олега Анатольевича]

== Разное ==
* [http://amath.colorado.edu/documentation/LaTeX/Symbols.pdf Символы Latex]

Полезная литература

2013-05-20T06:27:14Z

Ssapra:

Специальные системы модулей

2013-04-29T08:04:01Z

Ssapra: /* 4-элементные системы */

== 3-элементные системы ==
=== {2n-1, 2n, 2n+1} ===
{2n-1, 2n, 2n+1} - наиболее часто встречающийся набор специальных модулей. Преимущества: легкость реализаций сумматоров, умножителей и немодульных операций. Система отлично изучена и часто используется.

=== {2n-1, 2n, 2n+1} ===
Общий случай предыдущей системы. Оличается легкостью создания обратных преобразователей.

=== {2n-1, 2n, 2n-1-1} ===
Система позволяет избежать сложных операций по модулю вида 2n+1, но сокращает динамический диапазон.
* Residue-to-binary arithmetic converter for the moduli set (2 k, 2 k-1, 2 k-1-1)

=== {22n+1+2n-1, 22n+1-1, 2n-1, 23n, 23n+1-1} ===
Система использует набор из трех оснований {22n+1+2n-1, 22n+1-1, 2n-1} для вычислений и 2 дополнительных модуля {23n, 23n+1-1} для обнаружения и исправления ошибок
* Study of Error Controllability for the New Modulus {22n+1+2n-1, 22n+1-1, 2n-1, 23n, 23n+1-1}

== 4-элементные системы ==

=== {2n-1, 2n, 2n+1, 2n+1-1} ===
* Efficient reverse converters for the four-moduli sets $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n + 1} - 1\}$ and $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n-1} - 1\}$

=== {2n-1, 2n, 2n+1, 2n-1-1} ===
* Efficient reverse converters for the four-moduli sets $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n + 1} - 1\}$ and $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n-1} - 1\}$

=== {2n-1, 2n, 2n+1, 22n+1} ===
* An efficient reverse converter for the 4-moduli set $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{2n} + 1\}$ based on the new chinese remainder theorem

=== {2n-1, 2n, 2n+1, 2n-1+1} ===
Модули взаимнопросты для n = 2k + 1, k = 1, 2, 3...

=== {2n+2+3, 2n+1+1, 2n+1, 2} ===
Модули взаимнопросты для всех n

=== {2, 2n-1, 2n+2n-1-1, 2n+1+2n-1} ===
* [http://elibrary.ru/item.asp?id=1333658 FOUR-MODULI SET {2, 2n-1, 2n+2n-1-1, 2n+1+2n-1} SIMPLIES THE RESIDUE TO BINARY CONVERTERS BASED ON CRT I]

== 5-элементные системы ==
=== {2n-1, 2n, 2n+1, 2n+1-1, 2n-1-1} ===
Работает для четных n. Динамический диапазон 5n-1 бит.
* A Residue-to-Binary Converter for a New Five-Moduli Set

== Удобные простые числа ==
=== Близкие к степени 2 ===
'''2n-1''': 3 (22-1) 7 (23-1) 31 (25-1) 127 (27-1) 8191 (213-1) 131071 (217-1)

'''2n+1''': 5 (22+1) 17 (24+1) 257 (28+1) 65537 (216+1)

'''2n-3''': 13 (24-3) 29 (25-3) 61 (26-3) 509 (29-3) 1021 (210-3) 4093 (212-3) 16381 (214-3)

'''2n+3''': 11 (23+3) 19 (24+3) 67 (26+3) 131 (27+3) 4099 (212+3) 32771 (215+3) 65539 (216+3) 262147 (218+3)

== 32-битная система ==
* 3*5*7*11*13*17*19*31*32 = 4811046240

== 64-битная система ==
* 17*31*127*257*511*512*513*8191 = 18910047147635040768 > 2^64
* 5*7*11*13*17*19*29*31*61*67*127*131*256 = 25297984113594832640 > 2^64

== 128-битная система ==

Специальные системы модулей

2013-04-29T07:52:38Z

Ssapra: /* 3-элементные системы */

== 3-элементные системы ==
=== {2n-1, 2n, 2n+1} ===
{2n-1, 2n, 2n+1} - наиболее часто встречающийся набор специальных модулей. Преимущества: легкость реализаций сумматоров, умножителей и немодульных операций. Система отлично изучена и часто используется.

=== {2n-1, 2n, 2n+1} ===
Общий случай предыдущей системы. Оличается легкостью создания обратных преобразователей.

=== {2n-1, 2n, 2n-1-1} ===
Система позволяет избежать сложных операций по модулю вида 2n+1, но сокращает динамический диапазон.
* Residue-to-binary arithmetic converter for the moduli set (2 k, 2 k-1, 2 k-1-1)

=== {22n+1+2n-1, 22n+1-1, 2n-1, 23n, 23n+1-1} ===
Система использует набор из трех оснований {22n+1+2n-1, 22n+1-1, 2n-1} для вычислений и 2 дополнительных модуля {23n, 23n+1-1} для обнаружения и исправления ошибок
* Study of Error Controllability for the New Modulus {22n+1+2n-1, 22n+1-1, 2n-1, 23n, 23n+1-1}

== 4-элементные системы ==

=== {2n-1, 2n, 2n+1, 2n+1-1} ===
* Efficient reverse converters for the four-moduli sets $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n + 1} - 1\}$ and $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n-1} - 1\}$

=== {2n-1, 2n, 2n+1, 2n-1-1} ===
* Efficient reverse converters for the four-moduli sets $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n + 1} - 1\}$ and $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n-1} - 1\}$

=== {2n-1, 2n, 2n+1, 22n+1} ===
* An efficient reverse converter for the 4-moduli set $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{2n} + 1\}$ based on the new chinese remainder theorem

=== {2n-1, 2n, 2n+1, 2n-1+1} ===
Модули взаимнопросты для n = 2k + 1, k = 1, 2, 3...

=== {2n+2+3, 2n+1+1, 2n+1, 2} ===
Модули взаимнопросты для всех n

== 5-элементные системы ==
=== {2n-1, 2n, 2n+1, 2n+1-1, 2n-1-1} ===
Работает для четных n. Динамический диапазон 5n-1 бит.
* A Residue-to-Binary Converter for a New Five-Moduli Set

== Удобные простые числа ==
=== Близкие к степени 2 ===
'''2n-1''': 3 (22-1) 7 (23-1) 31 (25-1) 127 (27-1) 8191 (213-1) 131071 (217-1)

'''2n+1''': 5 (22+1) 17 (24+1) 257 (28+1) 65537 (216+1)

'''2n-3''': 13 (24-3) 29 (25-3) 61 (26-3) 509 (29-3) 1021 (210-3) 4093 (212-3) 16381 (214-3)

'''2n+3''': 11 (23+3) 19 (24+3) 67 (26+3) 131 (27+3) 4099 (212+3) 32771 (215+3) 65539 (216+3) 262147 (218+3)

== 32-битная система ==
* 3*5*7*11*13*17*19*31*32 = 4811046240

== 64-битная система ==
* 17*31*127*257*511*512*513*8191 = 18910047147635040768 > 2^64
* 5*7*11*13*17*19*29*31*61*67*127*131*256 = 25297984113594832640 > 2^64

== 128-битная система ==

Main

2013-02-25T08:54:54Z

Ssapra:

= Генераторы Verilog =

== Базовые операции ==

=== Сумматоры ===
# [http://vscripts.ru/2012/generator-sum-2n-1.php Генератор Verilog для сумматора по модулю 2n-1] - реализация на базе двух сумматоров и мультиплексора (вариант Романа).
# [http://vscripts.ru/dima/adder.php Генератор Verilog для сумматора по модулю 2n-1] - полностью комбинационная реализация без мультиплексора (вариант Димы).
# [http://vscripts.ru/dima/all_adders.php?n=31 Генератор Verilog для сумматора по произвольному модулю] - реализация предлагающая оптимальный вариант.

=== Умножители ===
# [http://vscripts.ru/2012/index-modulo-multiplication.php Генератор Verilog для умножения по модулю (метод 1)] - от 3 до 1000 по индексному методу (умножение заменено на сложение).
# [http://vscripts.ru/2012/index-modulo-multiplication-sqr.php Генератор Verilog для умножения по модулю (метод 2)] - от 3 до 1000 по методу разности квадратов (X*Y = (1/4)*(X+Y)2 - (1/4)*(X-Y)2)

=== Прямые и обратные преобразователи ===
# [http://vscripts.ru/2012/forward-converter-2supn-generator.php Генератор Verilog для прямого преобразователя в базиса вида (2n-1, 2n, 2n+1)] - прямой преобразователь из позиционной системы счисления в систему остаточных классов (версия Романа).
# [http://vscripts.ru/dima/fwd_generator.php Генератор Verilog для прямого преобразователя в базиса вида (2n-1, 2n, 2n+1)] - прямой преобразователь из позиционной системы счисления в систему остаточных классов (версия Димы).
# [http://vscripts.ru/2012/reverse-converter-2supn-generator.php Генератор Verilog для обратного преобразователя из базиса вида (2n-1, 2n, 2n+1)] - сверхбыстрый обратный преобразователь в позиционную систему.

=== Другое ===
# [http://vscripts.ru/2012/generator-sum-kwain.php Генератор Verilog для модулярных операций по методу Квайна] - генератор операций сложения и умножения, для малых модулей (от 3 до 15).
# [http://vscripts.ru/2012/generator-sub-sqr.php Генератор Verilog для квадрата разности по модулю p] - состоит из вычитателя и таблицы квадратов (LUT).

== SAD процессоры (поиск различия между двумя картинками) ==
# [http://vscripts.ru/2012/sad_generator.php Генератор Verilog для реализации позиционного SAD процессора] - поиск векторов компенсации движения в стандартном виде.
# [http://vscripts.ru/2012/sad_modular_generator.php Генератор Verilog для реализации модулярного SAD процессора] - поиск векторов компенсации движения в модулярном базисе вида (2n-1, 2n, 2n+1).

== Формулы и математика ==
# [http://vscripts.ru/2012/prime-set-generator.php Генератор простых чисел Прота для реализации операции свёртки] - по методу БПФ в конечном поле.
# [http://vscripts.ru/2012/basis-15x16x17-simple.php Формула для обратного преобразователя для базиса вида (2n-1, 2n, 2n+1)] - обратный преобразователь для спец. системы модулей из системы остаточных классов в позиционный код.
# [http://vscripts.ru/2012/basis-15x16x17.php Проверка формул обратного преобразователя для базиса вида (2n-1, 2n, 2n+1)] - обратный преобразователь для спец. системы модулей из системы остаточных классов в позиционный код.
# [http://vscripts.ru/2012/sad-modular-basis-calculator.php Генератор базисов для SAD процессоров разной размерности] - базисы специального вида и обычного.

== Временные и тестовые скрипты ==
# [http://vscripts.ru/2012/prime.php Список случайных простых чисел] - для теста от 900 до 20000
# [http://vscripts.ru/2012/multable.php Таблица умножения по модулю] - от 3 до 100

== Справочные материалы ==
* [[Система остаточных классов]] - определение
* [[Алгоритм Espresso]] - эффективный алгоритм для мнимизации булевых функций
* [[Введение в АЦП]] - описание видов аналого-цифровых преобразователей (двоичных и модулярных)
* [[Полезная литература]]

== Результаты исследований ==
# 2013.02 - [[Результат сравнения модулярных сумматоров в стандартном исполнении и по методу Espresso]]
# 2013.01 - [[Результат сравнения модулярных сумматоров в стандартном исполнении и по методу Квайна]]
# 2012.12 - [[Результат сравнения SAD-процессоров модулярный vs позиционный (промежуточный отчет 12.2012)]]
# 2012.12 - [[Исследование позиционного умножения на нашей библиотеке]]
# 2012.12 - [[Сравнение разных методов умножения по модулю]] - сравнение позиционного, [http://vscripts.ru/2012/index-modulo-multiplication.php индексного умножителя] и [http://vscripts.ru/2012/index-modulo-multiplication-sqr.php умножителя по методу разности квадратов]
# 2012.12 - [[Сравнение разных методов сложения по модулю 2^n-1]] (модуль вида 2n-1) - сравнение позиционного сумматора и двух вариантов реализации сумматора по модулю 2n-1 ([http://vscripts.ru/2012/generator-sum-2n-1.php Генератор 1], [http://vscripts.ru/dima/adder.php Генератор 2]).

Полезная литература

2013-02-25T08:54:21Z

Ssapra:

Main

2013-02-25T05:52:22Z

Ssapra:

= Генераторы Verilog =

== Базовые операции ==

=== Сумматоры ===
# [http://vscripts.ru/2012/generator-sum-2n-1.php Генератор Verilog для сумматора по модулю 2n-1] - реализация на базе двух сумматоров и мультиплексора (вариант Романа).
# [http://vscripts.ru/dima/adder.php Генератор Verilog для сумматора по модулю 2n-1] - полностью комбинационная реализация без мультиплексора (вариант Димы).
# [http://vscripts.ru/dima/all_adders.php?n=31 Генератор Verilog для сумматора по произвольному модулю] - реализация предлагающая оптимальный вариант.

=== Умножители ===
# [http://vscripts.ru/2012/index-modulo-multiplication.php Генератор Verilog для умножения по модулю (метод 1)] - от 3 до 1000 по индексному методу (умножение заменено на сложение).
# [http://vscripts.ru/2012/index-modulo-multiplication-sqr.php Генератор Verilog для умножения по модулю (метод 2)] - от 3 до 1000 по методу разности квадратов (X*Y = (1/4)*(X+Y)2 - (1/4)*(X-Y)2)

=== Прямые и обратные преобразователи ===
# [http://vscripts.ru/2012/forward-converter-2supn-generator.php Генератор Verilog для прямого преобразователя в базиса вида (2n-1, 2n, 2n+1)] - прямой преобразователь из позиционной системы счисления в систему остаточных классов (версия Романа).
# [http://vscripts.ru/dima/fwd_generator.php Генератор Verilog для прямого преобразователя в базиса вида (2n-1, 2n, 2n+1)] - прямой преобразователь из позиционной системы счисления в систему остаточных классов (версия Димы).
# [http://vscripts.ru/2012/reverse-converter-2supn-generator.php Генератор Verilog для обратного преобразователя из базиса вида (2n-1, 2n, 2n+1)] - сверхбыстрый обратный преобразователь в позиционную систему.

== Немодульные операции ==
* [[http://mod.stavsu.ru/articles/sokcon36.pdf]] - Методы и алгоритмы округления, масштабирования и деления чисел

=== Другое ===
# [http://vscripts.ru/2012/generator-sum-kwain.php Генератор Verilog для модулярных операций по методу Квайна] - генератор операций сложения и умножения, для малых модулей (от 3 до 15).
# [http://vscripts.ru/2012/generator-sub-sqr.php Генератор Verilog для квадрата разности по модулю p] - состоит из вычитателя и таблицы квадратов (LUT).

== SAD процессоры (поиск различия между двумя картинками) ==
# [http://vscripts.ru/2012/sad_generator.php Генератор Verilog для реализации позиционного SAD процессора] - поиск векторов компенсации движения в стандартном виде.
# [http://vscripts.ru/2012/sad_modular_generator.php Генератор Verilog для реализации модулярного SAD процессора] - поиск векторов компенсации движения в модулярном базисе вида (2n-1, 2n, 2n+1).

== Формулы и математика ==
# [http://vscripts.ru/2012/prime-set-generator.php Генератор простых чисел Прота для реализации операции свёртки] - по методу БПФ в конечном поле.
# [http://vscripts.ru/2012/basis-15x16x17-simple.php Формула для обратного преобразователя для базиса вида (2n-1, 2n, 2n+1)] - обратный преобразователь для спец. системы модулей из системы остаточных классов в позиционный код.
# [http://vscripts.ru/2012/basis-15x16x17.php Проверка формул обратного преобразователя для базиса вида (2n-1, 2n, 2n+1)] - обратный преобразователь для спец. системы модулей из системы остаточных классов в позиционный код.
# [http://vscripts.ru/2012/sad-modular-basis-calculator.php Генератор базисов для SAD процессоров разной размерности] - базисы специального вида и обычного.

== Временные и тестовые скрипты ==
# [http://vscripts.ru/2012/prime.php Список случайных простых чисел] - для теста от 900 до 20000
# [http://vscripts.ru/2012/multable.php Таблица умножения по модулю] - от 3 до 100

== Справочные материалы ==
* [[Система остаточных классов]] - определение
* [[Алгоритм Espresso]] - эффективный алгоритм для мнимизации булевых функций
* [[Введение в АЦП]] - описание видов аналого-цифровых преобразователей (двоичных и модулярных)
* [[Полезная литература]]

== Результаты исследований ==
# 2013.02 - [[Результат сравнения модулярных сумматоров в стандартном исполнении и по методу Espresso]]
# 2013.01 - [[Результат сравнения модулярных сумматоров в стандартном исполнении и по методу Квайна]]
# 2012.12 - [[Результат сравнения SAD-процессоров модулярный vs позиционный (промежуточный отчет 12.2012)]]
# 2012.12 - [[Исследование позиционного умножения на нашей библиотеке]]
# 2012.12 - [[Сравнение разных методов умножения по модулю]] - сравнение позиционного, [http://vscripts.ru/2012/index-modulo-multiplication.php индексного умножителя] и [http://vscripts.ru/2012/index-modulo-multiplication-sqr.php умножителя по методу разности квадратов]
# 2012.12 - [[Сравнение разных методов сложения по модулю 2^n-1]] (модуль вида 2n-1) - сравнение позиционного сумматора и двух вариантов реализации сумматора по модулю 2n-1 ([http://vscripts.ru/2012/generator-sum-2n-1.php Генератор 1], [http://vscripts.ru/dima/adder.php Генератор 2]).