2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Помехоустойчивое кодирование
Сообщение26.04.2006, 11:42 


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

 Профиль  
                  
 
 
Сообщение26.04.2006, 19:13 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение26.04.2006, 19:38 


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

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

 Профиль  
                  
 
 
Сообщение26.04.2006, 20:47 


25/01/06
102
Цитата:
Прочитал про коды Хемминга, но они как я понял исправляют только одну ошибку.


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

 Профиль  
                  
 
 
Сообщение26.04.2006, 20:59 
Заслуженный участник


15/05/05
3445
USA
Несколько ссылок:

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

 Профиль  
                  
 
 
Сообщение27.04.2006, 08:41 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
pEtr0 писал(а):
Прочитал про циклические коды (CRC,БЧХ) но там везде используется деление а у меня его аппаратного нету

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

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

 Профиль  
                  
 
 
Сообщение28.11.2006, 01:27 


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

 Профиль  
                  
 
 
Сообщение28.11.2006, 02:11 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group