Математический форум Math Help Planet
http://mathhelpplanet.com/

Матрица для XOR
http://mathhelpplanet.com/viewtopic.php?f=62&t=24387
Страница 2 из 2

Автор:  novichok [ 19 май 2013, 17:23 ]
Заголовок сообщения:  Re: Матрица для XOR

Sonic писал(а):
novichok писал(а):
Я предлагаю новый подход к этой задаче.
У меня есть уже наработки по оптимизации, но они пока не столь эффективны.
Не, я Вас понимаю :) Я Вас просто предупреждаю сразу, что это серьезная теоретическая задача, на которую легко убить кучу времени, вряд ли она решается так "насильно".
Но что и как делать - решать, конечно, Вам.


Я за красивые и простые решения ). Уверен, что решение есть и простое.

Автор:  Sonic [ 19 май 2013, 17:53 ]
Заголовок сообщения:  Re: Матрица для XOR

Короче, я не вижу пока явный способ переписать соотношение [math]AB=F[/math] полностью в виде системы уравнений в [math]\mathbb{Z}_2[/math] в виде битовых переменных [math]a_j,b_j,f_j[/math] :( . Надо сначала суметь это сделать, а потом пытаться упрощать полученные уравнения.
Т.е. Вы делаете так:
[math]A=\sum\limits_{j=0}^na_j2^j, \ B=\sum\limits_{j=0}^nb_j2^j, \ F=\sum\limits_{j=0}^{2n}f_j2^j[/math]
Перемножаем [math]A,B[/math], вводим обозначение [math]s_k=\sum\limits_{j=0}^ka_jb_{k-j}[/math], получаем соотношение [math]\sum\limits_{j=0}^{2n}s_j2^j=\sum\limits_{j=0}^{2n}f_j2^j[/math], но здесь [math]f_j\in\{0;1\}[/math], а [math]s_j[/math] таково, что [math]0\leqslant s_j\leqslant n[/math], т.е. [math]s_j[/math] - уже не булева переменная. И надо исхитряться. Ясно, что [math]s_j\equiv f_j \pmod 2[/math] и тогда [math]s_j=r_j+2p_j[/math], Вы пишите сложение битов, но [math]p_j[/math] - не булево, оно потенциально неограниченно при возрастании [math]n[/math].
Надеюсь, я понятно написал :(

Автор:  novichok [ 19 май 2013, 18:43 ]
Заголовок сообщения:  Re: Матрица для XOR

Понятно. Вы главное не поняли :) Вся фишка в p[i] - я смог прописать его в виде булевого выражения, как и значение s[i]. Очень много времени и сил потратил на это, а решение оказалось простым.

Пересмотрите внимательно пост с примером системы уравнений. Особенно на f[1], p[1], f[2], p[2], f[3], p[3]

Постараюсь пояснить на примере. Кстати все вычисления подразумевают полином Жегалкина, а не вычеты по модулю 2. Так проще.
e[i]={0,1}
r[3]={0,1}
r[3] = e[0]+e[1]+e[2]+e[3]
r[3]/2 = e[0](e[1]+e[2]+e[3])+e[1](e[2]+e[3])+e[2]e[3]

[math]p\limits_{n}=\sum\limits_{i=0}^{n-1}e_{i}\sum\limits_{k=i+1}^{n}e_{k}[/math]

И еще, чтобы не путаться отделите сумму бит (xor) для каждого разряда s[i] от суммы бит переноса и p[i]. Иначе есть риск запутаться и усложнить формулу.

Автор:  novichok [ 19 май 2013, 18:56 ]
Заголовок сообщения:  Re: Матрица для XOR

Использовал данный рисунок при анализе умножения в двоичном виде. Возможно и вам он поможет как наглядное пособие.
Изображение

Автор:  Sonic [ 19 май 2013, 19:04 ]
Заголовок сообщения:  Re: Матрица для XOR

Цитата:
Понятно. Вы главное не поняли :) Вся фишка в p[i] - я смог прописать его в виде булевого выражения, как и значение s[i]. Очень много времени и сил потратил на это, а решение оказалось простым.
Так ведь [math]p_j[/math] не является булевой переменной. Либо является (определений явных нет, потому мутно буду писать), но тогда надо аккуратно формулы выписать

