Избыточное кодирование, код Хэмминга — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
("<=" => \le, two consecutive <tex> sections merged)
(Вынесение расстояния Хэмминга в отдельную статью)
Строка 28: Строка 28:
  
 
Итого, увеличивая код длиной <tex>n</tex> на <tex>2\log_2 n</tex>, можно обнаружить и исправить одну ошибку.
 
Итого, увеличивая код длиной <tex>n</tex> на <tex>2\log_2 n</tex>, можно обнаружить и исправить одну ошибку.
 
== Расстояние Хэмминга ==
 
'''Расстояние Хэмминга''' — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых q-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
 
 
Например: <math>d(10{\color{Blue}1}1{\color{Blue}1}01, 10{\color{Red}0}1{\color{Red}0}01)=2</math>
 
 
Расстояние Хэмминга обладает свойствами метрики, удовлетворяя следующим условиям:
 
* <math>~d(x,y) \ge 0</math>
 
* <math>~d(x,x)=0</math>
 
* <math>~d(x,y)=d(y,x)</math>
 
* <math>~d(x,z) \le d(x,y) + d(y,z)</math>
 
  
 
== Определение и устранение ошибок в общем случае ==
 
== Определение и устранение ошибок в общем случае ==
 
Пусть <tex>\Sigma</tex> - исходный алфавит, <tex>C: \Sigma \to B^m</tex> - кодирование, <tex>B=(0,1)</tex>
 
Пусть <tex>\Sigma</tex> - исходный алфавит, <tex>C: \Sigma \to B^m</tex> - кодирование, <tex>B=(0,1)</tex>
  
 +
<tex>d: B^m,B^m \to R^+</tex> <tex>-</tex> [[Расстояние Хэмминга]] между двумя кодами.
 
Определим <tex>d = \min</tex> <math>~d(c(x),c(y))</math>, <tex>x,y \in \Sigma</tex>, <tex>x \ne y</tex>
 
Определим <tex>d = \min</tex> <math>~d(c(x),c(y))</math>, <tex>x,y \in \Sigma</tex>, <tex>x \ne y</tex>
  

Версия 19:44, 20 ноября 2010

Избыточное кодирование - вид кодирования, использующий избыточное количество информации с целью последующего контроля целостности данных при записи/воспроизведении информации или при её передаче по линиям связи.

Код, определяющий одну ошибку

Увеличив объем кода на 1 бит, можно получить возможность определять при передаче наличие одной ошибки. Для этого к коду нужно добавить бит x: [math]0110..10x[/math], такой, чтобы сумма всех единиц была четной. В случае, если контрольная сумма окажется нечетной, следует отправить запрос на повторную посылку элемента, в котором была обнаружена ошибка. Такое кодирование применяется только если вероятность ошибки крайне мала, например, в оперативной памяти компьютера.

Кодирование Хэмминга

Кодирование Хэмминга предусматривает как возможность обнаружения ошибки, так и возможность её исправления. Рассмотрим простой пример [math]-[/math] закодируем четыре бита: [math]a, b, c, d[/math]. Полученный код будет иметь длину 8 бит и выглядеть следующим образом: [math]a,b,c,d, a \oplus b, c \oplus d, a \oplus c, b \oplus d.[/math] Рассмотрим табличную визуализацию кода:

[math]a[/math] [math]b[/math] [math]a \oplus b[/math]
[math]c[/math] [math]d[/math] [math]c \oplus d[/math]
[math]a \oplus c[/math] [math]b \oplus d[/math]

Как видно из таблицы, даже если один из битов [math]a, b, c, d[/math] передался с ошибкой, содержащие его [math]xor[/math]-суммы не сойдутся. Итого, зная строку и столбец в проиллюстрированной таблице можно точно исправить ошибочный бит.

По аналогичному принципу можно закодировать любое число бит. Пусть мы имеем исходную строку длиной в [math]2^k[/math] бит. Для получения её кода добавим к ней [math]k[/math] пар бит по следующему принципу:

  • Первая пара: сумма четных бит и сумма нечетных бит
  • Вторая пара: сумма тех бит, в чьем номере второй бит с конца ноль и сумма тех бит, в чьем номере второй бит с конца единица

...

  • [math]k[/math]-тая пара: сумма тех бит, в чьем номере [math]k[/math]-тый бит с конца ноль и сумма тех бит, в чьем номере [math]k[/math]-тый бит с конца единица

Легко понять, что если в одном бите из строки допущена ошибка, то с помощью дописанных [math]k[/math] пар бит можно точно определить, какой именно бит ошибочный. Это объясняется тем, что каждая пара определяет один бит номера ошибочного бита в строке. Всего пар [math]k[/math], следовательно мы имеем [math]k[/math] бит номера ошибочного бита, что вполне достаточно: общее число бит строки не превосходит [math]2^k[/math].

Итого, увеличивая код длиной [math]n[/math] на [math]2\log_2 n[/math], можно обнаружить и исправить одну ошибку.

Определение и устранение ошибок в общем случае

Пусть [math]\Sigma[/math] - исходный алфавит, [math]C: \Sigma \to B^m[/math] - кодирование, [math]B=(0,1)[/math]

[math]d: B^m,B^m \to R^+[/math] [math]-[/math] Расстояние Хэмминга между двумя кодами. Определим [math]d = \min[/math] [math]~d(c(x),c(y))[/math], [math]x,y \in \Sigma[/math], [math]x \ne y[/math]

Тогда легко понять, что код, полученный преобразованием [math]C[/math] может исправлять [math]~[[/math][math]{d-1}\over{2}[/math][math]~][/math] и обнаруживать [math][d-1][/math] ошибок. Действительно, при любом натуральном количестве допустимых ошибок [math]r[/math] любой код [math]S[/math] образует вокруг себя проколотый шар таких строк [math]S_i[/math], что [math]0\lt d(S,S_i)\le r[/math]. Если этот шар не содержит других кодов (что выполняется при [math]r\lt d[/math]) , то можно утверждать, что если в него попадает строка, то она ошибочна. Аналогично можно утверждать, что если шары всех кодов не пересекаются (что выполняется при [math]r\le {{d-1}\over{2}} [/math]), то попавшую в шар строку [math]S_i[/math] можно считать ошибочной и тождественно исправить на центр шара — строку [math]S[/math].

Ссылки