|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 01 Mar 2002 16:54:52
To : Vladimir Mosgalin
Subject : Коррекция ошибок (Хемминг)
--------------------------------------------------------------------------------
Thu Feb 28 2002 11:44, Vladimir Mosgalin wrote to All:
VM> Кто-нибудь может рассказать подробно сабжевый алгоритм (для одной
VM> ошибки), или урл дать, а то у меня краткое описание есть, но я не понимаю
VM> как сами биты контроля считаются.
Пример на пальцах :
Кодируем 4-битовое число 1011 в 7-битовое кодовое слово.
1. Пронумеруем биты кодового слова от 1 до 7. Биты с номерами 1,2 и 4 отложим
- это будут проверочные биты. Распихаем по остальным битам информационные :
1 2 3 4 5 6 7
х х 1 х 0 1 1
2. Вычисляем сумму (по модулю 2 - обычный xor) _номеров_ позиций, в которых
стоят единицы : 3 xor 6 xor 7 = 011 xor 110 xor 111 = 010. Это число даст нам
значения проверочных битов 4,2 и 1. Подставим их в кодовое слово :
1 2 3 4 5 6 7
0 1 1 0 0 1 1
3. Полученное слово передаем в канал связи, записываем в память и т.п.
Декодируем 7-битовое слово.
Вычисляем синдром ошибки. По существу это та же операция, что и в п.2
кодирования : 2 xor 3 xor 6 xor 7 = 000. Получили ноль = ошибки нет.
Предположим, мы получили испорченное слово - бит 3 стал нулевым :
1 2 3 4 5 6 7
0 1 0 0 0 1 1
тогда 2 xor 6 xor 7 = 011 непосредственно даст _номер_ испорченного бита.
Инвертируем его и получаем исходное слово.
Теперь осталось извлечь из слова исходные информационные биты. Все.
Hадеюсь, что помог.
Сергей
...Hаша компания сама выращивает и перерабатывает байты...
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Коррекция ошибок (Хемминг) 
