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


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

Любой код можно представить в виде точек в 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

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

Не очень понятно какой корректирующий коэффициент т.е. наподобие корректирующего коэффициента для укороченного кода при инициализации, только alfa^0 ?

SKov
Спасибо большое спасибо за подробное объяснение.

алгоритм форни считает Yi = -z^m0 *omega(z)/z*lambda'(z), где m0 - степень первого корня. Но для m = 0, там будет 1 и коррекция не нужны. Ошибся немного %)

У меня получается правильные величины ошибки (если синдромы считать с alfa^0 как в моем случае) только если omega(x)=alfa0*S2 + (alfa1*S3 +alfa2*S2)x + (alfa0*S4+alfa1*S3+alfa2*S2)x^2+ ....-хотя по теории надо считать
omega(x)=alfa0*S1 + (alfa1*S2 +alfa2*S1)x + (alfa0*S3+alfa1*S2+alfa2*S1)x^2+ ... В чем может быть ошибка или я теорию неправильно понял?

для выяснения проблемы вышлите мне параметры используемого вами кода : {m, n,k, m0, rootspace} и пару закодированных блоков. посмотрю что к чему. Лучше на почту.

Деление a/b в алгоритме Форни для декодера Рида-Соломона (255,239) реализовал через умножение используя таблицу инверсных элементов 1/b на блочной памяти (в таблицы номер ячейки значение b, значение ячейки соответственно результат 1\b). Подскажите правильная ли у меня таблица и если нет то где ошибка? Если кто-то реализовал алгоритм Форни для декодера на ПЛИС без использования таблицы инверсий, сколько места занял делитель в поле Галуа?

Продолжаю пиарить красоту SV.

На сей раз использование возможностей SV для простого моделирования алгоритмов на примере сверточного дуобинарного турбокода. Поддерживаются стандарты DVB и Wimax + сделано расширение скоростей кодирования. Кодер синтезируемый, декодер пока только идеалка близкая к железу по организации вычислений и интерфейсам. Тестбенч - так называемый bertest. Поддерживается пока только QPSK. В идеалке можно покрутить разрядности, алгоритмы (семейство MAX Log MAP) посмотреть что и куда идет и как считается.

Запилил идеалку для прямого портирования на RTL уровень. Отличие от идеалки общего вида :
1. Одновременный проход прямой и обратной рекурсии
2. collision-free интерливер для одновременного доступа для метрик прямой и обратной ветви.
3. Компрессия метрик состояний ветвей для уменьшения расхода памяти метрик (прекрасно ложится на плис).
4. Изменена концепция работы с буферами данных для оптимизации ресурса памяти плиса.
5. Код почищен от мусора.

До синтезируемого RTL кода 1,5 шага
ЗЫ. Пока все проверяется на QPSK скорости 1/3 и 1/2. Другие скорости и модуляции пока не проверял.

Синтезируемый, статически конфигурируемый, однопроходный (один проход на полуитерацию) декодер DVB-RSC кода и бертест для него. Синтез в ква 9.1 для сыклона и7 для блока 128 бит : ~6000LE, 15M9K, 106МГц настройки по умолчанию. Тактовая упирается в расчет рекурсии. Нормализация вынесена из нее, все уперлось в ограничения алгоритма.

Последняя версия кодека:
1. Добавлена таблица перемежений Wimax-OFDM, Wimax-OFDMA
2. Переписана работа кодера (таблицы, генератор адресов), архитектура оптимизирована под ПЛИС
3. Сделан рекурсивный процессор с комбинированной модульно-классической арифметикой, ресурс тот же, но тактовая поднялась за счет уменьшения длинны трасс.
4. Убран атрибут синтеза в памяти метрик, приводил к некорректной работе в ПЛИС. Кое где вбиты атрибуты, во избежание имплементации сдвиговых регистров на памяти.
5. Кодек проверен в железе на разных пакетах и разных скоростях кодирования на последовательностях до 1е9 бит.

На этом опенсорсная часть, этого кодека окончена

