Модулярная арифметика - Новые страницы [ru]

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

2015-12-21T10:18:35Z

Turbo:

В данной статье приведен метод реализации модулярных сумматоров и умножителей на базе таблиц истинности, минимизированных с помощью [[Алгоритм 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 файлы можно ниже:
* [http://vscripts.ru/res/2015/sum_mod3-255_espr.7z Модулярные сумматоры (.7z ~3MB)]
* [http://vscripts.ru/res/2015/mul_mod3-255_espr.7z Модулярные умножители (.7z ~40MB)]

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

2015-12-07T09:20:45Z

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

Программа для проверки представимости булевой функции линейным арифметическим полиномом (PHP)

2015-11-26T22:07:46Z

Turbo: Новая страница: «== Описание == Программа проверяет можно ли заданную булеву функцию представить линейным…»

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

Программа проверяет можно ли заданную булеву функцию представить линейным арифметическим полиномом. Используются материалы из статьи "В. П. Шмерко, Теоремы Малюгина: новое понимание в логическом управлении, проектировании сбис и структурах данных для новых технологий, Автомат. и телемех., 2004, выпуск 6, 61–83" [http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=at&paperid=1589&option_lang=rus '''Статья''']

== Входные данные ==

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

<pre>
4 3
0 0 0 0 0 0 0
0 0 0 1 0 0 1
0 0 1 0 0 1 0
0 0 1 1 0 1 1
0 1 0 0 0 0 1
0 1 0 1 0 1 0
0 1 1 0 0 1 1
0 1 1 1 1 0 0
1 0 0 0 0 1 0
1 0 0 1 0 1 1
1 0 1 0 1 0 0
1 0 1 1 1 0 1
1 1 0 0 0 1 1
1 1 0 1 1 0 0
1 1 1 0 1 0 1
1 1 1 1 1 1 0
</pre>

Здесь первые два числа количество входных N и выходных K переменных соответственно. Далее следуют 2N строк, в каждой N + K чисел "0" или "1". Первые N чисел - логические значения входов, следующие K чисел логические значения выходов.

== Исходник на PHP ==

<source lang="php" line>
<?php
set_time_limit(3600);

function kronecker_product($a1, $a2) {
$x1 = count($a1);
$y1 = count($a1[0]);
$x2 = count($a2);
$y2 = count($a2[0]);

$ret = array();
for ($i1 = 0; $i1 < $x1; $i1++) {
for ($i2 = 0; $i2 < $x2; $i2++) {
for ($j1 = 0; $j1 < $y1; $j1++) {
for ($j2 = 0; $j2 < $y2; $j2++) {
$ret[$i1*$x2+$i2][$j1*$y2+$j2] = $a1[$i1][$j1]*$a2[$i2][$j2];
}
}
}
}
return $ret;
}

function get_conversion_matrix($num) {
$arr[0][0] = 1;
$arr[0][1] = 0;
$arr[1][0] = -1;
$arr[1][1] = 1;
if ($num == 1) {
return $arr;
}
$narr = $arr;
for ($i = 1; $i < $num; $i++) {
$narr = kronecker_product($narr, $arr);
}
return $narr;
}

function gen_polinom_koeffs($kron, $f) {
$len1 = count($f);
$len2 = count($kron);
if ($len1 != $len2) {
echo "Something strange ($len1 != $len2)";
exit;
}

$res = array();
for ($i = 0; $i < $len1; $i++) {
$res[$i] = 0;
for ($j = 0; $j < $len1; $j++) {
$res[$i] += $kron[$i][$j]*$f[$j];
}
}
return $res;
}

function print_2d_matrix($arr) {
$x = count($arr);
$y = count($arr[0]);

for ($i = 0; $i < $x; $i++) {
for ($j = 0; $j < $y; $j++) {
echo $arr[$i][$j]." ";
}
echo "\n";
}
echo "\n";
}

function print_polinom($res) {
$alpha = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l');
$len = count($res);
echo "Polinom: ";
for ($i = 0; $i < $len; $i++) {
if ($res[$i] != 0) {
if ($res[$i] > 0)
echo "+";
echo $res[$i];

$pos = 0;
$cur = $i;
while ($cur) {
if ($cur & 1)
echo $alpha[$pos];
$pos++;
$cur = $cur >> 1;
}
echo "";
}
}
echo "\n";
}

function count_ones($val) {
$c = 0;
while ($val) {
if ($val & 1)
$c++;
$val = $val >> 1;
}
return $c;
}

function check_polinom_linearity($res) {
$len = count($res);
for ($i = 1; $i < $len; $i++) {
if (count_ones($i) > 1) {
if ($res[$i] != 0)
return false;
}
}
return true;
}

function get_bit($j, $num) {
return ($j >> $num) & 1;
}

function if_pow_2($j) {
if ($j == 0)
return true;
for ($i = 0; $i < 32; $i++) {
if ($j == (1 << $i))
return true;
}
return false;
}

function swap(&$arr, $i, $j) {
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}

function gen_permute($arr, $i, $n) {
global $permutations;
if ($i == $n) {
$permutations[] = $arr;
} else {
for ($j = $i; $j < $n; $j++) {
swap($arr, $i, $j);
gen_permute($arr, $i+1, $n);
swap($arr, $i, $j);
}
}
}

function check_linearization_possibility_for_permutation_based_on_kroneker($f, $inum) {
$kron = get_conversion_matrix($inum);
$koefs = gen_polinom_koeffs($kron, $f);
$result = check_polinom_linearity($koefs);
if ($result == true || 1) {
print_polinom($koefs);
}
return $result;
}

function check_linearization_possibility_for_permutation($f, $in, $out, $inum, $onum, $number) {

for ($j = 0; $j < (1 << $inum); $j++) {
if (if_pow_2($j))
continue;

// Считаем значение функции в точке j
$sum = 0;
for ($i = 0; $i < $inum; $i++) {
$jni = get_bit($j, $inum-1-$i);
$f2i = $f[1 << $i];
$sum += $jni*$f2i;
}
$calc = 0;
for ($i = 0; $i < $inum; $i++) {
$jni = get_bit($j, $i);
$calc += $jni;
}
$sum = $sum + $f[0]*(1 - $calc);
if ($sum != $f[$j]) {
echo "$sum != ".$f[$j]." for J = $j\n";
return false;
}
}

return true;
}

function check_linearization_possibility($in, $out) {
global $permutations;
$inum = count($in[0]);
$onum = count($out[0]);
$number = count($in);

if ($onum > 10) {
echo "It's not possible to check all permuatations for $onum number of outputs!\n";
exit;
}

$permutations = array();
for ($j = 0; $j < $onum; $j++) {
$arr[$j] = $j;
}
gen_permute($arr,0,count($arr));

foreach ($permutations as $perm) {
echo "Check permuation of outputs:";
for ($j = 0; $j < $onum; $j++) {
echo " ".$perm[$j];
}
echo "\n";

// Получаем вектор f для выхода
for ($i = 0; $i < $number; $i++) {
$f[$i] = 0;
for ($j = 0; $j < $onum; $j++) {
$f[$i] += ($out[$i][$j] << $perm[$j]);
}
}

if (check_linearization_possibility_for_permutation_based_on_kroneker($f, $inum)) {
return true;
}
}
return false;
}

function read_tt($file, &$in, &$out) {
$lines = explode("\n", $file);
$arr = explode(" ", $lines[0]);
$inum = $arr[0];
$onum = $arr[1];

$ci = 0;
for ($i = 1; $i < count($lines); $i++) {
$l = trim($lines[$i]);
if ($l == '')
continue;
$l = preg_replace("/[^0-9]/i", " ", $l);
$l = preg_replace("/[[:blank:]]+/i", " ", $l);
$l = trim($l);
$arr = explode(" ", $l);
if (count($arr) != ($inum + $onum)) {
echo "Some problem at line $i: ".$lines[$i]." (".count($arr)." != ".$inum." + ".$onum.")\n";
print_r($arr);
exit;
}
for ($j = 0; $j < $inum; $j++) {
$in[$ci][$j] = $arr[$j];
}
for ($j = 0; $j < $onum; $j++) {
$out[$ci][$j] = $arr[($j+$inum)];
}
$ci++;
}
if (count($in) != 1 << $inum) {
echo "Check number of lines in truth table (".count($in)." != ".(1 << $inum).")\n";
exit;
}
}

function gen_random_truth_table($inum, $onum, &$in, &$out) {
$number = (1 << $inum);

for ($i = 0; $i < $number; $i++) {
for ($j = 0; $j < $inum; $j++) {
$in[$i][$j] = get_bit($i, $j);
}
for ($j = 0; $j < $onum; $j++) {
$out[$i][$j] = mt_rand(0, 1);
}
}
// print_r($in);
// print_r($out);
}

function print_table_to_file($file, $in, $out) {
$inum = count($in[0]);
$onum = count($out[0]);
$number = count($in);
$o = fopen($file, "w");
fprintf($o, "%d %d\n", $inum, $onum);
for ($i = 0; $i < $number; $i++) {
fprintf($o, "%d", $in[$i][0]);
for ($j = 1; $j < $inum; $j++) {
fprintf($o, " %d", $in[$i][$j]);
}
for ($j = 0; $j < $onum; $j++) {
fprintf($o, " %d", $out[$i][$j]);
}
fprintf($o, "\n");
}
fclose($o);
}

function simple_test() {
$kron = get_conversion_matrix(3);
$f = array(0, 2, 6, 4, 7, 5, 1, 2);
$ret = gen_polinom_koeffs($kron, $f);
print_2d_matrix($kron);
print_r($ret);
print_polinom($ret);
check_polinom_linearity($ret);
}

function check_truth_table_linearity($in_file) {
$file = file_get_contents($in_file);
read_tt($file, $in, $out);
if (check_linearization_possibility($in, $out)) {
echo "Possible !!!!\n";
} else {
echo "Not possible\n";
}
}

function try_to_find_linear_truth_table($out_file, $inum, $onum) {
for ($i = 0; $i < 100000; $i++) {
unset($in);
unset($out);
gen_random_truth_table($inum, $onum, $in, $out);

if (check_linearization_possibility($in, $out)) {
print_table_to_file($out_file, $in, $out);
echo "Possible !!!!\n";
break;
} else {
echo "Not possible\n";
}
}
echo "\n\n";
}

check_truth_table_linearity("example.txt");
// try_to_find_linear_truth_table("tt.txt", 3, 2);

?>
</source>

== Примеры логических функций ==

=== Представимы линейным полиномом ===

<pre>
3 4
0 0 0 0 1 1 1
0 0 1 0 0 1 1
0 1 0 1 0 0 0
0 1 1 0 1 0 0
1 0 0 1 1 1 0
1 0 1 1 0 1 0
1 1 0 1 1 1 1
1 1 1 1 0 1 1
</pre>

=== Непредставимы линейным полиномом ===

ISCAS85 C17:
<pre>
5 2
(0, 0, 0, 0, 0) | (0, 0)
(0, 0, 0, 0, 1) | (0, 1)
(0, 0, 0, 1, 0) | (0, 0)
(0, 0, 0, 1, 1) | (0, 1)
(0, 0, 1, 0, 0) | (0, 0)
(0, 0, 1, 0, 1) | (0, 1)
(0, 0, 1, 1, 0) | (0, 0)
(0, 0, 1, 1, 1) | (0, 0)
(0, 1, 0, 0, 0) | (1, 1)
(0, 1, 0, 0, 1) | (1, 1)
(0, 1, 0, 1, 0) | (1, 1)
(0, 1, 0, 1, 1) | (1, 1)
(0, 1, 1, 0, 0) | (1, 1)
(0, 1, 1, 0, 1) | (1, 1)
(0, 1, 1, 1, 0) | (0, 0)
(0, 1, 1, 1, 1) | (0, 0)
(1, 0, 0, 0, 0) | (0, 0)
(1, 0, 0, 0, 1) | (0, 1)
(1, 0, 0, 1, 0) | (0, 0)
(1, 0, 0, 1, 1) | (0, 1)
(1, 0, 1, 0, 0) | (1, 0)
(1, 0, 1, 0, 1) | (1, 1)
(1, 0, 1, 1, 0) | (1, 0)
(1, 0, 1, 1, 1) | (1, 0)
(1, 1, 0, 0, 0) | (1, 1)
(1, 1, 0, 0, 1) | (1, 1)
(1, 1, 0, 1, 0) | (1, 1)
(1, 1, 0, 1, 1) | (1, 1)
(1, 1, 1, 0, 0) | (1, 1)
(1, 1, 1, 0, 1) | (1, 1)
(1, 1, 1, 1, 0) | (1, 0)
(1, 1, 1, 1, 1) | (1, 0)
</pre>

Модульные операции

2015-02-18T09:05:38Z

Isaeva: Новая страница: «Возможность применения СОК в вычислительных алгоритмах обусловлено наличием определён…»

Возможность применения СОК в вычислительных алгоритмах обусловлено наличием определённого изоморфизма между математическими операциями над целыми числами и соответствующими операциями над системой целых неотрицательных остатков по отдельным модулям. Сложение, умножение, возведение в целую положительную степень любых целых положительных чисел идентичны соответствующим операциям, выполняемым над системой остатков.

Пусть операнды <math>A</math> и <math>B</math>, а также результаты операций сложения и умножения <math>A+B</math> и <math>A \cdot B</math> представлены соответственно остатками <math>{\alpha}_i, {\beta}_i, {\gamma}_i, {\delta}_i</math> по основаниям <math>p_i (i=1, \ldots, n)</math>, причём оба числа и результаты находятся в диапазоне <math>[0, P)</math>, то есть

:<math>A=({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n)</math>,
:<math>A=({\beta}_1, {\beta}_2, \ldots, {\beta}_n)</math>,
:<math>A=({\gamma}_1, {\gamma}_2, \ldots, {\gamma}_n)</math>,
:<math>A=({\delta}_1, {\delta}_2, \ldots, {\delta}_n)</math>

и

:<math>0 \le A <P, 0 \le B <P, 0 \le A+B <P, 0 \le A\cdot B <P</math>.

<to be continued>

Matlab residue library

2015-02-11T14:04:04Z

Turbo: Новая страница: «Состав * [http://vscripts.ru/res/2015/matlab/residue_lib.mdl residue_lib.mdl] - библотека модулярных умножителей, сумат…»

Состав

* [http://vscripts.ru/res/2015/matlab/residue_lib.mdl residue_lib.mdl] - библотека модулярных умножителей, суматоров, преобразователей и т.д.
* [http://vscripts.ru/res/2015/matlab/module_convolution.mdl module_convolution.mdl] - основная схема с параметризируемыми подблоками и схемами, в разных вариациях
* [http://vscripts.ru/res/2015/matlab/module_basic.mdl module_basic.mdl] - вспомогательная схема проверки основных операций сложения и умножения.

Теорема о делении с остатком. Алгоритм Евклида

2014-12-10T09:07:53Z

Isaeva:

Напомним теорему о делении с остатком:

'''Теорема о делении с остатком'''

Для любых целых <math>a</math> и <math>b</math>, <math>b \not= 0</math>, существует единственный набор целых чисел <math>q</math> и <math>r</math>, что <math>a = bq + r</math> и <math>0 \le r < |b|</math>, где <math>|b|</math> — модуль числа <math>b</math>.

Легко доказывается, что для любых целых чисел <math>a</math> и <math>b</math>, <math>b \not= 0</math> деление с остатком возможно и числа <math>q</math> и <math>r</math> определяются однозначно.

Рассмотрим следующий пример:

'''Пример'''

Пусть модуль <math>p = 6</math>.

Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:

:<math>K_0 = \left\{\ldots,-18,-12,-6,0,6,12,18,\ldots \right\}, r=0</math>;

:<math>K_1 = \left\{\ldots,-17,-11,-5,1,7,13,19,\ldots \right\}, r=1</math>;

:<math>K_2 = \left\{\ldots,-16,-10,-4,2,8,14,20,\ldots \right\}, r=2</math>;

:<math>K_3 = \left\{\ldots,-15,-9,-3,3,9,15,21,\ldots \right\}, r=3</math>;

:<math>K_4 = \left\{\ldots,-14,-8,-2,4,10,16,22,\ldots \right\}, r=4</math>;

:<math>K_5 = \left\{\ldots,-13,-7,-1,5,11,17,23,\ldots \right\}, r=5</math>,

где через <math>r</math> обозначен остаток от деления целого числа на 6.

В данном примере полная система наименьших неотрицательных вычетов есть множество <math>\left\{0, 1, 2, 3, 4, 5 \right\}</math>;

полная система наименьших положительных вычетов – множество <math>\left\{1, 2, 3, 4, 5, 6 \right\}</math>;

полная система наименьших по абсолютной величине вычетов – множество <math>\left\{-2,-1, 0, 1, 2, 3 \right\}</math>;

приведённая система вычетов – множество <math>\left\{1,5 \right\}</math>, так как <math>\varphi(6) = 6\,\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right) = 2</math>;

фактор-множество <math>Z{|{\equiv}_6} = \left\{K_0, K_1, K_2, K_3, K_4, K_5 \right\}</math>.

Один из методов выполнения арифметических операций над целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные числа – модули <math>p_1, p_2, \ldots, p_n</math>.
Чаще всего модули <math>p_1, p_2, \ldots, p_n</math> выбирают из множества простых чисел.

Пусть

: <math>A \equiv {\alpha}_1 \pmod{p_1}</math>,
: <math>A \equiv {\alpha}_2 \pmod{p_2}</math>,
: <math>\ldots</math>,
: <math>A \equiv {\alpha}_n \pmod{p_n}</math>.

Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. <math>\forall a \in Z, \forall b \in Z, b\not= 0 \, \exist q \in Z, \exist r \in Z (0 \le r <b):\, a=bq+r </math>, то кольцо Z, по определению, является евклидовым. Таким образом, в качестве чисел <math> {\alpha}_i, i=0,\ldots,n </math> можно выбрать остатки от деления числа <math>A</math> на <math>p_i</math> соответственно.

Рассмотрим гомоморфное отображение:

:<math>Z \to Z{|{\equiv}_{p_1}} \times Z{|{\equiv}_{p_2}} \times \ldots \times Z{|{\equiv}_{p_n}} </math> .

Тогда каждому целому числу <math>A</math> можно поставить в соответствие кортеж <math>\left\{{\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n \right\}</math> наименьших неотрицательных вычетов по одному из соответствующих классов.

Важно отметить, что при преобразовании числа нет потери информации, если выполнено условие <math>A < p_1 \cdot p_2 \cdot \ldots \cdot p_n</math>, поскольку всегда, зная <math>\left({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n \right)</math> можно восстановить само число <math>A</math>. Поэтому кортеж можно рассматривать как один из способов представления целого числа <math>A</math> – модулярное представление, или представление в системе остаточных классов (СОК).

Для дальнейшего используем расширенный алгоритм Евклида или его аналог – алгоритм нахождения линейного представления наибольшего общего делителя целых чисел: если числа а и b одновременно не равны нулю, то существуют целые числа <math>x</math> и <math>y</math>, такие, что <math>a \cdot b = a \cdot x + b \cdot y</math>.

Действительно, пусть <math>d</math> – наименьшее целое положительное число вида <math>a \cdot x + b \cdot y</math>, например, <math>d = a \cdot x_0 + b \cdot y_0</math>, где числа <math>x_0</math> и <math>y_0</math> не обязательно определены однозначно. Существование числа <math>d</math> следует только из принципа полной упорядоченности. Очевидно, что <math>d > 0</math>. Остаётся показать, что <math>d = (a,b)</math>. Для этого надо проверить выполнение двух условий: а) <math>d|a</math> и <math>d|b</math> б) если <math>c|a</math> и <math>c|b</math>
то <math>c|d</math>.

От противного: допустим, что свойство а) не выполняется, для определенности положим, что не выполнено <math>d|b</math>. Тогда по теореме о делении с остатком <math>a = dq + r</math>, <math>0 \le r < |d|</math>, и, следовательно,

:<math>r=b-dq = b-(ax_0+by_0)q = a(-qx_0)+b(1-qy_0)</math>,

что противоречит минимальности <math>d</math>.

Выполнение свойства б) проверяется непосредственно:

:<math>c|a \Rightarrow \left(\exist q_1 \in Z\right)\left(a = q_1\, c\right)</math>;

:<math>c|b \Rightarrow \left(\exist q_2 \in Z\right)\left(a = q_2\, c\right)</math>;

:<math>d=ax_0 + by_0 \Rightarrow d = q_1 c x_0 + q_2 c y_0 \Rightarrow d = \left(q_1 x_0 + q_2 y_0\right) c|d </math>.

'''Алгоритм Евклида для целых чисел'''

Пусть <math>a</math> и <math>b</math> — целые числа, не равные одновременно нулю, и последовательность чисел
: <math> a > b > r_1 > r_2 > r_3 > r_4 > \cdots >r_n</math>
определена тем, что каждое <math>r_k</math> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
: <math>a = bq_0 + r_1</math>
: <math>b = r_1q_1 + r_2</math>
: <math>r_1 = r_2q_2 + r_3</math>

: <math>\cdots</math>
: <math>r_{k-2} = r_{k-1} q_{k-1} + r_k</math>

: <math>\cdots</math>
: <math>r_{n-2} = r_{n-1}q_{n-1}+ r_n</math>
: <math>r_{n-1} = r_n q_n</math>

Тогда '''НОД''' <math>(a,b)</math>, наибольший общий делитель <math>a</math> и <math>b</math>, равен
<math>r_n</math>, последнему ненулевому члену этой последовательности.

'''Существование''' таких <math>r_1, r_2, ...</math>, то есть возможность деления с остатком <math>a</math> на <math>b</math> для любого целого <math>a</math> и целого <math>b\ne 0</math>, доказывается индукцией.

'''Корректность''' этого алгоритма вытекает из следующих двух утверждений:

* Пусть <math>a = bq + r</math>, тогда '''НОД''' <math>(a,b)</math> = '''НОД''' <math>(b,r)</math>.
* '''НОД''' <math>(0,r)</math> = <math>r</math> для любого ненулевого <math>r</math> (так как 0 делится на любое целое число, кроме нуля).

'''Расширенный алгоритм Евклида для целых чисел'''

Рассмотрим расширенный алгоритм Евклида для нахождения линейного представления наибольшего общего делителя <math>(a,b) = ax + by </math>.

Значения <math>x</math> и <math>y</math> вычисляются в серии шагов, в каждом из которых мы выражаем <math>a_i</math> (вычисленное в процессе работы алгоритма Евклида) в форме <math>a x_i + b y_i </math>. А именно, рассмотрим последовательность

: <math>a_0 = a</math>, <math>a_0 = a x_0 + b y_0</math>,

: <math>a_1 = b</math>, <math>a_1 = a x_1 + b y_1</math>,

: <math>a_2 = a_0 - a_1 q_1</math>, <math>a_2 = a x_2 + b y_2</math>,

: <math>a_3 = a_1 - a_2 q_2</math>, <math>a_3 = a x_3 + b y_3</math>,

: <math>\cdots</math>

: <math>a_i = a_{i-2} - a_{i-1} q_{i-1}</math>, <math>a_i = a x_i + b y_i</math>,

: <math>\cdots</math>

: <math>a_k = a_{k-2} - a_{k-1} q_{k-1}</math>, <math>a_k = a x_k + b y_k</math>,

: <math>0 = a_{k-1} - a_k q_k</math>, <math>0 = a x_{k+1} + b y_{k+1}</math>,

В левом столбце алгоритма записана последовательность делений, которая получается в результате работы алгоритма Евклида и которая разрешена относительно остатков. Согласно теореме Ламе (1844 г.) число делений, которое необходимо выполнить для нахождения <math>(a,b)</math>, не превосходит числа цифр в меньшем из чисел <math>a</math> и <math>b</math>, умноженного на 5 (оценка наихудшего случая для алгоритма Евклида). Теорема Ламе доказывается на основе последовательности Фибоначчи.

В правом столбце алгоритма каждый остаток выражен через <math>a x_i + b y_i</math>. Надо вычислить <math>x_i</math> и <math>y_i</math>. Очевидно, что <math>x_0 = 1, y_0 = 0</math> и <math>x_1 = 0, y_1 = 1</math>. Сравнивая обе части на ''i''-м шаге, получим

:<math>a_i = a x_i + b y_i = a_{i-2} - a_{i-1} q_{i-1} = \left(a x_{i-2} + b y_{i-2} \right) - \left(a x_{i-1} + b y_{i-1} \right) q_{i-1} =</math>

:<math> \left(a x_{i-2} - x_{i-1} q_{i-1} \right) + \left(b y_{i-2} - y_{i-1} q_{i-1} \right)</math>,

откуда получается следующая индуктивная процедура вычисления <math>x_i</math> и <math>y_i</math>:

:<math>q_{i-1} = \left \lfloor \frac{a_{i-2}}{a_{i-1}} \right \rfloor</math>,

:<math>a_i = a_{i-2} - a_{i-1} q_{i-1}</math>,

:<math>x_i = x_{i-2} - x_{i-1} q_{i-1}</math>,

:<math>y_i = y_{i-2} - y_{i-1} q_{i-1}</math>.

'''Пример (Расширенный алгоритм Евклида)'''.

Применим расширенный алгоритм Евклида к числам <math>a = 342, b = 612</math>.

Весь алгоритм представим в виде следующей таблицы.

<math> \begin{array}{|c|r|r|r|r|r|r|r|} \hline Iteration & q & a_0 & a_1 & x_0 & x_1 & y_0 & y_1
\\ \hline 0 & - & 342 & 612 & 1 & 0 & 0 & 1
\\ \hline 1 & 0 & 612 & 342 & 0 & 1 & 1 & 0
\\ \hline 2 & 1 & 342 & 270 & 1 & -1 & 0 & 1
\\ \hline 3 & 1 & 270 & 72 & -1 & 2 & 1 & -1
\\ \hline 4 & 3 & 72 & 54 & 2 & -7 & -1 & 4
\\ \hline 5 & 1 & 54 & 18 & -7 & 9 & 4 & -5
\\ \hline 6 & 3 & 18 & 0 & 9 & -34 & -5 & 19

\\ \hline \end{array} </math>

Заметим, что равенство <math>a_0 = a x_0 + b y_0</math> выполняется на каждом шаге итерации. Алгоритм выдаёт

:<math>d = 18, x = 9, y = -5</math>,

и тогда

:<math>18=342 \cdot 9 + 612 \cdot (-5)</math>.

Расширение диапазона представления чисел

2014-12-03T13:31:36Z

Isaeva:

Расширение системы оснований является одной из основных немодульных операций в СОК. Выполнение этой операции бывает необходимо при выполнении операции деления чисел, при вычислении позиционных характеристик, при обнаружении переполнения при выполнении сложения или умножения чисел.
Задачу расширения системы оснований можно сформулировать следующим образом: найти остаточное представление числа по новому основанию (новым основаниям), если известно представление числа по другим основаниям остатки от деления на другие числа.
Один из путей расширения системы оснований состоит в переводе числа в позиционную систему счисления и вычисления остатка от деления на новый модуль. Этот путь не является рациональным с точки зрения числа операций.
Другой метод расширения системы оснований позволяет определить цифру числа по новому основанию, базируясь на таких позиционных характеристиках числа, как ранг числа, след числа. Пусть вновь задана система оснований <math>p_1, p_2, \ldots, p_n</math> с диапазоном <math>P</math>, ортогональными базисами <math>B_1, B_2, \ldots, B_n</math>, веса которых <math>m_1, m_2, \ldots, m_n</math>. По определению, <math>B_i = m_i \cdot \frac{P}{p_i}, i=1, \ldots, n</math>. Пусть в этой системе задано число <math>A = ({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n)</math>. Расширим систему оснований, добавляя основание <math>p_{n+1}</math>, тогда диапазон системы станет <math>P' = p_{n+1} \cdot P</math>, ортогональные базисы системы <math>{B_1}', {B_2}', \ldots, {B_n}', {B_{n+1}}'</math>, их веса <math>{m_1}', {m_2}', \ldots, {m_n}', {m_{n+1}}'</math>, причём <math>{B_i}' = {m_i} \cdot \frac{p_{n+1} \cdot P}{p_i}, i=1, \ldots, n+1</math>. Задача состоит в определении цифры <math>{\alpha}_{n+1})</math> числа <math>A = ({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n)</math> по основанию <math>p_{n+1}</math>. Минимальным следом числа называют цифру <math>{S^*}_A</math>, при которой число <math>A^* = ({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n), {S^*}_A</math> находится в интервале <math> \left[0,\frac{P'}{p_{n+1}}\right]</math>, и число <math>A \in \left[0,P\right)</math>. Определение цифры по основанию <math>p_{n+1}</math> сводится тогда к определению минимального следа числа <math>A</math> в расширенной системе оснований.

Интервальные методы перевода

2014-10-22T13:55:56Z

Isaeva:

Достаточно эффективными методами перевода чисел из СОК в ПСС являются интервальные методы, основанные на интервальных характеристиках чисел. Одна из таких характеристик – номер интервала.

Рассмотрим СОК, заданную системой оснований <math>p_1, p_2, \ldots, p_n</math> с объёмом диапазона <math>P = p_1\cdot p_2\cdot \ldots \cdot p_n</math>. Выберем дробящий модуль <math>p_i</math> и проведём дробление заданного диапазона на интервалы путём деления <math>P</math> на модуль <math>p_i</math>. Тогда количество интервалов <math>m = P_i = \frac {P}{p_i}</math>, а длина интервала определяется величиной модуля.

В результате величину любого числа <math>A</math>, заданного в СОК по выбранным основаниям, можно определить по номеру интервала:

:<math>l_A = \left [\frac {A}{p_i}\right ]</math> (1),

в котором находится число <math>A</math>, и по цифре <math>\alpha_i</math> числа <math>A</math> в СОК по модулю <math>p_i</math>, т.е.

:<math>A = p_i \cdot l_A + {\alpha}_i</math> (2).

Так как <math>(p_i, P_i) = 1</math>, то по теореме Эйлера:

:<math>{P_i}^{\varphi(p_i)} \equiv 1\pmod {p_i}</math> (3),

где <math>\varphi(p_i)</math> - – функция Эйлера.
Причём если <math>p_i</math> – простое число, то <math>\varphi(p_i) = p_i - 1</math>.

Число <math>A</math> можно представить в виде

:<math>A = \left| \sum _{i = 1}^{n} {P_i}^{\varphi(p_i)} \cdot \alpha_i \right| \pmod P</math> (4).

Для определения номера интервала <math>l_A</math>, подставим выражение (4) в (1):

:<math>l_A = \left [\frac {A}{p_i}\right ]</math>