63. Принцип реализации двоичного кода с проверкой на четность. Достоинства и недостатки данного вида кодирования.

Формула его работы:

n=n₀+1

Это означает, что к “n₀” информационным элементам неизбыточного кода добавляется только один проверочный элемент.

Причём если данная кодовая комбинация (n=n₀+1) содержит чётное число единиц в информационной части n0, то на передающей стороне добавляется проверочный элемент, имеющий значение”0”. Если же в кодовой комбинации нечётное число единиц в информационной части, то на передающей(!) стороне в конце кодовой комбинации “1”.

Пример:

На приёмной стороне тракта передачи кода декодирующее устройство контролирует чётность числа информационных единиц с помощью переключаемого триггера. При этом анализирует как принятый проверочный элемент (“0 или 1”), так и чётность принятых информационных единиц.

Если, например, проверочный элемент 0, а число единиц в n₀ – чётное, то это разрешённая комбинация и сигнал проходит на выход декодера.

Достоинства: обеспечивается защита от любых единичных (!) ошибок (=1) в кодовой комбинации.

Недостатки: Ошибки при этом только обнаруживаются, но не исправляются (не корректируются).

64. Алгоритм определения кодового расстояния для конкретных кодовых комбинаций при использовании кода Хэмминга. Достоинства и недостатки кода Хэмминга. Порядок построения кода Хэмминга.

Для того, чтобы определить кодовое расстояние для конкретных кодовых комбинаций, необходимо производить сложение по модулю 2 соответствующих элементов (единиц) в табличных записках кода.

Сложение по модулю 2 обозначается и производится без переноса единицы в старший разряд, т.е. 1 1=0; 1 0=1)

Так, например, если заданы две комбинации 5-разрядного, то суммируя поразрядно “по модулю 2”, получим:

0 1 0 0 1

0 1 1 1 0

0 0 1 1 1.

Теперь определяем общее (суммарное) количество единиц в результате этого суммирования, которое и будет искомым кодовым расстоянием:

D = 3 (три единицы в сумме по модулю 2)

Далее, используя известную нам формулу для d_min:

получаем Δ = S = 1, что означает:

рассматриваемые кодовые комбинации могут передаваться с обеспечением только обнаружения двукратной ошибки или обнаружения однократной ошибки и исправления ее.

Определим избыточность этого кода (в данном примере).

n = 5 (пятиразрядный код) при передаче 4-х комбинаций.

Т.к. комбинаций 4, то для их составления достаточно двух символов, т.е. n₀ = 2. Тогда избыточность .

Достоинства: код позволяет исправлять (корректировать) однократные ошибки

Недостатки: позволяет только обнаруживать – двукратные ошибки.

Порядок построения кода Хэмминга следующий:

1. Определяется необходимое количество информационных “n₀” и проверочных “k” разрядов.

Количество n₀ информационных разрядов определяется необходимым числом кодируемых комбинаций (2ⁿ⁰).

Количество проверочных разрядов k определяется из условия:

или

Код Хэмминга, следовательно, должен иметь разрядов.

2. Число проверок на чётность в дальнейшем будет равно числу проверочных разрядов “k”.

Все проверки заключаются в вычислении суммы по “модулю 2” кодовых элементов в соответствующих разрядах кодовой комбинации.

При первой проверке выбираются те разряды кодов, двоичный номер которых содержит единицу в первом разряде, т.е. 1, 3, 5, 7, 9-й и т.д.

При второй проверке выбираются разряды, двоичный номер которых содержит “1” во втором разряде, т.е. 2, 3, 6, 7, 10-й и т.д.

При третьей проверке вбираются 4, 5, 6, 7, 12, 13-й разряды и т.д.

3. Место расположения проверочных разрядов в кодовой комбинации в принципе может быть выбрано произвольным(!), однако, при выбранном правиле проверок (см. п. 2) удобнее их размещать в разрядах, номера которых равны целой степени числа 2, т.е. в 1-м, 2-м, 4-м, 8-м и т.д.

4. Способ заполнения проверочных разрядов определяется правилом проверки корректирующего кода (проверкой на чётность с учётом рекомендаций п. 2 по номерам проверяемых разрядов при соответствующих порядковых номерах проверок).

После приёма кодовой комбинации делается проверка её наличия в кодовой таблице и, если этой комбинации там нет, тогда делаются “k” проверок на чётность. Результаты проверок в виде символов “0” или ”1” записываются справа-налево и образуют контрольное число, соответствующее номеру искаженного разряда в проверяемой кодовой комбинации.