Умножение в поле Галуа

Ответить

Djony1987 0

29 апреля, 2010

Опубликовано 29 апреля, 2010 (изменено) · Жалоба

Здравствуйте!

Знающие, подскажите - необходимо реализовать умножение на константы в расширенном поле Галуа GF(2^8) с порождающим полиномом x^8 + x^4 + x^3 + x^2 + 1.

Как я понял, читая разные источники есть 3 наиболее распространенных способа:

1) сделать полный умножитель - сложный

2) сделать LUT

3) сделать эквивалентую логическую цепь

Хотелось бы сделать 3-й вариант.

Для GF(2^4) понятно, здесь описано как:

Но мне надо для 16 констант и + полином элемента - 7 степени, т.е. таблица довольно большая получается, может есть способы автоматизировать получение логических выражений?

Спасибо!

Изменено 29 апреля, 2010 пользователем Djony1987

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

Djony1987 0

30 апреля, 2010

Опубликовано 30 апреля, 2010 (изменено) · Жалоба

Попытался сделать данным способом, что не получается(

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

Например умножение на коэфф. 52 (00110100).

У меня такие выражения получились:

o7 = a2 xor a3 xor a5

o6 = a1 xor a2 xor a4

o5 = a0 xor a1 xor a3 xor a7

o4 = a0 xor a2 xor a6

o3 = a1 xor a5 xor a6

o2 = a0 xor a4

o1 = a3 xor a5 xor a6 xor a7

o0 = a3 xor a4 xor a6

Код, которым проверяю в матлабе:

p = 2; m = 8;
prim_poly = [1 0 1 1 1 0 0 0 1];
% правый старший
a = [0 1 0 0 0 0 0 0]; % какое-то число, которое умножается
b = [0 0 1 0 1 1 0 0]; % 52
notsimple = gfconv(a,b,p);
simple = gftuple(notsimple,prim_poly,p)

В чем может быть проблема?

Изменено 30 апреля, 2010 пользователем Djony1987

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

Djony1987 0

30 апреля, 2010

Опубликовано 30 апреля, 2010 · Жалоба

Откопал 1 сатью: http://www.soel.ru/cms/f/?/355485.pdf, подскажите плис где эту библиотеку взять?

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

tojvo 0

1 мая, 2010

Опубликовано 1 мая, 2010 · Жалоба

Попробуйте ещё посмотреть описание арифметики в пункте 4.2.1 FIPS-197 (AES-Rijndael Std.). Я именно по нему делал, когда писал на Си для контрольной в институте, и, судя по простоте алгоритма, на ПЛИС он тоже должен лечь.

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

Oldring 0

2 мая, 2010

Опубликовано 2 мая, 2010 · Жалоба

1) сделать полный умножитель - сложный
2) сделать LUT

3) сделать эквивалентую логическую цепь

Странный выбор.

Сделайте полный умножитель в виде функции, вызовите её с константой в виде одного параметра и позвольте синтезатору самому заоптимизировать.

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

barabek 0

3 мая, 2010

Опубликовано 3 мая, 2010 · Жалоба

Хотелось бы сделать 3-й вариант.

У меня сейчас та же проблема. А из какой книги отрывок приведен? (Что-то я его понять не могу, может в контексте будет понятней. Что-то туплю с правилом заполнения приведенной таблицы) . А полный умножитель, мне кажется, никто не делает. Скачивал с опенкореса - там один из проектов выполнен по такому же принципу умножения. (Другой - сдвигом, но это долго.) Но проект с параллельным умножением мне тоже не подходит-там поле 2^5, а у мне необходимо такое же как у Вас 2^8.

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

Djony1987 0

3 мая, 2010

Опубликовано 3 мая, 2010 · Жалоба

У меня сейчас та же проблема. А из какой книги отрывок приведен? (Что-то я его понять не могу, может в контексте будет понятней. Что-то туплю с правилом заполнения приведенной таблицы) . А полный умножитель, мне кажется, никто не делает. Скачивал с опенкореса - там один из проектов выполнен по такому же принципу умножения. (Другой - сдвигом, но это долго.) Но проект с параллельным умножением мне тоже не подходит-там поле 2^5, а у мне необходимо такое же как у Вас 2^8.

Вот весь документ: http://dl.dropbox.com/u/2907327/WHP031.pdf

Можешь еще здесь посмотреть: http://www.edaboard.com/viewtopic.php?t=33...ighlight=galois

