сделал отдельную тему для проекта с началом здесь

сообщения из кросс тем переместил.


продолжаем пиарить красоту SV. итак

новый релиз проекта БЧХ :
1. переписана работа с математикой в полях галуа. Теперь ква собирает декодер много быстрее, почти не задумываясь и не требует кучу памяти %)
2. переписан статически конфигурируемый БЧХ кодер/декодер, удалены лишние модули, ясность выше код чище
3. добавлен статический конфигурируемый RS кодер/декодер, стиль унифицирован с БЧХ кодером. Внимание : в сорцах есть реализация BM алгоритма, требующая на декодирование всего check тактов (!!! именно тактов а не шагов).
4. модифицированы random constraints тестбенчи, ясность выше, код чище.
5. Все как и прежде, не требует каких либо генераторов, скриптов и т.д. Вычисляется и синтезируется по месту. Расчет генераторного полинома БЧХ по прежнему не сделан %(

Динамически конфигурируемые кодеры/декодеры выкладывать не буду, это уж как нить сами

UPD. Естественно осталась возможность использовать несколько инстансов кодеров с разными параметрами в одном проекте %)

там непосредственное перемножение полиномов.

Шаг 1. берем x+a
Шаг 2. умножаем на (x+a^2). получаем x^2 + x(a + a^2) + (a*a^2).
Шаг 3. умножаем на (x+a^3). получаем x^3 + x^2(a + a^2 + a^3) + x(a*a^2 + a^3*(a+a^2)) + (a*a^2*a^3).
и т.д.

Т.е. gf_mul в этой функции это учет раскрытия скобок с умножением на следующий корень, а gf_add это накопление значения при коэффициенте.


можно переделать идеальный gf_mul на синтезируемый gf_mult_a_by_b, может тогда ему станет лучше. но мне было лень это делать %)

1. Реализована функция расчета генераторного полинома БЧХ. В качестве прототипа использовалась функция из матлаба.

Сравнил с полиномами из таблицы один в один. В симуляторе все прекрасно работает. Но при синтезе ква 9.1 долго думает когда ищет циклотомические классы. Но тем не менее полином в ква 9.1 считается и ресурс энкодера после синтеза такой же что и при использовании таблиц. Из особенностей : т.к. кол-во классов и членов классов априори не известно, а ква не может использовать массивы больше чем 2^28 бит, настройка размерностей массивов в функции генерации полиномов задается в ручную через макросы (файл bch_define.v).


2. Заменил функции gf_add/gf_mul в генерации полинома РС на синтезируемые xor/gf_mult_a_by_b. Тест показал что все работает, ква тоже съел и не подавился. Сделал для проверки синтезируемости на сторонних синтезаторах (в частности Symplify)

стесняюсь спросить, а какая разрядность Вашего Symplify ? 32 или 64 ? У меня лицензия только под 32 позволяет работать. Менял я уже gf_mult на gf_mult_a_by_b. Это для 32 бит ничего не давало. Видимо в разрядности синтезатора собака зарыта.

да у меня пока никакого нету, ставить надо %)

При декодировании кода Рида-Соломона (к примеру RS(255,239)) заметил такую особенность: когда ошибок в сигнале нет первый синдром практически всегда получается ненулевым, остальные S2..S16 равны нулю. Решатель ключевого уравнения показывает что кол-во ошибок равно нулю и собственно ничего не исправляется. Все таки непонятно почему первый синдром ненулевой?Ведь по теории такого быть не должно (если ошибок нет значит все синдромы должны быть равны нулю!!!). Интересно, что при внесении ошибок неправильного исправления не наблюдал. У БЧХ такой закономерности не встречал.

Сообщение отредактировал Gold777 - Oct 30 2012, 17:01

ищите ошибку, вот результат прогона 10 блоков такого кода без ошибок

Спасибо, буду искать ошибку. Странно, что у БЧХ такого не наблюдалось.

Более подробно опишу ранее описанную проблему. При расчете синдромов первый синдром вычисляю подставляя alfa^1 т.е. S1(alfa^1 ), S2(alfa^2), S16(alfa^16) или надо первый синдром считать подставляя alfa^0 т.е. S1(alfa^0)...S16(alfa^15)? Если расчет по второму варианту делать, то если нет ошибок все синдромы равны нулю (Позиции ошибок считаются правильно, а величины). По первому варианту S16(alfa^16) получается ненулевым (при этом позиции ошибок и величины считаются верно). Вот не могу понять, где у меня ошибка и какой вариант при расчете правильный? И еще вопрос все ли 16 синдромов всегда используются при декодировании или можно не все их вычислять(по идее существует 2^128 различных вариантов комбинаций синдромов, а возможных комбинаций ошибок и величин будет меньше)?

Сообщение отредактировал Gold777 - Nov 1 2012, 19:01

Все зависит от того, как именно у вас рассчитан генераторный полином. Если вы брали корни полинома как a^[0:check] то и синдромы нужно считать для корней со степенями [0:check], если a^[1:check+1] то соответственно будет сдвиг.


ИМХО нужно вычислять все, могу ошибаться. Думаю что гуру поправят %)

