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

1. Если у меня 60 проверочных бит (исправляет 6 ошибок) - то у меня должно быть 60 бит синдрома ошибок?
2. Синдром вычисляем сдвиговым регистром (умножаем на порождающий полином). А вот дальше тупик. Что с ним делать?
Надо искать полином локаторов ошибок. Нашел реализацию процедуры ченя (картинка). Что есть что на ней непонятно, несколько раз прочитал- все равно не понятно. Кто имел дело с декодированием, наверняка все очевидно покажется.
3. Что такое альфа и лябда на картинке?
4. Чему равно t - количеству проверочных бит или общему количеству бит?
5. Написано все возможные положения ошибок проверяются последовательно - если у меня 560 бит всего, то я что, должен проверить 2^560 вариантов комбинаций ошибок? Что то нереально. Или по одной надо проверять последовательно?
6. Что делает квадрат на блок схеме с лябдой? Это регистр?

Если спросил что-то глупое- сразу извиняюсь, недавно в тему начал вникать, каша в голове

сорцы мои слейте, там все написано %) причем потом еще и укороченные коды прикрутил

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

прошу извинить а где можно слить сорцы?

разрядность синдрома ошибки t+1 m битовых чисел


искать по синдрому полином локаторов ошибок, потом по полиному локаторов искать положения ошибок. Для битовых кодов все.


альфа примитивный элемент поля галуа, лямбда - полином локаторов ошибок

кхм, в матлабе читаем хелп, по кодам БЧХ


последовательно, за кол-во операций == размерности кодового слова. 560 не айс для кодов БЧХ, ИМХО.


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


у меня там даже поведенческая модель есть референсная, там БЧХ кодер по косточкам разложен. да и код там написан простым языком. скелет вычисляется на раз + RiBM, SiBM алгоритмы есть.



В теме AHDL vs System Verilog, предпоследний пост вроде бы. После этого я еще пару ошибок устранил (при определенных полиномах баги лезли) + подчистил код. Как нить соберусь и выложу. Вот только генерация порождающего полинома мне пока не дается. времени нет %(

Пожалуй, все-таки ближе к t m битовых чисел

на данной схеме Альфа не элемент поля, а скорее вектор ошибки кратности 1...t, где t - макс.число исправляемых кодом ошибок.
для вектора ошибки соотв. кратности ищется свой полином локатора ошибок Лямбда, корни которого находятся процедурой Ченя.
затем алгоритмом Форни ищется конфигурация ошибок (характер вектора ошибки)
и исправляется простым xor с исходным кодовым словом

согласен, сбила адресация [1:t] в коде, привык что обычно индексация с нуля идет


ИМХО вы ошибаетесь, даже текст на картинке говорит об обратном, но спорить о терминах не буду

да, чето я подзабыл алгоритм БМ... конечно, корнем многочлена локатора является элемент поля

Спасибо! Стало яснее, дальше грызу гранит БЧХ кодов

раз уж разговор зашел
подскажите, нет ли у кого для DVB-S2 кодера-декодера, референс код BCH-LDPC на разные скорости
что-то в сети найти не могу, секрет что ли большой..

смешно

PS. поймите правильно, я не пытаюсь обидеть. просто на этом поприще бьется куча народу, вряд ли ближайшие лет 5 такой мультиформатный декодер кто то выложит. Но опенкоресах кстати есть на фиксированную скорость LDPC кодер декодер

спасибо, обнадежили, я думал, что гугл сломался ))
сделаю сам на C/C++ прототип, пару мес надеюсь хватит

Не забудьте выложить в доступном месте
Если серьезно - пару месяцев уйдет на то, чтобы прочесть хотя бы 10 (лучше 30-50) статей и разобраться
с разновидностями декодеров и выбрать, что вам подходит по цвету и вкусу

Как раз такой декодер и делаю, только не DVB-S, а специализированный. LDPC осилил , поддерживает 9 длин входных блоков, каждый на 3 скорости декодировать можно. Не без ниоса конечно, но ниос только при смене длины блока/скорости участвует (переконфигурирует).

БЧХ в процессе, вопрос, если позволите (возвращаясь к теме):

