3.2    Примеры кодов, исправляющих ошибки

Машинистка, печатая некоторый текст на русском или английском язы­ке, может сделать опечатки. Это обычно не мешает нам восстановить пра­вильный текст. И связано это с избыточностью языка. Например, избы­точность английского языка равна 70% ([10]). При передаче закодированной информации могут возникать помехи, которые исказят передаваемую ин­формацию. Поэтому необходимо уметь выявлять ошибки при передаче сообщений. Это делается за счет избыточности передаваемой информа­ции. Сначала мы рассмотрим схему (модель) передачи закодированного сообщенияот источника

информации

преобра­зователь сообщений источника в двоичную последова­тельность

кодер

моду­лятор

шум

канал

демоду­лятор

к получателю

информации

преобразователь двоичной последовательности в исходное сообщение для получателя

 

Исходная информация с помощью преобразователя преобразуется в по­следовательность двоичных символов, затем передается в кодер, где в неё вводится избыточность. Модулятор преобразует передаваемые ему симво­лы в сигналы, которые, в свою очередь, передаются по каналу. В процессе передачи сигналы подвергаются воздействию помех и шумов. Возникают искажения. Демодулятор преобразует искаженные (неискаженные) сигна­лы в последовательность двоичных символов. Декодер, используя избы­точность символов, обнаруживает и исправляет ошибки.

Рассмотрим примеры кодов, обнаруживающих ошибки.

Пример 1. Рассмотрим канал, по которому за время ^ передается один импульс типа "О" или "1". Вероятность ошибки равна р. Каждый символ а передается по каналу пять раз, т.е. в виде импульсов ааааа. При прие­ме полученную последовательность разбивают на блоки (по 5 символов в каждом). Если вероятность С|р3(1 — р)2 + С'\р1 (1 — р) + ръ мала, то блоки, содержащие не более двух 0 (из 5 возможных), декодируются как 11111, а блоки, содержащие не более двух 1, декодируются как 00000. Недостат­ком этого способа является большой объем времени (передача одного бита информации требует 5 • Ц времени).

Задача 1. Пусть передаются по каналу п символов и вероятность ошиб­ки при передаче равна р. Доказать, что вероятность к ошибок равна

С£р*(1-р)п_*.

Пример 2. Предположим, что мы имеем С* сообщений. Каждому со­общению поставим в соответствие последовательность длины п из 0 и 1, в которой число 1 равно к. Такое кодирование называется равновесным. Например, закодируем первые 10 чисел (цифр)

0 ->   (ООО 11)

1 ->   (001 01)

2 ->   (001 10)

3 ->   (010 01)

4 ->   (010 10)

5 ->   (011 00)

6 ->   (100 01)

7 ->   (100 10)

8 ->   (101 00)

9 ->   (110 00)

Здесь С| = 10. Возникновение одной ошибки при передаче такой по­следовательности приводит к блоку из 5 символов, в котором либо одна 1, либо 3 единицы, т.е. мы обнаруживаем наличие ошибки, не зная, в каком месте она произошла.

Пример 3. Рассмотрим множество сообщений мощности не более 2". Каждое сообщение закодировано в виде последовательности из 0 и 1.

(ai,..., ап).

Введем дополнителный символ an+i, удовлетворяющий условию ап+\ =

п

=      "ii'iiod'l)- Вместо последовательности (с/|..... а,,) будем передавать

i=l

последовательность (а\,..., ап, an+i). Число единиц в новой последователь­ности является четным. Если при передаче произошло нечетное число оши­бок (в частности, одна ошибка), то число единиц в переданной последова­тельности

а

і ап+1

является нечетным. Т.е. этим способом "проверки на четность" мы можем обнаружить только существование ошибок, если их число нечетное.

Задача 2. Предположим, что множество сообщений имеет мощность не более 104. Поставим в соответствие каждому сообщению а натуральное

число abed, т.е. а —>• abed, a,b,c,d Є {0,1,..., 9}. Вместо передачи по каналу последовательности abed будем посылать abede, где {e + a + b + c + d) = = 0(morf9). Что позволяет обнаружить такое кодирование при передаче?

ОТВЕТ: Мы обнаружим, что либо ошибки нет, либо 0 заменена на 9, либо цифра 9 заменена на 0, либо число ошибок не менее двух.

Пример 4 (R.W.Hamming, 1950). Приведем пример кода, исправля­ющего одну ошибку в словах длины 7, содержащих 4 бита информации. Именно, предположим, что нам необходимо передать последовательность а, Ь, с, d) из нулей и единиц. Рассмотрим вектор

/х\

У а

z

Ъ

с

С

где x + a + b + d = 0,       у + а + с эти условия в матричном виде. Пусть

/

Я =

W

d = 0,

z + b + c + d = 0. Запишем

V

10 10 10 1 0 110 0 11 0 0 0 1 1 1 1

\

/матрица, в которой г—й столбец имеет такие вхождения г, в, что

г = г • 2° + в • 21 + * ■ 22 = (гвг)2,

т.е. это цифры в двоичной записи числа г. Тогда Н-С = 0. Пусть получатель получает на выходе вектор

Я =

Если р - вероятность ошибки при передачи одной цифры, то вероятность того, что при передаче С допущено не более одной ошибки, равна у = = (1 — р)7 + 7(1 — р)6 • р. Например, если р = 0,1, то у = 0,998. Если у -вероятность близка к 1, то у нас есть уверенность, что вектор Я отличается от С не более, чем на одно вхождение (одну координату). Рассмотрим Е == Я - С. Тогда НЯ = НС + НЕ = НЕ. Если Я = С. то Е = 0 и НЕ = 0. Если Я ф С. то Е вектор-столбец, в котором одна координата равна единице, а остальные равны нулю. В этом случае НЕ - столбец Н, номер г которого в Н совпадает с номером координаты, равной 1 в Е. Например, если

Я

0 1 1

о 1

V1/ то Н ■ Я

/101010^

0 110 0 11 0 0 0 1 1 1 1 /1 \

о 1 1 о 1

V1/ /Л

1

V1/

/о\

о о о о о 1

Vі/

а) Если R

Упражнение 1.

/і\

1 1 О О 1

\Ч /о\

о о 1 о о

Vі/ /о\

1 о 1 о 1

б) если R =

в) если R

т.е. С

О 1 1 О

1

то проверить, что Я • R

1

Vі/

и С

то HR =

/Л і

и

С =

о 1 1 о о

Vі/

то Я • Я = О и С = R:

1 1 О

о ог) декодировать слово (вектор)

о 1 1 о 1 1

V1/

Перед изложением нижеследующих примеров 5-7 приведем необходимые сведения из теории коммутативных колец.