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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
м (Кодирование Хэмминга: Исправлена опечатка в примере с таблицей)
(не показаны 23 промежуточные версии 4 участников)
Строка 1: Строка 1:
'''Избыточное кодирование''' {{---}} вид кодирования, использующий избыточное количество информации с целью последующего контроля целостности данных при записи/воспроизведении информации или при её передаче по линиям связи.
+
'''Избыточное кодирование''' (англ. ''redundant encoding'') {{---}} вид кодирования, использующий избыточное количество информации с целью последующего контроля целостности данных при записи/воспроизведении информации или при её передаче по линиям связи.
  
 
== Код, определяющий одну ошибку ==
 
== Код, определяющий одну ошибку ==
Увеличив объем кода на 1 бит, можно получить возможность определять при передаче наличие одной ошибки. Для этого к коду нужно добавить бит <tex>x</tex>:  <tex>0110..10x</tex>, такой, чтобы сумма всех единиц была четной. В случае, если контрольная сумма окажется нечетной, следует отправить запрос на повторную посылку элемента, в котором была обнаружена ошибка. Такое кодирование применяется только если вероятность ошибки крайне мала, например, в оперативной памяти компьютера.
+
Увеличив объем кода на <tex>1</tex> бит, можно получить возможность определять при передаче наличие одной ошибки. Для этого к коду нужно добавить бит <tex>x</tex>:  <tex>0110..10x</tex>, такой, чтобы сумма всех единиц была четной. В случае, если контрольная сумма окажется нечетной, следует отправить запрос на повторную посылку элемента, в котором была обнаружена ошибка. Такое кодирование применяется только если вероятность ошибки крайне мала, например, в оперативной памяти компьютера.
  
 
== Кодирование Хэмминга ==
 
== Кодирование Хэмминга ==
 
Кодирование Хэмминга предусматривает как возможность обнаружения ошибки, так и возможность её исправления.
 
Кодирование Хэмминга предусматривает как возможность обнаружения ошибки, так и возможность её исправления.
Рассмотрим простой пример {{---}} закодируем четыре бита: <tex>a, b, c, d</tex>. Полученный код будет иметь длину 8 бит и выглядеть следующим образом: <tex>a,b,c,d, a \oplus b, c \oplus d, a \oplus c, b \oplus d.</tex>
+
Рассмотрим простой пример {{---}} закодируем четыре бита: <tex>a, b, c, d</tex>. Полученный код будет иметь длину <tex>8</tex> бит и выглядеть следующим образом: <tex>a,b,c,d, a \oplus b, c \oplus d, a \oplus c, b \oplus d.</tex>
 
Рассмотрим табличную визуализацию кода:
 
Рассмотрим табличную визуализацию кода:
  