Если поймешь - дай знать плис! :) Я попытался все там умножить, но так как у них не получается :(

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

SergeyF 0

3 мая, 2010

Опубликовано 3 мая, 2010 · Жалоба

Советую два пути:

1. Взять декриптор и декриптовать корку RS из альтеровских мегафункций. Там реализован полный комбинаторный умножитель на VHDL. Жутко навороченный, так как параметризирован под произвольный порождающий полином.

2. Взять упомянутую в статье Полякова под номером [5] статью "Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication over GF(2^m)" и реализовать по ней самостоятельно.

И так, и так, полный умножитель занимает около 50-52 (сейчас не вспомню) логических элементов Stratix. Причем Альтеровский даже на один элемент меньше занимал, кажется.

И если уж говорить об opencores, то вот тут умножители точно есть:

http://opencores.org/project,reed_solomon_decoder

http://opencores.org/project,rs_dec_enc

http://opencores.org/project,rsencoder

В последнем, кажется, просто втупую уравнения расписаны. Длиииинные xor'ы. В остальных не смотрел. Так как все это - RS под соотв. стандарт (DVB и связанное с ним), то и поле Ваше.

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

barabek 0

4 мая, 2010

Опубликовано 4 мая, 2010 · Жалоба

Вот весь документ: http://dl.dropbox.com/u/2907327/WHP031.pdf

Можешь еще здесь посмотреть: http://www.edaboard.com/viewtopic.php?t=33...ighlight=galois

Если поймешь - дай знать плис! :) Я попытался все там умножить, но так как у них не получается :(

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

П.С. Если не затруднит - проверте отпишите, у Вас уже вроде как модуль проверочный имеется. Я в матлабе не силен :(. Буду проверять уже в симуляторе.

output.txt

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

Djony1987 0

5 мая, 2010

Опубликовано 5 мая, 2010 · Жалоба

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

П.С. Если не затруднит - проверте отпишите, у Вас уже вроде как модуль проверочный имеется. Я в матлабе не силен :(. Буду проверять уже в симуляторе.

Не подскажешь как там это делается, круто было б сам алгоритм программки :)

Проверил сейчас в Матлабе несколько умножений - все правильные.

Советую два пути:
1. Взять декриптор и декриптовать корку RS из альтеровских мегафункций. Там реализован полный комбинаторный умножитель на VHDL. Жутко навороченный, так как параметризирован под произвольный порождающий полином.

2. Взять упомянутую в статье Полякова под номером [5] статью "Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication over GF(2^m)" и реализовать по ней самостоятельно.

И так, и так, полный умножитель занимает около 50-52 (сейчас не вспомню) логических элементов Stratix. Причем Альтеровский даже на один элемент меньше занимал, кажется.

И если уж говорить об opencores, то вот тут умножители точно есть:

...

В последнем, кажется, просто втупую уравнения расписаны. Длиииинные xor'ы. В остальных не смотрел. Так как все это - RS под соотв. стандарт (DVB и связанное с ним), то и поле Ваше.

Спасибо за совет!! Статья уже была :)

Ну не под стандарт скорее - а под порождающий полином. Для 8-ми битных символов пока только 2 полинома видел.

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

barabek 0

5 мая, 2010

Опубликовано 5 мая, 2010 · Жалоба

Не подскажешь как там это делается, круто было б сам алгоритм программки :)

Я ее чуть добил, чтобы еще максимальное колличество XOR-ов на кодер/декодер определять. Для моего требования максимального числа ошибок 4 (8 дополнительных байтов) график приложил. Получается самый выгодный кодер при начальной степени корня образующего полинома а^110. Выходной файл проги тоже приложил. А вместо алгоритма приложил сам текст кода. Только нужно расширение поменять с txt на cpp. ( Делал в билдере. Все остальное вроде не нужно. У меня очень лаконичный GUI получился -форма, на ней кнопка, нажал - получил файл :) Очень редко пишу для компа, так что за прогу не обессудьте. )

PS. Хотя, насколько я знаю, для cycloneIII без разницы что 5, что 6 что 7 входов XOR-ить. По времени одно и тоже.

GFmanipul.txt

output.txt

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

Djony1987 0

5 мая, 2010

Опубликовано 5 мая, 2010 · Жалоба

Я ее чуть добил, чтобы еще максимальное колличество XOR-ов на кодер/декодер определять. Для моего требования максимального числа ошибок 4 (8 дополнительных байтов) график приложил. Получается самый выгодный кодер при начальной степени корня образующего полинома а^110. Выходной файл проги тоже приложил. А вместо алгоритма приложил сам текст кода. Только нужно расширение поменять с txt на cpp. ( Делал в билдере. Все остальное вроде не нужно. У меня очень лаконичный GUI получился -форма, на ней кнопка, нажал - получил файл :) Очень редко пишу для компа, так что за прогу не обессудьте. )

PS. Хотя, насколько я знаю, для cycloneIII без разницы что 5, что 6 что 7 входов XOR-ить. По времени одно и тоже.

Спасибо большое за код!!

Мне пока только кодер надо сделать (255, 239). С декодером еще не разбирался, поэтому не могу пока что-то сказать.

ЗЫ Ты и кодер и декодер собираешься делать?

Цитата

Поделиться сообщением

Ссылка на сообщение

Поделиться на другие сайты

barabek 0

5 мая, 2010

Опубликовано 5 мая, 2010 · Жалоба

ЗЫ Ты и кодер и декодер собираешься делать?

Да. Читаю/пишу в nand flash. Флэшка самсунговская с 2-мя битами на cell. Производитель рекомендует контролировать до 4 ошибок. Но может декодирование сделаю и программно. Но рассчет синдромов и определение битой/не битой записи в любом случае хардверно.