slava_edf 0 9 марта, 2011 Опубликовано 9 марта, 2011 · Жалоба Для полинома x^8 + x^4 + x^3 + x^2 + 1, поле Галуа будет GF(2^9), а не полем GF(2^8). Смотри в свою же подсказку где GF(2^4), его полином (значение бита)x3+ (значение бита)x2 + (значение бита)x1 + (значение бита)1. Все операции по модулю то ли "+" то ли "х" здесь на пальцах: http://av5.com/journals-magazines-online/1/34/296 GF(p), где p - "простое число" .... http://av5.com/journals-magazines-online/1/34/296 если брать розрядность в двочном виде то берм "p" из списка к примеру прост. число 251 и 257. Будет два поля Галуа с елементами GF(p) для р=251, GF(251)= 0, 1, 2.....p-1=250; для р=257, GF(257)=0, 1,2...p-1=256. Как следствие GF(251)=GF(2^8) - двоичный вид;GF(257)=GF(2^9)- двоичный вид Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
slava_edf 0 11 марта, 2011 Опубликовано 11 марта, 2011 · Жалоба Список простих чисел http://uk.wikipedia.org/wiki/Список_простих_чисел Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ivanpa 0 5 апреля, 2011 Опубликовано 5 апреля, 2011 · Жалоба а табличка не катит для арифметики? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Oldring 0 5 апреля, 2011 Опубликовано 5 апреля, 2011 · Жалоба GF(251)=GF(2^8) ... GF(257)=GF(2^9) Кхм... :cranky: Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Muscat 0 12 мая, 2011 Опубликовано 12 мая, 2011 · Жалоба Подниму пожалуй тему А кто нибудь делал умножитель двух элементов поля Галуа? Я имею ввиду не умножитель на константу, как в кодере, а умножитель одного произвольного элемента поля на другой? Сгенерировал строковое описание через матлаб вида rez<="001" when "0011100" else... на 64 строки, получилась красивая комбинационная схемка на 25 ячеек из 25000 мне доступных. Попробовал осуществить то же самое для поля GF(2^8), но редактор кода отказался проверять его, синтезатор считал его минут 20, дальше я понял что смысла мучаться с ним нет. Очевидный вариант - соптимизировать таблицу умножения и положить ее на RAM и обращаться по мере необходимости. В принципе таких умножителей потребуется пару десятков, в принципе возможностей ПЛИС должно хватить, но этот вариант мне не очень нравится. Какие еще есть способы? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SuperFly 0 12 мая, 2011 Опубликовано 12 мая, 2011 · Жалоба ...Какие еще есть способы? можно на логике без использования памяти, например так: //////////////////////////////////////////////////////////////////////////////// // Galois Field (2^13) multiplier //////////////////////////////////////////////////////////////////////////////// module GF13_MULT ( input [12:0] A, input [12:0] B, output [12:0] C ); wire [12:0] d; wire [11:0] e; assign d[0] = ( A[0] & B[0]); assign d[1] = ( A[1] & B[0]) ^ ( A[0] & B[1]); assign d[2] = ( A[2] & B[0]) ^ ( A[1] & B[1]) ^ ( A[0] & B[2]); assign d[3] = ( A[3] & B[0]) ^ ( A[2] & B[1]) ^ ( A[1] & B[2]) ^ ( A[0] & B[3]); assign d[4] = ( A[4] & B[0]) ^ ( A[3] & B[1]) ^ ( A[2] & B[2]) ^ ( A[1] & B[3]) ^ ( A[0] & B[4]); assign d[5] = ( A[5] & B[0]) ^ ( A[4] & B[1]) ^ ( A[3] & B[2]) ^ ( A[2] & B[3]) ^ ( A[1] & B[4]) ^ ( A[0] & B[5]); assign d[6] = ( A[6] & B[0]) ^ ( A[5] & B[1]) ^ ( A[4] & B[2]) ^ ( A[3] & B[3]) ^ ( A[2] & B[4]) ^ ( A[1] & B[5]) ^ ( A[0] & B[6]); assign d[7] = ( A[7] & B[0]) ^ ( A[6] & B[1]) ^ ( A[5] & B[2]) ^ ( A[4] & B[3]) ^ ( A[3] & B[4]) ^ ( A[2] & B[5]) ^ ( A[1] & B[6]) ^ ( A[0] & B[7]); assign d[8] = ( A[8] & B[0]) ^ ( A[7] & B[1]) ^ ( A[6] & B[2]) ^ ( A[5] & B[3]) ^ ( A[4] & B[4]) ^ ( A[3] & B[5]) ^ ( A[2] & B[6]) ^ ( A[1] & B[7]) ^ ( A[0] & B[8]); assign d[9] = ( A[9] & B[0]) ^ ( A[8] & B[1]) ^ ( A[7] & B[2]) ^ ( A[6] & B[3]) ^ ( A[5] & B[4]) ^ ( A[4] & B[5]) ^ ( A[3] & B[6]) ^ ( A[2] & B[7]) ^ ( A[1] & B[8]) ^ ( A[0] & B[9]); assign d[10] = (A[10] & B[0]) ^ ( A[9] & B[1]) ^ ( A[8] & B[2]) ^ ( A[7] & B[3]) ^ ( A[6] & B[4]) ^ ( A[5] & B[5]) ^ ( A[4] & B[6]) ^ ( A[3] & B[7]) ^ ( A[2] & B[8]) ^ ( A[1] & B[9]) ^ ( A[0] & B[10]); assign d[11] = (A[11] & B[0]) ^ (A[10] & B[1]) ^ ( A[9] & B[2]) ^ ( A[8] & B[3]) ^ ( A[7] & B[4]) ^ ( A[6] & B[5]) ^ ( A[5] & B[6]) ^ ( A[4] & B[7]) ^ ( A[3] & B[8]) ^ ( A[2] & B[9]) ^ ( A[1] & B[10]) ^ ( A[0] & B[11]); assign d[12] = (A[12] & B[0]) ^ (A[11] & B[1]) ^ (A[10] & B[2]) ^ ( A[9] & B[3]) ^ ( A[8] & B[4]) ^ ( A[7] & B[5]) ^ ( A[6] & B[6]) ^ ( A[5] & B[7]) ^ ( A[4] & B[8]) ^ ( A[3] & B[9]) ^ ( A[2] & B[10]) ^ ( A[1] & B[11]) ^ ( A[0] & B[12]); assign e[0] = (A[12] & B[1]) ^ (A[11] & B[2]) ^ (A[10] & B[3]) ^ ( A[9] & B[4]) ^ ( A[8] & B[5]) ^ ( A[7] & B[6]) ^ ( A[6] & B[7]) ^ ( A[5] & B[8]) ^ ( A[4] & B[9]) ^ ( A[3] & B[10]) ^ ( A[2] & B[11]) ^ ( A[1] & B[12]); assign e[1] = (A[12] & B[2]) ^ (A[11] & B[3]) ^ (A[10] & B[4]) ^ ( A[9] & B[5]) ^ ( A[8] & B[6]) ^ ( A[7] & B[7]) ^ ( A[6] & B[8]) ^ ( A[5] & B[9]) ^ ( A[4] & B[10]) ^ ( A[3] & B[11]) ^ ( A[2] & B[12]); assign e[2] = (A[12] & B[3]) ^ (A[11] & B[4]) ^ (A[10] & B[5]) ^ ( A[9] & B[6]) ^ ( A[8] & B[7]) ^ ( A[7] & B[8]) ^ ( A[6] & B[9]) ^ ( A[5] & B[10]) ^ ( A[4] & B[11]) ^ ( A[3] & B[12]); assign e[3] = (A[12] & B[4]) ^ (A[11] & B[5]) ^ (A[10] & B[6]) ^ ( A[9] & B[7]) ^ ( A[8] & B[8]) ^ ( A[7] & B[9]) ^ ( A[6] & B[10]) ^ ( A[5] & B[11]) ^ ( A[4] & B[12]); assign e[4] = (A[12] & B[5]) ^ (A[11] & B[6]) ^ (A[10] & B[7]) ^ ( A[9] & B[8]) ^ ( A[8] & B[9]) ^ ( A[7] & B[10]) ^ ( A[6] & B[11]) ^ ( A[5] & B[12]); assign e[5] = (A[12] & B[6]) ^ (A[11] & B[7]) ^ (A[10] & B[8]) ^ ( A[9] & B[9]) ^ ( A[8] & B[10]) ^ ( A[7] & B[11]) ^ ( A[6] & B[12]); assign e[6] = (A[12] & B[7]) ^ (A[11] & B[8]) ^ (A[10] & B[9]) ^ ( A[9] & B[10]) ^ ( A[8] & B[11]) ^ ( A[7] & B[12]); assign e[7] = (A[12] & B[8]) ^ (A[11] & B[9]) ^ (A[10] & B[10]) ^ ( A[9] & B[11]) ^ ( A[8] & B[12]); assign e[8] = (A[12] & B[9]) ^ (A[11] & B[10]) ^ (A[10] & B[11]) ^ ( A[9] & B[12]); assign e[9] = (A[12] & B[10]) ^ (A[11] & B[11]) ^ (A[10] & B[12]); assign e[10] = (A[12] & B[11]) ^ (A[11] & B[12]); assign e[11] = (A[12] & B[12]); assign C[0] = d[0] ^ e[0] ^ e[9] ^ e[10]; assign C[1] = d[1] ^ e[0] ^ e[1] ^ e[9] ^ e[11]; assign C[2] = d[2] ^ e[1] ^ e[2] ^ e[10]; assign C[3] = d[3] ^ e[0] ^ e[2] ^ e[3] ^ e[9] ^ e[10] ^ e[11]; assign C[4] = d[4] ^ e[0] ^ e[1] ^ e[3] ^ e[4] ^ e[9] ^ e[11]; assign C[5] = d[5] ^ e[1] ^ e[2] ^ e[4] ^ e[5] ^ e[10]; assign C[6] = d[6] ^ e[2] ^ e[3] ^ e[5] ^ e[6] ^ e[11]; assign C[7] = d[7] ^ e[3] ^ e[4] ^ e[6] ^ e[7]; assign C[8] = d[8] ^ e[4] ^ e[5] ^ e[7] ^ e[8]; assign C[9] = d[9] ^ e[5] ^ e[6] ^ e[8] ^ e[9]; assign C[10] = d[10] ^ e[6] ^ e[7] ^ e[9] ^ e[10]; assign C[11] = d[11] ^ e[7] ^ e[8] ^ e[10] ^ e[11]; assign C[12] = d[12] ^ e[8] ^ e[9] ^ e[11]; endmodule //////////////////////////////////////////////////////////////////////////////// Теория тут: Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication over GF(2^m) 4__pb_tc_aug04.pdf Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Muscat 0 12 мая, 2011 Опубликовано 12 мая, 2011 · Жалоба Правильно ли я понимаю что это автоматически сгенерированное по некоторму алгоритму, описанному в прилагаемом файле, описание? То есть схема по прежнему делается на чисто комбинационной логике, но мы облегчаем задачу синтезатору? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SuperFly 0 12 мая, 2011 Опубликовано 12 мая, 2011 · Жалоба Правильно ли я понимаю что это автоматически сгенерированное по некоторму алгоритму, описанному в прилагаемом файле, описание? Да, правильно - для некоторых типов неприводимых полиномов есть красивое и оптмизированное (по временным задержкам и аппаратным ресурсам) решение, описанное в статье То есть схема по прежнему делается на чисто комбинационной логике, но мы облегчаем задачу синтезатору? Да, схема на чисто комбинационной логике и такое решение мне показалось единственно возможным для GF(2^13) - не каждый синтезатор сможет соптимизировать такую матрицу для умножителя "влоб". Вы писали что для GF(2^8) у Вас синтезатор "думал" 20 минут :-) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Muscat 0 12 мая, 2011 Опубликовано 12 мая, 2011 · Жалоба Спасибо огромное! Буду вникать. Со стороны описанная вами схема выглядит совсем не страшно :-) А 20 минут это не он думал, 20 минут это я думал, пока не жмакнул на кнопку Cancel :-) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Muscat 0 18 мая, 2011 Опубликовано 18 мая, 2011 · Жалоба Эх, жаль большие перерывы приходится делать в работе =( Скажите, я правильно понимаю, что если у меня полином 1+X^2+X^3+X^4+X^8, то для него этот метод годится, поскольку он является "пента-номом" (pentanomial) с ненулевыми коэффициентами. Ага? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SuperFly 0 18 мая, 2011 Опубликовано 18 мая, 2011 · Жалоба Скажите, я правильно понимаю... правильно =) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SuperFly 0 18 мая, 2011 Опубликовано 18 мая, 2011 · Жалоба ... полином 1+X^2+X^3+X^4+X^8 ... Ага? Для вашего случая по первым прикидкам такая схема получается: //////////////////////////////////////////////////////////////////////////////// // Galois Field (2^8) multiplier p(x) = 1 + x^2 + x^3 + x^4 + x^8 //////////////////////////////////////////////////////////////////////////////// module GF8_MULT ( input [7:0] A, input [7:0] B, output [7:0] C ); wire [7:0] d; wire [6:0] e; assign d[0] = (A[0] & B[0]); assign d[1] = (A[1] & B[0]) ^ (A[0] & B[1]); assign d[2] = (A[2] & B[0]) ^ (A[1] & B[1]) ^ (A[0] & B[2]); assign d[3] = (A[3] & B[0]) ^ (A[2] & B[1]) ^ (A[1] & B[2]) ^ (A[0] & B[3]); assign d[4] = (A[4] & B[0]) ^ (A[3] & B[1]) ^ (A[2] & B[2]) ^ (A[1] & B[3]) ^ (A[0] & B[4]); assign d[5] = (A[5] & B[0]) ^ (A[4] & B[1]) ^ (A[3] & B[2]) ^ (A[2] & B[3]) ^ (A[1] & B[4]) ^ (A[0] & B[5]); assign d[6] = (A[6] & B[0]) ^ (A[5] & B[1]) ^ (A[4] & B[2]) ^ (A[3] & B[3]) ^ (A[2] & B[4]) ^ (A[1] & B[5]) ^ (A[0] & B[6]); assign d[7] = (A[7] & B[0]) ^ (A[6] & B[1]) ^ (A[5] & B[2]) ^ (A[4] & B[3]) ^ (A[3] & B[4]) ^ (A[2] & B[5]) ^ (A[1] & B[6]) ^ (A[0] & B[7]); assign e[0] = (A[7] & B[1]) ^ (A[6] & B[2]) ^ (A[5] & B[3]) ^ (A[4] & B[4]) ^ (A[3] & B[5]) ^ (A[2] & B[6]) ^ (A[1] & B[7]); assign e[1] = (A[7] & B[2]) ^ (A[6] & B[3]) ^ (A[5] & B[4]) ^ (A[4] & B[5]) ^ (A[3] & B[6]) ^ (A[2] & B[7]); assign e[2] = (A[7] & B[3]) ^ (A[6] & B[4]) ^ (A[5] & B[5]) ^ (A[4] & B[6]) ^ (A[3] & B[7]); assign e[3] = (A[7] & B[4]) ^ (A[6] & B[5]) ^ (A[5] & B[6]) ^ (A[4] & B[7]); assign e[4] = (A[7] & B[5]) ^ (A[6] & B[6]) ^ (A[5] & B[7]); assign e[5] = (A[7] & B[6]) ^ (A[6] & B[7]); assign e[6] = (A[7] & B[7]); assign C[0] = d[0] ^ e[0] ^ e[4] ^ e[5] ^ e[6] ; assign C[1] = d[1] ^ e[1] ^ e[5] ^ e[6]; assign C[2] = d[2] ^ e[0] ^ e[2] ^ e[4] ^ e[5]; assign C[3] = d[3] ^ e[0] ^ e[1] ^ e[3] ^ e[4]; assign C[4] = d[4] ^ e[0] ^ e[1] ^ e[2]; assign C[5] = d[5] ^ e[1] ^ e[2] ^ e[3]; assign C[6] = d[6] ^ e[2] ^ e[3] ^ e[4]; assign C[7] = d[7] ^ e[3] ^ e[4] ^ e[5]; endmodule //////////////////////////////////////////////////////////////////////////////// Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Muscat 0 20 мая, 2011 Опубликовано 20 мая, 2011 · Жалоба Спасибо огромное! Попробую проверить. Соблазнительно конечно взять ваш код как готовый, но я еще все таки попробую разобраться с теорией и сгенерить это описание через Матлаб. Благо пока задача не горит. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SuperFly 0 20 мая, 2011 Опубликовано 20 мая, 2011 · Жалоба Спасибо огромное! Попробую проверить. Соблазнительно конечно взять ваш код как готовый, но я еще все таки попробую разобраться с теорией и сгенерить это описание через Матлаб. Благо пока задача не горит. Смотрите статью - там все просто: результат умножения - это (по формуле 9) c = d + QTe , где d = Lb ; e = Ub (L и U - треугольные матрицы с коэф. a) матрица Q для вашего случая определяется как сумма 4-х матриц (как показано на рис. 6) в вашем случае матрица Q такая: 10111000 01011100 00101110 00010111 10110011 11100001 11000000 Доступно объяснил? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Muscat 0 20 мая, 2011 Опубликовано 20 мая, 2011 · Жалоба Вполне доступно, да Повторил действия в М-лабе clc; clear; A(1:7,1:8)=0; A(1:7,1:7)=eye(7); A(5:7,1:3)=eye(3); A(6:7,1:2)=A(6:7,1:2)+eye(2); A(7,1)=1; B(1:7,1:8)=0; B(:,3:8)=A(:,1:6); C(1:7,1:8)=0; C(:,4:8)=A(:,1:5); D(1:7,1:8)=0; D(:,5:8)=A(:,1:4); Q=mod((A+B+C+D),2); результат совпал 1 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 Спасибо! Извините, если я задаю глупые вопросы, я пока только постигаю дао-инженера :-) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
