[repstosw 18]

Подскажите где можно посмотреть имплементацию алгоритма CIRC на языке Cи ?

 

Это два кодирования Рид-Соломон с перемежением, который используется в CD-дисках для коррекции ошибок.

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

 

Вот где это можно посмотреть?

И есть ещё блочные турбо-коды (BTC), они вроде тоже работают со стираниями в несколько итераций.

 

Ну и вопрос общего плана:  как узнать где стирание?  Когда пакет прилетает с эфира, я не знаю в каком месте произошла ошибка - как это узнать? Как организовать данные?

Пакет большой:  6 - 8 кБ данных.

[des00 25]

55 minutes ago, repstosw said:

Ну и вопрос общего плана:  как узнать где стирание?  Когда пакет прилетает с эфира, я не знаю в каком месте произошла ошибка - как это узнать? Как организовать данные?

Относительно CIRC в википедии же написано

Quote

The first element of a CIRC decoder is a relatively weak inner (32,28) Reed–Solomon code, shortened from a (255,251) code with 8-bit symbols. This code can correct up to 2 byte errors per 32-byte block. More importantly, it flags as erasures any uncorrectable blocks, i.e., blocks with more than 2 byte errors. The decoded 28-byte blocks, with erasure indications, are then spread by the deinterleaver to different blocks of the (28,24) outer code. Thanks to the deinterleaving, an erased 28-byte block from the inner code becomes a single erased byte in each of 28 outer code blocks. The outer code easily corrects this, since it can handle up to 4 such erasures per block.

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

Метрика стираний, на уровне символа, может быть любая: импульсная наводка, не корректный символ, не корректная последовательность символов, нулевая LLR и т.д. Более того, зная входные метрики можно алгоритм Чейза применить, для "мягкого" декодирования. Правда для символов в поле GF(2^N) надо разбираться как это корректно применяется.

[repstosw 18]

17 minutes ago, des00 said:

Относительно CIRC в википедии же написано

Я этот текст тоже читал, забавно что в англоязычной версии приводится другая исправляющая способность - до 3500  бит на блок.  А не 4000 бит, как в русскоязычной версии.

Мне нужна точная имплементация данного алгоритма. Википедиям я не верю.

Особенно интересен перемежитель, как он там сделан.  От него будет зависеть эффективность декодирования на уровне стираний.

 

P.S. Рида-Соломона с перемежением научился уже делать, работает.  Но хочется не только ошибки, но и стирания.

[des00 25]

17 minutes ago, repstosw said:

Мне нужна точная имплементация данного алгоритма. Википедиям я не верю.

Особенно интересен перемежитель, как он там сделан.  От него будет зависеть эффективность декодирования на уровне стираний.

неужели стандарт из 5 строки гугла не помог? https://www.ecma-international.org/wp-content/uploads/ECMA-130_2nd_edition_june_1996.pdf

ЗЫ. CIRC сделан специально под характерные ошибки записи на CD, для вашего радиоканала он может не подойти)

[repstosw 18]

1 hour ago, des00 said:

неужели стандарт из 5 строки гугла не помог? https://www.ecma-international.org/wp-content/uploads/ECMA-130_2nd_edition_june_1996.pdf

Не помог вообще.  Я узнал из него не больше, чем в википедии.

 

И всётаки... Как перевести ошибки в разряд стираний?

 

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

 

Изменено 28 августа, 2023 пользователем repstosw

[des00 25]

4 hours ago, repstosw said:

Не помог вообще.  Я узнал из него не больше, чем в википедии.

Вообще странно, Annex C  (normative) Error correction encoding by CIRC, полностью расписано то, чего в википедии я не видел. Какие блоки, какие байты  и куда идут, что и как задерживается, перемежается и т.д. 

4 hours ago, repstosw said:

И всётаки... Как перевести ошибки в разряд стираний?

В посте выше же написано.

Quote

This code can correct up to 2 byte errors per 32-byte block. More importantly, it flags as erasures any uncorrectable blocks, i.e., blocks with more than 2 byte errors.

стирается сразу весь блок.

4 hours ago, repstosw said:

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

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

[repstosw 18]

9 hours ago, des00 said:

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

Ладно.  CIRC отставить...

 

Нашёл статью с имплементацией блочного кода на базе Рида-Соломона:

https://we.easyelectronics.ru/Soft/2d-reed-solomon-block-turbo-codes-rs-btc.html

 

В чём эффективность такого кода по сравнению с Ридом-Соломоном + перемежение?

Проверочные символы добавляются и по вертикали и по горизонтали: общее число проверочных символов увеличивается.

Но что происходит с исправляющей способностью блочного 2Д-кода?

 

Допустим полезное сообщение: M x M байт.   Всё сообщение:  N x N байт.   Число проверочных:  N*N - M*M.

Как вывести максимальное число ошибок которые могут быть исправлены в таком коде?  Формула.

 

 

[des00 25]

36 minutes ago, repstosw said:

В чём эффективность такого кода по сравнению с Ридом-Соломоном + перемежение?

Проверочные символы добавляются и по вертикали и по горизонтали: общее число проверочных символов увеличивается.

Но что происходит с исправляющей способностью блочного 2Д-кода?

Классический блочный турбокод произведение. Самый простой вариант прочитать главу 8 Морелоса Сарагосы "Итеративно декодируемые коды"(страниц 10 вроде). На примере обычного кода проверки на четность, который не может исправлять ошибки, показано что подобная схема может корректировать ошибки. ЕМНП в лоб там не выводится корректирующая способность, все вероятностное.

