В данной статье приведен метод реализации модулярных сумматоров и умножителей на базе таблиц истинности, минимизированных с помощью [[Алгоритм Espresso|Espresso]].

== Описание ==

Модулярные сумматоры и умножители в силу своей малой размерности могут быть реализованы как произвольная логическая функция и описана в виде таблицы истинности. Если размерность модуля <math>p</math> равна <math>k</math> бит, то таблица истинности будет иметь <math>2k</math> входных столбцов и <math>2^{2k}</math> строк. Для выходов будет соответственно <math>k</math> столбцов. Так как в модулярных устройствах размерность модуля небольшая, то и размерность таблицы истинности обычно приемлемых размеров. Получив таблицу истинности её можно минимизировать и записать для каждого выхода выражение как ДНФ.

== Пример Verilog файла ==

* Пример для умножителя по модулю 5.

<pre>
module mul_modulo_5 (A, B, X);
input [2:0] A;
input [2:0] B;
output[2:0] X;

assign X[0] = (A[0]&B[0]&~B[1]) | (~A[0]&A[1]&B[0]&B[1]) | (A[0]&~A[1]&B[0]) | (A[0]&A[1]&~B[0]&B[1]) | (A[2]&B[2]) | (A[2]&~B[0]&B[1]) | (~A[0]&A[1]&B[2]);
assign X[1] = (A[0]&~A[1]&B[1]) | (A[1]&B[0]&~B[1]) | (A[1]&B[2]) | (A[2]&B[1]);
assign X[2] = (A[0]&~A[1]&B[2]) | (~A[0]&A[1]&~B[0]&B[1]) | (A[0]&A[1]&B[0]&B[1]) | (A[2]&B[0]&~B[1]);
endmodule
</pre>

== Ссылки на файлы ==

