Main

<mediawiki xmlns="http://www.mediawiki.org/xml/export-0.8/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.mediawiki.org/xml/export-0.8/ http://www.mediawiki.org/xml/export-0.8.xsd" version="0.8" xml:lang="ru">
  <siteinfo>
    <sitename>Модулярная арифметика</sitename>
    <base>https://vscripts.ru/w/Main</base>
    <generator>MediaWiki 1.23.17</generator>
    <case>first-letter</case>
    <namespaces>
      <namespace key="-2" case="first-letter">Медиа</namespace>
      <namespace key="-1" case="first-letter">Служебная</namespace>
      <namespace key="0" case="first-letter" />
      <namespace key="1" case="first-letter">Обсуждение</namespace>
      <namespace key="2" case="first-letter">Участник</namespace>
      <namespace key="3" case="first-letter">Обсуждение участника</namespace>
      <namespace key="4" case="first-letter">Проект</namespace>
      <namespace key="5" case="first-letter">Обсуждение Проект</namespace>
      <namespace key="6" case="first-letter">Файл</namespace>
      <namespace key="7" case="first-letter">Обсуждение файла</namespace>
      <namespace key="8" case="first-letter">MediaWiki</namespace>
      <namespace key="9" case="first-letter">Обсуждение MediaWiki</namespace>
      <namespace key="10" case="first-letter">Шаблон</namespace>
      <namespace key="11" case="first-letter">Обсуждение шаблона</namespace>
      <namespace key="12" case="first-letter">Справка</namespace>
      <namespace key="13" case="first-letter">Обсуждение справки</namespace>
      <namespace key="14" case="first-letter">Категория</namespace>
      <namespace key="15" case="first-letter">Обсуждение категории</namespace>
    </namespaces>
  </siteinfo>
  <page>
    <title>Main</title>
    <ns>0</ns>
    <id>3</id>
    <revision>
      <id>1134</id>
      <parentid>1133</parentid>
      <timestamp>2025-11-05T07:59:44Z</timestamp>
      <contributor>
        <username>Turbo</username>
        <id>1</id>
      </contributor>
      <text xml:space="preserve" bytes="24219">&lt;table style=&quot;width: 100%;&quot;&gt;&lt;tr&gt;&lt;td style=&quot;width: 50%; vertical-align: top; border-right: 1px solid gray; padding: 0px 5px;&quot;&gt;
== Генераторы Verilog (базовые операции) ==

=== Модулярные сумматоры === 
# [http://vscripts.ru/2012/generator-sum-2n-1.php Генератор Verilog для сумматора по модулю 2&lt;sup&gt;n&lt;/sup&gt;-1] - реализация на базе двух сумматоров и мультиплексора (Р-2012).
# [http://vscripts.ru/dima/adder.php Генератор Verilog для сумматора по модулю 2&lt;sup&gt;n&lt;/sup&gt;-1] - полностью комбинационная реализация без мультиплексора (Д-2012).
# [http://vscripts.ru/dima/all_adders.php?n=31 Генератор Verilog для сумматора по произвольному модулю] - реализация предлагающая оптимальный вариант.
# [http://vscripts.ru/2014/modular-multi-sum.php Генератор Verilog для многовходового сумматора по произвольному модулю] - несколько различных вариантов сумматора нескольких переменных по модулю.
# [http://vscripts.ru/dima/Gorodecky_adder_web.php Генератор Verilog для многовходового сумматора по произвольному модулю] - реализация на базе метода сложения в позиционных кодах (Г-2015).