{| border="1"
+
{| class="wikitable" style="width:10cm" border=1
! <tex>a</tex> || <tex>b</tex> || <tex>a \oplus b</tex>
+
|-align="center" bgcolor=#F0F0F0
|-
+
! <tex>a</tex> || <tex>b</tex> ||style="background:#FFF"| <tex bgcolor=#FFF>a \oplus b</tex>
! <tex>c</tex> || <tex>d</tex> || <tex>c \oplus d</tex>
+
|-align="center" bgcolor=#F0F0F0
|-
+
! <tex>c</tex> || <tex>d</tex> ||style="background:#FFF"| <tex>c \oplus d</tex>
! <tex>a \oplus c</tex> || <tex>b \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, 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>2^k</tex> бит. Для получения её кода добавим к ней <tex>k</tex> пар бит по следующему принципу:
Строка 63: Строка 64:
  
  
Легко понять, что если в одном бите из строки допущена ошибка, то с помощью дописанных <tex>k</tex> пар бит можно точно определить, какой именно бит ошибочный. Это объясняется тем, что каждая пара определяет один бит номера ошибочного бита в строке. Всего пар <tex>k</tex>, следовательно мы имеем <tex>k</tex> бит номера ошибочного бита, что вполне достаточно: общее число бит строки не превосходит <tex>2^k</tex>.
+
Легко понять, что если в одном бите из строки допущена ошибка, то с помощью дописанных <tex>k</tex> пар бит можно точно определить, какой именно бит ошибочный. Это объясняется тем, что каждая пара определяет один бит номера ошибочного бита в строке. Всего пар <tex>k</tex>, следовательно мы имеем <tex>k</tex> бит номера ошибочного бита, что вполне достаточно: общее число бит строки не превосходит <tex>2^k+2k</tex>.
  
Теперь заметим, что в случае наличия ошибки в исходной строке, ровно один бит в каждой паре будет равен единице. Тогда можно оставить только один бит из пары. Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строке, то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит {{---}} <tex>xor</tex> всех битов строки.
+
Теперь заметим, что в случае наличия ошибки в исходной строке, ровно один бит в каждой паре будет равен единице. Тогда можно оставить только один бит из пары. Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строке, то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит {{---}} <tex> \mathrm X \mathrm O \mathrm R</tex> всех битов строки.
  
 
Итого, увеличивая код длиной <tex>n</tex> на <tex>\log_2 n + 1</tex>, можно обнаружить и исправить одну ошибку.
 
Итого, увеличивая код длиной <tex>n</tex> на <tex>\log_2 n + 1</tex>, можно обнаружить и исправить одну ошибку.
Строка 72: Строка 73:
 
Пусть <tex>\Sigma</tex> &mdash; исходный алфавит, <tex>C: \Sigma \to B^m</tex> &mdash; кодирование, <tex>B=(0,1)</tex>
 
Пусть <tex>\Sigma</tex> &mdash; исходный алфавит, <tex>C: \Sigma \to B^m</tex> &mdash; кодирование, <tex>B=(0,1)</tex>
  
<tex>d: B^m,B^m \to R^+</tex> &mdash; [[Расстояние Хэмминга]] между двумя кодами. <br>
+
<tex>d: B^m \times B^m \to \mathbb{R}</tex> &mdash; [[расстояние Хэмминга]] между двумя кодами. <br>
 
Определим <tex>d_0 = \min</tex> <math>~d(c(x),c(y))</math>, <tex>x,y \in \Sigma</tex>, <tex>x \ne y</tex>
 
Определим <tex>d_0 = \min</tex> <math>~d(c(x),c(y))</math>, <tex>x,y \in \Sigma</tex>, <tex>x \ne y</tex>
  
Тогда легко понять, что код, полученный преобразованием <tex>C</tex> может исправлять <math>~[</math><tex>{d_0-1}\over{2}</tex><math>~]</math> и обнаруживать <tex>[d_0-1]</tex> ошибок. Действительно, при любом натуральном количестве допустимых ошибок <tex>r</tex> любой код <tex>S</tex> образует вокруг себя проколотый шар таких строк <tex>S_i</tex>, что <tex>0<d(S,S_i)\leqslant r</tex>. Если этот шар не содержит других кодов (что выполняется при <tex>r<d_0</tex>) , то можно утверждать, что если в него попадает строка, то она ошибочна. Аналогично можно утверждать, что если шары всех кодов не пересекаются (что выполняется при <tex>r \leqslant {{d_0-1}\over{2}} </tex>), то попавшую в шар строку <tex>S_i</tex> можно считать ошибочной и тождественно исправить на центр шара &mdash; строку <tex>S</tex>.<br>
+
Тогда легко понять, что код, полученный преобразованием <tex>C</tex> может исправлять <math>~[</math><tex dpi = 150> {d_0-1}\over{2}</tex><math>~]</math> и обнаруживать <tex>[d_0-1]</tex> ошибок. Действительно, при любом натуральном количестве допустимых ошибок <tex>r</tex> любой код <tex>S</tex> образует вокруг себя проколотый шар таких строк <tex>S_i</tex>, что <tex>0<d(S,S_i)\leqslant r</tex>. Если этот шар не содержит других кодов (что выполняется при <tex>r<d_0</tex>) , то можно утверждать, что если в него попадает строка, то она ошибочна. Аналогично можно утверждать, что если шары всех кодов не пересекаются (что выполняется при <tex dpi = 150>r \leqslant {{d_0-1}\over{2}} </tex>), то попавшую в шар строку <tex>S_i</tex> можно считать ошибочной и тождественно исправить на центр шара &mdash; строку <tex>S</tex>.<br>
[[Файл:Ham.png]]
+
[[Файл:Ham.png|350px]]
  
 
== Источники информации ==
 
== Источники информации ==
*[http://en.wikipedia.org/wiki/Hamming_code Hamming code - Wikipedia, the free encyclopedia]
+
*[http://en.wikipedia.org/wiki/Hamming_code Wikipedia {{---}} Hamming code]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Алгоритмы сжатия ]]
 
[[Категория: Алгоритмы сжатия ]]

Версия 19:17, 29 октября 2015

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

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

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

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

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

Теперь заметим, что в случае наличия ошибки в исходной строке, ровно один бит в каждой паре будет равен единице. Тогда можно оставить только один бит из пары. Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строке, то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит — [math] \mathrm X \mathrm O \mathrm R[/math] всех битов строки.

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

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

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

[math]d: B^m \times B^m \to \mathbb{R}[/math]расстояние Хэмминга между двумя кодами.
Определим [math]d_0 = \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_0-1}\over{2}[/math][math]~][/math] и обнаруживать [math][d_0-1][/math] ошибок. Действительно, при любом натуральном количестве допустимых ошибок [math]r[/math] любой код [math]S[/math] образует вокруг себя проколотый шар таких строк [math]S_i[/math], что [math]0\lt d(S,S_i)\leqslant r[/math]. Если этот шар не содержит других кодов (что выполняется при [math]r\lt d_0[/math]) , то можно утверждать, что если в него попадает строка, то она ошибочна. Аналогично можно утверждать, что если шары всех кодов не пересекаются (что выполняется при [math]r \leqslant {{d_0-1}\over{2}} [/math]), то попавшую в шар строку [math]S_i[/math] можно считать ошибочной и тождественно исправить на центр шара — строку [math]S[/math].
Ham.png

Источники информации