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

[Shadow]

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

[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)

Фух. Вот и вспомнил