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

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

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

Всем привет!

Есть вопрос по определителям в двоичной системе. Я не математик, пожалуйста отнестись к моему описанию с пониманием.

Дано выражение
Где + = xor в двоичном представлении
a[0], b[0], c[0] - переменные с возможным значением 0 или 1.
f[] - результат
Возможно ли ниже приведенную выражение как-то привести к матричному ввиду (определителю), чтобы в более простой и легкой форме производить операции умножения или сложения (исключающие или) с аналогичными выражениями.

[math](a[0]+b[0]+c[0])(b[0]+c[0])(c[0])[/math]

Возможны операции
умножение
[math](a[0]+b[0]+c[0])(b[0]+c[0])(c[0]) (a[1]+b[1]+c[1])(b[1]+c[1])(c[1])=f[0][/math]
или сложения
[math](a[0]+b[0]+c[0])(b[0]+c[0])(c[0]) (a[1]+b[1]+c[1])(b[1]+c[1])(c[1])=f[1][/math]
или сложения


Посоветуйте, какую литературу почитать. Кол-во слагаемых и множителей может быть любым.

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

Вы хотите упростить выражение [math]x_0(x_0+x_1)(x_0+x_1+x_2)...(x_0+x_1+...+x_n)[/math] над полем вычетов по модулю 2?
Если да, то его проще явно вычислять, оно очевидно, чему равно.
У Вас [math]a(0)[/math] и [math]a(1)[/math] никак не связаны кроме имени?

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

Да мне нужно максимально упростить выражение исключая четные повторяющиеся слагаемые.
Кол-во переменных может очень большим и в этом случае простой метод перебора становиться не практичным.

Вот еще пример выражения для примера для оптимизации
[math]((a[1]b[0]+a[0]b[1])+f[1]+1)(a[1]b[0]a[0]b[1](a[2]b[0]+a[1]b[1]+a[0]b[2])+a[1]b[1]+f[2]+1).......()=1(mod 2)[/math]

Вопрос в каком виде представить данное выражением для оптимизации ? Подходит ли для этой задачи - определитель ?

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

Давайте сначала с первым примером разберемся.
Обозначим [math]y_k=x_1+...+x_k[/math], получим [math]y_1y_2...y_n[/math]. Чему может быть равно это выражение по модулю 2? Либо 0, либо 1. [math]y_1y_2...y_n\equiv 1\pmod 2[/math] только в одном очевидном случае (найдите его). Теперь, когда мы нашли [math]y_k[/math], мы можем найти [math]x_k[/math]: [math]x_1=y_1, x_k=y_k-y_{k-1}[/math] и все. После этого можете просто восстановить СДНФ или СКНФ (или полином Жегалкина - что удобнее покажется) по значениям, может быть упростить ее, если получится.

Со вторым примером: все [math]a_j,b_j,f_j[/math] независимы? Или [math]f_j[/math] - те, что определены выше. И закон выписывания выражения я не понял - поясните (у Вас там [math]a[1]b[1][/math] два раза повторен).

И еще я не понял - откуда тут у Вас определители?

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

Sonic писал(а):
Давайте сначала с первым примером разберемся.
Обозначим [math]y_k=x_1+...+x_k[/math], получим [math]y_1y_2...y_n[/math]. Чему может быть равно это выражение по модулю 2? Либо 0, либо 1. [math]y_1y_2...y_n\equiv 1\pmod 2[/math] только в одном очевидном случае (найдите его). Теперь, когда мы нашли [math]y_k[/math], мы можем найти [math]x_k[/math]: [math]x_1=y_1, x_k=y_k-y_{k-1}[/math] и все. После этого можете просто восстановить СДНФ или СКНФ (или полином Жегалкина - что удобнее покажется) по значениям, может быть упростить ее, если получится.

Со вторым примером: все [math]a_j,b_j,f_j[/math] независимы? Или [math]f_j[/math] - те, что определены выше. И закон выписывания выражения я не понял - поясните (у Вас там [math]a[1]b[1][/math] два раза повторен).

И еще я не понял - откуда тут у Вас определители?


Кол-во переменных и выражений в скобках может быть больше > 100. Полимон Жегалкина, это то что мне нужно получить и исключив повторяющиеся (четные) слагаемые после раскрытия скобок.

