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

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК Сборник переводов Под редакцией А. А. ЛЯПУНОВА и О. Б. ЛУПАНОВА ИЗДАТЕЛЬСТВО «МИР» Москва 1968 УДК 519. 95 Научный совет по кибернетике Академии наук СССР Пятый выпуск новой серии кибернетических сборников состоит из двух разделов: математические, вопросы w некоторые технические реализации. В первом разделе представлены работы по теории кодирования, теории автоматов и статьи * (С. Гинзбурга и др. ) по математической лингвистике, также тесно связанные с теорией автоматов. Во втором разделе помещена оригинальная статья Ван Хао, посвященная некоторым проблемам неразрешимости. Сборник рассчитан на научных работников, инженеров, аспирантов и студентов различных специальностей, интересующихся кибернетикой в ее математическом аспекте. Редакция литературы по математическим наукам Инд. 2-2-3 математические вопросы Анализ рекуррентных кодов1} Э. Вайнер и Р. Эш I. Введение Двоичный корректирующий^ блоковый код может быть определен как множество двоичных n-мерных векторов-столбцов Х\ называемых «кодовыми словами» и удовлетворяющих множеству т проверочных уравнений А'Х' = 0 (mod 2), (1) где А— бинарная (тХп)-матрица. Предполагая, что уравнения (1) независимы, можно произвольно выбрать k = n— т символов X' (в качестве «информационных» символов); тогда остальные т символов (называемые «проверочными») будут определяться уравнениями (1). Если последовательность передаваемых информационных символов очень велика, кодовое слово можно рассматривать как полубесконечный вектор (последовательность) Ху удовлетворяющий проверочным уравнениям А 0 0 0 0 А 0 0 0 0 А 0 АХ-. Х = 0, (2) где А' есть (тХп)-матрица из (1). Следовательно, закодированное сообщение можно рассматривать как последовательность блоков из п символов, в которой символы различных блоков полностью независимы. На рис. 1 приведена блок-схема системы связи, в которой можно использовать такие коды. Передаваемая информация кодируется по k символов одновременно в блоки из п символов. l) Wyner A. D. , Ash R. В. , Analysis of recurrent codes, IEEE Trans, on Inf. Theory, IT-9, № 3 (1963), 143—156. Перевод статьи публикуется без приложений; в текст статьи внесены соответствующие изменения и замечания. — Прим. ред. б Э. Вайнер, Р. Эш Избыточность, включенная в передаваемое сообщение, используется в декодирующем устройстве для того, чтобы исправить ошибки, которые могли произойти из-за шума в канале. Выходом декодирующего устройства является последовательность исправленных информационных символов. В 1955 г. Элайес [1] предложил один тип корректирующего кода, названного им «сверточным» кодом, в котором кодовыми словами являются полубесконечные двоичные векторы. Эти коды отличаются от кодов (2) тем, что их матрицы не могут быть разбиты на блоки. Сверточные коды были переоткрыты в Информация Кодирующее устройство Закодированное сообщение Канал Полученное сообщение (У=Х+Е) Декодирующее устройство Исправленная информация Шум (£) Рис. 1.