des00, спасибо большое за труды.

Что планируете реализовать в закрытой части, если не секрет?
Чтобы знать, к чему стремиться

Именно по этому кодеку планов громадье :
1. Динамически конфигурируемый кодек, в том числе с переключением на лету.
2. Эконом версию декодера с меньшим ресурсом.
3. Добавить модуляции до КАМ64.
4. Текущий декодер, на частоте 100 МГц и 8 итерациях дает где-то 12 Мб/с скорость декодирования, есть задумки сделать декодер на ~100 мегабит

Ну и затем BTC, LDPC

Wimax LDPC encoder со статической конфигурацией. Поддерживаемые скорости 1/2, 2/3B, 3/4A, 5/6.
Параметры кодера для сыклона 3 и7:
Кодирование по 4 бита, скорость 5/6, длина 576 : 456 плиток хлопающих на частоте 250МГц (~1 Гбит/с)
Кодирование по 4 бита, скорость 5/6, длина 2304 : 1342 плитки хлопающих на частоте 200МГц (~800Мб/с)
Кодирование по 8 бит, скорость 5/6, длина 2304 : 1145 плитки хлопающих на частоте 210МГц (~1.68Гбит/с)

UPD. Метод проверки - по эталонной модели и матлабу. Код для матлаба в теме про кодирование в Алгоритмах
UPD2. Возможность работать по 4/8 бит определяется целочисленной кратностью expansion factor (zf) 4/8 битам.

Спасибо за еще один пример пользы SystemVerilog'a!
Вы намеренно по асинхронному сбросу сбрасываете только val и state? Исходите из каких-то соображений по разводке или из философии, что сбрасывать надо только управляющие сигналы?

Все по заветам Кена Чапмена(автора пикоблейза и Xilinx гуру): When creating each section of a design, simply ask, “Does this bit need to be reset”?
Все в системе определяется по сигналу валидности и состоянием конечного автомата, смысла сбрасывать другие сигналы нет. Помимо этого, на некоторых платформах (где триггер может быть только с одним типом сброса), можно потерять в ресурсе или производительности.

Благодарю за ответ.
Со временем тоже пришел к аналогичной философии: сбрасывать только то, что надо сбрасывать. Но иногда лень берет своё, и сбрасываю всё.
Недавно копался в интерконнекте Альтеры, и заметил, что они тоже "ленятся", и как-то общих рекомендаций и философии не прослеживается.
Видимо от самих разработчиков этих модулей зависит.

То сбрасывают всё:


А вот тут наоборот, сбрасывают только то, что надо

Скорее от лени и прилежания Обычно после получения необходимой функциональности и закрепления результатов, я провожу ручной рефакторинг кода (удаляю все ненужное, делаю расширенные комментарии, правлю описания сбросов, убираю большинство варнингов синтеза и т.д.). Т.е. рассматриваю код как товарный продукт. Да это "шашечки", но зато всегда могу вернуться к коду и понять как он работает. Ну а кому то нужно "ехать" и они забывают заветы Ф. Брукса о том что написание кода это 15% от всего проекта

1. BERtest + идеальный matlab style декодер.
2. идеальный RTL like декодер (один шаг до RTL реализации для любого разработчика). Содержит параметр pLLR_BY_CYCLE - количество метрик обрабатываемых за 1 такт. Должно быть меньше чем expansion factor.

Wimax LDPC кодек со статической конфигурацией. Поддерживаемые скорости 1/2, 2/3B, 3/4A, 5/6.

Метод декодирования 2D normalized Min-Sum. Декодер работает с прямыми метриками, ширина интерфейса определяется количеством метрик обрабатываемых за 1 такт. Количество метрик за такт должно быть кратно размеру T матрицы H (24). expansion factor (Zf)