Нужно получить 2t синдромов. Для этого по Блейхуту (рис) надо найти v(a), v(a^2), ...v(a^2t) v- входные данные, альфа - элемент поля. Не соображу как это. Подозреваю, что делается это схемой умножения или деления полиномов, типа той что на рисунке, но что есть что тут? Сдесь a^n задается конфигурацией обратных связей или я вообще не туда?
Если все таки это то, а^n - это тоже элемент поля, и обратные связи строятся по его двоичному представлению?

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

тоже что ли время на LDPC найти....


у вас же даже код под рукой, там синдром считается на примитивной логике. кодовое слово рассматривается как полином, в который подставляется в качестве корня (правильный термин не придумывается) примитивный элемент поля в степени от 1 до t

Уважаемый Des, увидел такую штуку в Вашем коде при вычислении синдрома:

mult_by_a[i] = ^(data & MULT_BY_A[i]);

MULT_BY_A - это как я понял таблица перемножений в поле Галуа 2^m. А обязательна эте таблица? Перемножение нельзя сделать схемой деления/умножения полиномов, типа той что я в пред. посте выкладывал? Ато памяти жалко на таблицу при m=10.

тема уже обсуждалась http://electronix.ru/forum/index.php?showtopic=80688
посмотрите - там выложена статья по аппаратной реализации умножителей в поле Галуа на комбинационнной логике (без памяти)

Можно разменять память на время. Обычно при большом поле делают переход к представлению элементов из 2^m в виде пары элементов
из 2^(m/2). При этом операция умножения в большом поле сводится к 2м операциям умножения в половинном
поле + некоторые простые операции (типа сложение). Т.е. в вашем случае нужны таблицы размера 2^5.
Но, боюсь, это трудно объяснить на пальцах, а самому вам не разобраться..

откуда там память? посмотрите синтез %)

умножитель в полях галуа вида variable by constant это ксор, определенных битов variable. вот эти определенные биты заранее рассчитываются и их маска сидит в "памяти".

ушло 2 часа на то, чтобы разобраться, что выбирать особо не из чего ))
пара удобоваримых для реализации алгоритмов для БЧХ (БМ и Евклида) и тройка для LDPC (мягкий BP, min-sum и класс многопороговых).
а если к вопросу подойти творчески, то внешний код БЧХ можно использовать лишь для обнаружения, исправляя все внутренним LDPC...
посмотрим

Ой, ступил, извините. Редко в чужих кодах копаюсь, обычно свое все пишу, не привык Копаю дальше...

У вас два часа ушло, чтобы выучить несколько красивых слов
Если Вы пишете про "мягкий BP" (а что, бывает жесткий?) и через запятую поминаете класс многопороговых алгоритмов - Вам еще разбираться и разбираться в этих хитросплетениях. И почему вы называете БЧХ внешним? Он там, скорее, внутренний
и предназначен не для обнаружения ошибок (LDPC и сам прекрасно все обнаруживает.)
В общем, "еще 5 тысяч ведер, и ключик будет ваш" )

Человек прав БЧХ - внешний, а LDPC - внутренний, более мощный, а вот по поводу многопороговых алгоритмов декодирования, то здесь с ним не соглашусь, для LDPC они не подходят, так как эти коды не соответсвуют условиям ортогональности.

Строго говоря, в этом стандарте не классическая каскадная схема, где действует правило
умножения минимальных расстояний каскадируемых кодов. Поэтому термины внутренний-внешний
тут принимают немного другой смысл, чем это принято в классических каскадных кодах.
Если считать, что внешний тот, который кодирует первым, а декодирует последним, то тогда согласен.
LDPC обычно имеют ортогональные проверки относительно каждого символа (других примеров LDPC мне не известно).
Сейчас точно не помню, как строятся коды в стандарте, но было бы очень странно, если бы там не было ортогональных проверок.
Так что их вполне можно декодировать много раз с разными порогам. Так, кстати, иногда и делают.
Это называется weighted majority decoding. По сложности - это очень просто,
а по качеству до BP или MIN-SUM, как до неба.

Вроде как всегда было так принято.

Перечитал Золотарева, действительно все так, как Вы писали

