2014 dxdy logo

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

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




 
 Коды с автоматической коррекцией ошибок
Сообщение09.08.2011, 17:45 
Подскажите, пожалуйста, в какую сторону покопать для решения такой задачи.
Нужно придумать кодировку N десятичных чисел такую, чтобы если при ошибке ввода допущено не более n опечаток и m вставок/удалений, то была возможна автоматическая коррекция. Допустим, нужно закодировать 3 числа, код должен обнаружить и исправить 1 опечатку и 1 вставку/удаление. Тогда возможные варианты кодов будут, например.
Код 1. 0, 111, 122.
Код 2. 11, 22, 33.

 
 
 
 Re: Коды с автоматической коррекцией ошибок
Сообщение09.08.2011, 18:11 
Коды, в которых можно исправить одну ошибку и обнаружить наличие двух ошибок называются кодами Хэмминга с расстоянием 3 - можете погуглить или в литературе найти. Коды Хэмминга могут быть обобщены и на большее расстояние - в результате получается упаковка шаров радиуса $d$ в $\mathbb{Z}_2^n$. Это Вам немного подходит, только у Вас вместо $\mathbb{Z}_2$ все $\mathbb{Z}$ и расстояние произвольное. А вот насчет вставок или удалений - не знаю.

 
 
 
 Re: Коды с автоматической коррекцией ошибок
Сообщение09.08.2011, 20:54 
Sonic86 в сообщении #474519 писал(а):
только у Вас вместо $\mathbb{Z}_2$ все $\mathbb{Z}$ и расстояние произвольное.

Тут проблема:
1) $\mathbb{Z}$ - не поле, так что модуль $\mathbb{Z}^n$ будет не очень хороший,
2) В компьютере невозможно хранить произвольные целые числа.

Так что возникает прежде всего вопрос, насколько большие числа нужно хранить.

 
 
 
 Re: Коды с автоматической коррекцией ошибок
Сообщение10.08.2011, 06:54 
Kallikanzarid в сообщении #474546 писал(а):
1) $\mathbb{Z}$ - не поле, так что модуль $\mathbb{Z}^n$ будет не очень хороший,

А мне не нужно было поле. Мне нужно было множество, кодирующее алфавит счетной мощности.
Kallikanzarid в сообщении #474546 писал(а):
2) В компьютере невозможно хранить произвольные целые числа.

Ну может у ТС конечный алфавит произвольной мощности :-)

 
 
 
 Re: Коды с автоматической коррекцией ошибок
Сообщение10.08.2011, 08:27 
Sonic86 в сообщении #474614 писал(а):
Мне нужно было множество, кодирующее алфавит счетной мощности.

Шары-то паковать там все равно потом придется :wink:

 
 
 
 Re: Коды с автоматической коррекцией ошибок
Сообщение10.08.2011, 08:41 
Kallikanzarid в сообщении #474624 писал(а):
Sonic86 в сообщении #474614 писал(а):
Мне нужно было множество, кодирующее алфавит счетной мощности.

Шары-то паковать там все равно потом придется :wink:

Наверное я зря взял $\mathbb{Z}$ - там и шаров будет бесконечно много. Надо было взять $\mathbb{Z}_n$. Только я все равно не понял, зачем нам именно поле. Мы же просто расстояние считаем. Для этого вполне достаточно аддитивной полугруппы :roll:

 
 
 
 Re: Коды с автоматической коррекцией ошибок
Сообщение10.08.2011, 09:10 
Sonic86 в сообщении #474627 писал(а):
Только я все равно не понял, зачем нам именно поле.

Незачем :)

 
 
 
 Re: Коды с автоматической коррекцией ошибок
Сообщение10.08.2011, 09:40 
Аватара пользователя
Сходу нашлось:

А. С. Долгополов, “Недвоичные коды, исправляющие вставки, выпадения и замены символов”, Пробл. передачи информ., 21:1 (1985), 35–39

ссылка (доступен полный текст)

-- Ср авг 10, 2011 10:42:16 --

посмотрите также с этой страницы ссылки на другие статьи, может быть там что-то найдется

ключевые слова - insertion deletion correction codes

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group