Расширенный код Хэмминга
Краткие теоретические сведения
Код Хемминга с кодовым расстоянием dmin = 4 называется расширенным. Он обеспечивает исправление всех однократных ошибок и обнаружение всех двух- и трехкратных ошибок. Для этого вводится дополнительный проверочный разряд b0, который дописывается к проверочной матрице Хемминга с кодовым расстоянием dmin = 3, благодаря чему последнее увеличивается на 1.
Дополнительный проверочный разряд занимает последний столбец единичной подматрицы проверочной матрицы. Кроме того, увеличение количества проверочных разрядов в комбинации кода Хемминга ведет к возрастанию количества строк проверочной матрицы. Дополнительная строка получается путем дополнения столбцов проверочной матрицы до непарности.
На практике лучше применять иной метод получения расширенного кода Хемминга. Для этого кодовую комбинацию кода Хемминга просто дополняют дополнительным проверочным элементом b0, который находится с помощью проверки кодовой комбинации на парность. При этом проверочный элемент равен 1, если количество единиц в закодированной кодовой комбинации непарное, и 0, если парное.
Декодируют в обратной последовательности: сначала выполняют общую проверку, а потом проверку без дополнительного элемента b0. При этом могут возникнуть такие варианты:
1) ошибок нет (обе проверки дают нулевые синдромы);
2) есть однократная ошибка (общая проверка говорит о существовании ошибки, а проверка без дополнительного элемента дает синдром, который указывает номер ошибочного элемента);
3) есть двукратная ошибка (общая проверка говорит об отсутствии ошибок, а проверка без дополнительного проверочного элемента показывает место ошибки; но эту ошибку исправлять не надо, надо просто констатировать то, что ошибки 2).
4) есть трехкратная ошибка (общая проверка говорит о наличии ошибки, а синдром проверки без дополнительного проверочного элемента может принимать любые значения, в том числе и нулевое).
С учетом вышесказанного коды Хемминга с dmin = 4 используются, как правило, для обнаружения одно-, двух-, и трехкратных ошибок.
Кодирование
Кодовая комбинация, которую необходимо закодировать:
Сначала необходимо закодировать комбинацию обычным кодом Хемминга (с кодовым расстоянием dmin = 3), что было выполнено в разделе 3.5.3. Был получен следующий результат:
111111011111111001001.
Для получения расширенного кода Хемминга далее выполняем кодирование с проверкой на четность, тем самым расширяя обычный код Хемминга дополнительным проверочным элементом b0. Количество единиц в кодовом слове – 16, следовательно, проверочный разряд равен 0, поскольку тогда количество единиц в закодированной кодовой комбинации будет четное. Дописываем дополнительный проверочный разряд и получаем закодированное сообщение:
111111011111111001001 0.
Декодирование
Пускай при передаче закодированного сообщения произошла ошибка в 13-ом разряде, и декодер получил следующую искаженную кодовую комбинацию:
1111110111110110010010.
Сначала выполним декодирование кода с проверкой на четность. Сумма единиц в полученном слове равна 15, то есть число нечетное, что свидетельствует о наличии ошибки. Поскольку расширенный код Хэмминга позволяет исправлять только одиночные ошибки, то предположим, что произошедшая ошибка одиночная, и исправим ее. Отбрасываем дополнительный проверочный разряд и получаем кодовую комбинацию обычного кода Хэмминга, в которой есть одиночная ошибка:
Далее выполняем декодирование обычного кода Хэмминга. Для этого для данной кодовой комбинации вычислим синдром ошибки при помощи системы, полученной в п. 3.5.3. из проверочной матрицы H21,16:
| s1 = | (+) 1 | (+) 1 | (+) 0 | (+) 1 | (+) 0 | (+) 0 | (+) 0 | (+) 0 | (+) 0 | (+) 1 | = 1 |
| s2 = | (+) 1 | (+) 1 | (+) 0 | (+) 1 | (+) 0 | (+) 1 | (+) 0 | (+) 1 | (+) 0 | = 0 | |
| s3 = | (+) 1 | (+) 1 | (+) 0 | (+) 1 | (+) 0 | (+) 1 | (+) 0 | (+) 1 | (+) 1 | = 1 | |
| s4 = | (+) 1 | (+) 1 | (+) 0 | (+) 0 | (+) 0 | (+) 1 | (+) 1 | = 1 | |||
| s5 = | (+) 0 | (+) 1 | (+) 0 | (+) 1 | (+) 1 | = 0 |
Следовательно, синдром имеет вид:
Полученный результат свидетельствует о том, что ошибка допущена в 13-м разряде принятой кодовой комбинации.
Инвертируем искаженный 13-й разряд, отбрасываем проверочные 1-й, 2-й, 4-й, 8-й и 16-й разряды и получаем декодированное сообщение с исправленной ошибкой:
Итеративный код
Краткие теоретические сведения
Для передачи информации широко используются итеративные коды, обладающие высокой обнаруживающей способностью. При определении проверочных элементов q-ичных итеративных кодов производят сложение элементов кодовых комбинаций базового кода по модулю q. Обнаружение ошибок производится по аналогии с двоичным кодом – сравнением проверочных элементов каждой строки (столбца), принятых из канала и полученных на приемной стороне путем вычислений.
Исправление искаженного элемента производят следующим образом. Если не выполняется проверка для i-ой строки и j-ого столбца, то элемент, находящийся на пересечении i-ой строки и j-ого столбца, заменяется элементом, вычисленным путем сложения данного принятого элемента (ошибочного) со значением, полученным путем вычитания значений принятого из канала и вычисленного на приемной стороне проверочных элементов i-ой строки (или j-ого столбца).
Кодирование
Кодовая комбинация, которую необходимо закодировать:
11101111 11101001 11110111.
Необходимо разбить нашу кодовую комбинацию на блоки таким образом, чтобы матрица, строки которой представляют собой эти блоки, была наиболее близка к квадратной – тогда количество проверочных разрядов будет наименьшим. Следовательно, нашу 24-битную комбинацию нужно разбить на блоки по 6 бит (6×4 = 24):
111011 111110 100111 110111.
Построим матрицу из этих 4-х блоков и вычислим проверочные символы путем сложения элементов строк и столбцов матрицы по модулю 2, то есть, кодируем строки и столбцы кодом с проверкой на четность.
| 1 | ||||||
| 1 | ||||||
| 0 | ||||||
| 1 | ||||||
| 0 | 1 | 0 | 1 | 0 | 1 | 1 |
Записываем строки матрицы последовательно в одну строку и получаем закодированное сообщение:
1110111 1111101 1001110 11011110101011.
Декодирование
Пускай при передаче закодированного сообщения произошла ошибка в 10-ом разряде, и декодер получил следующую искаженную кодовую комбинацию:
1110111 1101101 1001110 1101111 0101011.
Строим проверочную матрицу для полученной комбинации и производим сложение элементов строк и столбцов матрицы по модулю 2 (проверка на четность):
| 0 | ||||||
| 0 | 1 | |||||
| 0 | ||||||
| 0 | ||||||
| 0 | ||||||
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
Видим, что не выполняется проверка для 2-ой строки и 3-ого столбца. Это означает, что элемент, находящийся на пересечении 2-ой строки и 3-ого столбца, необходимо заменить элементом, вычисленным путем сложения по модулю 2 данного принятого элемента (ошибочного) со значением, полученным на приемной стороне при проверке на четность 2-ой строки (или 3-ого столбца). Проще говоря, необходимо инвертировать элемент, находящийся на пересечении 2-ой строки и 3-ого столбца
Инвертируем искаженный элемент, отбрасываем проверочные элементы (записываем строки матрицы 6×4 последовательно в одну строку) и получаем декодированное сообщение с исправленной ошибкой:
Код Хэмминга. Пример работы алгоритма
Прежде всего стоит сказать, что такое Код Хэмминга и для чего он, собственно, нужен. На Википедии даётся следующее определение:
Коды Хэмминга — наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления.
Другими словами, это алгоритм, который позволяет закодировать какое-либо информационное сообщение определённым образом и после передачи (например по сети) определить появилась ли какая-то ошибка в этом сообщении (к примеру из-за помех) и, при возможности, восстановить это сообщение. Сегодня, я опишу самый простой алгоритм Хемминга, который может исправлять лишь одну ошибку.
Также стоит отметить, что существуют более совершенные модификации данного алгоритма, которые позволяют обнаруживать (и если возможно исправлять) большее количество ошибок.
Сразу стоит сказать, что Код Хэмминга состоит из двух частей. Первая часть кодирует исходное сообщение, вставляя в него в определённых местах контрольные биты (вычисленные особым образом). Вторая часть получает входящее сообщение и заново вычисляет контрольные биты (по тому же алгоритму, что и первая часть). Если все вновь вычисленные контрольные биты совпадают с полученными, то сообщение получено без ошибок. В противном случае, выводится сообщение об ошибке и при возможности ошибка исправляется.
Как это работает.
Для того, чтобы понять работу данного алгоритма, рассмотрим пример.
Подготовка
Допустим, у нас есть сообщение «habr», которое необходимо передать без ошибок. Для этого сначала нужно наше сообщение закодировать при помощи Кода Хэмминга. Нам необходимо представить его в бинарном виде.
На этом этапе стоит определиться с, так называемой, длиной информационного слова, то есть длиной строки из нулей и единиц, которые мы будем кодировать. Допустим, у нас длина слова будет равна 16. Таким образом, нам необходимо разделить наше исходное сообщение («habr») на блоки по 16 бит, которые мы будем потом кодировать отдельно друг от друга. Так как один символ занимает в памяти 8 бит, то в одно кодируемое слово помещается ровно два ASCII символа. Итак, мы получили две бинарные строки по 16 бит:
и
После этого процесс кодирования распараллеливается, и две части сообщения («ha» и «br») кодируются независимо друг от друга. Рассмотрим, как это делается на примере первой части.
Прежде всего, необходимо вставить контрольные биты. Они вставляются в строго определённых местах — это позиции с номерами, равными степеням двойки. В нашем случае (при длине информационного слова в 16 бит) это будут позиции 1, 2, 4, 8, 16. Соответственно, у нас получилось 5 контрольных бит (выделены красным цветом):
Было:
Стало:
Таким образом, длина всего сообщения увеличилась на 5 бит. До вычисления самих контрольных бит, мы присвоили им значение «0».
Вычисление контрольных бит.
Теперь необходимо вычислить значение каждого контрольного бита. Значение каждого контрольного бита зависит от значений информационных бит (как неожиданно), но не от всех, а только от тех, которые этот контрольных бит контролирует. Для того, чтобы понять, за какие биты отвечает каждых контрольный бит необходимо понять очень простую закономерность: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N. Не очень понятно, но по картинке, думаю, станет яснее:
Здесь знаком «X» обозначены те биты, которые контролирует контрольный бит, номер которого справа. То есть, к примеру, бит номер 12 контролируется битами с номерами 4 и 8. Ясно, что чтобы узнать какими битами контролируется бит с номером N надо просто разложить N по степеням двойки.
Но как же вычислить значение каждого контрольного бита? Делается это очень просто: берём каждый контрольный бит и смотрим сколько среди контролируемых им битов единиц, получаем некоторое целое число и, если оно чётное, то ставим ноль, в противном случае ставим единицу. Вот и всё! Можно конечно и наоборот, если число чётное, то ставим единицу, в противном случае, ставим 0. Главное, чтобы в «кодирующей» и «декодирующей» частях алгоритм был одинаков. (Мы будем применять первый вариант).
Высчитав контрольные биты для нашего информационного слова получаем следующее:
и для второй части:
Вот и всё! Первая часть алгоритма завершена.
Декодирование и исправление ошибок.
Теперь, допустим, мы получили закодированное первой частью алгоритма сообщение, но оно пришло к нас с ошибкой. К примеру мы получили такое (11-ый бит передался неправильно):
Вся вторая часть алгоритма заключается в том, что необходимо заново вычислить все контрольные биты (так же как и в первой части) и сравнить их с контрольными битами, которые мы получили. Так, посчитав контрольные биты с неправильным 11-ым битом мы получим такую картину:
Как мы видим, контрольные биты под номерами: 1, 2, 8 не совпадают с такими же контрольными битами, которые мы получили. Теперь просто сложив номера позиций неправильных контрольных бит (1 + 2 + 8 = 11) мы получаем позицию ошибочного бита. Теперь просто инвертировав его и отбросив контрольные биты, мы получим исходное сообщение в первозданном виде! Абсолютно аналогично поступаем со второй частью сообщения.
Заключение.
В данном примере, я взял длину информационного сообщения именно 16 бит, так как мне кажется, что она наиболее оптимальная для рассмотрения примера (не слишком длинная и не слишком короткая), но конечно же длину можно взять любую. Только стоит учитывать, что в данной простой версии алгоритма на одно информационное слово можно исправить только одну ошибку.
Примечание.
На написание этого топика меня подвигло то, что в поиске я не нашёл на Хабре статей на эту тему (чему я был крайне удивлён). Поэтому я решил отчасти исправить эту ситуацию и максимально подробно показать как этот алгоритм работает. Я намеренно не приводил ни одной формулы, дабы попытаться своими словами донести процесс работы алгоритма на примере.
Помехоустойчивое кодирование. Коды Хэмминга
Назначение помехоустойчивого кодирования – защита информации от помех и ошибок при передаче и хранении информации. Помехоустойчивое кодирование необходимо для устранения ошибок, которые возникают в процессе передачи, хранения информации. При передачи информации по каналу связи возникают помехи, ошибки и небольшая часть информации теряется.
Без использования помехоустойчивого кодирования было бы невозможно передавать большие объемы информации (файлы), т.к. в любой системе передачи и хранении информации неизбежно возникают ошибки.
Рассмотрим пример CD диска. Там информация хранится прямо на поверхности диска, в углублениях, из-за того, что все дорожки на поверхности, часто диск хватаем пальцами, елозим по столу и из-за этого без помехоустойчивого кодирования, информацию извлечь не получится.
Использование кодирования позволяет извлекать информацию без потерь даже с поврежденного CD/DVD диска, когда какая либо область становится недоступной для считывания.
В зависимости от того, используется в системе обнаружение или исправление ошибок с помощью помехоустойчивого кода, различают следующие варианты:
Возможен также гибридный вариант, чтобы лишний раз не гонять информацию по каналу связи, например получили пакет информации, попробовали его исправить, и если не смогли исправить, тогда отправляется запрос на повторную передачу.
Исправление ошибок в помехоустойчивом кодировании
Любое помехоустойчивое кодирование добавляет избыточность, за счет чего и появляется возможность восстановить информацию при частичной потере данных в канале связи (носителе информации при хранении). В случае эффективного кодирования убирали избыточность, а в помехоустойчивом кодировании добавляется контролируемая избыточность.
Простейший пример – мажоритарный метод, он же многократная передача, в котором один символ передается многократно, а на приемной стороне принимается решение о том символе, количество которых больше.
Допустим есть 4 символа информации, А, B, С,D, и эту информацию повторяем несколько раз. В процессе передачи информации по каналу связи, где-то возникла ошибка. Есть три пакета (A1B1C1D1|A2B2C2D2|A3B3C3D3), которые должны нести одну и ту же информацию.
Но из картинки справа, видно, что второй символ (B1 и C1) они отличаются друг от друга, хотя должны были быть одинаковыми. То что они отличаются, говорит о том, что есть ошибка.
Необходимо найти ошибку с помощью голосования, каких символов больше, символов В или символов С? Явно символов В больше, чем символов С, соответственно принимаем решение, что передавался символ В, а символ С ошибочный.
Для исправления ошибок нужно, как минимум 3 пакета информации, для обнаружения, как минимум 2 пакета информации.
Параметры помехоустойчивого кодирования
Первый параметр, скорость кода R характеризует долю информационных («полезных») данных в сообщении и определяется выражением: R=k/n=k/m+k
Параметры n и k часто приводят вместе с наименованием кода для его однозначной идентификации. Например, код Хэмминга (7,4) значит, что на вход кодера приходит 4 символа, на выходе 7 символов, Рида-Соломона (15, 11) и т.д.
Второй параметр, кратность обнаруживаемых ошибок – количество ошибочных символов, которые код может обнаружить.
Третий параметр, кратность исправляемых ошибок – количество ошибочных символов, которые код может исправить (обозначается буквой t).
Контроль чётности
Самый простой метод помехоустойчивого кодирования это добавление одного бита четности. Есть некое информационное сообщение, состоящее из 8 бит, добавим девятый бит.
Если нечетное количество единиц, добавляем 0.
1 0 1 0 0 1 0 0 | 0
Если четное количество единиц, добавляем 1.
1 1 0 1 0 1 0 0 | 1
Если принятый бит чётности не совпадает с рассчитанным битом чётности, то считается, что произошла ошибка.
1 1 0 0 0 1 0 0 | 1
Под кратностью понимается, всевозможные ошибки, которые можно обнаружить. В этом случае, кратность исправляемых ошибок 0, так как мы не можем исправить ошибки, а кратность обнаруживаемых 1.
Есть последовательность 0 и 1, и из этой последовательности составим прямоугольную матрицу размера 4 на 4. Затем для каждой строки и столбца посчитаем бит четности.
Прямоугольный код – код с контролем четности, позволяющий исправить одну ошибку:
И если в процессе передачи информации допустим ошибку (ошибка нолик вместо единицы, желтым цветом), начинаем делать проверку. Нашли ошибку во втором столбце, третьей строке по координатам. Чтобы исправить ошибку, просто инвертируем 1 в 0, тем самым ошибка исправляется.
Этот прямоугольный код исправляет все одно-битные ошибки, но не все двух-битные и трех-битные.
Рассчитаем скорость кода для:
Здесь R=16/24=0,66 (картинка выше, двадцать пятую единичку (бит четности) не учитываем)
Более эффективный с точки зрения скорости является первый вариант, но зато мы не можем с помощью него исправлять ошибки, а с помощью прямоугольного кода можно. Сейчас на практике прямоугольный код не используется, но логика работы многих помехоустойчивых кодов основана именно на прямоугольном коде.
Классификация помехоустойчивых кодов
По используемому алфавиту:
Блочные коды делятся на
В случае систематических кодов, выходной блок в явном виде содержит в себе, то что пришло на вход, а в случае несистематического кода, глядя на выходной блок нельзя понять что было на входе.
Смотря на картинку выше, код 1 1 0 0 0 1 0 0 | 1 является систематическим, на вход поступило 8 бит, а на выходе кодера 9 бит, которые в явном виде содержат в себе 8 бит информационных и один проверочный.
Код Хэмминга
Код Хэмминга — наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Позволяет устранить одну ошибку и находить двойную.
Код Хэмминга (7,4) — 4 бита на входе кодера и 7 на выходе, следовательно 3 проверочных бита. С 1 по 4 информационные биты, с 6 по 7 проверочные (см. табл. выше). Пятый проверочный бит y5, это сумма по модулю два 1-3 информационных бит. Сумма по модулю 2 это вычисление бита чётности.
Декодирование кода Хэмминга
Декодирование происходит через вычисление синдрома по выражениям:
Синдром это сложение бит по модулю два. Если синдром не нулевой, то исправление ошибки происходит по таблице декодирования:
Расстояние Хэмминга
Расстояние Хэмминга — число позиций, в которых соответствующие символы двух кодовых слов одинаковой длины различны. Если рассматривать два кодовых слова, (пример на картинке ниже, 1 0 1 1 0 0 1 и 1 0 0 1 1 0 1) видно что они отличаются друг от друга на два символа, соответственно расстояние Хэмминга равно 2.
Кратность исправляемых ошибок и обнаруживаемых, связано минимальным расстоянием Хэмминга. Любой помехоустойчивый код добавляет избыточность с целью увеличить минимальное расстояние Хэмминга. Именно минимальное расстояние Хэмминга определяет помехоустойчивость.
Помехоустойчивые коды
Современные коды более эффективны по сравнению с рассматриваемыми примерами. В таблице ниже приведены Коды Боуза-Чоудхури-Хоквингема (БЧХ)
Из таблицы видим, что там один класс кода БЧХ, но разные параметры n и k.
Несмотря на то, что скорость кода близка, количество исправляемых ошибок может быть разное. Количество исправляемых ошибок зависит от той избыточности, которую добавим и от размера блока. Чем больше блок, тем больше ошибок он исправляет, даже при той же самой избыточности.
Пример: помехоустойчивые коды и двоичная фазовая манипуляция (2-ФМн). На графике зависимость отношения сигнал шум (Eb/No) от вероятности ошибки. За счет применения помехоустойчивых кодов улучшается помехоустойчивость.
Из графика видим, код Хэмминга (7,4) на сколько увеличилась помехоустойчивость? Всего на пол Дб это мало, если применить код БЧХ (127, 64) выиграем порядка 4 дБ, это хороший показатель.
Компромиссы при использовании помехоустойчивых кодов
Чем расплачиваемся за помехоустойчивые коды? Добавили избыточность, соответственно эту избыточность тоже нужно передавать. Нужно: увеличивать пропускную способность канала связи, либо увеличивать длительность передачи.
Необходимость чередования (перемежения)
Все помехоустойчивые коды могут исправлять только ограниченное количество ошибок t. Однако в реальных системах связи часто возникают ситуации сгруппированных ошибок, когда в течение непродолжительного времени количество ошибок превышает t.
Например, в канале связи шумов мало, все передается хорошо, ошибки возникают редко, но вдруг возникла импульсная помеха или замирания, которые повредили на некоторое время процесс передачи, и потерялся большой кусок информации. В среднем на блок приходится одна, две ошибки, а в нашем примере потерялся целый блок, включая информационные и проверочные биты. Сможет ли помехоустойчивый код исправить такую ошибку? Эта проблема решаема за счет перемежения.
Пример блочного перемежения:
На картинке, всего 5 блоков (с 1 по 25). Код работает исправляя ошибки в рамках одного блока (если в одном блоке 1 ошибка, код его исправит, а если две то нет). В канал связи отдается информация не последовательно, а в перемешку. На выходе кодера сформировались 5 блоков и эти 5 блоков будем отдавать не по очереди а в перемешку. Записали всё по строкам, но считывать будем, чтобы отправлять в канал связи, по столбцам. Информация в блоках перемешалась. В канале связи возникла ошибка и мы потеряли большой кусок. В процессе приема, мы опять составляем таблицу, записываем по столбцам, но считываем по строкам. За счет того, что мы перемешали большое количество блоков между собой, групповая ошибка равномерно распределится по блокам.