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

Любой элемент поля 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

Сообщение отредактировал andyp - Feb 2 2016, 15:01

Статей на эту тему много, и одно время было очень модным при декодировании длинных БЧХ переходить от 2^14 к 2^7.
Однако, на практике оказывается, что особого выигрыша это не дает.
Удобно реализовывать прямое умножение элементов в полном поле и использовать декодер без обратных элементов.
Все это ИМХО, разумеется.

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

Сообщение отредактировал Neznaika - Feb 2 2016, 11:34

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

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

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

Результат 1:

116 - ALUT
421,76 МГц

Результат 2:

171 - ALUT
405,84 МГц

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

Сообщение отредактировал Neznaika - Feb 4 2016, 09:50

Ну, не могу с Вами согласиться.
Сейчас уже не помню подробностей, но году этак в 2005 с интересом разбирался в этой теме и, в частности,
смотрел статью по оптимизации маленького поля. И там были данные, что если для прямого умножения (в 2^14)
требуется 500 сумматоров XOR и еще сколько-то AND и еще сколько-то чего-то
(все цифры сейчас беру с потолка, но идея будет понятна), то для реализации такого же умножителя, использующего переход в поле
2^7, требуется только 300 сумматоров XOR, чуть меньше AND и еще меньше чего-то еще. Но главноый результат статьи заключался в том,
что, как оказалось, сложность реализации умножителя в маленьком поле зависит от выбора полинома для построения маленького поля.
Ребята перебрали все неприводимые полиномы для маленького поля и нашли,
что оптимальный выбор может сэкономить дополнительно еще 50 XOR-ов и еще 10 AND-ов. Совершенно нормальная статья
Другими словами:
1) Переход в маленькое поле все-таки дает некоторый выигрыш по сравнению с прямым умножением (если все аккуратно сделать).
2) Статьи на это тему как появлялись, так и будут появляться с подобными вполне "печатными" результатами.
3) Практическая ценность этого не очень значительна, т.к. экономия в пару сотен XOR-ов почти
не заметна на фоне 150K гейтов общей сложности декодера для длинного кода.
А "прозрачность", "читабельность" и удобство отладки программы (особенно вериложной) заметно страдает от использования двух полей.
Так что выигрыш есть, но стоит ли за ним гнаться - этот вопрос решает для себя каждый проектировщик индивидуально

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

Принялся вычислять синдромы разными способами и разными умножителями. Получил странные результаты. Если допустить одну ошибку на позиции 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. В нем и обнаружил ошибку. Теперь все работает как нужно, всем спасибо за внимание и беспокойство)

Сообщение отредактировал Neznaika - Feb 10 2016, 09:49

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

Всем привет! Продолжаю грызть БЧХ-декодер. Собрал его на простеньких алгоритмах 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 - это коэффициенты полинома локаторов ошибок или нет?

Сообщение отредактировал Neznaika - Mar 2 2016, 13:40

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

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

Сообщение отредактировал andyp - Mar 2 2016, 16:50

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

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

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