Цитата:
Пересмотрите внимательно пост с примером системы уравнений. Особенно на f[1], p[1], f[2], p[2], f[3], p[3]
Ну как обычно :( попробую понять...

Цитата:
Постараюсь пояснить на примере. Кстати все вычисления подразумевают полином Жегалкина, а не вычеты по модулю 2. Так проще.
Не понял. Полиномы Жегалкина - они всегда по модулю 2.

Цитата:
e[i]={0,1}
r[3]={0,1}
r[3] = e[0]+e[1]+e[2]+e[3]
r[3]/2 = e[0](e[1]+e[2]+e[3])+e[1](e[2]+e[3])+e[2]e[3]

[math]p\limits_{n}=\sum\limits_{i=0}^{n-1}e_{i}\sum\limits_{k=i+1}^{n}e_{k}[/math]
А как [math]e_i[/math] определяются?

Цитата:
И еще, чтобы не путаться отделите сумму бит (xor) для каждого разряда s[i] от суммы бит переноса и p[i]. Иначе есть риск запутаться и усложнить формулу.
Тоже не понял :(

Боюсь, придется все формально выписывать.

Посмотрел на рисунок: ну вот, я же говорил: [math]p_j[/math] не является булевой переменной, значит для нее не существует полинома Жегалкина (в смысле, бессмысленно говорить о полиноме Жегалкина для [math]p_j[/math]).

Короче, я сейчас картинку поразбираю и сам все выпишу. Наверное...

upd: на картинке в предпоследней строке надо писать [math]S_i+P_i[/math], а не дробь :unknown:
Вообще на картинке обычное умножение в двоичной системе счисления. В ней [math]f_j=s_j+p_j \bmod 2[/math], а [math]p_j=\left[\frac{s_j}{2}\right][/math]. Это все понятно, но как Вы это в булев вид переводите - это проблема.

Автор:  novichok [ 19 май 2013, 20:12 ]
Заголовок сообщения:  Re: Матрица для XOR

Цитата:
Так ведь p[i] не является булевой переменной.

p[i] - содержит кол-во бит переноса для текущего разряда. информацию о кол-во нужно сохранять, чтобы корректно рассчитывать последующие разряды.
((s[i]+p[i-1])/2)(mod 2)=f[i] - так для вас привычней.
вычет по модулю два от выражения суммы бит текущего разряда плюс сумма бит переноса деленное на два равно значению текущего разряда.

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

в приведенном примере раскрыт подход
e[i] - это булева переменная
+ в данном примере означает ИСКЛЮЧАЮЩЕЕ ИЛИ
r[3] = e[0]+e[1]+e[2]+e[3]
r[3]/2 = e[0](e[1]+e[2]+e[3])+e[1](e[2]+e[3])+e[2]e[3]

допустим все значения e равны 1
тогда
r[3] = 1+1+1+1 = 0, а математически = 4 кол-во бит хранимой информации
r[3]/2 = 1(1+1+1)+1(1+1)+1(1)=0, а математически = 2 кол-во бит хранимой информации

другой пример
r[3] = 1+1+1+0 = 1, а математически = 3
r[3]/2 = 1(1+1+0)+1(1+0)+1(0)=1, а математически 1. так и есть целое(3/2) = 1

рисунок помогал мне перепроверять корректность формулы
я не могу записать формулу для p[15] - пятнадцатого разряда, потому что мне не хватит места в теле сообщений. такое большое выражение будет из-за рекурсии. но для 3 бит пример я привел в первых постах.

Автор:  novichok [ 20 май 2013, 19:36 ]
Заголовок сообщения:  Re: Матрица для XOR

надо смотреть на p[n] не в контексте значения 0 или 1, а в контексте булевого выражения с N переменными.

Автор:  novichok [ 03 июн 2013, 05:38 ]
Заголовок сообщения:  Re: Матрица для XOR

Придумал простое решение как отказаться от "тяжелой" рекурсии для вычисления выражения p[i]

Автор:  romus [ 26 ноя 2015, 02:48 ]
Заголовок сообщения:  Re: Матрица для XOR

Жаль автор не оставил решения. Очень надо.

Автор:  romus [ 27 ноя 2015, 18:26 ]
Заголовок сообщения:  Re: Матрица для XOR

В продолжение данной темы. Я понял, что автор не смог решить свою проблему. А мне надо ее решить.

f - известно
надо найти a и b

+ = [math]\oplus[/math] = XOR

Для 5 бит:

f0=a0*b0
f1=a0*b1+a1*b0
f2=a0*b2+a1*b1+a2*b0
f3=a0*b3+a1*b2+a2*b1+a3*b0
f4=a0*b4+a1*b3+a2*b2+a3*b1+a4*b0
f5= a1*b4+a2*b3+a3*b2+a4*b1
f6= a2*b4+a3*b3+a4*b2
f7= a3*b4+a4*b3
f8= a4*b4


a0 и b0 - всегда равны 1
Размер битности a и b достигает 100. Методом перебора, постройкой таблиц решить данную задачу не могу.
Пробовал подстановкой. Но получаются слишком сложные вложенности.

Помогите решить задачу. Или, что почитать.

Страница 2 из 2 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/