Модулярные сумматоры и умножители были синтезированы для всех модулей от 2 до 255 включительно. Скачать Verilog файлы можно ниже:
* [Модулярные сумматоры (.7z ~3MB)|http://vscripts.ru/res/2015/sum_mod3-255_espr.7z]
* [Модулярные умножители (.7z ~40MB)|http://vscripts.ru/res/2015/mul_mod3-255_espr.7z]

Аппаратные реализации модулярных сумматоров и умножителей на базе минимизированной таблицы истинности

2015-12-21T10:18:35Z

Turbo: Новая страница: «В данной статье приведен метод реализации модулярных сумматоров и умножителей на базе т…»

Система остаточных классов

2015-12-21T09:07:32Z

Turbo:

'''Система остаточных классов (СОК)''' (от англ. [http://en.wikipedia.org/wiki/Residue_number_system Residue number system], другое название '''Модулярная арифметика''') - [http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F#.D0.9D.D0.B5.D0.BF.D0.BE.D0.B7.D0.B8.D1.86.D0.B8.D0.BE.D0.BD.D0.BD.D1.8B.D0.B5_.D1.81.D0.B8.D1.81.D1.82.D0.B5.D0.BC.D1.8B_.D1.81.D1.87.D0.B8.D1.81.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F непозиционная система счисления]. Представление числа в системе остаточных классов основано на понятии [http://ru.wikipedia.org/wiki/%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D1%8E вычета] и [http://ru.wikipedia.org/wiki/%D0%9A%D0%B8%D1%82%D0%B0%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE%D0%B1_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%B0%D1%85 китайской теореме об остатках]. СОК определяется набором [http://ru.wikipedia.org/wiki/%D0%92%D0%B7%D0%B0%D0%B8%D0%BC%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0 взаимно простых] ''модулей'' <math>(m_1, m_2, \dots, m_n)</math> с произведением <math>M=m_1\cdot m_2\cdot \dots\cdot m_n</math> так, что каждому целому числу <math>x</math> из отрезка <math>[0,M-1]</math> ставится в соответствие набор вычетов <math>(x_1, x_2, \dots, x_n)</math>, где
: <math>x_1 \equiv x \pmod{m_1};</math>
: <math>x_2 \equiv x \pmod{m_2};</math>
: …
: <math>x_n \equiv x \pmod{m_n}.</math>
При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка <math>[0,M-1]</math>.

== Преимущества системы остаточных классов ==
* В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в <math>[0,M-1]</math>.
Формула для сложения:
<math>(x_1, x_2, \dots, x_n) + (y_1, y_2, \dots, y_n) = (z_1, z_2, \dots, z_n)</math>, где
: <math>z_1 \equiv (x_1 + y_1) \pmod{m_1};</math>
: <math>z_2 \equiv (x_2 + y_2) \pmod{m_2};</math>
: ...
: <math>z_n \equiv (x_n + y_n) \pmod{m_n};</math>
Аналогично выполняются вычитание, умножение и деление.
'''Замечание''': на деление накладываются дополнительные ограничения: деление должно быть целочисленным, то есть делитель должен нацело делить делимое. Делитель должен быть взаимопростым со всеми модулями базиса.

== Недостатки системы остаточных классов ==
* Возможность представления только ограниченного количества чисел.
* Отсутствие эффективных алгоритмов для сравнения чисел, представленных в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям <math>(m_1, m_1\cdot m_2, \dots, m_1\cdot m_2\cdot\dots\cdot m_{n-1})</math>.
* Медленные и требующие работы с большими числами реализации алгоритмов перевода из позиционной системы счисления в СОК и обратно.
* Сложные алгоритмы деления (для случая, когда результат не является целым)
* Трудность в обнаружении переполнения

== Применение системы остаточных классов ==
СОК широко используется в микроэлектронике в специализированных устройствах [ЦОС], где требуется:
* контроль за ошибками, за счет введения дополнительных избыточных модулей
* высокая скорость работы, которую обеспечивает параллельная реализация базовых арифметических операций

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

== Численный пример ==

== Пример ==

Рассмотрим СОК с базисом <math>(2;3;5)</math>. В этом базисе можно взаимооднозначно представить числа из промежутка от <math>0</math> до <math>29</math>, так как <math>M = 2\times 3\times 5 = 30</math>. Таблица соответствия чисел из позиционной системы счисления и системы остаточных классов:
{| class="wikitable"
|-
| <math>0=(0;0;0)</math> || <math>1=(1;1;1)</math> || <math>2=(0;2;2)</math> || <math>3=(1;0;3)</math> || <math>4=(0;1;4)</math>
|-
| <math>5=(1;2;0)</math> || <math>6=(0;0;1)</math> || <math>7=(1;1;2)</math> || <math>8=(0;2;3)</math> || <math>9=(1;0;4)</math>
|-
| <math>10=(0;1;0)</math> || <math>11=(1;2;1)</math> || <math>12=(0;0;2)</math> || <math>13=(1;1;3)</math> || <math>14=(0;2;4)</math>
|-
| <math>15=(1;0;0)</math> || <math>16=(0;1;1)</math> || <math>17=(1;2;2)</math> || <math>18=(0;0;3)</math> || <math>19=(1;1;4)</math>
|-
| <math>20=(0;2;0)</math> || <math>21=(1;0;1)</math> || <math>22=(0;1;2)</math> || <math>23=(1;2;3)</math> || <math>24=(0;0;4)</math>
|-
| <math>25=(1;1;0)</math> || <math>26=(0;2;1)</math> || <math>27=(1;0;2)</math> || <math>28=(0;1;3)</math> || <math>29=(1;2;4)</math>
|}

=== Пример сложения ===
Сложим два числа 9 и 14 в базисе <math>(2;3;5)</math>. Их представление в заданном базисе <math>9=(1;0;4)</math> и <math>14=(0;2;4)</math> (см. табличку выше). Воспользуемся формулой для сложения:
<math>(z_1, z_2, z_3) = (1, 0, 4) + (0, 2, 4)</math>
: <math>z_1 \equiv (x_1 + y_1) \pmod{m_1} \equiv (1 + 0) \pmod{2} = 1;</math>
: <math>z_2 \equiv (x_2 + y_2) \pmod{m_2} \equiv (0 + 2) \pmod{3} = 2;</math>
: <math>z_3 \equiv (x_3 + y_3) \pmod{m_3} \equiv (4 + 4) \pmod{5} = 3;</math>
<math>(z_1, z_2, z_3) = (1, 2, 3)</math> - по таблице убеждаемся, что результат равен 23.

=== Пример умножения ===
Умножим два числа 4 и 5 в базисе <math>(2;3;5)</math>. Их представление в заданном базисе <math>4=(0;1;4)</math> и <math>5=(1;2;0)</math> (см. табличку выше). Воспользуемся формулой для умножения:
<math>(z_1, z_2, z_3) = (0, 1, 4) * (1, 2, 0)</math>
: <math>z_1 \equiv (x_1 * y_1) \pmod{m_1} \equiv (0 * 1) \pmod{2} = 0;</math>
: <math>z_2 \equiv (x_2 * y_2) \pmod{m_2} \equiv (1 * 2) \pmod{3} = 2;</math>
: <math>z_3 \equiv (x_3 * y_3) \pmod{m_3} \equiv (4 * 0) \pmod{5} = 0;</math>
<math>(z_1, z_2, z_3) = (0, 2, 0)</math> - по таблице убеждаемся, что результат равен 20.

Замечание: если бы мы умножали или складывали числа, которые дали в результате умножения число больше или равное <math>M = 30</math>, то полученный результат <math>RES \equiv REAL \pmod{M}</math>, где <math>REAL</math> - результат операции в позиционной системе счисления.

=== Пример деления, при условии, что оно делится нацело ===
Деление может быть выполнено аналогично умножению, но только если делитель делит делимое нацело, без остатка.
 
Для модулей <math>(29;31;32)</math> разделим число 1872 на 9. 
Делим <math>1872=(16;12;16)</math> на <math>9=(9;9;9)</math>. 

Воспользуемся формулой 
<math>z_i \equiv (x_i * y_i^{-1}) \pmod{m_i};</math>
 
Здесь надо сказать, что <math>y_i^{-1}*y_i=1 \pmod{m_i}</math>, что не то же самое, что просто разделить x на y. 
По формуле <math>y_i^{m_i-1}=1 \pmod{m_i}</math> получаем 
<math>9^{29-2} \pmod{29} = 13</math> 
<math>9^{31-2} \pmod{31} = 7</math> 
<math>9^{32-2} \pmod{32} = 17</math> 

<math>z_1 \equiv (16*13) \pmod{29} = 5</math> 
<math>z_2 \equiv (12*7) \pmod{31} = 22</math> 
<math>z_3 \equiv (16*17) \pmod{32} = 16</math> 
 
Это и есть правильный результат - число 208. Однако такой результат можно получить только если известно, что деление производится без остатка.

== Ссылки ==
* Книга "Residue Number Systems: Theory and Implementation", Amos Omondi, Benjamin Premkumar - наиболее исчерпывающая информация о применении СОК с подробными примерами (на английском языке).

Main

2015-12-09T09:01:55Z

Turbo:

<table style="width: 100%;"><tr><td style="width: 50%; vertical-align: top; border-right: 1px solid gray; padding: 0px 5px;">
== Генераторы 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/2014/modular-multi-sum.php Генератор 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/2015/index-modulo-multiplication-def.php Генератор Verilog для умножения по модулю (метод 3)] - позиционное умножение с последующим прямым преобразованием
# [http://vscripts.ru/2015/index-modulo-multiplication-table.php Генератор Verilog для умножения по модулю (метод 4)] - модулярный умножитель на базе таблицы (case)
# [http://vscripts.ru/2013/multiplication-mod-2-pow-n-plus-1.php Генератор Verilog для умножителя по модулю 2n+1] - для n от 3 до 43.
# [http://vscripts.ru/2013/multiplication-mod-2-pow-n-minus-1.php Генератор Verilog для умножителя по модулю 2n-1] - для n от 3 до 43.
# [http://vscripts.ru/2013/multiplication-mod-2-pow-n.php Генератор Verilog для умножителя по модулю 2n] - для n от 3 до 43.

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

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

=== Обратные модулярные преобразователи ===
# [http://vscripts.ru/2012/reverse-converter-2supn-generator.php Генератор Verilog для обратного преобразователя из базиса вида (2n-1, 2n, 2n+1)] - сверхбыстрый обратный преобразователь в позиционную систему.
# [http://vscripts.ru/2013/reverse-converter-4-mod-generator.php Генератор Verilog для обратного преобразователя из 4-х элементного базиса (2n-1, 2n+1, 2n+1-1, 2n+1+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(N2).
# [http://vscripts.ru/2013/simple-modular-fir-filter-generator.php Генератор Verilog для конвейерных КИХ-фильтров на базе модулярного базиса (2n-1, 2n, 2n+1)]
# [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&len=128 Генератор Verilog для прямых и инверсных Теоретико Числовых БПФ] - используется конвейерная структура Radix2SPDF.
# [http://vscripts.ru/2014/coder_decoder_galua_generator.php Генератор Verilog для кодера и декодера Галуа] - только отдельные кодер и декодер.

== 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/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 Проверка формул обратного преобразователя для базиса вида (2n-1, 2n, 2n+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 Генератор базисов для рекурсивной модулярной арифметики]

</td><td style="width: 50%; vertical-align: top; padding: 0px 5px;">

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

</td></tr></table>
__NOTOC__

Простой прототип модулярного процессора с коррекцией сбоев

2015-12-09T08:59:35Z

Turbo:

В данном материале приводится пример модулярного процессорного ядра (МПЯ), которое можно использовать для решения задач цифровой обработки сигналов. За счет избыточных модулей, есть возможность либо увеличить динамический диапазон рассчетов, либо обнаруживать ошибку в рассчетах, либо исправлять одиночную ошибку в рассчетах.

== Основные параметры МПЯ ==
* Вычисления с фиксированной запятой
* ...

== Базис для МПЯ ==

'''Базис полный (78 бит):'''

3 5 7 11 13 17 23 29 31 37 41 43 47 53 59 61 64 (Динамический диапазон: 197538326500053845866560 или 78 бит)

'''Рабочие модули (66 бит):'''

3 5 7 11 13 17 23 29 31 37 41 43 47 53 59 (Динамический диапазон: 50598956583005595765 или 66 бит)

'''Проверочные модули:'''

61 64

Указанный базис включает 8-битные модули (значения для модуля 64, тоже укладываются в 8 бит). Особенность модулярной арифметики не позволяет без существенных затрат определять факт переполнения, поэтому за переполнением диапазона должен следить программист.

== Состав памяти ==
# Регистр позиционный 78-битный для ввода / вывода RPOS
# Регистры модулярные AMOD, BMOD, CMOD и DMOD для операций
# Регистры U0, U1, U2, U3 - 12-битные для условных переходов.
# Регистр флагов F1 - F16 (F1 - флаг наличия ошибки)
# Программное ПЗУ - здесь хранится программа предварительно записанная в память устройства. Она не будет меняться до момента перепрошивки. Указатель текущей команды стоит в нулевой позиции перед запуском программы.
# Модулярное ОЗУ - размер 4096 строк по модулям (см. "Базис полный")
# Модулярное ОЗУ - размер 64 строки для хранения позиционных данных

== Таблица микрокоманд ==
<table border=1 cellpadding=5 cellspacing=0>
<tr>
<td >Код команды (5 бит)</td>
<td >Параметр 1 (кол-во бит)</td>
<td >Параметр 2 (кол-во бит)</td>
<td >Параметр 3 (кол-во бит)</td>
<td ></td>
<td ></td>
<td >Описание команды</td>
</tr>
<tr>
<td colspan=7>Обмен данными:</td>
</tr>
<tr>
<td >0</td>
<td>---</td>
<td colspan=4 ></td>
<td>Взять число с внешнего устройства и положить в RPOS</td>
</tr>
<tr>
<td >1</td>
<td>Код регистра (2 бита)</td>
<td>Код регистра U (2 бита)</td>
<td colspan=3 ></td>
<td>Отправить число из модулярного регистра (AMOD, ... DMOD) в модулярное ОЗУ по указанному адресу (адрес указан в U)</td>
</tr>
<tr>
<td >2</td>
<td>Код регистра (2 бита)</td>
<td>Код регистра U (2 бита)</td>
<td colspan=3 ></td>
<td>Отправить число из ОЗУ по указанному адресу (адрес указан в U) в модулярный регистр (AMOD, ... DMOD)</td>
</tr>
<tr>
<td >3</td>
<td>Адрес в позиционном ОЗУ (8 бит)</td>
<td colspan=4 ></td>
<td>Отправить число из позиционного регистра (RPOS) в позиционное ОЗУ по указанному адресу</td>
</tr>
<tr>
<td >4</td>
<td>Адрес в позиционном ОЗУ (8 бит)</td>
<td colspan=4 ></td>
<td>Отправить число из позиционное ОЗУ по указанному адресу в позиционный регистр (RPOS)</td>
</tr>
<tr>
<td >5</td>
<td>Код регистра (2 бита)</td>
<td>Код регистра (2 бита)</td>
<td colspan=3 ></td>
<td>Скопировать данные из одного регистра в другой (первые 4 бита модулярные, вторые 4 бита U)</td>
</tr>
<tr>
<td colspan=7>Преобразования между системами счисления:</td>
</tr>
<tr>
<td >8</td>
<td>Код регистра (2 бита)</td>
<td colspan=4 ></td>
<td>Преобразовать число в RPOS в модулярный вид и переложить в один из
регистров (AMOD, ....)</td>
</tr>
<tr>
<td >9</td>
<td>Код регистра (2 бита)</td>
<td colspan=4 ></td>
<td>Преобразовать число из модулярного регистра (AMOD, ... DMOD) в позиционный вид и положить в RPOS (в случае наличия ошибки, регистр F1 будет содержать 1)</td>
</tr>
<tr>
<td colspan=7>Арифметические операции:</td>
</tr>
<tr>
<td >11</td>
<td>Код регистра (2 бита)</td>
<td>Код регистра (2 бита)</td>
<td colspan=3 ></td>
<td>Сложить числа из заданных модулярных регистров и положить результат в первый регистр (без контроля переполнения, за переполнением следит программист)</td>
</tr>
<tr>
<td >12</td>
<td>Код регистра (2 бита)</td>
<td>Код регистра (2 бита)</td>
<td colspan=3 ></td>
<td>Умножить числа из заданных модулярных регистров и положить результат в первый регистр (без контроля переполнения, за переполнением следит программист)</td>
</tr>
<tr>
<td >13</td>
<td>Код регистра (2 бита)</td>
<td colspan=4 ></td>
<td>Обнулить заданный модулярный регистр (AMOD-DMOD)</td>
</tr>
<tr>
<td >14</td>
<td>---</td>
<td colspan=4 ></td>
<td>Обнулить RPOS</td>
</tr>
<tr>
<td >15</td>
<td>Код регистра (2 бита)</td>
<td>Код канала (5 бит)</td>
<td>Значение для модуля (8 бит)</td>
<td colspan=2 ></td>
<td>Положить в модулярный регистр (AMOD-DMOD) модулярный канал номер N заданное значение K (меньше N)</td>
</tr>
<tr>
<td colspan=7>Проверка на ошибки:</td>
</tr>
<tr>
<td >16</td>
<td>Код регистра (2 бита)</td>
<td>Позиция в стеке команд (14 бит)</td>
<td colspan=3 ></td>
<td>Проверить есть ли ошибка в указаном регистре (за счет двух проверочных модулей) в случае отсутствия ошибки перейти по указанному адресу</td>
</tr>
<tr>
<td >17</td>
<td>Код регистра (2 бита)</td>
<td colspan=4 ></td>
<td>Исправить однократную ошибку в указанном регистре (дольше чем проверка)</td>
</tr>
<tr>
<td colspan=7>Условные переходы:</td>
</tr>
<tr>
<td >18</td>
<td>Код регистра U (2 бита)</td>
<td>Адрес в позиционном ОЗУ (8 бит)</td>
<td colspan=3 ></td>
<td>Установить значение регистра U0, U1, U2 или U3 значение взятое из ячейки позиционного ОЗУ</td>
</tr>
<tr>
<td >19</td>
<td>Код регистра U (2 бита)</td>
<td>Значение (14 бит)</td>
<td colspan=3 ></td>
<td>Установить значение регистра U0, U1, U2 или U3 значение переданное в команде</td>
</tr>
<tr>
<td >20</td>
<td>Код регистра U (2 бита)</td>
<td colspan=4 ></td>
<td>Установить значение регистра U0, U1, U2 или U3 значение 0</td>
</tr>
<tr>
<td >21</td>
<td>Код регистра U (2 бита)</td>
<td colspan=4 ></td>
<td>Вычесть из значения регистра U0, U1, U2 или U3 единицу</td>
</tr>
<tr>
<td >22</td>
<td>Код регистра U (2 бита)</td>
<td colspan=4 ></td>
<td>Прибавть к регистру U0, U1, U2 или U3 единицу</td>
</tr>
<tr>
<td >23</td>
<td>Код регистра U (2 бита)</td>
<td>Позиция в стеке команд (14 бит)</td>
<td colspan=3 ></td>
<td>Переход к команде в позиции X (в стеке команд) если в регистре U0, U1, U2 или U3 значение равно 0.</td>
</tr>
</table>

== Пример решаемой задачи ==
Написать программу, которая выполняет скалярное произведение произвольного числа 32-х битных элементов менее чем 1024 в формате - сначала подается число элементов вектора (N), затем последовательно сначала элемент вектора 1, потом элемент вектора 2 и.т.д. Всего 2*N значений. Финальный результат проверяется на ошибки, в случае наличия ошибки в рассчетах выполняется пересчет.

== Текстовое описание программы ==
Описание приводится с использованием команд, которые поддерживает процессорное ядро.

* 0: Обнулить CMOD
* 1: Обнулить U1
* 2: Взять число с внешнего устройства - положить в RPOS
* 3: Отправить число из позиционного регистра (RPOS) в позиционное ОЗУ по адресу 0
* 4: Установить регистр U0 в значение взятое из ячейки позиционного ОЗУ по адресу 0
* 5: Перейти к команде 18 программы если в U0 находится 0
* 6: Взять число с внешнего устройства и положить в RPOS
* 7: Преобразовать число в RPOS в модулярный вид и переложить в AMOD
* 8: Взять число с внешнего устройства и положить в RPOS
* 9: Преобразовать число в RPOS в модулярный вид и переложить в BMOD
* 10: Умножить числа из AMOD и BMOD и положить результат в AMOD
* 11: Сложить числа из CMOD и AMOD - результат в CMOD
* 12: Положить число из AMOD в ОЗУ с адресом из U1
* 13: Прибавить к U1 единицу
* 14: Положить число из BMOD в ОЗУ с адресом из U1
* 15: Прибавить к U1 единицу
* 16: Вычесть из U0 единицу
* 17: Перейти к позиции 5 в стеке команд
* 18: Проверить есть ли ошибка в регистре CMOD. В случае отсутствия ошибки перейти к команде 32.
* 19: Установить регистр U0 значение взятое из регистра U1
* 20: Обнулить U1
* 21: Обнулить CMOD
* 22: Перейти к команде 31 программы если в U0 находится 0
* 23: Отправить число из ОЗУ по адресу указанному в U1 в модулярный регистр AMOD
* 24: Прибавить к U1 единицу
* 25: Отправить число из ОЗУ по адресу указанному в U1 в модулярный регистр BMOD
* 26: Прибавить к U1 единицу
* 27: Умножить числа из AMOD и BMOD и положить результат в AMOD
* 28: Сложить числа из CMOD и AMOD - результат в CMOD
* 29: Вычесть из U0 единицу
* 30: Перейти к позиции 22 в стеке команд
* 31: Перейти к команде 18 в стеке команд
* 32: Завершить работу программы

== Программа в машинных кодах ==

* 0: 01101 10
* 1: 10100 01
* 2: 00000
* 3: 00011 00000000
* 4: 10010 00 00000000
* 5: 10111 00 00000000010010
* 6: 00000
* 7: 01000 00
* 8: 00000
* 9: 01000 01
* 10: 01100 00 01
* 11: 01011 10 00
* 12: 00001 00 01
* 13: 10110 01
* 14: 00001 01 01
* 15: 10110 01
* 16: 10101 00
* 17: 10111 10 00000000000101
* 18: 10000 10 00000000100000
* 19: 00101 0100 0101
* 20: 10100 01
* 21: 01101 10
* 22: 10111 00 00000000011111
* 23: 00010 01 00
* 24: 10110 01
* 25: 00010 01 01
* 26: 10110 01
* 27: 01100 00 01
* 28: 01011 10 00
* 29: 10101 00
* 30: 10111 10 00000000010110
* 31: 10111 10 00000000010010
* 32: EOP

Простой прототип модулярного процессора с коррекцией сбоев

2015-12-09T08:45:28Z

Turbo:

Main

2015-12-07T09:41:15Z

Turbo:

<table style="width: 100%;"><tr><td style="width: 50%; vertical-align: top; border-right: 1px solid gray; padding: 0px 5px;">
== Генераторы 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/2014/modular-multi-sum.php Генератор 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/2015/index-modulo-multiplication-def.php Генератор Verilog для умножения по модулю (метод 3)] - позиционное умножение с последующим прямым преобразованием
# [http://vscripts.ru/2015/index-modulo-multiplication-table.php Генератор Verilog для умножения по модулю (метод 4)] - модулярный умножитель на базе таблицы (case)
# [http://vscripts.ru/2013/multiplication-mod-2-pow-n-plus-1.php Генератор Verilog для умножителя по модулю 2n+1] - для n от 3 до 43.
# [http://vscripts.ru/2013/multiplication-mod-2-pow-n-minus-1.php Генератор Verilog для умножителя по модулю 2n-1] - для n от 3 до 43.
# [http://vscripts.ru/2013/multiplication-mod-2-pow-n.php Генератор Verilog для умножителя по модулю 2n] - для n от 3 до 43.

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

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

=== Обратные модулярные преобразователи ===
# [http://vscripts.ru/2012/reverse-converter-2supn-generator.php Генератор Verilog для обратного преобразователя из базиса вида (2n-1, 2n, 2n+1)] - сверхбыстрый обратный преобразователь в позиционную систему.
# [http://vscripts.ru/2013/reverse-converter-4-mod-generator.php Генератор Verilog для обратного преобразователя из 4-х элементного базиса (2n-1, 2n+1, 2n+1-1, 2n+1+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(N2).
# [http://vscripts.ru/2013/simple-modular-fir-filter-generator.php Генератор Verilog для конвейерных КИХ-фильтров на базе модулярного базиса (2n-1, 2n, 2n+1)]
# [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&len=128 Генератор Verilog для прямых и инверсных Теоретико Числовых БПФ] - используется конвейерная структура Radix2SPDF.
# [http://vscripts.ru/2014/coder_decoder_galua_generator.php Генератор Verilog для кодера и декодера Галуа] - только отдельные кодер и декодер.

== 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/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 Проверка формул обратного преобразователя для базиса вида (2n-1, 2n, 2n+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 Генератор базисов для рекурсивной модулярной арифметики]

</td><td style="width: 50%; vertical-align: top; padding: 0px 5px;">

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

== Результаты исследований ==
# 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]] (модуль вида 2n-1) - сравнение позиционного сумматора и двух вариантов реализации сумматора по модулю 2n-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

</td></tr></table>
__NOTOC__

2014-07-11T06:16:16Z

Turbo:

Набор типовых комбинационных микроэлектронных схем для тестирования эффективности алгоритмов

== Список схем набора ==
<table>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">Наименование схемы</td><td style="border: 1px solid black; width: 100px; padding: 5px;">Исходное описание схемы</td><td style="border: 1px solid black; width: 100px; padding: 5px;">В базисе библиотеки Nangate</td><td style="border: 1px solid black; width: 100px; padding: 5px;">В базисе библиотеки Nangate c базовыми вентилями</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c17</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c17.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c17_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c17_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c432</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c432_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c432_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c499</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c499.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c499_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c499_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c880</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c880.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c880_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c880_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c1355</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c1355.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c1355_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c1355_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c1908</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c1908.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c1908_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c1908_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c2670</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c2670.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c2670_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c2670_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c3540</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c3540.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c3540_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c3540_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c5315</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c5315.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c5315_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c5315_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c6288</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c6288.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c6288_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c6288_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">c7552</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c7552.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat/c7552_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/ISCAS_flat_cut/c7552_flat_cut.v verilog]</td></tr>
</table>

Набор подсхем из схемы c432
<table>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">Наименование схемы</td><td style="border: 1px solid black; width: 100px; padding: 5px;">Исходное описание схемы</td><td style="border: 1px solid black; width: 100px; padding: 5px;">В базисе библиотеки Nangate</td><td style="border: 1px solid black; width: 100px; padding: 5px;">В базисе библиотеки Nangate c базовыми вентилями</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">74181</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74181.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74181_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74181_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">74182</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74182.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74182_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74182_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">74283</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74283.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74283_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74283_flat_cut.v verilog]</td></tr>
<tr><td style="border: 1px solid black; width: 100px; padding: 5px;">74L85</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74L85.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74L85_flat.v verilog]</td><td style="border: 1px solid black; width: 100px; padding: 5px;">[http://vscripts.ru/res/testckt/verilog/c432_parts/74L85_flat_cut.v verilog]</td></tr>
</table>
== Используемые библиотеки стандартных ячеек ==

[http://vscripts.ru/res/testckt/verilog/libs/NangateOpenCellLibrary.db Исходная библиотека Nangate в ".db" формате]

[http://vscripts.ru/res/testckt/verilog/libs/NangateOpenCellLibrary_typical_conditional_nldm.lib Исходная библиотека Nangate в ".lib" формате]

[http://vscripts.ru/res/testckt/verilog/libs/NangateOpenCellLibraryCut.db Сокращенная библиотека базовых стандартных ячеек Nangate в ".db" формате]

[http://vscripts.ru/res/testckt/verilog/libs/NangateOpenCellLibrary_Cut.lib Сокращенная библиотека базовых стандартных ячеек Nangate в ".lib" формате]

2014-05-07T10:32:18Z

Turbo: Новая страница: «Решение приводится для Windows-систем для классической простой задачи. Пусть на входе имеет…»

Решение приводится для Windows-систем для классической простой задачи. Пусть на входе имеется файл test.v, в котором задана схема для моделирования и записан тест-бенч.

== Порядок действий ==
Для начала необходимо найти расположение папки с ModelSim. Сделать это можно к примеру нажав правой кнопкой мыши на ярлык программы. Выбрав "Свойтсва/Properties" и далее в открывшемся окошке "Open file location".

В нашем случае путь такой:
<pre>C:\Programs\Altera\modelsim_ase\win32aloem\modelsim.exe</pre>

Создайте в той же папке что и module.v файл run.bat. И запишите в нем следующие команды:
<pre>C:\Programs\Altera\modelsim_ase\win32aloem\vlog.exe test.v
C:\Programs\Altera\modelsim_ase\win32aloem\vsim.exe -c -do test.do adder</pre>

Замечание: замените пути до файлов на свои и замените adder на имя своего модуля верхнего уровня.

Этот исполняемый BAT-файл по двойному клику запустит компиляцию Verilog-файла и затем запустит задание на моделирование, которое надо будет написать в файле test.do. В большинстве случаев структура у test.do файла будет одинаковая:

<pre>run -all
quit</pre>

== Полезные функции для Test Bench ==

Поскольку вы озаботились запуском ModelSim из командной строки значит вы скорее всего автоматизируете работу моделирования. И в этом случае вместо команд $display в Test Bench пригодится запись в файл. Запись в файл обеспечивается следующими функциями:

<pre>file = $fopen("output.dat");
$fwrite (file, "%f", var);
$fclose(file);</pre>

Данная последовательность команд запишет в файл с именем output.dat значение вещественной переменной var.