Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 17:23 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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


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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 17:53 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Короче, я не вижу пока явный способ переписать соотношение [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].
Надеюсь, я понятно написал :(

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 18:43 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Понятно. Вы главное не поняли :) Вся фишка в 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]. Иначе есть риск запутаться и усложнить формулу.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 18:56 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 19:04 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Цитата:
Понятно. Вы главное не поняли :) Вся фишка в 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]. Это все понятно, но как Вы это в булев вид переводите - это проблема.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 20:12 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Цитата:
Так ведь 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 бит пример я привел в первых постах.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 20 май 2013, 19:36 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 03 июн 2013, 05:38 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 26 ноя 2015, 02:48 
Не в сети
Начинающий
Зарегистрирован:
26 ноя 2015, 00:46
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Жаль автор не оставил решения. Очень надо.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 27 ноя 2015, 18:26 
Не в сети
Начинающий
Зарегистрирован:
26 ноя 2015, 00:46
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

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. Методом перебора, постройкой таблиц решить данную задачу не могу.
Пробовал подстановкой. Но получаются слишком сложные вложенности.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу Пред.  1, 2  Страница 2 из 2 [ Сообщений: 20 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Матрица

в форуме Линейная и Абстрактная алгебра

Nas_tya+-

7

561

20 ноя 2015, 22:05

Матрица

в форуме Линейная и Абстрактная алгебра

maksim-maksim

1

355

25 сен 2017, 20:09

Матрица

в форуме Линейная и Абстрактная алгебра

Matematic123

1

434

14 июн 2019, 21:16

Матрица

в форуме Линейная и Абстрактная алгебра

Ra1DeX

3

191

22 сен 2021, 20:13

Матрица

в форуме Дискретная математика, Теория множеств и Логика

Lera25802580

1

255

18 май 2015, 14:19

Матрица

в форуме Линейная и Абстрактная алгебра

maksim-maksim

6

707

23 сен 2017, 18:09

Матрица

в форуме Линейная и Абстрактная алгебра

BusinkaAnna

1

336

03 ноя 2015, 11:51

Матрица

в форуме Линейная и Абстрактная алгебра

kicultanya

5

493

02 янв 2017, 16:15

Матрица Якоби

в форуме Численные методы

hypersenator

0

305

23 ноя 2016, 20:43

Матрица перехода

в форуме Линейная и Абстрактная алгебра

Windiv

12

390

05 ноя 2020, 16:15


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2024 MathHelpPlanet.com. All rights reserved