Привет!
Подскажите, пожалуйста, какой код коррекции ошибок оптимально использовать? Требования и ограничения таковы: количество информационных блоков n = степень двойки. В практическом плане интересны решения для n = 32 или 64. Количество контрольных блоков = n. То есть, rate кода = 1/2. Количество корректируемых ПОТЕРЬ = n (это важно!) или хотя бы n-1...n-2 (при n = 32). Таким образом, коды со слабой корректирующей способностью не подходят!
Какой код может устранить "n" потерь при "n" входных блоках и "n" контрольных? Позиции потерь известны заранее, а устранение ошибок, позиции которых неизвестны — не требуется (то есть, нужна коррекция именно потерь блоков, а не искажений).
Из известных мне кодов коррекции ошибок такими характеристиками обладают только вариации на тему кодов Рида-Соломона. Но RS-коды считаются очень медленными в software реализации.
Поэтому есть второй вопрос: какова ОЦЕНКА сложности для декодера RS-кодов в ситуации, когда есть только потери и их позиции известны декодеру?
Например, сколько времени нужно самому совершенному существующему декодеру для восстановления в случае потери всех исходных символов? Предположим, что у меня осталось только "n" контрольных блоков, все исходные потеряны. Сколько времени сожрет лучший из практически реализованных декодеров RS-кодов — O(n^2) или есть лучшие схемы? Если есть лучшие решения, то какой именно алгоритм следует использовать, и где он описан...
Заранее СПАСИБО за любую содержательную информацию по теме!

Здравствуйте, sysprg, Вы писали:

S>Привет!
S>Подскажите, пожалуйста, какой код коррекции ошибок оптимально использовать? Требования и ограничения таковы: количество информационных блоков n = степень двойки. В практическом плане интересны решения для n = 32 или 64. Количество контрольных блоков = n. То есть, rate кода = 1/2. Количество корректируемых ПОТЕРЬ = n (это важно!) или хотя бы n-1...n-2 (при n = 32). Таким образом, коды со слабой корректирующей способностью не подходят!

S>Какой код может устранить "n" потерь при "n" входных блоках и "n" контрольных? Позиции потерь известны заранее, а устранение ошибок, позиции которых неизвестны — не требуется
Никакой. Максимальное количество стираний (ошибок, позиции которых известны), исправляемых блочным кодом <= n-1, где n — количество контрольных разрядов. Равенство достигается только при использовании т.н. оптимального кода, а оптимального кода, у которого n==k, сдается мне, не существует.
При скорости кода 1/2 имеет смысл посмотреть сверточные коды, но если ошибки равновероятны в каждом блоке и независимы, выигрыша от них не будет.

S>Из известных мне кодов коррекции ошибок такими характеристиками обладают только вариации на тему кодов Рида-Соломона. Но RS-коды считаются очень медленными в software реализации.
Ну не знаю.. А какие тогда быстрыми? Коды РC являются оптимальными, но половину блока все равно исправить не смогут, а плюс к тому Вы не построите код, у которого число контрольных разрядов равно числу информационных. В плане вычислительной сложности вроде бы ничего особенного. На какой платформе это будет происходить и о каких скоростях идет речь? Если длина слова не больше 8 бит, умножение можно табличным сделать, тогда вообще быстро.

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

Из потоковых сейчас в моде сверточные коды с декодированием по максимуму правдоподобия, с использованием информации демодулятора о вероятности ошибки в каждом символе. Они действительно требуют приличной вычислительной мощности. Из блочных — РС самые популярные.
Блочные коды имеет смысл использовать, только если канал ориентирован на блочную передачу (решен вопрос блочной синхронизации), ошибки в блоках распределены более-менее равномерно и независимо.
В реальных системах, где требуется исправление большого количества ошибок (например, GSM) используют 2 и более кодов, исправляющих разные роды ошибок.

Хотя я и не специалист по корректирующим кодам, но мне кажется, что вы предъявляете чересчур завышенные требования. Хорошими блоковыми кодами считаются БЧХ-коды, которые как минимум не хуже по корректирующей способности, чем код Рида-Соломона. Для их декодирования существуют быстрые алгоритмы, например, алгоритм Берлекэмпа-Месси.

Прочтите лучше книгу Р. Блейхут "Теория и практика кодов, контролирующих ошибки". Там все подробно описано касательно блочных кодов. Но для понимания она, пожалуй, сложновата.

Здравствуйте, sz36, Вы писали:

s>>Какой код может устранить "n" потерь при "n" входных блоках и "n" контрольных? Позиции потерь известны заранее, а устранение ошибок, позиции которых неизвестны — не требуется