Результаты декодера на плис средние. Сыклон 4, спидгрейт с7, длина 2304, скорость кодирования 5/6, 8 метрик за 1 такт, разрядность метрики 5 бит: 11872LC, 6624Reg, 37 M9K, тактовая 210 МГц. Тормозит генерация адресов памяти, т.к. в ваймаксе есть нечетные сдвиги, что делает невозможным работу с блочком памяти в режиме больше 1 метрики.

Тестбенч бертест, кпск, 2/4/6/8/16 метрик за такт. Время декодирования = 2*((Niter + 0.5)*length/кол-во метрик за такт) + латентность порядка 30 тактов).

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

1. Отучил кодер от ограничений на размер интерфейса 2^N кратный pT pZF, теперь любое числое кратное pТ pZF.
2. Оптимизировал управление конвейером в декодере, выиграл немного тактов.
3. Сделал декодер с разделенным входным буфером и более сложным управлением. В зависимости от размера блока памяти потребуется больше, но зато можно совместить последнюю полуитерацию декодирования с загрузкой рабочей памяти новыми данными.

Этот релиз последний.

маппер и мягкий демапер для модуляций BPSK, QPSK, 8PSK, QAM16, QAM32, QAM64, QAM128, QAM256, QAM1024.

Созвездия:
BPSK - повернуто на 45 грудусов
QPSK, QAM16-QAM256 - из доки от AHA.
8PSK - повернуто на 22.5 градуса.

Метрики квадратных КАМов, BPSK, 8PSK - конфигурируемой разрядности, остальные нечетные КАМы - фиксированные 4 бита. Метрики = логарифм отношения надежностей битов символа, при условии sigma^2 = 0.5

Результаты на арию 5 С5: демапер 623/791 ALM/Reg, частота за 300 МГц

Тестбенч простой, просто проверяет только жесткое решение.

ЗЫ. Разыскивается созвездие КАМ512. Можно свое нарисовать, но несколько часов терять не охота

Как то совсем забыл про матлаб. В итоге весь ряд модуляций (правда матлабовские 32 и 128 отличаются от ахашных).
Немного поэкспериментировал с ква, странно но generate for дал более хороший результат, чем процедурный for + перевел таблицы кам128 и 512 на использование разбиения таблиц блоками 8х8, вместо 16х16. Это дало суммарную экономию ~250 плиток. Итоговый результат на полный демаппер 852 ALM, 1076 регистров, частота упала до 280МГц (еще один слой регистров добавлять лень, да и целевая у меня 250).

LDPC Кодер (7154, 8176) для стандарта GSFC-STD-9100. При работе с 7ми битными словами параметры кодера для Aria V : 3610ALM/~275МГц, производительность > 1,5Гигабит в сек.

Кодер работал неправильно, вот что значит читать стандарты по диагонали Архив прибил.

NASA GSFC LDPC codec 7154/8176 (GSFC-STD-9100).

В аттаче : RTL кодер, декодер идеалка и самая медленная версия RTL декодера, работающая по 4 нода за такт и с не буферизированным выходом. Ресурсы для Арии 5 : ALM/REG/M10K 565/1218/24. Оцененная частота для С5 261.44 MHz. Более быстрые декодеры уже сами

Немного почистил код, оптимизировал сигналы готовности vnode/cnode движков, проверил режим работы с большим количеством метрик за такт.

Набираю информацию по F-LDPC кодам(GRA коды). Может у кого есть хорошая подборка?

Делаю подходы к TPC : кодер Хэмминга. Совершенный, расширенный, в систематической форме.

Появилось окно. Стало скучно. Таки добил старый TODO. БЧХ со стираниями, работает на лету, 250 мегабит на ария 5.

Где можно почитать про декодер со стираниями? Можно ли их использовать для итеративного декодирования?

Offtop.
Послушайте Денис, Вы не думали завести репозитарий на github например для всяких таких поделок?
Мне кажется это было бы удобнее, если Вашим работам разрешено находиться в открытом доступе.

Р. Морелос-Сарагоса «Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение».
стр.103-105.

В случае с БЧХ-кодами получаются две итерации декодирования.

dvladim, присоединяюсь.

