Спирина, М.С. Дискретная математика

счет канала. Тогда разность А/, = Н(Х1пр) - I{Xinp, Хош) и будет мерой потери информации. Оставшийся «полумесяц» — множе­ ство Хт1\Х1пр — это то, чего не было на входе, но появилось на выходе, т.е. шум, а изменение информации, связанное с этим, равно Д/2 = Н(Х0Ш) - I{Xinp, ХоШ). В задачи помехоустойчивого кодирования входит обнаружение и исправление ошибок третьего вида. Эта цель достигается введе­ нием избыточной информации. Избыточность информации можно получить аппаратными (схемными), логическими и информаци­ онными средствами. Конечно, для обнаружения ошибки можно перепроверить ре­ зультат другим способом, например применив другой математи­ ческий метод. Но эта перепроверка сможет только установить на­ личие ошибки. Другой способ обнаружения ошибки заключается в удвоении каждого символа. Например, слово «март» можно закодировать в слово «ммаарртт». Тогда, в случае искажения одного из символов, ошибку можно обнаружить по второму, неискаженному символу. Так, получив искаженное слово «ммаарртс», мы должны прове­ рить оба варианта гипотез: «марс» и «март». При кодировании неизбежно возникает избыточная информа­ ция (шум), поэтому ставится задача сведения этой избыточности к минимуму. Теоремы Шеннона. Существует несколько десятков разнообраз­ ных методов распознавания и коррекции ошибок кодирования, предназначенных для каналов связи с различными характеристи­ ками помех. Выдающимся достижением в теории кодирования являются теоремы, сформулированные и доказанные Клодом Шенноном, о том, что при любых помехах и шумах возможна передача ин­ формации с минимумом потерь. Оговоримся, что здесь мы дадим популярную интерпретацию теорем Шеннона, так как их факти­ ческая формулировка оперирует с такими понятиями теории ве­ роятностей, как «условная вероятность», «условное распределе­ ние», и выходит далеко за рамки вузовской программы. Строгое доказательство теорем основано на неравенстве Фано. Согласно первой теореме Шеннона, если канал передачи не содержит собственных помех, то возможно так закодировать со­ общение, чтобы среднее число элементов кода (двоичных симво­ лов), приходящихся на один элемент кодируемого алфавита, было минимальным. Это так называемое эффективное статистическое кодирование. Первая теорема Шеннона утверждает, что вероятность ошибок при передаче информации сколь угодно мала, если энтропия S множества передаваемых сообщений меньше пропускной способ­ ности канала связи С, определяемой как наибольшее число бит, 318