Лучше всего этот код работает, когда код может вернуть мягкую метрику, чтобы передавать ее между итерациями. Решения для БЧХ я видел, но решений для РС кодов не находил. Не совсем понимаю как в РС посчитать мягкую метрику символа. Но и без мягкой метрики, за счет перемежения и корректной обработки отказа от декодирования, полагаю что код даст выигрыш. Подобная схема кстати в высокоскоростном Ethernet используется. Есть варианты для РС, есть для ММПЧ кодов. 

[repstosw 18]

1 hour ago, des00 said:

ЕМНП в лоб там не выводится корректирующая способность, все вероятностное.

Я так и думал.  Что это зависит от расположения ошибок.  Ну а если минимум и максимум вывести? Мне интересно это оценить с одиночным RS+перемежение.

У меня есть подозрения, что блочный турбо-код даст больше оверхеда, а ошибок он исправит не сильно больше, чем одиночный RS.

 

1 hour ago, des00 said:

Лучше всего этот код работает, когда код может вернуть мягкую метрику, чтобы передавать ее между итерациями. Решения для БЧХ я видел, но решений для РС кодов не находил. Не совсем понимаю как в РС посчитать мягкую метрику символа. Но и без мягкой метрики, за счет перемежения и корректной обработки отказа от декодирования, полагаю что код даст выигрыш. Подобная схема кстати в высокоскоростном Ethernet используется. Есть варианты для РС, есть для ММПЧ кодов. 

Что-то в последнее время многие говорят об этих мягких решениях, но кроме как в LDPC кодах я не видел эти решения вживую.

У меня твердый массив байт, работа с буфером.  Нету мягких решений.

 

1 hour ago, des00 said:

Самый простой вариант прочитать главу 8 Морелоса Сарагосы "Итеративно декодируемые коды"(страниц 10 вроде). На примере обычного кода проверки на четность, который не может исправлять ошибки, показано что подобная схема может корректировать ошибки. ЕМНП в лоб там не выводится корректирующая способность, все вероятностное.

 

1 hour ago, des00 said:

Подобная схема кстати в высокоскоростном Ethernet используется. Есть варианты для РС, есть для ММПЧ кодов. 

Видел такое.   Там в столбцах считается остаток от деления на 256 и вычитается из 255.  А по строкам Рид-Соломон.

 

Однако в своём приложении, я могу позволить только до 25% проверочных символов от общего числа.   Хотел использоватать каскадный код (RS + cверточный), но у него оверхед 67% (CR=1/3).    В моём случае оверхед не должен превышать 25% (CR>=3/4).  

 

Пока использую РС + перемежение. Оно работает и даже лучше, чем без него, но хочется бОльшего.

Использую RS(255,191).  Это 64 байта каждого блока на проверочные символы, что исправит максимум 32 ошибки в каждом блоке.  Число блоков: от 24 до 30. (зависит от FPS видео).    Хочется получить бОльшую исправляющую способность, при этом её увеличение должно быть больше, чем рост оверхеда.

Изменено 29 августа, 2023 пользователем repstosw

[des00 25]

3 minutes ago, repstosw said:

У меня есть подозрения, что блочный турбо-код даст больше оверхеда, а ошибок он исправит не сильно больше, чем одиночный RS.

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

3 minutes ago, repstosw said:

Что-то в последнее время многие говорят об этих мягких решениях, но кроме как в LDPC кодах я не видел эти решения вживую.

У меня твердый массив байт, работа с буфером.  Нету мягких решений.

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

[repstosw 18]

3 hours ago, des00 said:

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

Я правильно понял, что в случае если RS не может исправить ошибки (если их много), то он не может вернуть, что пакет неисправляем?  Это городить отдельно CRC надо?

[des00 25]

15 minutes ago, repstosw said:

Я правильно понял, что в случае если RS не может исправить ошибки (если их много), то он не может вернуть, что пакет неисправляем?  Это городить отдельно CRC надо?

почему? у вас же при процедуре ченя можно определить отказ от декодирования (когда количество найденых ченем корней не равно порядку полинома локаторов ошибок). В этом случае есть два варианта: размножаем ошибки(так делают в low latency декодера) или выдаем на выход входной сигнал, без исправлений. 

[repstosw 18]

24 minutes ago, des00 said:

почему? у вас же при процедуре ченя можно определить отказ от декодирования (когда количество найденых ченем корней не равно порядку полинома локаторов ошибок). В этом случае есть два варианта: размножаем ошибки(так делают в low latency декодера) или выдаем на выход входной сигнал, без исправлений. 

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

Сделал 2D кодирование RS.  Взял квадрат 255x255.   Промоделировал:  позиции ошибок случайные,  пакетная ошибка.

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

Выходит лучше  проверочные символы по второму измерению закинуть в первое - эффекта даст больше.

Приложил проект бенчмарк моделирования.

RS_Quad.zip

[petrov 6]

repstosw

Я правильно понял, что в случае если RS не может исправить ошибки (если их много), то он не может вернуть, что пакет неисправляем? Это городить отдельно CRC надо?

В общем случае не может. Можно попробовать сделать второй код просто CRC для определения стираний, после деперемежения RSом исправляете стирания.

 

[repstosw 18]

19 hours ago, petrov said:

Можно попробовать сделать второй код просто CRC для определения стираний, после деперемежения RSом исправляете стирания.

Смоделировал.  Взял 28 блоков по 255 байт. Посчитал CRC.

Действительно, исправляющая сила возрасла в 2 раза на пакетной ошибке.

Перемежение - простое транспонирование.

 

Какие есть более эффективные перемежения?   Исправляющая способность сильно зависит от характера ошибок: на случайных одиночных ошибках исправляющая эффективность данной конструкции падает до 40%   (40%  от половины числа исправляющих символов одного RS-блока)