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

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 8 Сборник переводов Под редакцией А. А. ЛЯПУНОВА и О. Б. ЛУПАНОВА ИЗДАТЕЛЬСТВО «МИР» Москва 1971 УДК 619. 95 Научный совет по кибернетике Академии наук СССР Восьмой выпуск серии кибернетических сборников посвящен математическим вопросам кибернетики. В нем содержатся статьи по теории кодирования, теории графов, теории автоматов (детерминированных и вероятностных) и теории алгоритмов. Смежные вопросы теории автоматов и теории алгоритмов обсуждаются в статьях Р. Стириза и М. Рабина. Особый интерес представляют статья С. Кука и С. Аандераа, в которой предлагается новый подход к оценкам сложности алгоритмов, а также небольшая статья Д. Клейтмана и Б. Ротшильда, в которой дано решение одной метрической задачи из теории графов. Сборник рассчитан на научных работников, инженеров, аспирантов и студентов различных специальностей, занимающихся и интересующихся кибернетикой в ее математическом аспекте. Редакция литературы по математическим наукам Инд. 2-2-3 10-71 Верхняя граница для k/n аффинно инвариантных кодов с фиксированным d/nl) Т. Касами Приводится верхняя граница скорости передачи k/n для двоичных циклических кодов, расширения которых инвариантны относительно аффинной группы перестановок. Как следствие показано, что скорость передачи k]n любого аффинно инвариантного кода с фиксированным d/n (d — минимальный вес) стремится к нулю с ростом длины кода п. Это утверждение является расширением результата Лина и Велдона для примитивных БЧХ-кодов. 1. ВВЕДЕНИЕ Пусть С означает двоичный циклический код длины п = 2?п— 1. Расширение кода С получается из кода добавлением слева одной позиции, являющейся проверкой на четность. Компоненты каждого кодового вектора расширенного кода нумеруются теперь следующим образом: первой компоненте ставится в соответствие 0, второй соответствует единица, i-й (i > 2) соответствует аг'~2, где а — примитивный элемент из GFBm). Под аффинным преобразованием с параметрами a, b из GFBm), аФ0> понимается перестановка, переводящая символ с позиции X в позицию аХ + Ь. Код будем называть инвариантным относительно аффинной группы, если любая аффинная перестановка переводит каждое кодовое слово в некоторое другое кодовое слово. В работах [1, 2] было показано, что расширение примитивных БЧХ-коДов (т. е. БЧХ-кодов длины 2т—1 с добавленной позицией, являющейся проверкой на четность), а также коды Рида — Маллера инвариантны относительно аффинной группы. Пусть *--натуральное число, меньшее 2т. В системе счисления по основанию 2 число i представляется в следующем виде: m-l '•=2 6/2', (i) где 0<6<<1. Число ненулевых 6* будем называть весом / и обозначать w(i). Для любого заданного i пусть J (i) означает множество л/« l\ihvSTml T,-\An uPPer bound on kln f°r affine-invariant codes with fixed a/n7 IEEE Trans. Inf. Theory, IT-15, № 1, part 1 A969), 174—17a 6 Т. Касами всех ненулевых целых /, таких, что m-l где 0 < at < 6* для 0 < / < т. Следующая теорема была доказана в работе [2].