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

нописи. Так, Бэкон, передавая сообщения с помощью букв А и В, зако­ дировал пятерками, состоящими из этих букв, весь латинский алфавит. Как известно, Лейбниц использовал принцип двоичного кодирования не только в своей двоичной арифметике, но также и в так называемой двухзначной логике. Кодирование информации преследует разные цели и поэтому использует различные методы. В качестве целей могут служить: • экономичность, т.е . уменьшение избыточности сообщений; • обеспечение максимальной пропускной способности канала связи; • надежность, т.е. защита сообщений от случайных искажений, помехоустойчивое кодирование; • сохранность, т.е. защита информации от постороннего досту­ па к ней; • повышение скорости передачи информации; • удобство физической реализации через соответствующие сред­ ства связи; • удобство восприятия сообщений. Иногда эти цели вступают в противоречие друг с другом. Так, надежность кода требует избыточности информации, а это неэко­ номично. Такую избыточную информацию содержат, например, многие финансовые документы, где денежную сумму записывают и числом, и прописью. Разработаны методы эффективного кодирования информации, позволяющие учитывать одновременно группу целей, решать ком ­ плекс задач. Методы эффективного кодирования информации. Как мы зн а ­ ем, для выявления ошибок в процессе передачи закодированной информации необходимо ввести информационную избыточность. Метод Шеннона—Фано. Один из самых эффективных путей кодирования основан на применении основной теоремы Шенно­ на для каналов без шума. Согласно этой теореме сообщение, с о ­ ставленное из букв некоторого алфавита, можно закодировать так, что среднее число двоичных символов на букву будет сколь угодно близко к энтропии источника этих сообщений, но не меньше этой величины. Это означает, что при выборе каждого символа кодо­ вой комбинации необходимо добиваться, чтобы знак нес макси­ мальную информацию, т.е. принятие каждым символом значений Ои 1 должно быть равновероятным, и этот выбор не должен зави ­ сеть от предыдущих значений символов. По имени авторов первых эффективных методов кодирования этот код получил название метода Шеннона—Фано. Для построения кода буквам алфавита ставят соответствие их частоты в порядке убывания вероятности. Затем их разделяют на две группы, уравнивая суммарные вероятности каждой группы. Процесс разделения на подгруппы продолжают до тех пор, пока 315