Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 04»

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 4 Сборник переводов Под редакцией А. А. ЛЯПУНОВА и О. Б. ЛУПАНОВА ИЗДАТЕЛЬСТВО «МИР» Москва 1967 УДК 519. 95 Научный совет по кибернетике Академии наук СССР Четвертый выпуск новой серии кибернетических сборников состоит из двух разделов: математические вопросы и математическая лингвистика. В первом из них помещены статьи по теории кодирования, линейному программированию и теории алгоритмов с оценками. Несомненный интерес у читателей вызовет впервые публикуемая в этом сборнике статья на весьма актуальную тему о вычислительной сложности алгоритмов (Хартманиса и Стириза). В раздел «Математическая лингвистика» включена работа Н. Хомского и Дж. Миллера, завершающая собой цикл статей, в которых обсуждаются математические модели языка. Сборник рассчитан на научных работников, инженеров, аспирантов и студентов различных специальностей, занимающихся и интересующихся кибернетикой в ее математическом аспекте^ Редакция литературы по вопросам математических наук Инд. 2-2-3 Математические вопросы Структура и свойства бинарных циклических алфавитов^) Дж. Мак-Вильяме Коды, которые могут использоваться для контроля ошибок в реальных системах передачи данных, ограничены природой передающей аппаратуры. Эти ограничения не связаны с главными функциями кода, хотя, конечно, они часто исключают большинство кодов, относительно которых в настоящее время что-либо известно. Например, код, который следует использовать для контроля ошибок и ретрансляции на линиях между центрами, коммутирующими данные, должен быть циклическим (или укороченным циклическим) кодом с 744 информационными позициями и 20 корректирующими позициями. Вычислительная проблема в этом случае локализуется на тех циклических кодах, которые имеют точно 20 корректирующих позиций и блоковую длину 764 или' больше, и. состоит в выборе такого кода, который является наиболее подходящим для контроля ошибок для конкретного канала. В данной статье дается процедура решения таких задач. В ней описывается, как определять циклические коды с фиксированной блоковой длиной и фиксированным числом корректирующих позиций, если, конечно, такие существуют, и даются некоторые методы нахождения числа кодовых слов каждого веса в данном коде. При известной статистике канала это позволяет оценить корректирующие свойства кода. Предлагаемая процедура основана на анализе алгебраической структуры циклических кодов, который проводится в разд. П. Разд. I содержит поэтапное описание процедуры без математического обоснования. Можно надеяться, что теория, приводимая в разд. П, окажется полезной в других приложениях. ВВЕДЕНИЕ В данной статье слово «алфавит» означает систематический код —код, в котором каждое кодовое слово содержит определенное фиксированное число k информационных позиций, значения которых являются произвольными, и фиксированное число п— k корректирующих позиций. Каждая цифра, стоящая в корректирующей позиции, является суммой значений, которые принимаются в определенном подмножестве информационных позиций.