21
правка
Изменения
м
→Кодирование Хэмминга: Исправлена опечатка в примере с таблицей
Рассмотрим табличную визуализацию кода:
{| class="wikitable" style="width:10cm" border=1! |-align="center" bgcolor=#F0F0F0!<tex>a</tex> || <tex>b</tex> ||style="background:#FFF"| <texbgcolor=#FFF>a \oplus b</tex>|-align="center"bgcolor=#F0F0F0!<tex>c</tex> || <tex>d</tex> ||style="background:#FFF"| <tex>c \oplus d</tex>|-align="center"bgcolor=#FFF!|<tex>a \oplus c</tex> || <tex>b \oplus d</tex>
|}
Как видно из таблицы, даже если один из битов <tex>a, b, c, d</tex> передался с ошибкой, содержащие его <tex>xor</tex>-суммы не сойдутся. Итого, зная строку и столбец в проиллюстрированной таблице можно точно исправить ошибочный бит. Если один из битов <tex>a \oplus b, a \oplus c, b \oplus d, c\oplus d</tex> передался с ошибкой, то не сойдется только одна строка или один столбец в проиллюстрированной таблице сумма и очевидно, что можно исправить ошибочный легко определить, какой битневерный
По аналогичному принципу можно закодировать любое число бит. Пусть мы имеем исходную строку длиной в <tex>2^k</tex> бит. Для получения её кода добавим к ней <tex>k</tex> пар бит по следующему принципу:
Легко понять, что если в одном бите из строки допущена ошибка, то с помощью дописанных <tex>k</tex> пар бит можно точно определить, какой именно бит ошибочный. Это объясняется тем, что каждая пара определяет один бит номера ошибочного бита в строке. Всего пар <tex>k</tex>, следовательно мы имеем <tex>k</tex> бит номера ошибочного бита, что вполне достаточно: общее число бит строки не превосходит <tex>2^k+k2k</tex>.
Теперь заметим, что в случае наличия ошибки в исходной строке, ровно один бит в каждой паре будет равен единице. Тогда можно оставить только один бит из пары. Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строке, то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит {{---}} <tex> \mathrm X \mathrm O \mathrm R</tex> всех битов строки.
Пусть <tex>\Sigma</tex> — исходный алфавит, <tex>C: \Sigma \to B^m</tex> — кодирование, <tex>B=(0,1)</tex>
<tex>d: B^m,\times B^m \to \mathbb{R^+}</tex> — [[расстояние Хэмминга]] между двумя кодами. <br>
Определим <tex>d_0 = \min</tex> <math>~d(c(x),c(y))</math>, <tex>x,y \in \Sigma</tex>, <tex>x \ne y</tex>
== Источники информации ==
*[http://en.wikipedia.org/wiki/Hamming_code Wikipedia, the free encyclopedia {{- --}} Hamming code]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