sz>Никакой. Максимальное количество стираний (ошибок, позиции которых известны), исправляемых блочным кодом <= n-1, где n — количество контрольных разрядов.Равенство достигается только при использовании т.н. оптимального кода, а оптимального кода, у которого n==k, сдается мне, не существует.

А разве обычный код Рида-Соломона не может исправить в точности "n" стираний, если n — это количество контрольных разрядов? Другое дело, что если я правильно понимаю теорию, то в обычном коде Рида-Соломона предельное количество контрольных сумм и данных = 2^q — 1. Опять-таки, насколько я понимаю теорию, с помощью расширенного кода Рида-Соломона можно поднять количество данных на 1 или на 2 (то есть, можно сделать код с k = 2^q данными), но количество контрольных разрядов по-прежнему останется равным 2^q — 1 даже у расширенного кода. И поэтому в таком режиме (кода количество данных k = 2^q) код будет корректировать на одно стирание меньше.

Правильно ли я понимаю, что кода Рида-Соломона с параметрами (2^q, 2^(q — 1)) в стандартной нотации "(длина сообщения, количество информационных символов в нем)" не существует в природе? А известен ли хоть один другой код с такими характеристиками для q > 3?

sz> Ну не знаю.. А какие тогда быстрыми? Коды РC являются оптимальными, но половину блока все равно исправить не смогут, а плюс к тому Вы не построите код, у которого число контрольных разрядов равно числу информационных.

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

s> А вообще эффективный код, исправляющий ошибки, подбирают по статистике ошибок канала. Грубо говоря код должен быть ориентирован на исправление именно тех ошибок, которые возникают с наибольшей вероятностью. Наука эта довольно сложная, но литературы хватает. Из того, что помню, например здесь

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

Здравствуйте, jhng, Вы писали:

J>Хотя я и не специалист по корректирующим кодам, но мне кажется, что вы предъявляете чересчур завышенные требования. Хорошими блоковыми кодами считаются БЧХ-коды, которые как минимум не хуже по корректирующей способности, чем код Рида-Соломона. Для их декодирования существуют быстрые алгоритмы, например, алгоритм Берлекэмпа-Месси.

РС-коды это как раз и есть недвоичные БЧХ-коды и для их декодирования используется в частности алгоритм Берлекемпа-Месси. При этом РС-коды обладают лучшими характеристиками по коррекции ошибок по сравнению с "обычными" бинарными БЧХ-кодами (именно за счет использования недвоичных символов).

Здравствуйте, sysprg, Вы писали:


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

Если у вас такие плохие носители, то стоит ли на них делать систему хранения . Если скорость кода 1/2, то проще продублировать данные. Затраты ресурсов носителей теже (хотя пожалуй надо ввести признак достоверности "немного снизив скорость"), а выйгрыш в скорости доступа к данным будет гораздо выше.
Каждый инструмент хорош в своей области.

Здравствуйте, tartilla, Вы писали:

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

T>Если скорость кода 1/2, то проще продублировать данные. Затраты ресурсов носителей теже (хотя пожалуй надо ввести признак достоверности "немного снизив скорость"), а выйгрыш в скорости доступа к данным будет гораздо выше.

Дублирование данных дает rate = 1/2, но не защищает даже от двойной ошибки и поэтому вообще не интересно. Если каждый блок просто продублирован на другом носителе, то для того, чтобы разрушить целостность данных достаточно убить всего ДВА произвольных блока! Если же, скажем, применен код Рида-Соломона RS(64,32) (полученный из RS(255, k) over GF(2^8)), то для разрушения данных придется убить 33 блока. Согласитесь, это намного лучше, чем разрушение данных при убитии всего двух блоков/носителей.

T>Каждый инструмент хорош в своей области.

В том-то и дело.

Здравствуйте, sysprg, Вы писали:

S>Дублирование данных дает rate = 1/2, но не защищает даже от двойной ошибки и поэтому вообще не интересно. Если каждый блок просто продублирован на другом носителе, то для того, чтобы разрушить целостность данных достаточно убить всего ДВА произвольных блока! Если же, скажем, применен код Рида-Соломона RS(64,32) (полученный из RS(255, k) over GF(2^8)), то для разрушения данных придется убить 33 блока. Согласитесь, это намного лучше, чем разрушение данных при убитии всего двух блоков/носителей.

