Размещение контрольных символов
В принципе местонахождение этих символов значения не имеет: их можно приписывать и перед информационными словами, и после них, и чередуя информационные символы с контрольными. Однако произвольное месторасположение контрольных символов будет затруднять проверку принятого кода. Поэтому для удобства обнаружения искаженного символа целесообразно размещать их на местах, кратных степени 2, то есть в позициях 1, 2, 4, 8 и т.д. Информационные символы располагаются на оставшихся местах. Поэтому, для 7-элементой закодированной комбинации можно записать:
23, k = 4 }
m = 3} m1, m2, k4, m3, k3, k2, k1 (2)
где k4 – старший или четвертый разряд исходной кодовой комбинации двоичного кода, подлежащий кодированию.
Определение состава контрольных символов
Выявление того, какой символ должен стоять на контрольной позиции (1 или 0), производится по коэффициентам при помощи проверки на четность. Рассмотрим определение коэффициентов на примере комбинации (2).
Таблица 2
| Разряды двоичных чисел | Символы кода (для 2) | |||
| 4(k4) | 3 (k3) | 2 (k2) | 1(k1) | |
| m1 | ||||
| m2 | ||||
| k4 | ||||
| m3 | ||||
| k3 | ||||
| k2 | ||||
| k1 |
|
|
|
В таблицу вписаны все кодовые комбинации (исключая нулевую) для 4-разрядного двоичного кода на все сочетания.
Таблица 3
Проверочная таблица
| m1 | k4 | k3 | k1 |
| m2 | k4 | k2 | k1 |
| m3 | k3 | k2 | k1 |
Из таблицы 2 составляется таблица 3, в которой вписаны символы в 3- х строках в следующей закономерности. В первую строку таблицы 3 записываются символы m1, k4, k3, k1, против которых проставлены единицы в младшем (первом) разряде комбинации двоичного кода в таблице 2. Так в комбинациях 0001, 011, 0101, 0111 единицы находятся в младших разрядах. Во вторую строку проверочных коэффициентов записываются символы, против которых стоит 1 во втором разряде двоичного кода. Это комбинации 0010, 0011, 0110 и 0111-записали m2, k4, k2, k1. В третью строку записываются символы, против которых стоят единицы в третьем разряде двоичных комбинаций (m3, k3, k2, k1)
В случае кодирования более длинных кодовых комбинаций таблицы 2 и 3 должны быть расширены, так как должны быть записаны четвертая, пятая и т.д. строки проверочных коэффициентов. Так для комбинации m1, m2, k11, m3, k10, k9, k8, m4, k7, k6, k5, k4, k3, k2, k1. таблицы 3 будет состоять из 4-х строк.
|
|
|
Число проверок, а, значит, и число строк таблицы 3 равно числу контрольных символов m.
Нахождение состава контрольных символов при помощи проверок производится следующим образом. Суммируются информационные символы, входящие в каждую строку таблицы 3.
Если сумма единиц в данной строке четная, то значение символа m, входящее в эту строку, равно 0, если нечетная, то 1.
При помощи первой строки таблицы 3 определяется значение символа m1, при помощи второй строки – значение m2, третьей – m3.
Декодирование
Для проверки правильности комбинации снова используется метод проверки на четность по коэффициентам таблицы 3. Если комбинация принята без искажения, то сумма единиц по модулю 2 даст 0.
При искажении какого-либо символа суммирование при проверке даст единицу. По результату суммирования каждой из проверок составляется двоичное число, указывающее на место искажения. Например, первая и вторая проверки показали наличие искажения, суммирование при третьей проверке дало 0.Записываем число 011=3, которое означает, что в 3-ем символе кодовой комбинации, включающей и контрольные символы (счет производится слева направо) возникло искажение, поэтому этот символ нужно исправить на обратный ему, то есть 1 переправить на 0 или 0 на 1.После этого контрольные символы, стоящие на заранее известных местах, отбрасываются.
|
|
|
Пример кодирования и декодирования
Предполагаем, что нужно передать комбинацию 1101, то есть k = 4.
Согласно таблице 1 число контрольных символов m =3, и размещаются они на позициях 3, 5, 6, 7. Можно записать:
| m1 | m2 | k4 | m3 | k3 | k2 | k1 |
| ? | ? | 1 | ? | 1 | 0 | 1 |
(3)
Для определения значения контрольных символов заполним таблицу 3 значениями из последовательности (3). По полученной таблице 4 произведем проверки на четность.
Таблица 4
Пример составления таблицы для кода Хэмминга
| m1+1 +1 +1 = 3 m1=1 k4 k3 k1 |
| m2+1 + 0 +1 = 2 m2=0 k4 k2 k1 |
| m3+1 +0 +1 = 2 m3=0 k3 k2 k1 |
Для того, чтобы вся первая строка после проставления в нее значения символа m1 дала в сумме четное число, необходимо, чтобы m1=1 (m1+ k4+k3+k1=1+1+1+1=0).
Вторая строка в сумме дает четное число, если m2=0 (m2+k4+k2+k1=0+1+++1=0)
Третья строка дает четное число, если m3=0 (m3+k3+k2+k1=0+1+0+1=0)
Таким образом, в линию послан код 1010101.
|
|
|
Предположим, что при передаче помеха исказила один из символов, и был принят код 1010111. Для нахождения номера ошибки принятого символа используют метод проверки на четность по таблице 3. Для этого запишем:
| m1 | m2 | k4 | m3 | k3 | k2 | k1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
По полученной последовательности символов и по таблице 3 составим таблицу 5.
Таблица 5
Пример декодирования кода Хэмминга
| 1 +1 +1 +1=0 m1 k4 k3 k1 |
| 0 +1 +1 +1=1 m2 k4 k2 k1 |
| 0 +1 +1 +1=1 m3 k3 k2 k1 |
После заполнения этой таблицы сумма символов первой строки оказалась четной (1+1+1+1=0), поэтому для четности справа в первой строке табл. 5 приписываем 0. Сумма символов второй строки равна 3, поэтому справа для четности добавляется 1. Также для получения четности необходимо приписать 1 и к третьей строке.
Все три приписанных символа дали двоичное число 110 (но не 011), так первая проверка производилась по коэффициентам, составленным по младшим разрядам двоичного кода.
Двоичное число 110 означает десятичное число 6. Это значит, что искажение произошло в шестом символе, считая слева направо, и символ 1 нужно исправлять на 0. Так как места расположения контрольных символов заранее известны, то после коррекции контрольные символы выбрасывают и получают переданную кодовую комбинацию, состоящую из одних информационных символов 1101.
Итак, для повышения помехоустойчивости кода необходимо посылать дополнительные контрольные символы, которые увеличивают длину кодовой комбинации, вследствие чего появляются дополнительные или избыточные кодовые комбинации, не используемые непосредственно для передачи информации.
Так, семиразрядный код принципиально обеспечивает передачу 27 = 128 кодовых комбинаций, однако количество информационных символов в 7-разрядном коде Хэмминга k = 4, то есть количество полезных информационных комбинаций равно 24 = 16.
Остальные 112 кодовых комбинаций из 128 предназначены для обеспечения помехоустойчивости кода и являются запрещенными. Таким образом, избыточность кода Хэмминга достаточно велика
Порядок выполнения работы
1. Получить у преподавателя исходные данные и длину кода n для построения и дальнейшего исследования кода Хэмминга.
2. Порядок выполнения задания по пункту 1.2.
2.1. Определить длину информационной k и длину проверочной r последовательности кода.
2.2. Построить проверочные матрицы кода в систематическом, упорядоченном и модифицированном (с проверкой на четность) виде.
2.3. Построить порождающую матрицу кода.
2.4. Сформировать системы проверочных и синдромных уравнений.
2.5. Сформировать кодовое слово исследуемого кода, ввести одиночную ошибку и показать ее исправление путем вычисления синдрома, а также по схеме декодера в процессе работы.
2.6. Показать на примере, что код не гарантирует обнаружение тройных ошибок.
3. Порядок выполнения задания по пункту 1.3.
3.1. Произвести первичное декодирование принятого сообщения, закодированного кодом Хэмминга. При этом осуществить обнаружение и исправление ошибок в кодовых словах, используя методику исправления с вычислением синдрома.
Содержание отчета
1. Наименование и цель работы.
2. Исходные данные для выполнения работы.
3. Результаты выполнения работы по п.п.2.1-2.6, 3.1.
4. Выводы с оценкой корректирующих свойств кода Хэмминга.
Дата добавления: 2018-05-12; просмотров: 304; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!