Помехоустойчивое кодирование

[pEtr0]

Всем добрый день!
Вот, возникла проблемма написания кодера/декодера с исправлением ошибок. Порылся в инете - алгоритмов полно, сложных и не очень а какие именно использовать (или какие обычно используют) непонятно...
Если у кого есть опыт использования или создания таких алгоритмов поделитесь пожалуйста.

[незваный гость]

Недолго думая -- все-таки выбираемые методы очень зависят от цели. Например, 8-из-14 физическое кодирование данных на CD определяется необходимостью избегать слишком больших последовательностей нулей и единиц. Коды с востановлением ошибок очень популярны в newsgroups. Пример программы -- QuickPAR. Они же используются в RAID и при записи данных (не звука) на CD. В каналах связи (point to point) обычно используют не восстановление, а перепосылку. Там добавляется контрольная сумма того или иного рода. (Раньше были популярны проверки четности на уровне байта, но в последнее время их почти никто не использует -- точнее, я не встречаю.)

[pEtr0]

Спасибо за ответ....
Мне как раз надо разработать код для канала связи, прадва общая шина, поэтому с перепосылкой проблемы. Если конкретно то длина пакета 512-1024 бит, код должен исправлять ошибку в 8-16 битах, очень критичен ресурс ЦПУ.
Прочитал про коды Хемминга, но они как я понял исправляют только одну ошибку.
Прочитал про циклические коды (CRC,БЧХ) но там везде используется деление а у меня его аппаратного нету

Что вы можете посоветовать конкретно для такой ситуации?
Заранее спасибо.

[Igor Borovikov]

Цитата:

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

Это не совсем так, на самом деле любое наперед заданное количество ошибок, их число зависит от избыточности.

[Yuri Gendelman]

Несколько ссылок:

1) The Error Correcting Codes (ECC) Page: http://www.eccpage.com/
- есть ссылки на turbo-codes

2) http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/errorcorrecting.html

3) Здесь http://members.aol.com/mnecctek/faqs.html рекомендуют коды Рида-Соломона

4) Здесь упоминаются коды Рида-Соломона в связи с записью на диск: http://www.storagereview.com/guide2000/ref/hdd/geom/errorECC.html

[незваный гость]

pEtr0 писал(а):

Прочитал про циклические коды (CRC,БЧХ) но там везде используется деление а у меня его аппаратного нету

CRC (по крайней мере, в том виде, который я знаю: CRC-32, CRC-16) ошибок не исправляет -- хотя и позволяет обнаружить факт ошибки. Хотя CRC и определяется через деление, но фактически деления нет -- используется предвычисление таблицы и сдвиг-XOR.

Те задачи, с которыми я сталкивался (в коммуникации), коды с восстановлением было непрактичны. Во-первых, даже если восстановление не нужно, необходимы процессорные затраты при посылке каждого сообщения. Во-вторых, процессорные затраты на восстановление занимали бы больше процессорного времени, чем время до прихода следующего сообщения (то есть, имелись бы более свежие данные). Выход -- поддержка в "железе". Что и происходит, например, с CD или сотовым телефоном. Впрочем, это зависит от частоты посылок, разумеется.

[Helene]

Всем привет! Может кто-нибудь что-нибудь знает про НЕПРИМИТИВНЫЕ КОДЫ БЧХ? Покополась в интернете, ничего не нашла? Мне сказали, что есть какая-то стандартная програмка декодирования. Подскажите, у меня диплом горит.

[незваный гость]

На вскидку — посмотрите Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. — Теория кодов, исправляющих ошибки. Судя по предметному указателю, там есть интересующая Вас информация.