мягкий BP - работающий по мягким решениям демодулятора, дающим начальные априорные вероятности для бит(символов)
термин мягкий употребляется по аналогии с мягким декодированием Витерби, или допустим мягким декодированием циклических кодов.
а что не понравилось во фразе класс МПД-алгоритмов ? это вообще-то целый табор вариантов формирования порогов и решающих схем исправления символов даже применительно к конкретному LDPC-коду, не считая алгоритмов MПД для двоичных/недвоичных, систематических/несист, блоковых/сверточных и т.д. кодов. Об этом есть фундаментальные труды Золотарева В.В.

если вести речь о конкретном стандарте DVB-S2, БЧХ все же внешний, ознакомьтесь повнимательнее
и может быть предназначен как для исправления, так и для обнаружения, в зависимости от схемы реализации декодера обощенного кода БЧХ-LDPC
т.е. по большому счету - это зависит от хотелок разработчика и с учетом характеристик канала связи.

я могу на свое усмотрение исправлять ошибки как обоими кодами, так и любым из них, используя второй для обнаружения

http://www.mtdbest.iki.rssi.ru/


и какой же смысл несут термины внутренний-внешний, кроме того, что один код внутренний, а другой внешний ?

Это все понятно. Просто я хотел подчеркнуть, что выражение "мягкий BP" выдает с головой новичка в этой области.
Т.к. "жесткий" BP теоретически возможен, но я ни разу не встречал его применительно к LDPC.
Поэтому упоминание о мягкости BP мне показалось излишним.


Декодер Витерби жесткий я встречал неоднократно. А вот жесткий BP - нет.
Если Вы встречали жесткий BP- с благодарностью приму от вас ссылку, как говорится, век живи - век учись.


Я вроде пытался ответить в предыдущем посте. Еще раз: характеристики МПД и BP абсолютно несравнимы
как по качеству декодироваия так и по сложности. Причем по качеству резкий перекос в одну сторону, а по сложности - в другую.


Я, в принципе, к трудам ВВЗ отношусь неплохо. Лучше, чем многие
Он первый перенес многопороговый алгоритм Таунсенда-Велдона для декодирования самоортогоналных
блоковых кодов на случай самоортогоналных сверточных кодов. И назвал это МПД.
И потом все жизнь бился (и, наверное, до сих пор бьется) с иппишниками за официальное
признание своих кодировочных достижений. Но, вроде бы, насколько я знаю,
так до сих пор и числится в "кодировочном андеграунде"
Но я не хотел бы здесь дискутировать на эту бесконечную тему.

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


Это уже какая-то ерунда.


Ой, вот только ссылок на МПД мне не надо! Увольте!!!

BP никогда не делал, как и декодеры турбо-кодов. С последних проектов по TCM+констурукции Унгербоека прошло много лет, с момента, когда ручками прорешивал ПГЦ и БМА, строил порождающие и проверочные матрицы.., - еще больше. Поэтому современную терминологию, широко принятую в узких кругах, еще пока не освоил.
может вы не поняли, но я не сравнивал их по качеству и сложности.
а если хорошо подумать ? я сходу вижу три подхода
1. оба исправляют: LDPC-BP + БЧХ-БМА
2. LDPC оценивает,
- БЧХ исправляет методом усеченного перебора ранжированных по достоверности символов (по какому-то порогу достоверности)
- БЧХ исправляет Чейзом
- стираем 2t малодостоверных, БЧХ восстанавливает стирания
3. БЧХ оценивает (= считаем синдром)
1) LDPC-MinSum, исправляет
2) считаем синдром БЧХ,
синдром ненулевой => корректируем априорные вероятности (критерий пока не важен), идем к п.1

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

ссылка вообще-то не вам была. увольняю )))

Это наиболее разумный вариант. Я бы добавил, что БЧХ может и обнаруживать тяжелые ошибки,
если в обнаружении есть какой-то смысл.


Это ерунда. ИМХО, конечно.


Предложить-то можно. Но делать не советую.

Вот опять дошли руки. Правильно ли я понял из Вашего кода, Des, что значения синдромов зависят только от входных данных, степени альфы и поля в котором выполняется вычисление? И не зависят от выбранных примитивных полиномов и порождающего (произведения выбранных примитивных)?
Функция, создающая маску MULT_BY_A не использует вроде ничего кроме степени альфы и таблицы Alpha_to. Или опять где-то недосмотрел?

