[andyp 9]

Спасибо, большое) Вы сделали все возможное и невозможное для разрешения моего вопроса.

Стал замахиваться на реализацию умножителя в композитном поле Галуа на базе умножителей в базовом поле GF(2^2). Нашел любопытную статью с более-менее внятным описанием того, как это делается.. но первое же вычисление вызвало недоумение.

Они взяли два элемента из GF(2^2) и перемножили их в параметрическом виде, т.е.:

 

C=c0+c1*alpha=(a0+a1*alpha)*(b0+b1*alpha)=a0b0+a1b1+(a1+b1+a1b1)*alpha

 

Эту формулу они и реализовали на логике и ссылаются на таблицу в которой приведены результаты перемножения. Эта статья, кусочек вычисления и сама схема прикреплена к сообщению. Но почему то результаты умножения из таблицы никак не согласованы с их вычислениями и схемой.

 

После моего перемножения получается немного другой результат и на его основе можно получить значения из таблицы:

 

С=a0b0+a1b1+(a1b0+a0b1+a1b1)*alpha

 

Может я чего то не понимаю и там подключены более высокие материи?

 

Статья - ужас какой-то.

 

Любой элемент поля GF(p^m) может быть представлен как линейная комбинация

базисных элементов {a^0,a^1,...a^(m-1)} с весами из GF(p)

 

Рассмотрим умножение в поле GF(2^2). Элементы могут быть представлены как a + b * A;

 

A - примитивный элемент поля

 

Умножение:

 

c= c0 + c1 * A;

с = (a0 + b0*A) * (a1 + b1*A) = a0b0 + (a0b1+a1b0) * A + b0b1*A^2 (*)

 

Вспоминаем, что А является корнем примитивного полинома p(x) = x^2+x+1, p(A) = 0. Отсюда:

 

A^2 = A+1.

 

Подставляем это в (*) и для коэффициентов разложения результата получаем:

 

с0 =a0b0 + b0b1 = b0(a0 + b1)

c1 = a0b1+a1b0 + b0b1 = a0b1 + b0(a1 + b0)

 

Может, это как-то дальше и упрощается, чтобы получить меньше логики.

 

Дальше пока не читал.

 

======================================================================

С формулами таки накосячил

с = (a0 + b0*A) * (a1 + b1*A) = a0a1 + (a0b1+a1b0) * A + b0b1*A^2 (*)

 

и соответственно:

с0 =a0a1 + b0b1

Изменено 2 февраля, 2016 пользователем andyp

[SKov 0]

Стал замахиваться на реализацию умножителя в композитном поле Галуа на базе умножителей в базовом поле GF(2^2). Нашел любопытную статью с более-менее внятным описанием того, как это делается.. но первое же вычисление вызвало недоумение.

Статей на эту тему много, и одно время было очень модным при декодировании длинных БЧХ переходить от 2^14 к 2^7.

Однако, на практике оказывается, что особого выигрыша это не дает.

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

Все это ИМХО, разумеется.

 

[Neznaika 0]

Ну как так то!? Столько времени потратил, чтобы разобраться с композитными полями, вспомнить полиномиальную логику.. и уже почти реализовал умножитель через композитное поле... думал, вот я молодец.. да я бог и властелин полей Галуа! А вы посадили меня в лужу. А я то думал.. придется теперь 2 умножителя сделать, чтобы посмотреть и сравнить.. э-эээх..

Но очень странно, что про эти поля твердят в новых статьях 2013-2014 года...

Изменено 2 февраля, 2016 пользователем Neznaika

[SKov 0]

Ну как так то!? Столько времени потратил, чтобы разобраться с композитными полями, вспомнить полиномиальную логику.. и уже почти реализовал умножитель через композитное поле... думал, вот я молодец.. да я бог и властелин полей Галуа! А вы посадили меня в лужу. А я то думал.. придется теперь 2 умножителя сделать, чтобы посмотреть и сравнить.. э-эээх..

Но очень странно, что про эти поля твердят в новых статьях 2013-2014 года...

Не расстраивайтесь. Все равно с этим полезно разобраться. Даже просто для общего кругозора.

Бесполезных знаний не бывает ;)

