Википедия

Код Хэмминга: различия между версиями

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
оформление, стилевые правки
Строка 14:
| обозначение = <math>[2^r-1, 2^r-r-1, 3]_2</math>
}}
'''Код Хэ́мминга''' — вероятно, наиболее известный из первых самоконтролирующихсясамоконтролирующийся и самокорректирующихсясамокорректирующийся [[код]]ов. Построен применительно к [[Двоичная система счисления|двоичной системе счисления]].

Позволяет исправлять одиночную ошибку (ошибка в одном бите слова) и находить двойную<ref>{{Cite web|accessdate = 2016-01-20|title = Коды Хемминга — "Все о Hi-Tech"|url = http://all-ht.ru/inf/systems/p_0_14.html|publisher = all-ht.ru}}</ref>.
 
НазваныНазван в честь американского математика [[Хэмминг, Ричард Уэсли|Ричарда Хэмминга]], предложившего ихкод.
 
== История ==
В середине 1940-х годов в лаборатории фирмы Белл ([[Bell Labs]]) была создана счётная машина ''Bell Model V''. Это была электромеханическая машина, использующая релейные блоки, скорость которых была очень низка: одинодна оборотоперация за несколько секунд. Данные вводились в машину с помощью [[Перфокарта|перфокарт]] с ненадёжными устройствами чтения, поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и снова запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую.
 
Хэмминг часто работал в выходные дни, и все больше и больше раздражался, потому что часто должен был перезагружать свою программу из-за ненадежности считывателя перфокарт. На протяжении нескольких лет он проводилискал многоэффективный времени над построением эффективных алгоритмовалгоритм исправления ошибок. В [[1950 год]]у он опубликовал способ кодирования, который известен как код Хэмминга.
 
== Систематические коды ==
Систематические коды образуют большую группу из блочных, разделимых кодов (в которых все символы слова можно разделить на проверочные и информационные). Особенностью систематических кодов является то, что проверочные символы образуются в результате [[Линейный код|линейных логических операций]] над информационными символами. Кроме того, любая разрешенная кодовая комбинация может быть получена в результате линейных операций над набором линейно независимых кодовых комбинаций.
 
== Самоконтролирующиеся коды ==
Коды Хэмминга являются самоконтролирующимися кодами, то есть кодами, позволяющими автоматически обнаруживать ошибки при передаче данных. Для их построения достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру этого разряда так, чтобы общее количество единиц в изображении любого числа было, например, нечетным. Одиночная ошибка в каком-либо разряде передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут даватьдают сигнал о наличии ошибок.
 
При проверочном бите этом невозможно узнать, в какомкакой именно разрядепозиции слова произошла ошибка, и, следовательно, нет возможности исправить её. Остаются незамеченными также ошибки, возникающие одновременно в двух, четырёх, и т. д. — в четном количестве разрядов. ВпрочемПредполагается, что двойные, а тем более четырёхкратныемногократные ошибки полагаются маловероятнымималовероятны.
 
== Самокорректирующиеся коды ==
Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно. Как видно из дальнейшего, количество контрольных разрядов <math>k</math> должно быть выбрано так, чтобы удовлетворялось неравенство <math>2^k \geq k+m+1</math> или <math> k \geq \log_2(k+m+1)</math>, где <math>m</math> — количество основныхинформационных двоичных разрядов кодового слова.
 
{| class="wikitable" style="float:left; margin-right:1em; clear:left"
Минимальные значения k при заданных значениях m, найденные в соответствии с этим неравенством, приведены в таблице.▼
 
{| class="wikitable"
|+
! Диапазон m
Строка 56:
| 6
|}
▲Минимальные значения k при заданных значениях m, найденные в соответствии с этим неравенством, приведены в таблице.
 
В настоящее время наибольшийНаибольший интерес представляют [[Обнаружение и исправление ошибок#Коды обнаружения и исправления ошибок|двоичные блочные корректирующие коды]]. При использовании таких кодов информация передаётся в виде блоков одинаковой длины и каждый блок кодируется и декодируется независимо друг от друга. Почти во всех блочных кодах символы можно разделить на информационные и проверочные или контрольные. Таким образом, все комбинации кодовслова разделяются на разрешенные (для которых соотношение информационных и проверочных символов возможно) и запрещенные.
 
Основными характеристиками самокорректирующихся кодов являются:
# Число разрешенных и запрещенных комбинаций. Если <math>n</math> — число символов в блоке, <math>r</math> — число проверочных символов в блоке, <math>k</math> — число информационных символов, то '''<math>2^n</math>''' — число возможных кодовых комбинаций, '''<math>2^k</math>''' — число разрешенных кодовых комбинаций, '''<math>2^n - 2^k</math>''' — число запрещенных комбинаций.
# Избыточность кода. Величину '''<math>\tfrac{r}{n}</math>''' называют избыточностью корректирующего кода.
# Минимальное кодовое расстояние. Минимальным кодовым расстоянием <math>d</math> называется минимальное число искаженных символов, необходимое для перехода одной разрешенной комбинации в другую.
# Число обнаруживаемых и исправляемых ошибок. Если <math>g</math> — количество ошибок, которое код способен исправить, то необходимо и достаточно, чтобы '''<math>d \geq 2g+1</math>'''
# Корректирующие возможности кодов.
 
[[Граница Плоткина]] даёт верхнюю границу кодового расстояния:
: <math>d\leqslant \tfrac{n \cdot 2^{k-1}}{2^k-1}</math>▼
или▼
: <math>r \geq 2\cdot(d-1)-\log_2 d</math>▼
при <math>n \geq 2 \cdot d-1</math>
 
▲: <math>d\leqslant \tfrac{n \cdot 2^{k-1}}{2^k-1},</math>
[[Граница Хэмминга]] устанавливает максимально возможное число разрешенных кодовых комбинаций▼
: <math>2^k \leq {2^n} / \sum_{i=0}^{\tfrac{d-1}{2}} C_n^i </math>▼
где <math>C_n^i</math> — число сочетаний из <math>n</math> элементов по i элементам. Отсюда можно получить выражение для оценки числа проверочных символов: <math>r \geq \log_2\left( \sum_{i=0}^{(d-1)/2} C_n^i\right) </math>▼
 
▲или:
Для значений <math>(d/n) \leq 0.3 </math> разница между границей Хемминга и границей Плоткина невелика.▼
 
▲: <math>r \geq 2\cdot(d-1)-\log_2 d</math> при <math>n \geq 2 \cdot d-1.</math>
[[Неравенство Гильберта — Варшамова|Граница Варшамова — Гилберта]] для больших n определяет нижнюю границу числа проверочных символов▼
:<math>r \geq \log_2\left(\sum_{i=0}^{d-2} C_{n-1}^i\right) </math>▼
 
▲[[Граница Хэмминга]] устанавливает максимально возможное число разрешенных кодовых комбинаций:
Все вышеперечисленные оценки дают представление о '''верхней границе''' d при фиксированных n и k или '''оценку снизу''' числа проверочных символов▼
 
▲: <math>2^k \leq {2^n} / \sum_{i=0}^{\tfrac{d-1}{2}} C_n^i ,</math>
 
▲: где <math>C_n^i</math> — число сочетаний из <math>n</math> элементов по <math>i</math> элементам. Отсюда можно получить выражение для оценки числа проверочных символов: <math>r \geq \log_2\left( \sum_{i=0}^{(d-1)/2} C_n^i\right) </math>
 
: <math>r \geq \log_2\left( \sum_{i=0}^{(d-1)/2} C_n^i \right).</math>
 
▲Для значений <math>(d/n) \leq 0.{,}3 </math> разница между границей ХеммингаХэмминга и границей Плоткина невелика.
 
▲[[Неравенство Гильберта — Варшамова|Граница Варшамова — Гилберта]] для больших n определяет нижнюю границу числа проверочных символов:
 
▲: <math>r \geq \log_2\left(\sum_{i=0}^{d-2} C_{n-1}^i\right) .</math>
 
▲Все вышеперечисленные оценки дают представление о '''верхней границе''' <math>d</math> при фиксированных <math>n</math> и <math>k</math> или '''оценку снизу''' числа проверочных символов.
 
== Код Хэмминга ==
Построение кодов Хэмминга основано на принципе проверки на четность числа единичных символов: к последовательности добавляется такой элемент, чтобы число единичных символов в получившейся последовательности было четным.:
 
: <math>r_1 = i_1 \oplus i_2 \oplus ... \oplus i_k.</math>
знак <math>\oplus </math> здесь означает [[сложение по модулю 2]]▼
 
▲знакЗнак <math>\oplus </math> здесь означает [[сложение по модулю 2]]:
: <math>S = i_1 \oplus i_2 \oplus ... \oplus i_n \oplus r_1 </math>.▼
<math>S = 0 </math> — ошибки нет, <math>S = 1 </math> однократная ошибка.▼
 
▲: <math>S = i_1 \oplus i_2 \oplus ... \oplus i_n \oplus r_1 .</math>.
Такой код называется <math>(k+1,k) </math> или <math>(n,n-1) </math>. Первое число — количество элементов последовательности, второе — количество информационных символов.▼
 
▲Если <math>S = 0 </math> — то ошибки нет, если <math>S = 1 </math> - то однократная ошибка.
Для каждого числа проверочных символов <math>r = 3,4,5.. </math> существует классический код Хэмминга с маркировкой▼
<math>(n,k)=(2^r-1,2^r-1-r)</math> то есть — <math>(7,4),(15,11),(31,26) </math>. При иных значениях k получается так называемый усеченный код, например международный телеграфный код МТК-2, у которого <math>k = 5 </math>. Для него необходим код Хэмминга <math>(9,5) </math>, который является усеченным от классического <math>(15,11) </math>.▼
 
▲Такой код называется <math>(k+1,\ k) </math> или <math>(n,\ n-1) </math>. Первое число — количество элементов последовательности, второе — количество информационных символов.
Для примера рассмотрим классический код Хемминга <math>(7,4) </math>. Сгруппируем проверочные символы следующим образом:▼
 
: <math>r_1 = i_1 \oplus i_2 \oplus i_3</math>▼
▲Для каждого числа проверочных символов <math>r = 3,\ 4,\ 5\ ... </math> существует классический код Хэмминга с маркировкой:
: <math>r_2 = i_2 \oplus i_3 \oplus i_4</math>▼
 
: <math>r_3 = i_1 \oplus i_2 \oplus i_4</math>▼
: <math>(n,k)=(2^r-1,2^r-1-r),</math> то есть — <math>(7,4),(15,11),(31,26) </math>.
 
▲<math>(n,k)=(2^r-1,2^r-1-r)</math>При тоиных есть —значениях <math>(7,4),(15,11),(31,26) k</math>. При иных значениях k получается так называемый усеченный код, например международный телеграфный код МТК-2, у которого <math>k = 5 </math>. Для него необходим код Хэмминга <math>(9,\ 5) ,</math>, который является усеченным от классического <math>(15,\ 11) .</math>.
 
▲Для примера рассмотрим классический код Хемминга <math>(7,\ 4) </math>. Сгруппируем проверочные символы следующим образом:
 
▲: <math>r_1 = i_1 \oplus i_2 \oplus i_3,</math>
▲: <math>r_2 = i_2 \oplus i_3 \oplus i_4,</math>
▲: <math>r_3 = i_1 \oplus i_2 \oplus i_4.</math>
 
Получение кодового слова выглядит следующим образом:
Строка 111 ⟶ 126 :
\end{pmatrix} </math> = <math>\begin{pmatrix}
i_1 & i_2 & i_3 & i_4 & r_1 & r_2 & r_3 \\
\end{pmatrix} </math>.
 
На вход декодера поступает кодовое слово
<math>V = (i_1',\ i_2',\ i_3',\ i_4',\ r_1',\ r_2',\ r_3')</math> где штрихом помечены символы, которые могут исказиться в результате действия помехи. В декодере в режиме исправления ошибок строится последовательность синдромов:
 
: <math>S_1 = r_1 \oplus i_1 \oplus i_2 \oplus i_3</math>▼
: <math>S_2S_1 = r_2r_1 \oplus i_2i_1 \oplus i_3i_2 \oplus i_4i_3,</math>
: <math>S_3S_2 = r_3r_2 \oplus i_1i_2 \oplus i_2i_3 \oplus i_4,</math>
▲: <math>S_1S_3 = r_1r_3 \oplus i_1 \oplus i_2 \oplus i_3i_4.</math>
 
<math>S = (S_1,\ S_2,\ S_3) </math> называется синдромом последовательности.
 
Получение синдрома выглядит следующим образом:
Строка 134 ⟶ 150 :
\end{pmatrix} </math> = <math>\begin{pmatrix}
S_1 & S_2 & S_3 \\
\end{pmatrix} </math>.
 
{| class="wikitable sortable" style="float:left; margin-right:1em; clear:left"
Кодовые слова <math>(7,4) </math> кода Хэмминга▼
{| class="standard"
|<math>i_1</math> || <math>i_2</math> || <math>i_3</math> || <math>i_4</math> || <math>r_1</math> || <math>r_2</math> || <math>r_3</math>
|-
Строка 262 ⟶ 277 :
|1
|}
▲Кодовые слова <math>(7,\ 4) </math> кода Хэмминга приведены в таблице.
 
Синдром <math>(0,0,0) </math> указывает на то, что в последовательности нет искажений. Каждому ненулевому синдрому соответствует определеннаяопределённая конфигурация ошибок, которая исправляется на этапе декодирования.
 
Для кода <math>(7,4) </math> в таблице ниже указаны ненулевые синдромы и соответствующие им конфигурации ошибок (для вида: <math>i_1</math> <math>i_2</math> <math>i_3</math> <math>i_4</math> <math>r_1</math> <math>r_2</math> <math>r_3</math>).
{| class="standard"
|Синдром
Строка 299 ⟶ 315 :
 
== Алгоритм кодирования ==
Предположим, что нужно сгенерировать код Хэмминга для некоторого информационного кодового слова. В качестве примера возьмём 15-битовое кодовое слово '''x'''<sub>1</sub>…'''x'''<submath>x_1 \dots \ x_{15},</submath>, хотя алгоритм пригоден для кодовых слов любой длины. В приведённой ниже таблице в первой строке даны номера позиций в кодовом слове, во второй — условное обозначение битов, в третьей — значения битов.
 
{| class="wikitable"
|-
Строка 312 ⟶ 327 :
|}
 
Вставим в информационное слово контрольные биты '''r'''<submath>0r_0 \dots \ r_4</sub>…'''r'''<sub>4</submath> таким образом, чтобы номера их позиций представляли собой целые степени двойки: 1, 2, 4, 8, 16… Получим 20-разрядное слово с 15 информационными и 5 контрольными битами. Первоначально контрольные биты устанавливаем равными нулю. На рисунке контрольные биты выделены розовым цветом.
 
{| class="wikitable"
Строка 340 ⟶ 355 :
|- align="center"
| 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0
| '''r'''<sub>0</sub> ||
|- align="center"
| 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0
| '''r'''<sub>1</sub> ||
|- align="center"
| 0 || 0 || 0 || 1 || 1 || 1 || 1 || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 || 0 || 0 || 0 || 0 || 1
| '''r'''<sub>2</sub> ||
|- align="center"
| 0 || 0 || 0 || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 0 || 0 || 0 || 0 || 0
| '''r'''<sub>3</sub> ||
|- align="center"
| 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 || 1
| '''r'''<sub>4</sub> ||
|}
 
В правой части таблицы мы оставили пустым один столбец, в который поместим результаты вычислений контрольных битов. Вычисление контрольных битов производим следующим образом. Берём одну из строк матрицы преобразования (например, r<submath>0r_0</submath>) и находим её скалярное произведение с кодовым словом, то есть перемножаем соответствующие биты обеих строк и находим сумму произведений. Если сумма получилась больше единицы, находим остаток от его деления на 2. Иными словами, мы подсчитываем сколько раз в кодовом слове и соответствующей строке матрицы в одинаковых позициях стоят единицы и берём это число по модулю 2.
 
Если описывать этот процесс в терминах матричной алгебры, то операция представляет собой перемножение матрицы преобразования на матрицу-столбец кодового слова, в результате чего получается матрица-столбец контрольных разрядов, которые нужно взять по модулю 2.
 
Например, для строки r<submath>0r_0</submath>:
 
: r<submath>0r_0</submath> = (1·0+0·0+1·1+0·0+1·0+0·0+1·1+0·0+1·0+0·0+1·1+0·0+1·1+0·1+1·1+0·0+1·0+0·0+1·0+0·1) mod 2 = 5 mod 2 = 1.
 
Полученные контрольные биты вставляем в кодовое слово вместо стоявших там ранее нулей. По аналогии находим проверочные биты в остальных строках. Кодирование по Хэммингу завершено. Полученное кодовое слово — 11110010001011110001.
Источник — https://ru.wikipedia.org/wiki/Код_Хэмминга