Кодирование с помощью кода Хэмминга

Код Хемминга – один из первых самокорректирующихся кодов. Он позволяет автоматическое исправление одной ошибки и обнаруживать две. Код Хэмминга используется в некоторых прикладных программах в области хранения данных.

Теоретическая часть

Для этого используются k – контрольных розрядов. И так если у нас задача закодировать m двоичных разрядов, то k должно удовлетворять неравенство 2k ≥ k+m+1 или k ≥ log2(k+m+1)
Таким образом мы можем найти минимальные значения k для заданных m:

Теперь, мы можем построить самокорректирующийся код m+k разрядов. Приступим.
Запишем эти разряды и пронумеруем в двоичной системе.



Будем считать, что разряд принадлежит n-той контрольной группе, если в двоичном представлении эго номера стоит единица в n-том разряде.

Среди m+k разрядов мы будем иметь k разрядов, которые принадлежат только одной группе (степени двойки, так как они в двоичном представлении имеют только одну единицу).

Эти k разрядов мы будем считать контрольными. Остальные m разрядов будут информационными разрядами.



В информационные разряды переписываем наши исходные m разрядов.

В каждый из контрольных разрядов запишем такую цифру (0 или 1), чтоб общее количество единиц в его контрольной группе была парной. Для этого нам надо просто просуммировать по модулю два двоичных представления тех информационных разрядов, в которых стоит единица. Таким образом, мы узнаем контрольные разряды, ну и соответственно все m+k закодированных разрядов.

Пример

Давайте рассмотрим пример.

Например, нам дана последовательность 1001000. В данном случае m = 7, значит k = 4.

Запишем наши m + k разряды.


Узнаем теперь контрольные разряды:


Запишем контрольные разряды.

Таким образом получаем закодированную последовательность 01100010000

Реализация

Реализуем теперь этот алгоритм на языке программирования PHP.
Зададим начальную последовательность

  $input = "1001000"; // задаем последовательость
  $m = strlen($input); // узнаем длину


Для начала узнаем количество контрольных разрядов:

  $k = 2; // задаем самое минимально возможное k
  $l2n = log10(2); //
  while ($k * $l2n < log10($k + $m + 1)) $k++; // вычисляем по формуле минимальное k


Запишем информационные разряды на свои места

  $result = Array(); // заводим массив разрядов
    
  for ($i = 1, $j=0, $n = $k+$m; $i <= $n; $i++) { // проходим по всем разрядам
    if (($i & $i-1) == 0) { // если степень двойки, то есть контрольный разряд, то пропускаем
      $result[$i] = '-';
      continue;
    }
    $result[$i] = $input[$j++]; // в информационные разряды записываем исходные данные
  }


Узнаем контрольную сумму:

$control = 0;
  for ($i = 1, $n = $k+$m; $i <= $k+$m; $i++) { // проходим по всем разрядам
    if ($result[$i] == 1)
      $control ^= $i; // если единица, то суммируем по модулю два
  }
  $control = decbin($control); // преобразовываем в двоичный код
  for ($i=0, $n = strlen($control); $i<$k-$n; $i++) // дописываем спереди нули
    $control = "0".$control;


И записываем контрольную сумму в контрольные разряды:

for ($i = 0, $j = 1, $n = strlen($control); $i < $n; $i++, $j*=2) {
    $result[$j] = $control[$i];
  }


Выдаем результат:

$output = "";
  for ($i= 1, $n = count($result); $i <= $n; $i++)
    $output .= $result[$i];
  echo $output;


Если это вам действительно интересно, в следующей статье напишу про декодер.