Автор: Shadow 9.08.2004 12:47
привет!!!
вот
поступил на канал связи код
011010111
какой символ искажен
----------
у меня получается 9
Автор: Shadow 9.08.2004 14:06
нет Я ошибся во втором 2
блин как он это придумал
Автор: BlackShadow 9.08.2004 14:56
А по-подробнее о самом методе можно?
Автор: Shadow 9.08.2004 16:55
ок подготовлю материал выложу тут
-------
а почитать моно тут
http://aforge.ibd.lv/?5
Автор: FreeMan 9.08.2004 17:34
Короче из прочитанного выходит:
011010111
ненулевые биты: 1,2,3,5,7,8
8 1000
7 0111
5 0101
3 0011
2 0010
1 0001
суммируем. получаем 1010?? наверное ошибки в 8-ом и 2-м битах...
Автор: trminator 9.08.2004 20:13
Черт, я забыл метод ( а вспоминать лень. Но мы это проходили ) и даже программу писАли ) и программа даже осталась, она выдает, что ошибка во 2-м бите. Исправляем ошибку (получаем 001010111), программа выдает, что нет ошибки.
А метод, AFAIK, позволяет только одиночные ошибки вылавливать...
Код
program hamming;
const n = 5;
logn = 4;
var a : array[1..logn, 1..n + logn] of byte;
s0 : array[1..logn] of byte;
b : array[1..n + logn] of byte;
i, j, k : integer;
src : array[1..n] of byte;
s : string;
begin
(************************************************)
(* Ч А С Т Ь 1 : К О Д И Р О В А Н И Е *)
(************************************************)
{ Ввод посл-ти }
readLn(s);
for i := 1 to n do src[i] := byte(s[i]) - byte('0');
{ Заполнение матр. a }
fillchar(a, sizeof(a), 0);
for i := 1 to n + logn do
begin
k := i;
for j := 1 to logn do
begin
a[j, i] := k mod 2;
k := k shr 1
end;
end;
{ Заполнение матр. b }
k := 0; j := 1;
for i := 1 to n + logn do
begin
if i shr k = 1 then begin
inc(k);
b[i] := 0
end
else begin b[i] := src[j]; inc(j) end;
end;
{ Подсчет контр. сумм }
for i := 1 to logn do
begin
k := 0;
for j := 1 to n + logn do
k := (k + a[i, j] * b[j]) mod 2;
s0[i] := k
end;
{ Запихивание их в результат вместо нулей }
k := 1;
for i := 0 to logn - 1 do
begin
k := 1 shl i;
b[k] := s0[i+1];
end;
{ Вывод результатов }
writeLn('_____________________________________________');
for i := 1 to logn do begin
write('a',i,'| ');
for j := 1 to n + logn do write(a[i,j] :2, '|');
write(' ||',s0[i]:2); writeLn;
end;
writeLn('_____________________________________________');
write('b | '); for i := 1 to n + logn do write(b[i]:2, '|'); writeLn;
(************************************************)
(* Ч А С Т Ь 2 : П О И С К О Ш И Б К И *)
(************************************************)
{ Ввод ошибочной посл-ти }
readLn(s);
for i := 1 to n + logn do
b[i] := byte(s[i]) - byte('0');
{ Поиск глюка в ошибочной посл-ти }
for i := 1 to logn do
begin
k := 0;
for j := 1 to n + logn do
k := (k + a[i, j] * b[j]) mod 2;
s0[i] := k
end;
{ Вывод }
k := 0;
for i := logn downto 1 do k := k shl 1 + s0[i];
if k <> 0 then writeLn('Ошибка в ', k, ' позиции')
else writeLn('Нет ошибки');
writeLn;
end.
Первая и вторая часть между собой не связаны, во второй части только используются матрица
A, которая имеет вид
1 0 1 0 1
0 1 1 0 0
0 0 0 1 1
0 0 0 0 0 .......
В переданном массиве (
b) на 1, 2, 4, 8 позициях - резервные биты, "подобранные" так, чтобы
A*b по модулю 2 == 0. Но если где-то есть ошибка, то
A*b (mod 2) дает ее позицию
Этот пример:
Код
1 0 1 0 1 0 1 0 1 |
0 1 1 0 0 1 1 0 0 |
0 0 0 1 1 1 1 0 0 |
0 0 0 0 0 0 0 1 1 |
------------------
0 1 1 0 1 0 1 1 1
В правой части будет накапливаться результат (в двоичном виде), внизу - полученное сообщение
Умножаем ПЕРВУЮ строку на сообщение (по модулю 2), то есть
k := 0;
for j := 1 to n+logn do k := (k + a[i, j] * b[j]) mod 2;
иными словами, сравниваем биты 1-й строки и сообщения, как только и там, и там единицы, увеличиваем двоичный счетчик. В первой строке 4 совпадения, по модулю 2 получаем 0. Во второй строке - 3 совпадения, или единица (mod 2)
Таким же макаром, пробежав по всем четырем строкам, получаем номер ошибки:
... | 0
... | 1
... | 0
... | 0
-- двоичное представление числа
2Кстати. В исходном сообщении было 5 бит, да 4 бита резервных. Почему четыре резервных? Получили сообщение длиной 9 бит, а 4-битным числом можем указать номер ошибочной позиции. Трех бит явно не хватает.
(x + log2(x) >= 9, x -> min, x in Z => x == 5)
Фух. Вот и вспомнил
Автор: FreeMan 9.08.2004 20:28
Классная прога. Надо её разобрать... Сложновато, правда написана. Я начал писать подобную прогу, но делал всё намного сложнее. Инвертировал все биты поочерёдно, пока не получал нулевую контрольную сумму.
Автор: Shadow 9.08.2004 23:21
что бы проверить код Хэмминга
т.е.
011010111
нужно пронумеровать биты
т.е.
123456789
011010111
и те в которых единица проделать последоав XOR с поряд номером
т.е.
2XOR3XOR5XOR7XOR8XOR9
ответ 2 второй бит нужно нвентировать ВСЕ
-----------------------------
FreeMan
только 2
-----------------------------
trminator
насчет колва корректир кодов жык формулка есть
взависимости от кол-лва длины кодового слова
и тот алгол кодирован на сайте данный и алгол провер корр
мне больше ндравиться чем у Яблонского будь он не ладен
Автор: trminator 10.08.2004 13:58
Цитата
Классная прога. Надо её разобрать... Сложновато, правда написана
Лучше не делай этого. AFAIR написана то ли на перерыве, то ли на забитом матане. Так-то работает, но неоптимально - 100%
Вот
Shadow дело сказал. Когда потребовалось делать прогу, чтобы файлы кодировала-проверяла, что-то такое и сделал. А тут - тупо.
Автор: BlackShadow 10.08.2004 15:35
Shadow, странно ты как-то биты пронумеровал... Непривычно как-то... Обычно справа налево...