Cтраница 2
Этот метод заимствован из теории линейных циклических кодов: каждая цифра ключа рассматривается как коэффициент полинома. Затем этот полином делится на некоторый заранее выбранный полином, один и тот же для всех ключей. Коэффициенты полинома-остатка от деления образуют адрес, соответствующий ключу. Из теории кодов с исправлением ошибок известно, что, если полином-делитель выбран правильно, все ключи, имеющие определенное минимальное расстояние по Хэммингу, будут преобразовываться в различные адреса. [16]
Цель настоящей главы состоит в изучении языков, распознаваемых автоматами с конечным числом состояний. Языки этого типа были введены Клини [1956] и названы им регулярными языками. В § 1 мы даем определение автомата и приводим общие алгебраические свойства автоматов. Главным результатом здесь является тот факт, что синтаксический моноид распознаваемого языка L конечен и совпадает с моноидом переходов минимального автомата, распознающего L. Параграф 2 содержит характеризацию распознаваемых языков в терминах формальных грамматик ( см. гл. Применяя к теории кодов вероятностный подход, мы используем в § 4 теорему Клини для получения некоторых ха-рактеризаций рациональных префиксных кодов. В § 5 рассматривается связь между языками и их синтаксическими моноидами. Центральной здесь является принадлежащая Эйленбергу [1976] теорема, устанавливающая взаимно однозначное соответствие между псевдомногообразиями конечных моноидов и некоторыми семействами рациональных языков, которые здесь называются потоками языков. Это соответствие подробно исследуется в гл. [17]
Теория информации - одна из немногих наук, год рождения которых можно указать точно: 1948 г. - год публикации известной статьи основоположника этой науки Клода Шеннона. Не сбылись лихие надежды оптимистов, пытавшихся применять ее везде, где уместно произнести слово информация. Теперь ясно, что адекватной областью применения этой науки являются задачи передачи информации по каналам связи и ее хранения в условиях, когда есть возможность широко варьировать методы кодирования и декодирования информации. Общие теоремы кодирования, которым посвящена книга И. Чисара и Я - Кернера, дают границы для скорости передачи и вероятности ошибки, достижимые при оптимальном выборе метода передачи, и образуют, с математической точки зрения, специальную главу теории вероятностей. Другой раздел теории информации - теория кодов, исправляющих ошибки, - связан с конкретными построениями и реализацией методов передачи, приближающихся к границам, даваемым общими теоремами. Он основан на комбинаторных и алгебраических идеях и остается вне рамок книги. Подытоживая достижения теории информации за 35 лет ее существования, можно сказать, что развитие и удешевление вычислительной техники, совмещенное с успехами математической теории кодирования, привело к тому, Что параметры передачи, существование которых доказывают теоремы кодирования, превратились из технической утопии в техническую реальность, Эти теоремы служат компасом, определи ющим направление развития теории и практики кодирования, мерилом, измеряющим уже пройденный и еще остающийся впереди путь, и этим определяется их значение. [18]