Второй пример не зависит от первого и соответственно значения f[i]. Повторяющиеся значения a[1]b[1] не случайность. Такое может быть при решении реальной задачи и мне как-то надо отслеживать повторяющиеся значения и удалять их.

Поясню для чего все это мне нужно
Наверняка вы знакомы с умножением чисел в двоичном виде.
Вот пример умножения двух чисел результат которого составляет 4 бита


[math]a[0]=1[/math]
[math]b[0]=1[/math]

[math]f[0],f[1],f[2],f[3][/math] - известные

[math]s[0]=a[0]b[0][/math]
[math]f[0]=a[0]b[0][/math] - значение 0 бита
[math]p[0]=f[0]|2= 0[/math] - перенос. значение f деленное на два

[math]s[1]=a[1]b[0]+a[0]b[1][/math]
[math]f[1]=s[1]+p[0]=a[1]b[0]+a[0]b[1][/math] - значение первого бита результат
[math]p[1]=f[1]|2=a[1]b[0]a[0]b[1][/math]

[math]s[2]=a[2]b[0]+a[1]b[1]+a[0]b[2][/math]
[math]f[2]=s[2]+p[1]=a[2]b[0]+a[1]b[1]+a[0]b[2]+a[1]b[0]a[0]b[1][/math]-значение второго бита результата
[math]p[2]=f[2]|2=a[2]b[0](a[1]b[1]+a[0]b[2]+a[1]b[0]a[0]b[1])+a[1]b[1](a[0]b[2]+a[1]b[0]a[0]b[1])+a[0]b[2](a[1]b[0]a[0]b[1])[/math]

[math]s[3]=a[0]b[3]+a[1]b[2]+a[2]b[1]+a[3]b[0][/math]
[math]f[3]=s[3]+p[2]=a[0]b[3]+a[1]b[2]+a[2]b[1]+a[3]b[0]+a[2]b[0](a[1]b[1]+a[0]b[2]+a[1]b[0]a[0]b[1])+a[1]b[1](a[0]b[2]+a[1]b[0]a[0]b[1])+a[0]b[2](a[1]b[0]a[0]b[1])[/math]-значение третьего бита результата

[math]s[n]+p[n-1]=f[n][/math]
[math]s[n]+p[n-1]+1=f[n]+1[/math]
[math]s[n]+p[n-1]+1+f[n]=1[/math]

[math](s[0]+1+f[0])(s[1]+p[0]+1+f[1])(s[2]+p[1]+1+f[2])(s[3]+p[3]+1+f[2])=1[/math]

Подставив вместо [math]s[n],p[n-1],f[n][/math] реальные выражения и раскрыв скобки мы получим в сокращенной форме выражение - которое и есть решение (множество) данного уравнения.
Проблема в том, что кол-во слагаемых и множителей в реально задаче будет гораздо больше. Вопрос как оптимизировать процесс решения.
Возможно все эти выражения можно записать в виде матриц и найти решение с помощью матриц (определителей), а не выражений?
Я не математик и не знаком со всеми инструментами. Поэтому ищу совет у знающих людей.
Что вы можете предложить, для уменьшения числа операций умножений, сложений и исключения повторяющихся значений?

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

Так, ну 1-й пример я написал, как делать (выписывать решение явно я не буду - непедагогично, сам сейчас выписал - у меня все упростилось (в определенном смысле))

Цитата:
[math]f[0]=a[0]b[0][/math] - значение 0 бита
[math]p[0]=f[0]|2= 0[/math]- перенос. значение f деленное на два
Вот это как-то странно выглядит. Из 1-го соотношения следует [math]f[0]\in\{0,1\}[/math], из этого и 2-го следует, что [math]p[0]=0[/math].

Так.
Нет.
Вы берете задачу и пытаетесь мне ее выписать "на низком уровне". Наверное, зря Вы пытаетесь выписывать длинные выражения, думаю, проще будет сказать, чего Вы хотите. У Вас дано 2 [math]N[/math]-битных числа и Вы хотите выписать полином Жегалкина их суммы и произведения?

