Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа. Помехоустойчивое кодирование
Цель работы: Научиться строить корректирующий код Хемминга и декодировать сообщения в коде Хемминга.
Краткие теоретические сведения
Код Хэмминга
Код Хэмминга, являющийся групповым (n,k) кодом, с минимальным расстоянием d=3 позволяет обнаруживать и исправлять однократные ошибки. Для построения кода Хэмминга используется матрица H. , где Ak- транспонированная подматрица, En-k - единичная подматрица порядка n-k.
Если Х - исходная последовательность, то произведение Х·Н=0. Пусть E- вектор ошибок. Тогда (Х+Е)·Н = Х·Н+Е·Н = 0+Е·Н=E·H - синдром или корректор, который позволяет обнаружить и исправить ошибки. Контрольные символы e1 ,e2 ,...,er образуются из информационных символов, путем линейной комбинации , где аj={0,1} - коэффициенты, взятые из подматрицы A матрицы H.
Рассмотрим Построение кода Хэмминга для k=4 символам. Число контрольных символов r=n-k можно определить по неравенству Хэмминга для однократной ошибки. Но так, как нам известно, только исходное число символов k, то проще вычислить по эмпирической формуле
, (5.2)
где [.] - означает округление до большего ближайшего целого значения. Вычислим для k=4 . Получим код (n,k)=(7,4); n=7; k=4; r=n-k=3; d=3. Построим матрицу H.
Контрольные символы ej определим по формуле . Например, . Для простоты оставляем только слагаемые с единичными коэффициентами. В результате получим систему линейных уравнений, с помощью которых вычисляются контрольные разряды. Каждый контрольный разряд является как бы дополнением для определенных информационных разрядов для проверки на четность.
При декодировании вычисляем корректор K=k4k2k1
Если корректор равен нулю, следовательно, ошибок нет. Если корректор не равен нулю, то местоположение вектор-столбца матрицы H, совпадающего с вычисленным корректором, указывает место ошибки. При передаче может возникнуть двойная и более ошибка. Корректор также не будет равен нулю. В этом случае произойдет исправление случайного символа и нами будет принят неверный код. Для исключения такого автоматического исправления вводится еще один символ для проверки всей комбинации на четность. Кодовое расстояние d=4. Тогда матрица H будет иметь вид
Пример 5.4. Дана 1101 - исходная комбинация (k=4). Закодировать ее в коде Хэмминга.
По формуле (5.2) находим число контрольных символов r=3. Берем регистр из 7 ячеек памяти. Размещаем исходную комбинацию в ячейках 3,5,6,7.
1 2 3 4 5 6 7
* * 1 * 1 0 1
Находим контрольные символы
е4 = 5 + 6 + 7 = 1 + 0 + 1 = 0
е2 = 3 + 6 + 7 = 1 + 0 + 1 = 0
е1 = 3 + 5 + 7 = 1 + 1 + 1 = 1
Закодированная комбинация будет иметь вид
1 2 3 4 5 6 7
1 0 1 0 1 0 1
Допустим, что при передаче возникла ошибка, и мы приняли неверную комбинацию
1 2 3 4 5 6 7
1 0 1 0 1 1 1
Проверяем ее
к 4 = 4 + 5 + 6 + 7 = 0 + 1 + 1 + 1 = 1
к2 = 2 + 3 + 6 + 7 = 0 + 1 + 1 + 1 = 1
к1 = 1 + 3 + 5 + 7 = 1 + 1 + 1 + 1 + 0
K= - в шестом разряде ошибка.
Если бы нам понадобилось построить код и для проверки двойных ошибок, необходимо было бы ввести еще один дополнительный нулевой разряд.
Получим следующий код
0 1 2 3 4 5 6 7
0 1 0 1 0 1 0 1
При передаче и возникновении ошибки код будет иметь вид
0 1 2 3 4 5 6 7
0 1 0 1 0 1 1 1
Проверка в этом случае показала бы, что корректор K=110, а проверка всей комбинации на четность E0 = 0+1+0+1+0+1+1+1=1. Это указывает на одиночную ошибку. Допускается автоматическое исправление ошибки.
Существует следующий алгоритм декодирования кода Хэмминга с d=4
|
Корректор - K |
Значение E0 |
Вывод |
|
K=0 |
E0=0 |
Ошибок нет |
|
K#0 |
E0#0 |
Произошла одиночная ошибка |
|
K#0 |
E0=0 |
Произошла двойная ошибка. Исправление запрещено. |
|
K=0 |
E0#0 |
Произошла тройная или более нечетная ошибка |
Код (7,4) является минимально возможным кодом с достаточно большой избыточностью.
Эффективность кода (k/n) растет с увеличением длины кода
|
Длина кода - n |
7 |
15 |
31 |
63 |
|
Число информационных разрядов - k |
4 |
11 |
26 |
57 |
|
Число контрольных разрядов - r |
3 |
4 |
5 |
6 |
|
Эффективность кода k/n |
0,57 |
0,73 |
0,84 |
0,9 |
.
Задания
Для исходного двоичного числа, заданного преподавателем, сформировать код Хемминга.
Выполнить декодирование при 1) отсутствии ошибок, 2) однократных ошибках; 3) двукратных ошибках. Сделать выводы.
Варианты заданий
|
№ вар |
Номера бит исходной комбинации |
Ошибки в битах* |
||||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
Однократн. |
Двойные |
||
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
2 |
3 и 9 |
|||
|
2 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
4 |
7 и 12 |
||
|
3 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
9 |
4 и 7 |
|
|
4 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
10 |
5 и 11 |
||
|
5 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
5 |
1 и 4 |
|||
|
6 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
6 |
6 и 11 |
||
|
7 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
8 |
2 и 10 |
|||
|
8 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
3 и 8 |
|||
|
9 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
7 |
8 и 10 |
||
|
10 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
13 |
6 и 9 |
|
|
11 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
9 |
5 и 6 |
|||
|
12 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
10 |
1 и 8 |
|
|
13 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
6 |
6 и 8 |
|||
|
14 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
5 |
4 и 5 |
|
|
15 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
7 |
1 и 10 |
|||
|
16 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
7 и 12 |
||
|
17 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
8 |
5 и 9 |
|
|
18 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
12 |
3 и 7 |
|||
|
19 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
5 |
4 и 10 |
|
|
20 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
6 |
2 и 7 |
*Ошибки указаны для номеров бит принимаемой, а не исходной комбинации