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

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 10 Сборник переводов Под редакцией |а. а. ляпунова|и о. б. лупанова ИЗДАТЕЛЬСТВО «МИР» Москва 1973 УДК StMB Десятый выпуск серии кибернетических сборников состоит из трех раз- разделов: математические вопросы; вопросы машинного перевода; вычислитель- вычислительные машины и мышление. В первом разделе представлены работы по теории кодирования, теории графов, синтезу управляющих систем, теории алгоритмов и по математиче- математической лингвистике. Особый интерес представляют статьи А. Шёнхаге и В. Штрассена, в которой описывается новый алгоритм умножения я-разряд- иых чисел, требующий немногим более n\gn операций, а также работа Н. Дж. А. Слоэна, содержащая обзор последних результатов по конструк- конструктивным кодам. Ко второму разделу относится статья Б. Вокуа, Ж. Вейона, Н. Недо- бежкина, С. Бургиньона, содержащая изложение работ французских ученых в области машинного перевода. В третьем разделе помещены статьи Э. Фейгенбаума и Л. Шиклошши, посвященные исследованиям в области искусственного интеллекта. Первая из них содержит подробный обзор работ последних лет в этой области. Сборник рассчитан на научных работников, инженеров, аспирантов и студентов различных специальностей, занимающихся и интересующихся мате- математической кибернетикой и ее приложениями. Дж. А. Слоэн ') 1. ВВЕДЕНИЕ Эта статья представляет собой обзор современных резуль- результатов по построению блоковых кодов для исправления случай- случайных ошибок. В 1948 г. Шеннон [98] показал, что существуют коды, кото- которые достигают малой вероятности ошибки на скоростях, близ- близких к пропускной способности. В 1952 г. Гилберт [31] получил нижнюю границу для din для наилучших кодов с заданной ско- скоростью. С тех пор было потрачено много усилий на то, чтобы построить сколь угодно длинные коды, которые лежат или под- подходят близко к границе Гилберта, но попытки пока не увенча- увенчались успехом (исключение составляют коды со скоростями, стремящимися к 0 или 1). Для умеренных длин блока, однако, были открыты многие хорошие коды. Хорошо известными среди них являются коды Рида —Маллера (РМ) ([79], [93], [В1, гл. 15]), Боуза — Чоудхури —Хоквингема (БЧХ) ([19], [45], [В!, гл. 7 и 10]) и квадратично-вычетные (KB) коды ([В1, гл. 15], [111, § 4. 4]). Систематическое описание этих и других кодов, открытых до 1968 г. , можно найти в [В1]. В этой статье будут описаны некоторые достижения теории кодирования, которые имели место после появления работы [В 11. Мы сосредоточим внимание на тех работах, которые по- посвящены построению новых кодов или представляют новые свойства ранее известных кодов. Важными темами, которые не рассматриваются здесь, являются нумераторы весов кодов [7, 8, 10, 14, 15, 32, 41, 53—57, 73, 81, 86, 94, 100, 106, 114], класси- классификация смежных классов кодов [9, 16, 94, 103], методы декоди- декодирования и исправление пакетов ошибок [20, 85, 95, 109, ПО], установление синхронизации [105], кодирование для источника и теория передачи с заданной мерой искажения [6, 47].