Сейчас буду по мелочи писать, что понял. Квадратные скобки я писать не буду, ибо многабукаф.
[math]s_k=\sum\limits_{j=0}^ka_jb_{k-j}[/math]

[math]a_j,b_j[/math] известные или нет?

Не, дальше я не понял: с одной стороны Вы пишите, что [math]f_j[/math] известные, с другой стороны - выражаете их через [math]a_j,b_j[/math] неясно как.

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

Sonic писал(а):
Так, ну 1-й пример я написал, как делать (выписывать решение явно я не буду - непедагогично, сам сейчас выписал - у меня все упростилось (в определенном смысле))

Цитата:
[math]f[0]=a[0]b[0][/math] - значение 0 бита
[math]p[0]=f[0]|2= 0[/math]- перенос. значение f деленное на два
Вот это как-то странно выглядит. Из 1-го соотношения следует [math]f[0]\in\{0,1\}[/math], из этого и 2-го следует, что [math]p[0]=0[/math].

Так.
Нет.
Вы берете задачу и пытаетесь мне ее выписать "на низком уровне". Наверное, зря Вы пытаетесь выписывать длинные выражения, думаю, проще будет сказать, чего Вы хотите. У Вас дано 2 [math]N[/math]-битных числа и Вы хотите выписать полином Жегалкина их суммы и произведения?

Сейчас буду по мелочи писать, что понял. Квадратные скобки я писать не буду, ибо многабукаф.
[math]s_k=\sum\limits_{j=0}^ka_jb_{k-j}[/math]


При умножение двух чисел в двоичном виде, значение переноса для нулевого разряда равно 0.

Задача на высоком уровне - факторизация чисел
Описанный метод - подход, который требует доработки.

Есть A * B = F, где A и B целые неизвестные и F - известное число
Пример
A*B = 15

Суть подхода - составит систему уравнений Жегалкина для каждого бита F[i] из значений битов A и B.
Далее решить систему уравнений.

Теперь когда описал задачу на высоком уровне, можете посмотреть на предыдущий пост по новому? Если что-то непонятно написал, то готов ответить на ваши вопросы.

Сразу не заметил

[math]s_k=\sum\limits_{j=0}^ka_jb_{k-j}[/math][/quote]
a[i] и b[k] - неизвестные

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

novichok писал(а):
Задача на высоком уровне - факторизация чисел
Описанный метод - подход, который требует доработки.

Есть A * B = F, где A и B целые неизвестные и F - известное число
Пример
A*B = 15

Суть подхода - составит систему уравнений Жегалкина для каждого бита F[i] из значений битов A и B.
Далее решить систему уравнений.
Ага! Теперь я понял :) Правда скажу сразу, что эту задачу без мозга слепо формально не решить. Но давайте подумаем...

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

Sonic писал(а):
novichok писал(а):
Задача на высоком уровне - факторизация чисел
Описанный метод - подход, который требует доработки.

Есть A * B = F, где A и B целые неизвестные и F - известное число
Пример
A*B = 15

Суть подхода - составит систему уравнений Жегалкина для каждого бита F[i] из значений битов A и B.
Далее решить систему уравнений.
Ага! Теперь я понял :) Правда скажу сразу, что эту задачу без мозга слепо формально не решить. Но давайте подумаем...


Я предлагаю новый подход к этой задаче.

У меня есть уже наработки по оптимизации, но они пока не столь эффективны.

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

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

upd: я вот только не могу понять, как составляется выражение для [math]p_k[/math]. [math]p_k[/math] - это число добавляемых разрядов, т.е. [math]p_k=\frac{s_k-f_k}{2}[/math], а вот как выражать через [math]a_j,b_j[/math]...
Т.е. понятно, что [math]s_1=a_0b_1+a_1b_0\leqslant 2[/math], причем равенство достигается, если все биты равны 1, значит [math]p_1=a_0a_1b_0b_1[/math]. А в общем...
upd2:
[math]f_k+s_k+p_{k-1}\equiv 0 \pmod 2[/math] - это верно, но можно ли отбрасывать соотношение [math]p_k=\frac{s_k-f_k}{2}[/math]? Просто если нельзя, то его еще надо суметь переписать в виде сравнения по модулю 2.

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