Коды Хемминга
ботай 1 курс, дискру 
используй гугл.
А так вообще смысл такой: для данного пространства n-битников и m исправляемых ошибок строится пространство n + 2m битников, и отображение из оригинального пространства в новое, при котором расстояние по хеммингу (то есть количество различающихся битов) между образами любых двух соседних по хеммингу элементов (то есть различающихся ровно одним битом) в точности равно 2m. Ну и обратное отображение, которое сопоставляет каждому элементу расширенного пространства тот элемент оригинального, чей образ к нему ближе всего.
Эк я завернул, а?
А так вообще смысл такой: для данного пространства n-битников и m исправляемых ошибок строится пространство n + 2m битников, и отображение из оригинального пространства в новое, при котором расстояние по хеммингу (то есть количество различающихся битов) между образами любых двух соседних по хеммингу элементов (то есть различающихся ровно одним битом) в точности равно 2m. Ну и обратное отображение, которое сопоставляет каждому элементу расширенного пространства тот элемент оригинального, чей образ к нему ближе всего.
Эк я завернул, а?
там везде 2m+1, причём, расстояние не обязано быть в точности равно, а может быть больше
+1 или поботать Танненбаума 
А, да, 2m + 1. Что-то меня попутало.
> расстояние не обязано быть в точности равно, а может быть больше
А разве не всегда можно полностью заполнить пространство хемминговскими сферами заданного произвольного радиуса?
> расстояние не обязано быть в точности равно, а может быть больше
А разве не всегда можно полностью заполнить пространство хемминговскими сферами заданного произвольного радиуса?
> А разве не всегда можно полностью заполнить пространство хемминговскими сферами заданного произвольного радиуса?
заполнить можно, но расстояние между образами некоторых элементов может быть больше, чем 2m+1, в том числе соседних
вообще, насколько я помню определение, требуется только, чтобы расстояние между любыми двумя было не меньше 2m+1
пример кода с n=4, m=1, где расстояние между образами соседей бывает больше, чем 2m+1:
построение:
c[1] = d[1]
c[2] = d[2]
c[3] = d[3]
c[4] = d[4]
c[5] = d[1]+d[2]+d[4]
c[6] = d[1]+d[3]+d[4]
c[7] = d[2]+d[3]+d[4]
восстановление:
предполагаем d[i]=c[i] и пересчитываем c[5]-c[7]
если среди c[5]-c[7] изменился один бит, то всё нормально (ошибка в нём если два или три, то ошибка в c[1]-c[4] и её легко найти
для соседних элементов, различающихся в бите d[4] расстояние между образами будет 4
заполнить можно, но расстояние между образами некоторых элементов может быть больше, чем 2m+1, в том числе соседних
вообще, насколько я помню определение, требуется только, чтобы расстояние между любыми двумя было не меньше 2m+1
пример кода с n=4, m=1, где расстояние между образами соседей бывает больше, чем 2m+1:
построение:
c[1] = d[1]
c[2] = d[2]
c[3] = d[3]
c[4] = d[4]
c[5] = d[1]+d[2]+d[4]
c[6] = d[1]+d[3]+d[4]
c[7] = d[2]+d[3]+d[4]
восстановление:
предполагаем d[i]=c[i] и пересчитываем c[5]-c[7]
если среди c[5]-c[7] изменился один бит, то всё нормально (ошибка в нём если два или три, то ошибка в c[1]-c[4] и её легко найти
для соседних элементов, различающихся в бите d[4] расстояние между образами будет 4
Оставить комментарий
stm7859222
Нужен алгоритм работы кодов Хэмминга.