=== Модулярные умножители ===
# [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)&lt;sup&gt;2&lt;/sup&gt; - (1/4)*(X-Y)&lt;sup&gt;2&lt;/sup&gt;) 
# [http://vscripts.ru/2015/index-modulo-multiplication-def.php Генератор Verilog для умножения по модулю (метод 3)] - позиционное умножение с последующим прямым преобразованием
# [http://vscripts.ru/2015/index-modulo-multiplication-table.php Генератор Verilog для умножения по модулю (метод 4)] - модулярный умножитель на базе большой таблицы (case)
# [http://vscripts.ru/2015/index-modulo-multiplication-sum.php Генератор Verilog для умножения по модулю (метод 5)] - на базе частичных сумм
# [http://vscripts.ru/2013/multiplication-mod-2-pow-n-plus-1.php Генератор Verilog для умножителя по модулю 2&lt;sup&gt;n&lt;/sup&gt;+1] - для n от 3 до 43.
# [http://vscripts.ru/2013/multiplication-mod-2-pow-n-minus-1.php Генератор Verilog для умножителя по модулю 2&lt;sup&gt;n&lt;/sup&gt;-1] - для n от 3 до 43.
# [http://vscripts.ru/2013/multiplication-mod-2-pow-n.php Генератор Verilog для умножителя по модулю 2&lt;sup&gt;n&lt;/sup&gt;] - для n от 3 до 43.

=== Классические умножители (до 128 бит) ===
# [http://vscripts.ru/2013/high-bit-int-multiplication.php Бинарный умножитель на базе модулярного базиса (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;, 2&lt;sup&gt;n&lt;/sup&gt;+1)]
# [http://vscripts.ru/2013/high-bit-int-multiplication-recur.php Бинарных умножитель на базе рекурсивной модулярного базиса (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;, 2&lt;sup&gt;n&lt;/sup&gt;+1)] - используется два иерархических уровня модулей вида (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;, 2&lt;sup&gt;n&lt;/sup&gt;+1).
# [http://vscripts.ru/2013/high-bit-int-multiplication-4-mod-generator.php Бинарный умножитель на базе модулярного базиса (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;+1, 2&lt;sup&gt;n+1&lt;/sup&gt;-1, 2&lt;sup&gt;n+1&lt;/sup&gt;+1)] - используется перспективный набор из 4-х модулей.
# [http://vscripts.ru/2013/high-bit-int-multiplication-hierarchical.php Бинарный умножитель на базе иерархического метода] - используется метод &quot;разделяй и властвуй&quot; без использования модулярной арифметики.

=== Прямые модулярные преобразователи ===
# [http://vscripts.ru/2012/forward-converter-2supn-generator.php Модулярный базис (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;, 2&lt;sup&gt;n&lt;/sup&gt;+1)] - прямой преобразователь из позиционной системы счисления в систему остаточных классов (Р-2012). 
# [http://vscripts.ru/dima/fwd_generator.php Модулярный базис (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;, 2&lt;sup&gt;n&lt;/sup&gt;+1)] - прямой преобразователь из позиционной системы счисления в систему остаточных классов (Д-2012). 
# [http://vscripts.ru/2013/forward-converter-4-mod-generator.php Модулярный базис (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;+1, 2&lt;sup&gt;n+1&lt;/sup&gt;-1, 2&lt;sup&gt;n+1&lt;/sup&gt;+1)] - прямой преобразователь из позиционной системы счисления в систему остаточных классов. 
# [http://vscripts.ru/2015/forward-converter-universal.php Универсальный прямой преобразователь] - прямой преобразователь из позиционной системы счисления в СОК для произвольной системы модулей (Две версии: комбинационный и конвейерный).

