Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Пусть р° — некоторая точка единичного /-мерного куба,
Определение. Совокупность (р°) точек 0 таких, что р(р°, р) < р, называется шаром с центром в р° и радиусом р.
Определение. Совокупность +0 (0°) точек р таких, что р{р°, 0) =*^, называется сферой с центром в 0° и радиусом р.
294
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
Очевидно, что если точка Р° является «кодовой» точкой, то при передаче по каналу связи, в котором действует источник помех, вызывающий не более р ошибок, точка р° перейдет в точку р такую, что
р(Р°, Р)<Л
т. е. точка р будет принадлежать шару С/7 ((3°) с центром в р“ и имеющему радиус р. Отсюда вытекает следующий факт.
Теорема 10. Для того чтобы множество II, принадлежащее единичному 1-мерному кубу, было множеством, принадлежащим самокорректирующемуся коду относительно источника помех, вызывающего не более р ошибок, необходимо и достаточно, чтобы для любых р' и р" (р'^р") из Н имело место
р(р', У')> 2р + 1.
Для доказательства лишь заметим, что условие р(Р7 Р")^2р-Ь1 эквивалентно тому, что шары Щ (|3') и и[‘ (Р") с центрами в р' и р" и имеющие радиусы р, не пересекаются. Последнее означает, что коду, полученному на выходе капала связи, соответствует точка, которая принадлежит ровно одному шару.
Данная теорема дает геометрический подход для построения самокорректирующихся кодов. С ней также связано и следующее утверждение.
Теорема 11. а) При 1 = 2' — 1 единичный 1-мер-иый куб может быть разбит в прямую сумму единичных шаров (т. е. шаров с радиусом 1).
б) При / = 2‘ единичный 1-мерный куб может быть разбит в прямую сумму единичных сфер.
Доказательство, а) В единичном ^-мерном кубе с I — 2‘ — 1 возьмем код Хэмминга Н}. Очевидно, имеем
А — I, тп = 2( — I — 1.
Около каждой точки из Н\ опишем шар радиуса 1. Покажем, что система всех таких шаров и задает искомое разбиение. Данные шары попарно не пересекаются (см. теорему 9). Отсюда сумарное число точек, содержащихся в
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ 295
этой системе шаров, раБно
(/ + 1) 2™ - « 22'-1 = 21.
Значит, эта система шаров содержит все точки единичного /-мерного куба.
б) Пусть 1 = 2‘. При фиксированной последней координате единичный /-мерный куб может быть «разрезан» на два единичных I— 1-мерпых куба. Для этих кубов существует естественное взаимно однозначное соответствие (1° ** где
... Р.-., 0), ..., р,.,. 1).
Так как I — 1 = 2* — 1, то / — 1-мерный единичный куб на основании пункта а) может быть разбит в прямую сумму
Рис. 16 Рис. 17
единичных шаров. Выберем я одном из / — 1-мерных кубов разбиение в прямую сумму единичных шаров. Газ-биение в другом I — 1-мерном кубе можно построить, пс-полъзуя естественное взаимно однозначное соответствие между этими кубами. Рассмотрим пару соответствующих
шаров (см. рис. 16) (р°) и и\-х (Р1).
Два данных I — 1-мерных едшгачпых шара можно преобразовать в две /-мерные единичные сферы (рис. 17).
Б самом деле, I — 1-мерные единичные шары являются объединением I — 1-мерной единичной сферы и своего центра, т. е.
^ 1-1 (Р°)у1-1 Ф°) и от* г/г_1(Р1) = П-1 (РЧиГ).
Очевидно, что для /-мерных единичных сфер имеют лес-
296
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
то равенства
п плотит,
у] ([У) = уи(Р1)и Г>.
Таким образом, если осуществить это преобразование для всех пар соответствующих шаров разбиений, получим искомое разбиение куба в прямую сумму единичных сфер. Теорема доказана.
Определение. Кодовое множество, принадлежащее ^-мерному единичному кубу и являющееся самокорректирующимся для дапного источника помех, называется максимальным, если оно имеет наибольшую мощность.
Следствие. При I — 2* — 1 код Хэмминеа II] является максимальным.
ЧАСТЬ V
НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Глава 1
ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ § 1. Понятие Д.Н.ф.
Проблема минимизации булевых функций
Пусть задан алфавит переменных хп}.
Определение. Выражение
к = & , . . & х7г (Ь> ф I» при V Ф р)
называется элементарной конъюнкцией. Число г называется рангом элементарной конъюнкции. По определению считаем констаиту 1 элементарной конъюнкцией ранга 0.
Определение. Выражение
К = V К{ {Кхф К} при г ф /),
где Кл {I = 1, «) —элементарная конъюнкция ран-
га г<, называется дизъюнктивной нормальной формой {д. н. ф,).
Очевидно, что д. н. ф. Й реализует некоторую булеву функцию /(д?1, ..., а:«). Из гл. 1 части I следует, что для каждой функции ас„) и / #0 существует д. н. ф.
Й такая, что
^{хи . = 91.
В качестве такой д. н. ф. можно взять, например, совершенную д. н. ф. для /, а именно:
й =* \] I г • »
208
Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Пример 1. Рассмотрим функцию 1(хи х2, жэ), заданную таблицей 4. Ее можно представить в виде совершенной д. н. ф.
9*! ~Х 1X2X3 V XIX 2X3 V ХуХгХз V Х^гХз V $1X2X3.
С другой стороны, непосредственной проверкой убеждаемся, что эта функция может быть представлена другой д. н. ф. % ~ х^Хз V ху.
Данный пример показывает, что функция алгебры логики может быть представлена в виде д. н. ф., вообще говоря, не единственным образом. В связи с этим возникает возможность выбора более предпочтительной реализации. Для этого вводится индекс простоты ?(9*), характеризующий «сложность» д. н. ф.