Основные преимущеста RS достигаются за счет применения перемежителя. Именно благодаря ему RS по общему мнению борется с блочными ошибками лучше остальных. Вероятность появления ошибки размазывается по времени и соответственно вероятность ошибки канала в конкретный момент времени снижается до приемлемой(если физические характеристики канала позволяют конечно), когда ПУ код способен эффективно работать. Особеность в том, что нужны вероятностные характеристики канала и именно они в конечном итоге влияют на выбор реализации ПУ кода. Для канала связи пользуют мягкие решения демодулятора и с их использованием повышат вероятностные характеристики, но в вашем случае(система хранения) аналогом будут именно жесткие решения. Природу не обманешь, одним проверочным битом больше одной ошибки не исправишь в идеальном теоритическом случае (при условии что проверочный бит не поврежден, на что тоже следует затратить ресурс избыточности).
Если вы считаете высокой степенью верояности разрушения одних и тех же данных на параллельных носителеях, то вероятность некритичного разрушения данных в информационной части и в проверочной области одного кодированного пакета ведущего к потере пакета, будут по крайней мере соизмеримы.
Ну а если вы настроены повышать скорость, то надо определится с вероятностю появления ошибки и характером распределения. И вероятней всего склонится к RS (как при записи на CD ). А повышение скорости алгоритма декодирования возможно будет только при рассмотрении конкретной реализации кода, характера данных, их распределением в памяти и тучей других параметров характерных именно для вашей системы. Только вот окупятся ли затраты на оптимизацию алгоритма с выйгрышем, который он даст .
Если данные настолько важны может лучше из продублировать в трех независимых местах? В целом выйдет дешевле чем потеря данных ?

Здравствуйте, tartilla, Вы писали:

T> Основные преимущеста RS достигаются за счет применения перемежителя. Именно благодаря ему RS по общему мнению борется с блочными ошибками лучше остальных.

Код Рида-Соломона по своей природе борется с блочными ошибками лучше многих других кодов, так как это MDS-код. Чередование (типа CIRC на CD) в сочетании со свойствами самого кода еще сильнее снижает вероятность потери данных. Но одного только чередования было бы недостаточно.

