Расширенный код Хэмминга
Краткие теоретические сведения
Код Хемминга с кодовым расстоянием dmin = 4 называется расширенным. Он обеспечивает исправление всех однократных ошибок и обнаружение всех двух- и трехкратных ошибок. Для этого вводится дополнительный проверочный разряд b0, который дописывается к проверочной матрице Хемминга с кодовым расстоянием dmin = 3, благодаря чему последнее увеличивается на 1.
Дополнительный проверочный разряд занимает последний столбец единичной подматрицы проверочной матрицы. Кроме того, увеличение количества проверочных разрядов в комбинации кода Хемминга ведет к возрастанию количества строк проверочной матрицы. Дополнительная строка получается путем дополнения столбцов проверочной матрицы до непарности.
На практике лучше применять иной метод получения расширенного кода Хемминга. Для этого кодовую комбинацию кода Хемминга просто дополняют дополнительным проверочным элементом b0, который находится с помощью проверки кодовой комбинации на парность. При этом проверочный элемент равен 1, если количество единиц в закодированной кодовой комбинации непарное, и 0, если парное.
Декодируют в обратной последовательности: сначала выполняют общую проверку, а потом проверку без дополнительного элемента b0. При этом могут возникнуть такие варианты:
1) ошибок нет (обе проверки дают нулевые синдромы);
2) есть однократная ошибка (общая проверка говорит о существовании ошибки, а проверка без дополнительного элемента дает синдром, который указывает номер ошибочного элемента);
3) есть двукратная ошибка (общая проверка говорит об отсутствии ошибок, а проверка без дополнительного проверочного элемента показывает место ошибки; но эту ошибку исправлять не надо, надо просто констатировать то, что ошибки 2).
4) есть трехкратная ошибка (общая проверка говорит о наличии ошибки, а синдром проверки без дополнительного проверочного элемента может принимать любые значения, в том числе и нулевое).
С учетом вышесказанного коды Хемминга с dmin = 4 используются, как правило, для обнаружения одно-, двух-, и трехкратных ошибок.
Кодирование
Кодовая комбинация, которую необходимо закодировать:
11101111 11101001.
Сначала необходимо закодировать комбинацию обычным кодом Хемминга (с кодовым расстоянием dmin = 3), что было выполнено в разделе 3.5.3. Был получен следующий результат:
111111011111111001001.
Для получения расширенного кода Хемминга далее выполняем кодирование с проверкой на четность, тем самым расширяя обычный код Хемминга дополнительным проверочным элементом b0. Количество единиц в кодовом слове – 16, следовательно, проверочный разряд равен 0, поскольку тогда количество единиц в закодированной кодовой комбинации будет четное. Дописываем дополнительный проверочный разряд и получаем закодированное сообщение:
111111011111111001001 0.
Декодирование
Пускай при передаче закодированного сообщения произошла ошибка в 13-ом разряде, и декодер получил следующую искаженную кодовую комбинацию:
1111110111110110010010.
Сначала выполним декодирование кода с проверкой на четность. Сумма единиц в полученном слове равна 15, то есть число нечетное, что свидетельствует о наличии ошибки. Поскольку расширенный код Хэмминга позволяет исправлять только одиночные ошибки, то предположим, что произошедшая ошибка одиночная, и исправим ее. Отбрасываем дополнительный проверочный разряд и получаем кодовую комбинацию обычного кода Хэмминга, в которой есть одиночная ошибка:
1111110111110110010010.
Далее выполняем декодирование обычного кода Хэмминга. Для этого для данной кодовой комбинации вычислим синдром ошибки при помощи системы, полученной в п. 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 |
Следовательно, синдром имеет вид:
011012 = 1310.
Полученный результат свидетельствует о том, что ошибка допущена в 13-м разряде принятой кодовой комбинации.
Инвертируем искаженный 13-й разряд, отбрасываем проверочные 1-й, 2-й, 4-й, 8-й и 16-й разряды и получаем декодированное сообщение с исправленной ошибкой:
11101111 11101001.
Итеративный код
Краткие теоретические сведения
Для передачи информации широко используются итеративные коды, обладающие высокой обнаруживающей способностью. При определении проверочных элементов q-ичных итеративных кодов производят сложение элементов кодовых комбинаций базового кода по модулю q. Обнаружение ошибок производится по аналогии с двоичным кодом – сравнением проверочных элементов каждой строки (столбца), принятых из канала и полученных на приемной стороне путем вычислений.
Исправление искаженного элемента производят следующим образом. Если не выполняется проверка для i-ой строки и j-ого столбца, то элемент, находящийся на пересечении i-ой строки и j-ого столбца, заменяется элементом, вычисленным путем сложения данного принятого элемента (ошибочного) со значением, полученным путем вычитания значений принятого из канала и вычисленного на приемной стороне проверочных элементов i-ой строки (или j-ого столбца).
Кодирование
Кодовая комбинация, которую необходимо закодировать:
11101111 11101001 11110111.
Необходимо разбить нашу кодовую комбинацию на блоки таким образом, чтобы матрица, строки которой представляют собой эти блоки, была наиболее близка к квадратной – тогда количество проверочных разрядов будет наименьшим. Следовательно, нашу 24-битную комбинацию нужно разбить на блоки по 6 бит (6x4 = 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-ого столбца
Инвертируем искаженный элемент, отбрасываем проверочные элементы (записываем строки матрицы 6x4 последовательно в одну строку) и получаем декодированное сообщение с исправленной ошибкой:
11101111 11101001 11110111.
Коды-спутники