| Математический форум 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 бита Вот это как-то странно выглядит. Из 1-го соотношения следует [math]f[0]\in\{0,1\}[/math], из этого и 2-го следует, что [math]p[0]=0[/math].[math]p[0]=f[0]|2= 0[/math]- перенос. значение f деленное на два Так. Нет. Вы берете задачу и пытаетесь мне ее выписать "на низком уровне". Наверное, зря Вы пытаетесь выписывать длинные выражения, думаю, проще будет сказать, чего Вы хотите. У Вас дано 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 бита Вот это как-то странно выглядит. Из 1-го соотношения следует [math]f[0]\in\{0,1\}[/math], из этого и 2-го следует, что [math]p[0]=0[/math].[math]p[0]=f[0]|2= 0[/math]- перенос. значение f деленное на два Так. Нет. Вы берете задачу и пытаетесь мне ее выписать "на низком уровне". Наверное, зря Вы пытаетесь выписывать длинные выражения, думаю, проще будет сказать, чего Вы хотите. У Вас дано 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/ |
|