И еще вопрос: вот такая конструкция {{m-1}{1'b0}} это что? Вот это {x,idat} - concatenate, понятно.

Вот отсюда:
osyndrome <= {{{m-1}{1'b0}}, idat} ^ mult_by_a(osyndrome);

Сам такое не использовал, в книжках не нашел...

это не наиболее разумный вариант, а наиболее дубовый и худший по критерию вероятности ошибки декодирования. Ошибочное декодирование с выхода LDPC размножит ошибку, с которой может не справиться БЧХ в режиме исправления (декодируя в неправильное разрешенное КС).
По этой причине для декодирования вот таких вот составных кодов имеет смысл передавать на след. уровень не единственное решение декодера, а подмножество, М-список решений. п.2-3, которые вам кажутся ерундой, в упрощенном виде реализуют именно эту идею. У циклических кодов БЧХ очень мощная обнаруживающая способность, у LDPC исправляющая, на этом надо и играть.

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

да, только поле считается по порождающему и примитивному полиному %)

да

репликация в конкатенации, т.е. вписать слева m-1 нулей



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

Худший по вероятности? Откуда такая уверенность?
Думаю, что это просто ваша смелая научная гипотеза.
Которая, вполне возможно, и не подтвердится.


Если LDPC не справится, то в любом случае все пропало В типичной ошибочной ситуации у него на выходе будет
примерено то же, что и на выходе канала. Т.е. полная каша, разгрести которую не под силу никакому БЧХ.
Вы не понимаете. Там предусмотрен хилый БЧХ для подчистки мелкого "мусора" после LDPC (почитайте про error floor).
Ну и дополнительная возможность для обнаружения ошибок.
LDPC в ходе декодирования исправляет десятки и даже сотни ошибок, а БЧХ из этого стандарта всего 8 или 12 - сейчас точно не помню.
Но даже если бы там стоял мощный BЧХ, который вы декодировали бы по Чейзу или по Форни со стираниями,
он все равно и рядом не стоял бы с LDPC, работающем с непрерывным выходом канала.
Именно поэтому LDPC и ценят. А вы их все пытаетесь представить полноценными партнерами в этой связке. Это все равно,
что перечислить BP и МПД через запятую.

Идея богатая. Могу совершенно точно сказать, что вреда она точно не принесет.
А вот относительно заметной пользы - есть сомнения. Которые вы нам наверняка проясните после реализации в программе.
Ждем-с.


Смелая научная гипотеза. Очень смелая
LDPC и сам хорошо обнаруживает ошибки и редко ошибается в кодовое слово.
Чаще он находит "псевдослово" и на нем зацикливается, но при этом все равно обнаруживает его.
Сейчас с Вами пока не о чем спорить. Играйте. Пробуйте.
Когда начнете моделирование LDPC, для вас многое прояснится.

лет 8 назад реализовывал связку TCM-код + CRC16, улучшив ЭВК около 0.6 дб относительно раздельного их декодирования. Как мне кажется, здесь тот же случай, только в профиль. Насколько правильно мы оценим подмножество малодостоверных символов на внутреннем коде LDPC, чтобы в него попало истинное КС, настолько больше шансов выбора из этого подмножества истинного КС внешним кодом БЧХ в режиме обнаружения.




Вы вообще-то совсем не поняли идею. Еще раз другими словами я ее передал выше. При декодировании составных кодов один из кодов можно использовать в режиме обнаружения, и лучше, чтобы это был код с меньшей исправляющей способностью и высокой обнаруживающей. т.е. в данном случае БЧХ. БЧХ будет исправлять по макс.правдоподобия, Чейзу или Форни уже выход LDPC, т.е. работать с подмножеством малодостоверных векторов.

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

спасибо, с HDL не очень дружу, но может разберусь если у себя затыки будут. Пока почти готов С/С++ прототип декодера БМА для укороченного РС(204,188) DVB-S, но тоже на задаваемый ручками полином и фикс. число ошибок. Хотел поглядеть на ваш, чтобы на БЧХ перенести на произв.полином и скорость
p.s. все, увидел с-пример Морелоса-Сарагосы

Попробовал перенести на С ваше hdl описание вычисления синдромов БЧХ (чтоб "пощупать", на си как-то удобнее). Оказывается в качестве прототипа С я использовал тот же сишный код что и Вы. Си декодер БЧХ у меня работает. Для кода без ошибок вычисляю синдромы - как и положено нулевые. Пробую вычислить те же синдромы "аналогом" Hdl описания - первый же синдром ненулевой. Похоже я где то недопонял, а где найти не могу. Если не трудно, пожалуйста ткните что где не так я сделал. Прицепляю файл. В последней колонке - функция на Си, она у меня работает правильно. В средней колонке - Ваше HDL описание вычисления синдромов, разбитое на функции, которые используются. В первой колонке - максимально приближенный к HDL код, который уже не работает нормально. Таблицы alpha_to, index_of беру те же, что и генерируются для рабочего кода. Таблица incode - каждый элемент принимает значение 0 или 1 - сгенерирована BCH_encode, сишной функцией декодируется нормально.

посмотрю позже

Исправил я у себя мелкие ошибки, скомпилировал Ваш проект. Взял отдельно модуль bch_syndrome_count_mult с параметром 1 (вычисляю пока только первый синдром), загнал в тестбенч, проверил со своим аналогом на си - данные (значения синдрома после каждого такта) совпадают, проверял на примерно 60 значениях. На вход подавал в одном случае все единицы, в другом последовательность 0,1,0,1,0,1,... В обоих случаях полное совпадение с результатами "модели" на си. Но когда в модель на си подаю реальный бчх код длиной 532 - синдром нулевой почему то не получается, при этом те же данные подаю на такой код:


первый синдром - нулевой. Таблицы alpha_to и index_of одни и те же.
Свои мысли кончились, подскажите где копать.

Кстати, значение синдрома после каждого клока должно совпадать со значением синдрома в этом коде после каждой итерации?

UPD: Развернул поток битов БЧХ зеркально (т.е. первый бит это последний, а последний- это первый), сишная модель hdl теперь выдает нормальный синдром 0,а код выше - то же значение которое выдавала сишная модель до разворота битов. Что сделать чтоб в таком же порядке биты подавать (как и в программу) и при этом чтоб hdl правильно считал синдромы?

да

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

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

Вопрос следующего рода. Можно ли заставить работать randomize() на пакете ModelSim Starter Edition?
Не хотелось бы связываться с контрафактом.
Подумываю, чтобы загружать тестбенч из графического файла.

Т.е. Ваши сорцы в ModelSim SE не проходят симуляцию.

Вот такой вопрос еще возник: если есть два укороченных кода с разной длиной блока, но кол-во проверочных бит и исправляемых ошибок одно и тоже, одинаковые генераторный полином и примитивный полином для построения поля, то их можно будет декодировать одним декодером без изменений, только вовремя надо подавать сигнал EOP?

Уважемые ГУРУ по кодам. Проясните ситуацию для меня темного.
Ситуация: на вход декодера БЧХ приходит последовательность бит с количеством ошибок превышающим количество исправляемое кодом; декодер рапартует об исправлении ошибок (т.к. после поиска Ченя количество корней полинома локаторов ошибок равняется его степени), но последовательность бит отличается от исходной.
Как и на какой стадии (вычисление синдромов ошибок, алгоритм Берлекемпа-Мэсси, поиск Ченя) определить что исходную последовательность восстановить невозможно?

http://electronix.ru/forum/index.php?s=&am...st&p=819362

Уважаемый Des, СПАСИБО! Со всем разобрался, все получилось как хотел. Помогли сэкономить кучу времени! Дай Бог здоровья тебе добрый человек!

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

думаю вам будет интересна реализация simplified reformulated IBM (SRIBM) алгоритма для БЧХ кодов, много лучше чем simplified IBM (SIBM).

Спасибо! Чуть разгребу с текучкой и попробую.

уже забыл про тему, но справедливости ради подниму, т.к. определенная работа все же была проделана.
реализованы BP и Min-Sum, из них естественно для аппаратной реализации остановились на Min-Sum
наибольшую трудность вызвала не сама реализация алгоритма, а построение Shuffle Network и Barrel-shifter в частности
при этом LDPC-декодер себя ведет так, что либо полностью исправляет ошибки (или почти полностью, оставляя 1-2 для БЧХ), либо ошибки размножает уже до полного безобразия

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