=== Обратные модулярные преобразователи ===
# [http://vscripts.ru/2012/reverse-converter-2supn-generator.php Генератор Verilog для обратного преобразователя из базиса вида (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;, 2&lt;sup&gt;n&lt;/sup&gt;+1)] - сверхбыстрый обратный преобразователь в позиционную систему.
# [http://vscripts.ru/2013/reverse-converter-4-mod-generator.php Генератор Verilog для обратного преобразователя из 4-х элементного базиса (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;+1, 2&lt;sup&gt;n+1&lt;/sup&gt;-1, 2&lt;sup&gt;n+1&lt;/sup&gt;+1)] - обратный преобразователь в позиционную систему.
# [http://vscripts.ru/2013/reverse-converter-crt2-based.php Генератор Verilog обратного преобразователя для произвольных взаимнопростых модулей] - универсальный обратный преобразователь в позиционную систему для произвольного числа модулей (комбинационная и конвейерная версии).
# [http://vscripts.ru/2014/reverse-converter-pipeline-mixed-radix.php Генератор Verilog конвеерного обратного преобразователя на базе полиадического кода] - универсальный обратный преобразователь в позиционную систему для произвольного числа модулей.
# [http://vscripts.ru/2014/reverse-converter-pipeline-mixed-radix-with-error-correction.php Генератор Verilog конвеерного обратного преобразователя на базе полиадического кода с коррекцией ошибок] - универсальный обратный преобразователь в позиционную систему для произвольного числа модулей с коррекцией одиночной ошибки в одном из каналов. Два старших модуля являются избыточными. Используется перспективная схема с уменьшенной площадью.
# [http://vscripts.ru/2014/straightforward_error_correction_reverse_converter.php Генератор Verilog конвеерного обратного преобразователя на базе полиадического кода с коррекцией ошибок] - универсальный обратный преобразователь в позиционную систему для произвольного числа модулей с коррекцией одиночной ошибки в одном из каналов. Два старших модуля являются избыточными. Используется стандартный метод проекций.

=== КИХ-фильтры ===
# [http://vscripts.ru/2013/simple-fir-filter-generator.php Генератор Verilog для КИХ-фильтров (простейший метод)] - конвейерная структура сделанная по формуле свертки O(N&lt;sup&gt;2&lt;/sup&gt;).
# [http://vscripts.ru/2013/simple-modular-fir-filter-generator.php Генератор Verilog для конвейерных КИХ-фильтров на базе модулярного базиса (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;, 2&lt;sup&gt;n&lt;/sup&gt;+1)], [http://vscripts.ru/2013/simple-modular-fir-filter-generator_v2.php  Вторая версия]
# [http://vscripts.ru/dima/verilog_generator_modular_fir_filter.php Генератор Verilog для конвейерных КИХ-фильтров на базе модулярной арифметики и БПФ] - перспективный метод с использование БПФ в конечном поле и сложностью O(N*logN)

=== Скалярное произведение ===
# [http://vscripts.ru/2013/simple-mac-unit.php Генератор Verilog для MAC-Unit (простейший метод)] - синхронный вариант с дефолтной реализацией.
# [http://vscripts.ru/2013/fast-simple-scalar-multiplication.php Генератор Verilog для быстрого вычисления скалярного произведения с конвейризацией] - синхронный вариант на обычной позиционной арифметике.
# [http://vscripts.ru/2014/modular_scalar_multiplication.php Генератор Verilog для вычисления скалярного произведения на базе модулярной арифметики] - синхронный вариант на модулярной арифметике.

=== Другое ===
# [http://vscripts.ru/2012/generator-sum-kwain.php Генератор Verilog для модулярных операций по методу Квайна] - генератор операций сложения и умножения, для малых модулей (от 3 до 15).
# [http://vscripts.ru/2012/generator-sub-sqr.php Генератор Verilog для квадрата разности по модулю p] - состоит из вычитателя и таблицы квадратов (LUT). 
# [http://vscripts.ru/2013/modular-multiplication-for-fir-filter.php Генератор умножителя для конвейерной реализации модулярного FIR-фильтра]
# [http://vscripts.ru/dima/fast_fourier_transform_web.php?p=257&amp;len=128 Генератор Verilog для прямых и инверсных Теоретико Числовых БПФ] - используется конвейерная структура Radix2SPDF.
# [http://vscripts.ru/2014/coder_decoder_galua_generator.php Генератор Verilog для кодера и декодера Галуа] - только отдельные кодер и декодер.
# [https://vscripts.ru/dima/systolic_matrix_mult.php Генератор Verilog для умножения матриц (систолический массив)]

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