[Neznaika 0]

======================================================================

С формулами таки накосячил

с = (a0 + b0*A) * (a1 + b1*A) = a0a1 + (a0b1+a1b0) * A + b0b1*A^2 (*)

 

и соответственно:

с0 =a0a1 + b0b1

 

Вот теперь точно накосячили)) Не мучайтесь, вы и так очень помогли, спасибо) Изначально вы перемножили так же как и я, правда с одной опечаткой, но это несущественно. Статья просто странная... говорят об одном, а рисуют другое.

 

[Neznaika 0]

Сделал два умножителя в поле GF(2^14). В одном реализовал прямое умножение (Результат 1), в другом умножение через композитное поле GF((2^2)^7) (Результат 2). Оценку быстродействия и ресурсов делал с помощью Quarus II на ПЛИС Altera EP3SL70F780I4L.

 

Результат 1:

 

116 - ALUT

421,76 МГц

 

Результат 2:

 

171 - ALUT

405,84 МГц

 

Для чего нужно городить огород с композитными полями не понятно...

Изменено 4 февраля, 2016 пользователем Neznaika

[SKov 0]

Для чего нужно городить огород с композитными полями не понятно...

Ну, не могу с Вами согласиться.

Сейчас уже не помню подробностей, но году этак в 2005 с интересом разбирался в этой теме и, в частности,

смотрел статью по оптимизации маленького поля. И там были данные, что если для прямого умножения (в 2^14)

требуется 500 сумматоров XOR и еще сколько-то AND и еще сколько-то чего-то

(все цифры сейчас беру с потолка, но идея будет понятна), то для реализации такого же умножителя, использующего переход в поле

2^7, требуется только 300 сумматоров XOR, чуть меньше AND и еще меньше чего-то еще. Но главноый результат статьи заключался в том,

что, как оказалось, сложность реализации умножителя в маленьком поле зависит от выбора полинома для построения маленького поля.

Ребята перебрали все неприводимые полиномы для маленького поля и нашли,

что оптимальный выбор может сэкономить дополнительно еще 50 XOR-ов и еще 10 AND-ов. Совершенно нормальная статья ;)

Другими словами:

1) Переход в маленькое поле все-таки дает некоторый выигрыш по сравнению с прямым умножением (если все аккуратно сделать).

2) Статьи на это тему как появлялись, так и будут появляться с подобными вполне "печатными" результатами.

3) Практическая ценность этого не очень значительна, т.к. экономия в пару сотен XOR-ов почти

не заметна на фоне 150K гейтов общей сложности декодера для длинного кода.

А "прозрачность", "читабельность" и удобство отладки программы (особенно вериложной) заметно страдает от использования двух полей.

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

[Neznaika 0]

Я не буду спорить, наверняка где то что то не так сделал. Но по факту... пересчитал количество элементов AND и XOR в каждом их умножителей... В обычном умножителе их получилось около 1000, в умножителе через композитное поле 2735. Компилятор конечно, что то убрал лишние и преобразовал их в ALUT. Но даже визуально видно. что второй умножитель будет кушать больше. В нем же используются матрицы перехода из одного поля в другое и обратно, навалом умножителей в поле GF(2^2) при перемножении полиномов 6-ой степени. Для любопытных прикрепил к сообщению файл с реализацией на VHDL... Может кто то сразу скажет в чем я заблуждаюсь?..

mult.txt

[Neznaika 0]

Принялся вычислять синдромы разными способами и разными умножителями. Получил странные результаты. Если допустить одну ошибку на позиции t в кодовом слове и вычислять напрямую синдромы, умножая принятую последовательность на a^1, a^2.. a^24, то синдромы s(a^1)=a^t, s(a^2)=a^2t и т.д., для всех a^i, кроме i=9,18, т.е. s(a^9)!=a^9t и s(a^18)!=a^18t. Почему так получается?..

В стандарте DVB-S2 дано несколько порождающих полиномов. Поле Галуа формировал по первому. Такое ощущение, что поле формируется как то иначе.

 

