Cтраница 4
Код Хэмминга является самым известным результатом теории кодирования, а его автор - самым удивительным из ученых, работавших в этой области. Дело в том, что Ричард Весли Хэмминг имеет лишь две публикации в области теории информации. Поэтому появление этой второй публикации Р. В. Хэмминга является в теории информации событием незаурядным. [46]
Посмотрим, как выглядят основные понятия теории универсзльного кодирования в применении к стационарным источникам. [47]
Среди методов получения оценок, используемых в теории кодирования, основными являются методы, основанные на максимальном заполнении и минимальном покрытии данного множества подмножествами определенного вида ( оценки Хем-минга [46], Гилберта [43], Варшамова [3]), а также метод случайного выбора кодирования, связанный с отысканием среднего значения рассматриваемого параметра. Однако, как правило, нижняя и верхняя оценки, полученные с помощью этих общих методов, существенно отличаются друг от друга. [48]
Настоящий раздел представляет собой обзор основных результатов теории кодирования. Главный упор в нем делается на описании конструкций и методов получения оценок. [49]
В работе развиваются и уточняются некоторые положения теории кодирования для каналов связи с шумами. Прежде всего с помощью уточнения рассуждений, основанных на методе случайного кодирования, дается оценка сверху вероятности ошибки при оптимальном кодировании в случае конечного дискретного канала без памяти. Затем выводится уравнение, позволяющее определить пропускную способность канала с конечным числом состояний в том случае, когда состояния могут быть вычислены и на передающем и на приемном концах. Анализируется также более сложный случай, когда состояние вычислимо на передающем конце, но не обязательно вычислимо на приемном конце. [50]
Нек-рые новые конструкции и методы получения границ, разработанные в теории кодирования, привели к существенному продвижению в вопросах, на первый взгляд весьма далеких от традиционных задач теории кодирования. Здесь следует указать на использование максимального кода с исправлением одной ошибки в асимптотически оптимальном методе реализации функций алгебры логики контактными схемами; на принципиальное улучшение верхней границы для плотности упаковки и-мерного евклидова пространства равными шарами; на использование неравенства ( 1) при оценке сложности реализации формулами одного класса функций алгебры логики. Идеи и результаты теории кодирования находят свое дальнейшее развитие в задачах синтеза самокорректирующихся схем и надежных схем из ненадежных элементов. [51]