Если у вас 2^128 разных синдромов, то ровно столько различных
ошибок может исправлять код. Там могут быть и ошибки веса много больше Dмин/2.
Исправить все можно, например, полным перебором кодовых слов (если много свободного времени )
Чем больше Dмин, тем дальше код от плотной упаковки и тем больше тяжелых ошибок (больше Dмин/2)
он в принципе может исправлять.
Вообще, не обязательно исправлять совсем все ошибки для хорошего декодера.
Есть , например, такой результат: достаточно исправлять все ошибки,
которые может исправить код, до веса Dвг,тогда вероятность ошибки декодирования не более чем вдвое
превосходит вероятность ошибки при декодировании полным перебором.
Здесь Dвг означает мин. расст. для данного кода, которое получается
из границы Варшамова-Гильберта для данных кодовых параметров.
Другое дело, что ваш конкретный алгоритм исправляет только часть этих ошибок.
Наример, он не исправляет ошибки веса больще Dмин/2.
Но если вы не будете в алгоритме испрользовать часть синдрома,
то часть исправимых алгоритмом ошибок еще больше уменьшится,
т.е. вы не сможете исправлять даже некоторые ошибки веса меньше Dмин/2.

Если в рекомендации указан следующий порождающий полином
Правильно ли я понимаю что надо считать с alfa^0?


Можете объяснить, что значит плотная упаковка кода и почему чем больше Dmin, тем больше ошибок можно исправить за пределами исправляющей способности кода?


Сообщение отредактировал Gold777 - Nov 2 2012, 13:32

Любой код можно представить в виде точек в n - мерном пространстве Хемминга.
У каждого кода есть минимальное расстояние. Это значит, что если провести в пространстве Х.
сферу радиуса Dmin/2 вокруг каждого кодового слова, то получившиеся сферы не будут пересекаться.
И наоборот, если провести сферы радиуса хоть на одну единицу больше - то сферы начнут пересекаться.
Рассмотри шары радиуса Dmin/2, т.е. пересечений еще нет.
Вопрос: какая доля всего пространства Хемминга векторов длины n "вычерпана" этими шарами?
Ответ зависит от кода. Для кодов Хэмминга (это те, которые исправляют одну ошибку),
эти шары вычерпывают ровно ВСЕ пространство. Известно, что "почти все" пространство
вычерпывают примитивные коды БЧХ, исправляющие две ошибки. Эти коды относят к классу плотно упакованных.
Чем больше радиус шаров, тем больше пространства остается "в промежутках" между шарами.
Конечно, это не абсолютное правило (вспомним код Голея), но общая тенденция именно такая.
Чем дальше кодовые параметры от границы Хемминга, тем хуже упакован код.
Удобнее рассматривать смежные классы кода, чтобы понять упакованность кода.
В лидерах смежных классов, как известно, находятся те вектора ошибок, которые может
исправить код (при оптимальном декодировании, например полным перебором).
Так вот, у совершенных кодов (например, код Хемминга), все лидеры имеет вес 1, причем это все вектора веса 1.
Для квазисовершеннх кодов в лидерах есть все вектора веса до Dmin/2, и некоторые вектора веса Dmin/2 +1.
Это, например, упомянутые выше квазисовершенные БЧХ коды с Dmin =5.
Чем хуже упаковано шарами Хеммингово пространство, тем больше тяжелых лидеров существует в стандартной
расстановке для данного кода.
Я когда-то делал моделирование для длинных БЧХ кодов (16тыс бит.)
Для кодов с Dmin = 7..13 довольно часто встречались случайные вектора ошибок веса n/2,
которые переводили слово в другую сферу. Т.е. происходила неисправимая ошибка, которая приводила к неправильному декодированию в другое кодовое слово.
Это значит, что шары для этих кодов более-менее плотно заполняли пространство.
А вот для кодов с Dmin >30 даже на сотнях тысяч опытов не удавалось попасть в кодовую сферу.
Т.е. в качестве вектора ошибки генерировался случайный вектор веса n/2, далее выполнялось
декодирование по БМ, но в результате получался отказ от декодирования,
т.е. от полученного вектора на расстоянии Dmin/2 не находилось ни одного кодового слова.
Это означает, что доля пространства, высекаемая кодовыми шарами радиуса Dmin/2 была почти нулевой для больших Dmin.
Так что даже случайно тыкая пальцем в произвольный вектор в пространстве Хемминга,
мы почти с нулевой вероятностью попадали в окрестность хоть какого-нибудь кодового слова.
Это и означает, что данные коды были весьма далеки от плотной упаковки.
А вообще задачи максимально плотно упаковки разных пространств
шарами или другими объектами - это отдельная наука (и не только кодировочная), на эту тему написана куча книжек.
Поищите в и-нете.

Да именно так, при этом нужно модифицировать еще и процедуру Ченя (ввести там корректирующий коэффициент)

2 SKov
Спасибо за разъяснение. Вам бы лекции или блог по кодированию вести, очень интересно.

Спасибо, но я уже более 25лет как лектор и , говорят, хороший.
К сожалению, кодирование не востребовано у нас сейчас.
Многие мой коллеги уехали еще в начале 90х туда, где кодирование востребовано.
Мне здоровье не позволяет длительные и дальние поездки.

Да уж, горькая правда жизни. Но, к сожалению, это касается не только кодирования, но и всей области телекоммуникаций. У нас в свое время курс по кодированию ограничился рассмотрением только кодов Хемминга и БЧХ. Даже сверточное не рассматривали, какие там Turbo и LDPC