Подскажите, кто разобрался. Реализую декодер БЧХ в поле GF (2^11), исправляет 8 ошибок на ПЛИС. После вычисления полинома локаторов ошибок необходимо решить данное уравнение с помощью процедуры Ченя. Каким образом решить данное уравнение? Пока вижу 2 способа: 1) перейти к полиномиальному представлению элементов поля, потом перейти к обычному полю и если уравнение будет равно нулю, значит обратный элемент будет корнем уравнения. 2) Решить уравнение с помощью умножителей в поле Галуа, потом считать из памяти корень уравнения, при котором урвнение обращается в нуль. В общем интересует, каким образом эту процедуру реализовать.

поиском по форуму, чую что найдете что-то интересное

Поискал я на форуме, много интересного почитал про БЧХ коды. Но про переход от ключевого уравнения к процедуре Ченя мне не очень понятен в реализации. На бумаге считаю, все получается. А вот если реализововать, переход от элементов поля к коэффициента alfa в степени мне не нравится, так как необходимо использовать 2 таблицы памяти (прямые и обратные коэффициенты).

так сложно читать сорцы на языке близком к Си ?

Да, нет. Не сложно. Меня интересует именно схемотехническая реализация.

ну уж если для вас HDL код на Verilog не является схемотехнической реализацией, я даже не знаю что вам ответить...

Спасибо за помощь.Я Verilog к сожалению не знаю, попробую разобраться, хотя в чужом коде сложновато. В принципе, мне только идея нужна. Есть полином локаторов, вопрос с какой формой представления работать.

Найдите "High-Speed VLSI Architecture for Parallel Reed–Solomon Decoder" Hanho Lee (в гугле первая строка ). Рисунок 5 как раз то, что Вы ищите.

У меня на сайте, в статьях есть "краткий курс HDL"...
удачи!

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

К примеру, если полином локаторов ошибок следующий
1) alfa(x)=838*x^8+1576*x^7+1157*x^6+273*x^5+1357*x^4+1328*x^3+1892*x^2+1141*x+917 соответсвенно 838, 1576 - элементы поля Галуа GF(2^11)
это же уравнение можно преобразовать к следующему
2)alfa(x)=alfa^1201*x^8+alfa^1552*x^7+alfa^685*x^6+alfa^1890*x^5+alfa^440*x^4+al
fa^347*x^3+alfa^1455*x^2+alfa^991*x+917
Если использовать уравнение 2 то мы можем складывыть степени при подстановке элементов использовать обычные операции сложения коэффициентов/
Если уравнение 1, то придется перемножать в поле Галуа и подставляя к примеру в восьмую степень элементы поля необходимо перемножать один и тот же элемент 8 раз. Как-то этот способ мне не очень нравится. Des, я правильно вас понял, что надо решать уравнение по 1-му способу

Я же Вам посоветовал литературу. Смотрим на рисунок. Не 8 раз, а в каждом такте предыдущее содержание регистра умножается на alfa^8 , т.е. на константу. Понятное дело, что 7 умножителей нужно для каждого члена полинома, кроме члена с нулевой степенью. Но результат в каждом такте.
Может это очевидно, но на всякий поясню. Возьмем Ваш старший член полинома 838*x^8. Подставляем в него альфа. 838*alfa*alfa*....*alfa=838*(alfa^8)=X1. На следующем такте нужно подставить вместо x alfa^2. Получаем 838*alfa^2*alfa^2*....*alfa^2=838*(alfa^16)=(838*(alfa^8))*alfa^8=X1*alfa^8=X2. Ну и так со всеми остальными степенями. Параллельно для всех членов полинома. Ага?

Получается на первом такте подставляю alfa во все степени уравнения и считаю результат, на втором такте alfa^2, но на основе первого уравнения и т.д. Итого получается за количество тактов равное размерности поля я найду все корни уравнения. К примеру для поля GF(2^11) за 2048 тактов. Только одно непонятно, как это в одну формулу объединить или для каждого такта надо будет уравнение записывать? И еще вопрос можно ли здесь без использования памяти, содержащей значения коэффициентов alfa^n обойтись забив их в ручную в уравнение?

Да, если длина пакета у Вас 2048 (максимальная для 11 степени), то так и есть. Длина пакета в общем случае может быть и меньше. Количество тактов равно длине пакета. Просто для укороченного пакета инициализация посложней.



Не понял. Куда записывать? Формула одна, а значение переменной разное. Процедура Ченя это просто нахождение корней уравнения перебором. Т.е. Вы подставляете поочереди элементы поля и определяете корни. Можно сказать численным методом, а не аналитически.



Конечно, зачем Вам память. На каждом блоке, соответствующему члену уравнения, своя константа= alfa^n. Забиваете вручную или ввиде параметра, а лучше чтобы этот параметр сам синтезатор посчитал в функции на этапе компиляции - дело Ваше.
каждый блок алгоритмически описывается:

Спасибо, помогли разобраться.

Подскажите, а как поступать с укороченным кодом

При укороченном пакете подразумевается, что все старшие члены нулевые и в них не может быть ошибки (если это не так, а это может быть только при количестве ошибок больше допустимого для выбранного количества проверочных символов, то это только на руку - повышается вероятность обнаружения неисправимой ошибки). Следовательно эти старшие члены можно быстро обсчитать и начать процедуру Ченя с нужной позиции. Если для полной длины начальным состоянием регистров были коэффициенты полинома lambda[n], то с укороченным lambda[n]*alfa^{{(LENGTHFULL-PACKLENGTH)*n}%( LENGTHFULL-1)}


где LENGTHFULL - 2 ^width (при 11-битном символе =2048)
PACKLENGTH- реальная длина пакета.

К примеру у Вас длина пакета 2037, на 10 меньше максимальной длины для 11-битного символа. Тогда для старшего члена многочлена lambda в степени 8 необходимо инициализировать регистр lambda[8]*alfa^10*8=lambda[8]*alfa⁸⁰ , для члена со степенью 7 lambda[7]*alfa⁷⁰ и т.д.

Чую следующий вопрос будет про мягкое декодирование кодов БЧХ.

Вот так общими усилиями и разработаем 3 велосипеда, и будет нам высокоплачиваемое счастье! На то и форум =)

не, ну я бы прикрутил к выложеным на форуме сорцам БЧХ/РС мягкое решение по алгоритму чейза и выложил бы его для всех %). правда я в этом еще ничего не понимаю, особенно как поступать в случае использования мягкого решения для модуляции выше BPSK ;(

Большое спасибо за подробный и понятный ответ.

Вроде все получилось. Нахожу корни уравнения. По теории обратные корни уравнения должны показывать позиции ошибок. А у меня получается, что найденные корни соответствуют позициям ошибок и обратные корни вообще мне не нужны. Вносил ошибки в сигнал и сравнивал с сигналом без ошибок, вот такую закономерность и увидел. Что может быть не так?

все так, в процедуре ченя поиск идет в обратном порядке, поэтому и не нужно обращение и все получается на лету. неплохо это объяснено в книге Кларка "Кодирование с исправлением ошибок"

Что значит поиск идет в обратном порядке? Я последовательно подставляю alfa, alfa^2,alfa^3 и так далее в ключевое уравнение. В теории, если к примеру подставим alfa и ключевое уравнение обратится в ноль, то позицией ошибки будет обратный элемент поля. А у меня получается, что корни уравнения это и есть обратные корни. Если возможно, объяните где я ошибаюсь?

на скриншоте же написано %)? по тексту "Возможные положения ошибок проверяются последовательно с индекса n-1. Суммируя величины на выходе регистра в момент i, проверяем, выполнено ли равенство L(alpha^-i) == 0".
Этот алгоритм основан на модульности арифметики в полях галуа и определении свойства поля о существовании обратного элемента по умножению. В вашем случае элементом обратным к элементу alpha^1 будет alpha^(n-1). Поэтому и не требуется отдельного обращения.

Понял. Спасибо.

в связи с праздниками и надоевшим ничегонеделанием, пришла в голову мысль, а не сделать ли открытый турбокодер, треллис, лдпц. Вот только оформить это в отдельную тему, вместе с БЧХ/РС....

[/quote]
По ходу дела возникло несколько вопросов по данной теме:
1) Код исправляет 8 ошибок. К примеру, для какого-то кодового слова получился полином локаторов ошибок 4-й степени. Т.е. по теории в кодовом слове возникло 4 ошибки. Посчитав для этого КС корни по процедуре Ченя у меня количество корней получается меньше степени полинома локаторов ошибок (к примеру 2 корня) и декодер рапортует об обнаружении неисправимой ошибки. Подскажите возможна ли такая ситуация или я где-то ошибаюсь?

2) Код исправляет 8 ошибок, значит обнаружить может 16. Про ошибки которые исправляются все понятно, определяются по степени полинома локаторов и им же ограничиваются т.е. для 8 ошибок 8-я степень. Я если к примеру у меня 13 ошибок, то, что произошла неисправимая ошибка я пойму в процедуре Ченя, увидив, что кол-во корней меньше степени полинома локаторов. Вопрос, как я обнаружу, что произошло именно 13 ошибок, а не 9 к примеру?

2)никак. Да и какая Вам разница если ошибки все равно не исправить?


1)Да вроде правильно рассуждаете.

А вообще просто промоделируйте свой декодер и сомнения в его работоспособности отпадут.

Еще добавлю. Я когда свой делал, то тестбенч писать влом было. Поэтому сделал интерфейс своего модуля схожим с таким от альтеровского модуля. Сгенерил мегавизардом альтеровский модуль с такими же как у меня параметрами и его тестбенч использовал для проверки своего декодера. Хотя он и не очень то и хорош. Я ожидал от такой конторы более детального теста. Проверка исправляющих и обнаруживающих свойств нормальная, а вот проверка (не знаю как правильно выразиться) соответствия интерфейса на взаимодействие с внешними устройствами никакущая. Я поэтому некоторые ошибки свои не сразу словил.