Урааа! Нашел ошибку) Сразу не посмотрел все синдромы и ушел далеко в лес. При отсутствии ошибок синдромы 9 и 18 были не нулевыми, следовательно а^9 и a^18 не являлись корнями общего порождающего полинома кода. Эти корни принадлежали 5-му полиному стандарта DVB-S2. В нем и обнаружил ошибку. Теперь все работает как нужно, всем спасибо за внимание и беспокойство)

Изменено 10 февраля, 2016 пользователем Neznaika

[andyp 9]

Принялся вычислять синдромы разными способами и разными умножителями. Получил странные результаты. Если допустить одну ошибку на позиции t в кодовом слове и вычислять напрямую синдромы, умножая принятую последовательность на a^1, a^2.. a^24, то синдромы s(a^1)=a^t, s(a^2)=a^2t и т.д., для всех a^i, кроме i=9,18, т.е. s(a^9)!=a^9t и s(a^18)!=a^18t. Почему так получается?..

В стандарте DVB-S2 дано несколько порождающих полиномов. Поле Галуа формировал по первому. Такое ощущение, что поле формируется как то иначе.

 

При одной ошибке для синдромов должно выполняться: S_i = (a^t)^i для всех i. a^9,18 являются корнями минимального полинома g_5 из статьи про вычисление синдромов. Если считаете синдромы по принятым битам, то скорее всего дело кодере.

[Neznaika 0]

Всем привет! Продолжаю грызть БЧХ-декодер. Собрал его на простеньких алгоритмах BMA и Ченя. Все получилось, находится полином локатора ошибок и по нему поиском Ченя определяются позиции. Решил усугубить декодер более продвинутыми алгоритмами. Взялся за iBM и riBM. Нашел статью с описанием алгоритмов. Решил начать с riBM. Получил странные коэффициенты полинома локатора ошибок отличные от тех, которые получаются в обычном BMA. При 3-х ошибках лямбда(0)!=0, лямбда(1)!=0, лямбда(2)!=0, лямбда(3)!=0, остальные ноль. При 1 ошибке лямбды только с индексами 0 и 1 не равны нулю. Пропустил их через поиск Ченя и он выдал на местах, где допущена ошибка, вместо нулевых значений - одинаковые константы. Написал программку iBM, к моему удивлению получились те же коэффициенты, что и в riBM. В связи с этим появилось пара пока не разрешимых для меня вопроса к гуру БЧХ:

 

1. Должны ли совпадать лямбды в обычном BMA и iBMA?

2. Полученные значения лямбды(2t) в iBMA и riBMA - это коэффициенты полинома локаторов ошибок или нет?

RSriBM.pdf

Изменено 2 марта, 2016 пользователем Neznaika

[andyp 9]

1. Должны ли совпадать лямбды в обычном BMA и iBMA?

2. Полученные значения лямбды(2t) в iBMA и riBMA - это коэффициенты полинома локаторов ошибок или нет?

 

В прицепленной статье сказано (втрой абзац в правой колонке на стр. 3), что iBM ищет полином-локатор, коэффиценты (лямбды) которого умножены на некий постоянный множитель. Очевидно, что корни у полинома f(x) и полинома a*f(x) совпадают.

 

PS Ненулевые значения при поиске Ченя могут быть вызваны тем, что реализация поиска считает, что lambda0 = 1. В случае iBM, судя по статье, свободный член равен некоторой константе lambda0 = a;

Изменено 2 марта, 2016 пользователем andyp

[Neznaika 0]

Спасибо огромное!)) Вы мне сэкономили как минимум день! При поиске ошибки в алгоритме обращал на не единичную лямбду(0) и не понимал почему она имеет какое то значение. Описание про то, что именно алгоритм вычисляет, также вчера разглядывал, но не увидел, что полученные коэффициенты полинома умножены на константу. Подкорректировал поиск Ченя, он действительно был сделан под свободный член полинома локатора ошибок равный 1. Теперь все работает как надо) Спасибо) Теперь настал черед siBM и tiBM! Трепещите!)

[Maverick_ 15]

гляньте здесь, может поможет...

[Neznaika 0]

да-да, спасибо) Про ошибку в статье о siBM я видел ранее. Действительно пока не заработало. Файлы проекта dess00 у меня есть, там видно отличие. Еще не разобрался что не так...