== Формулы и математика ==
# [http://vscripts.ru/2012/prime-set-generator.php Генератор простых чисел Прота для реализации операции свёртки] ([http://vscripts.ru/2012/prime-set-generator_new.php Версия 2]) - по методу БПФ в конечном поле.
# [http://vscripts.ru/2012/basis-15x16x17-simple.php Формула для обратного преобразователя для базиса вида (2n-1, 2n, 2n+1)] - обратный преобразователь для спец. системы модулей из системы остаточных классов в позиционный код.
# [http://vscripts.ru/2012/basis-15x16x17.php Проверка формул обратного преобразователя для базиса вида (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;, 2&lt;sup&gt;n&lt;/sup&gt;+1)] - обратный преобразователь для спец. системы модулей из системы остаточных классов в позиционный код. 
# [http://vscripts.ru/2012/sad-modular-basis-calculator.php Генератор базисов для SAD процессоров разной размерности] - базисы специального вида и обычного. 
# [http://vscripts.ru/2013/draw_complex_mod.php Рисовалка области значений комплексного вычета] - вычет комплексного числа по комлексному переменному
# [http://vscripts.ru/2015/check_basis.php Проверка базиса и расчет его динамического диапазона]
# [http://vscripts.ru/2013/find-inverse-by-mod.php Нахождение обратного элемента по модулю]
# [http://vscripts.ru/2013/radix_converter.php Преобразование позиционной системы счисления для заданного числа]
# [http://vscripts.ru/2014/backward_rns_converter_online.php Преобразование из системы остаточных классов в позиционный вид]
# [http://vscripts.ru/2014/recursieve_rns_basis_generator.php Генератор базисов для рекурсивной модулярной арифметики]

&lt;/td&gt;&lt;td style=&quot;width: 50%; vertical-align: top; padding: 0px 5px;&quot;&gt;

== Справочные материалы ==
=== Определения ===
* [[Система остаточных классов|Система остаточных классов (Модулярная арифметика)]] - определение
* [[Функция Эйлера]]
* [[Описание КТО II|Описание Китайской теоремы об остатках II (CRT II)]]
* [[Описание КТО III|Описание Китайской теоремы об остатках III (CRT III)]]
* [[Вычет по комплексному переменному‎]]
* [[Свёртка (цифровая обработка сигналов)|Свёртка (ЦОС)]]
* [[Полиадический код|Полиадический код (система счисления со смешанным основанием)]]
* [[Модулярная логарифметика‎]]
* [[Рекурсивная модулярная арифметика‎‎]]
* [[Бимодульная модулярная арифметика‎‎]]
* [[Система из 4 модулей (2^n-1, 2^n+1, 2^(n+1)-1, 2^(n+1)+1)|Теория по системе из 4-х модулей (2&lt;sup&gt;n&lt;/sup&gt;-1, 2&lt;sup&gt;n&lt;/sup&gt;+1, 2&lt;sup&gt;n+1&lt;/sup&gt;-1, 2&lt;sup&gt;n+1&lt;/sup&gt;+1)]]
* [[Фильтр с конечной импульсной характеристикой]]
* [[Теоретические основы применения модулярной арифметики для обнаружения и коррекции ошибок]]
* [[Описание работы универсального прямого преобразователя]]

=== Алгоритмы ===
* [[Метод инжектирования ошибок для оценки надежностных характеристик комбинационных схем]]
* [[Нахождение обратного элемента по модулю]]
* [[Схема коррекции ошибок Rajendra S. Katti]]
* [[Метод умножения Шёнхаге — Штрассена]]
* [[Расчет следующего значения функции на базе квадратичной интерполяции]]

