| Математический форум 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 |
Цитата: Понятно. Вы главное не поняли Так ведь [math]p_j[/math] не является булевой переменной. Либо является (определений явных нет, потому мутно буду писать), но тогда надо аккуратно формулы выписать Вся фишка в p[i] - я смог прописать его в виде булевого выражения, как и значение s[i]. Очень много времени и сил потратил на это, а решение оказалось простым.Цитата: Пересмотрите внимательно пост с примером системы уравнений. Особенно на f[1], p[1], f[2], p[2], f[3], p[3] Ну как обычно попробую понять...Цитата: Постараюсь пояснить на примере. Кстати все вычисления подразумевают полином Жегалкина, а не вычеты по модулю 2. Так проще. Не понял. Полиномы Жегалкина - они всегда по модулю 2. Цитата: e[i]={0,1} А как [math]e_i[/math] определяются?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]. Иначе есть риск запутаться и усложнить формулу. Тоже не понял ![]() Боюсь, придется все формально выписывать. Посмотрел на рисунок: ну вот, я же говорил: [math]p_j[/math] не является булевой переменной, значит для нее не существует полинома Жегалкина (в смысле, бессмысленно говорить о полиноме Жегалкина для [math]p_j[/math]). Короче, я сейчас картинку поразбираю и сам все выпишу. Наверное... upd: на картинке в предпоследней строке надо писать [math]S_i+P_i[/math], а не дробь ![]() Вообще на картинке обычное умножение в двоичной системе счисления. В ней [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 a0 и b0 - всегда равны 1 Размер битности a и b достигает 100. Методом перебора, постройкой таблиц решить данную задачу не могу. Пробовал подстановкой. Но получаются слишком сложные вложенности. Помогите решить задачу. Или, что почитать. |
|
| Страница 2 из 2 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|