T> Ну а если вы настроены повышать скорость, то надо определится с вероятностю появления ошибки и характером распределения. И вероятней всего склонится к RS (как при записи на CD .

Поэтому я про него и спрашиваю. Меня интересуют теоретические границы применимости RS кодов. А так же самые совершенные по быстродействию варианты кода. Пока что я склонен считать такими RS-подобные коды на основе матриц Коши.

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

Окупятся, так как "прямая" реализация кода Рида-Соломона вообще слабо применима для скоростной обработки информации в современном мире, а вот более поздние варианты алгоритмов кодирования и декодирования (и даже самого кода) уже приемлемы по скорости работы, но их много разных и нужно определиться, какие именно наиболее перспективны.

T>Если данные настолько важны может лучше из продублировать в трех независимых местах? В целом выйдет дешевле чем потеря данных?

Нет, дублирование даже в трех местах позволяет защититься только от двойной, но не от тройной ошибки. В моем случае нужна защита от 16-кратной ошибки — как минимум, за которым характеристики системы по надежности уже не устраивают. Поэтому я сразу задал вопрос о кодах 32 и 64 контрольными блоками и блоками данных. Причем желательно, чтобы все параметры кода были степенями двойки — это почти всегда удобно и в программировании, и в дизайне системы в целом.

Здравствуйте, sysprg, Вы писали:

S>Здравствуйте, jhng, Вы писали:

J>>Хотя я и не специалист по корректирующим кодам, но мне кажется, что вы предъявляете чересчур завышенные требования. Хорошими блоковыми кодами считаются БЧХ-коды, которые как минимум не хуже по корректирующей способности, чем код Рида-Соломона. Для их декодирования существуют быстрые алгоритмы, например, алгоритм Берлекэмпа-Месси.

S>РС-коды это как раз и есть недвоичные БЧХ-коды и для их декодирования используется в частности алгоритм Берлекемпа-Месси. При этом РС-коды обладают лучшими характеристиками по коррекции ошибок по сравнению с "обычными" бинарными БЧХ-кодами (именно за счет использования недвоичных символов).

Спасибо, понятно.

А если вопрос по ускорению алгоритма все еще не решен, могу предложить декодировать RS-код в частотной области. Правда, чтобы получить реальный выйгрыш в скорости, необходимо иметь код достаточно большой длины.

Здравствуйте, sysprg, Вы писали:


S>Нет, дублирование даже в трех местах позволяет защититься только от двойной, но не от тройной ошибки. В моем случае нужна защита от 16-кратной ошибки — как минимум, за которым характеристики системы по надежности уже не устраивают.

Под двойной ошибкой вы понимаете две ошибки на одном носителе, или по одной ошибке на двух разных носителях?
Выход из строя одного носителя это сколькомерная ошибка ?
А что вы думаете по поводу Турбокодов?

Здравствуйте, jhng, Вы писали:

J>А если вопрос по ускорению алгоритма все еще не решен, могу предложить декодировать RS-код в частотной области. Правда, чтобы получить реальный выйгрыш в скорости, необходимо иметь код достаточно большой длины.

Да, я смотрел статьи на эту тему. Но увы, пока что все найденные статьи про использование БПФ для кодов коррекции ошибок носят чисто академический характер. В них очень много высшей математики и нет конкретики, из-за чего моего образования недостаточно, чтобы по таким теоретическим математическим статьям (с оборотами вроде "очевидно, что существует матрица, такая, что <формула размером с лист>") написать конкретную работающую программу.

Здравствуйте, sysprg, Вы писали:

S>Здравствуйте, jhng, Вы писали:

J>>А если вопрос по ускорению алгоритма все еще не решен, могу предложить декодировать RS-код в частотной области. Правда, чтобы получить реальный выйгрыш в скорости, необходимо иметь код достаточно большой длины.

S>Да, я смотрел статьи на эту тему. Но увы, пока что все найденные статьи про использование БПФ для кодов коррекции ошибок носят чисто академический характер. В них очень много высшей математики и нет конкретики, из-за чего моего образования недостаточно, чтобы по таким теоретическим математическим статьям (с оборотами вроде "очевидно, что существует матрица, такая, что <формула размером с лист>") написать конкретную работающую программу.

Ну так самое главное — это реализовать БПФ в конечном поле. Да и соответсвующий код наверняка уже где-то есть. Все остальное — дело техники Не спорю, придется поднапрячь мозг. Но у меня же получается реализовывать алгоритмы по информации из статей, значит и у тебя получится. В конце концов можешь обратиться к авторам этих самых статей. Они ведь как-то проверяли то что написали.

Здравствуйте, tartilla, Вы писали:

T>Под двойной ошибкой вы понимаете две ошибки на одном носителе, или по одной ошибке на двух разных носителях?

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

T>А что вы думаете по поводу Турбокодов?

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

Здравствуйте, sysprg, Вы писали:

S>Я исхожу из худшего предположения — ошибка это выход из строя всего накопителя.

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

S>Недостаточная корректирующая способность, ориентированы на другие приложения.
Ну ПУ-коды в целом ориентированы на одно основное приложение.
А что вам мешает перемножать RS коды . До такой ркализации помоему еще никто не додумался, может есть какое-то теоритическое объяснение почему нельзя . А так каждый код выйдет попроще , а можно взять три кода. Перемежитель на уровне алгоритма, даже выдумывать куда его вставить не надо. Честно говоря не считал что будет если брать два кода таким образом что бы при перемножении их эффективность равнялась заданному (одному) коду и есть ли выйгрышь в вычислительном ресурсе, но по памяти выйгрышь должен быть да и при вычислениях вероятней есть.
А при хорошем качестве в целях оптимизации можно считать только один код (для оценки правильности) и не уходить в поиски достоверностей. Или если все делать правильно, то все равно, чем лучше сигнал, тем меньше итераций

Здравствуйте, sysprg, Вы писали:


S>Какой код может устранить "n" потерь при "n" входных блоках и "n" контрольных? Позиции потерь известны заранее, а устранение ошибок, позиции которых неизвестны — не требуется (то есть, нужна коррекция именно потерь блоков, а не искажений).
Обычный код Рида-Соломона. Устраняет N ошибок при добавлении N корректирующих слов при указании позиций всех N ошибок. Проверено — работает В отдельных случаях, для мягких метрик он может и больше чем N ошибок восстановить (но это как повезет и рассчитывать на это нельзя).
S>Из известных мне кодов коррекции ошибок такими характеристиками обладают только вариации на тему кодов Рида-Соломона. Но RS-коды считаются очень медленными в software реализации.
Это как посмотреть. Конечно, они сложнее кодов Хэмминга, но не так уж страшны.
Кодер и декодер замечательно "табличатся", а при маленьких N и K так вообще укладываются в несколько операций по таблицам. У меня хилые микроконтроллеры (там было всего 256 байт памяти) выполняли кодирование и декодирование кодов RS!
S>Поэтому есть второй вопрос: какова ОЦЕНКА сложности для декодера RS-кодов в ситуации, когда есть только потери и их позиции известны декодеру?
Оценка какая? Алгоритмическая что-ли? Или сколько потрнбуется памяти? или времени на реализацию?