== Программы == 
* [[(Prog) Генератор Verilog из таблиц истинности для сумматоров по модулю|Генератор Verilog из таблиц истинности для сумматоров по модулю]]
* [[(Prog) Расчет FIR-фильтра по стандартной формуле (Си)‎|Расчет FIR-фильтра по стандартной формуле]]
* [[(Prog) Расчет FIR-фильтра через ДПФ метод Overlap-Add (Си)‎|Расчет FIR-фильтра через ДПФ метод Overlap-Add]]
* [[(Prog) Расчет FIR-фильтра через ДПФ метод Overlap-Save‎|Расчет FIR-фильтра через ДПФ метод Overlap-Save‎]]
* [[(Prog) Расчет FIR-фильтра через ДПФ над конечным полем‎‎|Расчет FIR-фильтра через ДПФ над конечным полем‎‎]]
* [[Программа для проверки представимости булевой функции линейным арифметическим полиномом (PHP)]]

=== Разное ===
* [[Система остаточных классов - введение|Учебник по СОК]] - подробное описание системы остаточных классов
* [[Алгоритм Espresso]] - эффективный алгоритм для минимизации булевых функций
* [[MIS: A multiple-level logic optimization system]] - система логического синтеза
* [[Запустить ModelSim из командной строки]] - руководство по запуску ModelSim без использования графического интерфейса
* [[Введение в АЦП]] - описание видов аналого-цифровых преобразователей (двоичных)
* [[Модулярное АЦП]] - описание различных архитектур АЦП и их сравнение
* [[Специальные системы модулей]] - разные типы систем
* [[Пример коррекции ошибки на базе системы остаточных классов]]
* [http://vscripts.ru/2015/temperature.php Клеточный автомат для моделирования температуры]
* [[Схемы ISCAS85]]
* [[Полезная литература]]

== Результаты исследований ==
# 2015.11 - [[Простой прототип модулярного процессора с коррекцией сбоев]]
# 2014.07 - [[Исследование надежностных характеристик различных методов резервирования комбинационных схем с помощью метода инжектирования ошибок]]
# 2013.11 - [[Результаты синтеза прямых преобразователей для простых модулей в пределах 8 бит]]
# 2013.10 - [[Моделирование работы модулярного КИХ фильтра, исследование эффективности экстраполяционных методов для коррекции ошибок]]
# 2013.10 - [[Разработка модулярного КИХ фильтра на базе теоретико-числового БПФ]]
# 2013.08 - [[Комплексное исследование обратных преобразователей|Комплексное исследование обратных преобразователей (4 метода)]]
# 2013.05 - [[Комплексное исследование умножителей в диапазоне 3 - 64 бит]]
# 2013.04 - [[Результаты синтеза двоичных умножителей (3 - 64 бит)]]
# 2013.04 - [[Результаты синтеза прямых/обратных преобразователей на спец модулях вида 2^n-1, 2^n, 2^n+1 для Д.Д. до 128 бит.]]
# 2013.02 - [[Сравнение разных методов умножения по модулю - 2^n-1,индексный,по методу разности квадратов и позиционный.]]
# 2013.02 - [[Результат сравнения различных методов построения модулярных умножителей (индексный метод, разность квадратов, метод 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]] (модуль вида 2&lt;sup&gt;n&lt;/sup&gt;-1) - сравнение позиционного сумматора и двух вариантов реализации сумматора по модулю 2&lt;sup&gt;n&lt;/sup&gt;-1 ([http://vscripts.ru/2012/generator-sum-2n-1.php Генератор 1], [http://vscripts.ru/dima/adder.php Генератор 2]).

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

&lt;/td&gt;&lt;/tr&gt;&lt;/table&gt;
__NOTOC__</text>
      <sha1>ebhs3vfbakg4411vvh70x76dmwgq8yy</sha1>
      <model>wikitext</model>
      <format>text/x-wiki</format>
    </revision>
  </page>
</mediawiki>