ГитХаб превращается в тыкву. Все оттуда бегут.

Тогда GitLab.

Еще в помощь вот это http://the-art-of-ecc.com/3_Cyclic_BCH/index.html и пример от x736C, который он сделал по моей просьбе, за что отдельное спасибо). Про итеративное декодирование, будет время, сделаю турбокодер на основе приложенной статьи.


Тут несколько, неудобных для меня моментов:
1. Проекты в моем репо достаточно далеко разошлись от выложенных тут, что-то модернизированно, что-то переписано, где то запиленно под целевые ПЛИС и обвешано макросами. Выкладывать все как есть, не в моих интересах, а готовить сорцы к выкладыванию в общественный репо, времени нет.
2. Опыт выкладывания полноценной IP Core, с документацией, у меня есть (опенкорес). Времени на документирование ушло очень много. Чувство прекрасного, не позволяет выложить просто сорцы без описания архитектуры, рекомендации по использованию и т.д. На это нужно время.

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

Куда бегут? Какие есть достойные ресурсы?

В течение первых суток после новости о покупке ГитХаба Некрософтом на ГитЛаб смигрировало около 100 000 проектов.
Все они разной степени тормознутости и глючности.

А какие есть объективные и обоснованные опасения?
У меня просто там платный аккаунт. А я не в зуб ногой.

Извините за оффтоп (тема то про FEC), но для миграции с github куда-либо еще в настоящий момент нет ни малейших оснований. Миграция тысяч проектов лично мне не понятна, никаких негативных последствий от покупки компании так и не наступило, и вряд ли наступит вообще.

Какой порядок следования бит? Если у нас синдром задается следующей формулой, то в декодер сначала поступают r[n-1],r[n-2]... или наоборот?

в декодер сначала поступают r[n-1],r[n-2]...
И если преобразовать приведённую Вами формулу к виду, пригодному для реализации в железе, то будет понятно почему.

Появилось немного времени.

Статически конфигурируемый кодек турбокода, описанного в документе ETSI EN 301 545-2 V1.2.1 (DVB-RCS2). От DVB-RCS отличается решеткой на 16 состояний.
Поддерживаются все описанные в документе 34 размера блока(от 14 до 599 байт) и скорости кодирования(1/3....7/8). Тестбенч - бертест.

Результаты на 5 ой арии для блока на 14байт: кодер/декодер 107/5382ALM, частота 125МГц.

Всем доброго дня, нужна теоретическая помощь. Суть вот в чем.

Снял характеристики всех возможных режимов работы кодека и .... не вижу ощутимой разницы между DVB-RCS2 и DVB-RCS. Хотя она должна быть, т.к. кодовое расстояние решетки на 16 и 8 различно. Да и сами авторы, утверждают

а кое где встречается и

Код проштудировал, явной ошибки в алгоритме Max Log MAP не вижу, разрядности на переполнение проверил. Начал рыть в сети и получил результаты, которые еще больше поставили в тупик. Например, в приложенной статье приводятся коды на решетке 8(рисунок 5) и 16(рисунок 6). Видно что, для одной и тойже модуляции и скорости, код с решеткой 16 проигрывает коду с решеткой 8.

Других явных сравнений не нагуглилось, пошел с другой стороны. Вот народ продает корку www.sworld.com.au/pub/pcd04d4.pdf, смотрю ее характеристики и они в пределах +-0.1дб совпадают со снятыми мной (смотреть графики для MAX Log MAP, К - длина в битах(!!!)).



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

Matlab?
При реализации tc я обнаружил довольно неприятный эффект: можно сделать незначительные ошибки (перемежитель, выкалывание, хвост) , которые приводят к незначительному ухудшению корректирующей способности. Т.е. кодер и декодер tc до определенной степени устойчивы к ошибкам реализации: катастрофы не происходит, все продолжает работать, но хуже, чем заявлено.
Искать и отлаживать такие ошибки очень тяжело.

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

В матлабе есть реализация турбо кодера и декодера. С них можно начать.

Успехов