Код Хемминга , обнаружение 2й ошибки

САБЖ.
Как находить и исправлять 1у ошибку понял, а вот как находить 2ю не понял. Инфы вроде хватает, но чтобы было написано, что так и так - ничего. Может кто знает?

Если мне мой склероз не изменяет, то оно либо находит и исправляет одну ошибку, либо сигнализирует о наличии двух, но не исправляет их.

Black Star, код Хемминга действительно исправляет одинарную ошибку при минимальном кодовом расстоянии d=3 и находит (не исправляя) двойную ошибку при d=4. Я приаттачил доку с примерами, если что-то не понятно - переведу.
Прикреплённый файл____________.doc (48.5 Кбайт, скачиваний: 4744)

n0rd, нашел такую фразу:

Цитата

Коды Хемминга имеют бóльшую относительную избыточность, чем коды с проверкой на четность, и предназначены либо для исправления одиночных ошибок (при d = 3), либо для исправления одиночных и обнаружения без исправления двойных ошибок (d = 4).

Вот в ней и запутался. 1 ошибку находить знаю как.
Но я так понял что можно 1у исправить, но и заметить 2ю. На крайняк можно добавить 1 бит четности...

Swindler, что-то знакомое... Буду разбирать...

Добавлено 24.04.06, 11:43
Попутно хочу еще спросить про d - минимальное кодовое расстояние. Что-то не совсем понимаю его смысл и назначение. Расстояние между двумя любыми кодовыми комбинациями в заданном коде. И как это понять?

насколько я помню это количество несовпавших символов из алфавита кодового слова.
наприсер
110
011
кодовое расстояние -2 (1-й и 3-й символ не совпадают)

110
010
кодовое расстояние - 1

Добавлено 24.04.06, 12:47
ну а

Цитата Black Star @ 24.04.06, 11:30

Расстояние между двумя любыми кодовыми комбинациями в заданном коде.

значит что ты гарантируешь, что расстояние между любыми кодовыми словами, расчитанное по вышеописанному алгоритму будет такойто(3 или 4 в твоем случае)...

Расстояние (хеминговое) - число несовпадающих одноименных позиций в комбинациях:
между 11100011 и 10101010 расстояние =3.
минимальное кодовое расстояние - это минимальное расстояние между двумя любимыми комбинациями в коде.

Мммм...
Есть, например (как у меня), 10 битное число. Пусть А. В коде Хемминига будет оно будет как Б (уже 14 бит).
А: 0010000001
Б: 00100010001111
И как понять, что d=3 ?

Цитата Swindler @ 25.04.06, 17:59

Расстояние (хеминговое) - число несовпадающих одноименных позиций в комбинациях

И какие позиции одноименные?

Black Star,
сравниваються между собой числа, которые УЖЕ представлены в коде Хеминга.
Например:
10101010101010
10100100101010
d=3.

Не понял
Что значит

Цитата Swindler @ 27.04.06, 14:42

сравниваются между собой числа, которые УЖЕ представлены в коде Хемминга.

Если есть число, то оно будет одно. С чем его сравнивать?
10101010101010
10100100101010
Видно, что 3 несовпадения. Только что 1е число, и что 2е ?

Black Star, в посте номер 7 есть пример:
А: 0010000001
Б: 00100010001111
И стоит вопрос, какие позиции сравнивать.

Пишу по порядку, как работают с кодом Хемминга:
0) Постановка задачи - определить наличие ошибок в записи какого-то числа (последовательности бит).
1) Информация представляеться в коде Хемминга, для этого в записи числа добавляються новые позиции, информация в которых записываеться по спец. правилу (если надо, то я напишу как выбирать эти позиции и как записывать туда информацию). При этом колличество контрольных разрядов зависит от того, какая цель преследуеться: если найти одинарную ошибку и исправить её, то достаточно d=3, если необходимо определить наличие двойной ошибки то d=4.
2) Далее. Постановка задачи такая: есть число (последовательность бит). Необходимо определить, есть ли в ней одинарная ошибка и исправить её(при d=3), или найти двойную ошибку (при d=4).
3) Суть процесса сравнения: для каждой проверки (проверка контролирует определенные разряды) определяеться парность/непарность разрядов, и в регистр ошибок записываеться
0 и 1 соответственно. В результате проведения всех проверок, в регистре окажеться номер позиции, в которой есть ошибка.
А так чтоб совсем на пальцах: если расстояние d=3, то при наличии 1 ошибки видно, к какому числу необходимо исправить (так как от одного числа число с ошибкой отличаеться на 1 бит, а от другого - на 2). Соответственно исправляеться на то число, к которому "ближе":)

З.Ы. Если так непонятно, пиши формулировку задачи - будем разбираться по шагам.

Пишу...
Есть число. Найти 1у ошибку и исправить, если 2, то сообщить об ошибке.
Как 1у находить я ЗНАЮ ! Как 2 найти?

Для нахождения двойной ошибки добавляеться еще 1 контрольный разряд (кроме тех, что стоят на позициях 2^(i-1))- на позиции 0, котоый означает четность всего кодового числа. Получили d=4
Итого:
0) Если групповые проверки и общая проверка на четность в результате дают 0, то информация передана без ошибок
1) Если групповые проверки дают не нулевой результат, то берут во внимание результат проверки на четность по всему слову.
а) Нечетность этой проверки указывает на наличие одинарной ошибки, которая может быть исправлена.
б)четность - про наличие неисправимой двойной ошибки

Пример нужен?

Все. В итоге пришли к тому, что я и так понял давно
Меня в смущение вводило это d=4. Всеравно не понял его назначение и способ определения (когда 3, когда 4 )
Но остальное не суть важно. Главное, что курсач будет сделан

Swindler, сп. за упорное объяснение