коррекция кода Хэмминга, Дисмат Опции

[Shadow]

привет!!!
вот
поступил на канал связи код
011010111
какой символ искажен
----------
у меня получается 9

[Shadow]

нет Я ошибся во втором 2
блин как он это придумал

[BlackShadow]

А по-подробнее о самом методе можно?

[Shadow]

ок подготовлю материал выложу тут
-------
а почитать моно тут
http://aforge.ibd.lv/?5

Сообщение отредактировано: Shadow - 9.08.2004 16:57

[FreeMan]

Короче из прочитанного выходит:
011010111
ненулевые биты: 1,2,3,5,7,8
8 1000
7 0111
5 0101
3 0011
2 0010
1 0001
суммируем. получаем 1010?? наверное ошибки в 8-ом и 2-м битах...

[trminator]

Черт, я забыл метод ( а вспоминать лень. Но мы это проходили ) и даже программу писАли ) и программа даже осталась, она выдает, что ошибка во 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]

Классная прога. Надо её разобрать... Сложновато, правда написана. Я начал писать подобную прогу, но делал всё намного сложнее. Инвертировал все биты поочерёдно, пока не получал нулевую контрольную сумму.

[Shadow]

что бы проверить код Хэмминга
т.е.
011010111
нужно пронумеровать биты
т.е.

123456789
011010111

и те в которых единица проделать последоав XOR с поряд номером
т.е.
2XOR3XOR5XOR7XOR8XOR9
ответ 2 второй бит нужно нвентировать ВСЕ
-----------------------------

FreeMan
только 2
-----------------------------

trminator
насчет колва корректир кодов жык формулка есть
взависимости от кол-лва длины кодового слова
и тот алгол кодирован на сайте данный и алгол провер корр
мне больше ндравиться чем у Яблонского будь он не ладен

Сообщение отредактировано: Shadow - 9.08.2004 23:27

[trminator]

Классная прога. Надо её разобрать... Сложновато, правда написана

Лучше не делай этого. AFAIR написана то ли на перерыве, то ли на забитом матане. Так-то работает, но неоптимально - 100%

Вот Shadow дело сказал. Когда потребовалось делать прогу, чтобы файлы кодировала-проверяла, что-то такое и сделал. А тут - тупо.

[BlackShadow]

Shadow, странно ты как-то биты пронумеровал... Непривычно как-то... Обычно справа налево...

[Shadow]

BlackShadow
это не Япронумеровал это тот лектор который мне материалы составлял
будь он не ладен Я из-за этого двое суток не спал потомучто привык к ASM
и все справа на лево нумеровал 10 получалось

trminator
прогу можно сделать только придеться по буквам т.е. по байтно проверять
т.к. 1 буква 1 байт проверить ведь всего 1 бит можно, но эффективность кода
под сомнением...
напрмер в В.И. Юров практиум Глава 9 есть целый раздел CRC

Сообщение отредактировано: Shadow - 10.08.2004 16:27

[FreeMan]

Действительно 2.