1.5. ПРОСТЕЙШИЕ КОДЫ 2б

равными этим четырем информационным битам. Дополняем тремя проверочными битами, задавая их равенствами

Pi = + к + к,

Р2 = к + к + к,

Ps = к + к + к-Здесь + обозначает сложение по модулю 2: 0 + 0 = О, 0 + 1 = 1, 1+0=1, 1 + 1=0. Шестнадцать кодовых слов (7, 4)-кода Хэмминга выписаны в табл. 1.1. Декодер принимает 7-битовое

Таблица 1.1

(7, 4)-код Хэмминга

0 0 0 0 0 0 0 0 0 0 10 1 1 0 0 10 1 10 0 0 1 I 10 1 0 10 0 1 1 1 0 10 1 10 0 0 1 10 0 0 1

0 1110 10 10 0 0 10 1 10 0 1 1 10 10 10 0 1 1 10 1 10 0 0

1 10 0 0 10 1 10 10 0 1 1 1 10 10 0

1111111

слово V = 12, 1з, ц, pl, р2, рз). При передаче в этом слове произошло не более одной ошибки. Изображенный на рис. 1.4,6 декодер вычисляет биты

si = pi + il + 12 + is,

52 = P2 + 12 + ii + U,

53 = Рз + il + i2 + ii.

Трехбитовая последовательность (si, Sa, Sg) называется синдромом. Она зависит не от истинных информационных битов, а только от конфигурации ошибок. Всего имеется восемь возможных синдромов: один для случая отсутствия ошибки и по одному для каждой из семи возможных одиночных ошибок. Простая проверка показывает, что каждая из этих ошибок имеет свой единственный синдром. Таким образом, не составляет труда сконструировать цифровую логику, которая по синдрому локализует

соответствующий бит. После внесения исправления проверочные символы можно опустить. Две или более ошибки превышают возможности кодовой конструкции, и код будет ошибаться. Это означает, что он будет вносить неправильные исправления и выдавать искаженные информационные биты.

Идея этой кодовой конструкции, естественно, не меняется при перестановке позиций битов в кодовых словах. Все такие варианты называются (7, 4)-кодом Хэмминга.

ЗАДАЧИ

1.1. Исправляющие одну ошибку коды Хэмминга содержат 2" - 1 битов, т из которых являются проверочными битами.

а. Выпийть (и, k) для первых пяти нетривиальных кодов Хэмминга (начиная с m = 3).

б. Вычислить скорости этих кодов.

в. Выписать выражение для вероятности ре ошибки декодирования при условии, что код используется в двоичном канале с вероятностью ошибки q. Как ведет себя вероятность р с ростом п?

1.2. Руководствуясь рис. 1.4, сконструировать кодер,декодер для (15,11)-кода Хэмминга. Юпустить повторяющиеся детали (т. е. в принципе показать, как это можно сделать).

1.3. а. А1етодом проб и ошибок найти множество из четырех двоичных слов длиной 3, таких, что каждое слово находится от каждого другого слова на расстоянии, не меньшем 2.

б. Найти множество из 16 двоичных слов длиной 7, такое, что каждое слово находится от каждого другого слова на расстоянии, не меньшем 3.

1.4.а. Описать, как вырезать 88 кругов диаметром 1 дюйм («2,5 см) из листа бумаги шириной 8,5 дюйма и длиной 11 дюймов. Доказать, что нельзя вырезать более 119 кругов диаметром 1 дюйм.

б. Доказать, что нельзя найти 32 двоичных слова длиной 8, таких, что каждое слово отличается от каладого другого слова не менее чем тремя компонентами.

1.5. Доказать, что число k информационных символов любого блокового (п, й)-кода с минимальным расстоянием, не меньшим 2/-f I, удовлетворяет неравенству

п - k-\og, [l + (g 1) -Ь Q (g - 1)2 + . . . + () (g - !)

(граница Хэмминга для алфавита из q элементов).

1.6. Простейший пример кодовой конструкции, известной под названием «код-произведение», имеет вид

и 12 21

Проверка по столбцом -

i,+ i.fc,

-Проверка по строкам

/i./i,+i

Pk2+I.k, + 1

ЗАДАЧИ 27

где 12 символов верхнего левого блока являются двоичными информационными символами. Конструкция дает 1) (2+ 0. 12)-коД-

а. Показать, что Pk+i ki+i является проверочным символом и по строкам и по столбцам.

б. Показать, что данный код является кодом, исправляющим одну

ошибку.

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

г. Чему равно минимальное расстояние данного кода?

1.7. Доказать, что расстояние по Хэммингу обладает следующими тремя свойствами:

(i) d (х, у) О, причем равенство достигается тогда и только тогда, когда х = у:

(ii) d (X, у) = d (у, X);

(iii) выполняется неравенство треугольника d (х, у) d (у, г) +

+ d (х, г).

Функция расстояния, обладающая этими тремя свойствами, называется метрикой.

1.8.а. Показать, что кодй позволяет обнаруживать любую конфигурацию не более чем из d ошибок тогда и только тогда, когда минимальное расстояния кода ё больше d.

б. Показать, что код способен исправлять любую конфигурацию не более чем из t ошибок, если минимальное расстояние кода равно по меньшей мере 2+1.

в. Показать, что код можно использовать для исправления всех конфигураций не более чем из t ошибок и одновременного обнаружения всех конфигураций не более чем из d ошибок (d t), если минимальное расстояние кода не меньше d+ 1.

г. Показать, что код можно использовать для восстановления р стертых символов, если минимальное расстояние кода не меньше р + 1.

1.9.а. Показать, что если двоичный (15, 11)-код Хэмминга используется Б канале, который вносит две ошибки, то выход декодера всегда будет ошибочным.

б. Показать, как используя проверку на четность, расширить (15, 11)-код Хэмминга до (16, 11)-кода, исправляющего все одиночные и обнаруживающего все двойные ошибки. Чему равно минимальное расстояние этого кода?