более того, декодер может рапортовать что все хорошо и исправить "ошибки" родив другое кодовое слово %)

Но вообще где то видел статьи о достоверном обнаружении ошибок за границей кодов БЧХ, но так и не понял что именно авторы предлагали

может уже не актульно, но вот тема затрагивающая вопросы о детектировании ошибок за границей БЧХ http://electronix.ru/forum/index.php?showtopic=80688

Появился ряд вопросов. Реализовал процедуру Ченя, представленную на рисунке. Для 64 каналов соответственно поставил параллельно 64 таких блоков. Можно ли при данных условиях сэкономить по ресурсам? Вижу несколько вариантов: 1)Как в таком случае поступать при параллельной процедуре Ченя и что будет по ресурсам? В статьях сказано, что с использованием параллельной архитектуру можно найти решение за n/p тактов вмето n. Я правильно пониманию, что можно использовать один параллельный блок Ченя, для всех каналов? 2) Имеет ли смысл реализация так называемой strength-reduced parallel Chien search architecture для экономии ресурсов и в чем особенность этого метода.

В файле есть способ отимизации процедуры ченя.

По ресурсам плис, можно сэкономить только одним способом, задрав тактовую частоту и обрабатывать несколько каналов на одном блоке.

Параллельная архитектура используется для уменьшения времени поиска, ее имеет смысл применять когда требуется большая производительность, чем дает последовательный чень (например при работе со словами больше чем 1 бит или перебор решений при мягком декодировании кодов БЧХ).

Т.е. один параллельный блок Ченя можно использовать для обработки последовательно нескольких каналов ? Не очень понятно, что значит большая производительность?

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


например есть поток 400 мегабит/с и максимальная частота обработки в 100МГц. Надо либо сделать частоту обработки 400МГц, либо обрабатывать по 4 бита за 1 такт либо поставить 4 декодера.

Или вот еще, используете алгоритм Чейза, t битов взяли под мягкое решение, нужно перебрать 2^t вариантов за один пакет. А скорость поступления пакетов никто не собирается уменьшать в 2^t раз %))

По частоте успеваете?

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

я понял

Возник вопрос по реализации умножителей в поле Галуа на константу. Смысл состоит в преобразовании исходной матрицы упрощенному виду с целью упрощения умножителей.Используется для реализации параллельной процедуры Ченя. Если кто-нибудь разобрался объясните как это делается. Что-то я не совсем понял как это делается. В статья 4 этапа
Different from the algorithm in , our iterative matching algorithm
based on consists of following four basic steps:
1) determine the number of bit-wise matches (nonzero bits) be-
tweenall of the rows inthe binary matrix  ;
2) choose the best match;
3) eliminate the redundancy fromthe bestmatch; return the remain-
ders to the two rows that contribute the best match; append an
additional row at the bottom of the binary matrix to hold the re-
dundancy;
4) repeat steps 1–3 for all the rows in the binary matrix including
the appended rows until no improvement is achieved, i.e., the
best match is not greater than 1 bit.
Пример на рисунках. Непонятно каким образом они преобразуют матрицу. Так же прикладываю статью с примером и описанием.

Что там разбираться то, они делают то что во всех современных синтезаторах называют resource sharing, при этом эта опция очень неплохо работает.

ЗЫ. для ПЛИС вам это не нужно

Почему для ПЛИС это не нужно?

1. как бы предыдущий мой ответ дал уже подсказку , синтезаторы сами, автоматически и довольно качественно, занимаются такой оптимизацией с учетом архитектуры целевой ПЛИС.
2. базис плис, мягко говоря, сильно отличается от XOR ов асика, количество которых оптимизируется в рассматриваемой в статье.

Появился вопрос по реализации алгоритма Форни для декодера Рида-Соломона. Имеется код Рида-Соломона с параметрами n=255, k=239 в поле Галуа GF(2^8) примитивный полином p(x)=x^8 +x^4+x^3+x^2+1.
Внес 2 ошибки в кодовое слово в 2 младших бита символа(байта). После алгоритма декодирования получил следующие данные alfa(x)=84x^2 +215x+82 - полином локаторов ошибок, omega(x)= 228x + 38 - полином величин ошибок. После процедуры Ченя получаю корни уравнения alfa(x) - alfa^2 и alfa^3.
Далее вычисляю формальную производную alfa*(x)=alfa1=215. И соответственно сами величины ошибок
v1(alfa^2 )=228*4 xor 38/215=108, v2(alfa^3)=228*8 xor 38/215=235. В итоге получаю неправильный результат т.к. по идее величины ошибок должны быть равны v1=3 и v2=3. Подскажите, где я делаю ошибку