Предисловие редакторов русского издания

Предлагаемая советскому читателю книга посвящена одному из центральных разделов теории информации — кодам, исправляющим ошибки. Она написана японскими учеными Т. Касами, Н. Токура, Е. Ивадари и Я- Инагаки. Первые два автора приобрели мировую известность благодаря своим работам по теории кодов.

Из переводных книг по теории кодирования наибольшую из вестность в нашей стране получила книга У. Питерсона «Коды, исправляющие ошибки» (издательство «Мир», 1964). В 1976 г. издательство «Мир» выпустило перевод второго издания этой книги, подготовленного У. Питерсоном совместно с Э. Уэлдоном. Во многих отношениях эта замечательная книга основана на работах, выполненных до 1970 г. Однако в семидесятых годах учеными разных стран был получен ряд новых результатов, существенно обогативших теорию кодирования и в известном смысле изменивших некоторые ее общие концепции. Данная книга японских авторов включает наиболее важные из этих результатов, такие, как коды Юстесена, коды Гоппы, каскадные коды, циклические арифметические коды и др.

Теория кодирования является прикладной наукой. Она черпает задачи из техники связи, радиолокации, измерительной, вычислительной и управляющей техники. Поэтому важное значение имеют применимость получаемых результатов, их конкурентоспособность по сравнению с некодовыми методами защиты от ошибок. Практические достижения теории кодирования сейчас хорошо известны. Однако наиболее широкое применение получили лишь самые примитивные способы кодирования, такие, как проверка на четность, коды Хэмминга, циклические проверки для обнаружения ошибок, простейшие сверточные коды и т. п. С точки зрения специалистов по теории кодирования, отставание в использовании более мощных и нетривиальных кодовых конструкций происходит из-за сложности восприятия инженерами математического аппарата теории и из-за недостаточной разработанности вопросов взаимосвязи кодирования и модуляции.

Книга японских авторов помогает преодолеть это отставание. Авторы излагают математические вопросы весьма обстоятельно, неторопливо, сопровождая текст многочисленными примерами и задачами учебного характера. Восточная

медлительность здесь выступает удачной альтернативой западной лаконичности, образцом которой служат произведения Н. Бурбаки. В книгу помещена специальная глава , посвященная реализации и применениям кодов. В этой главе рассматриваются принципы построения кодирующих и декодирующих устройств для циклических и сверточных кодов. Приводятся способы использования двоичных и других дискретных кодов в реальных каналах, которые по своей физической природе являются аналоговыми. Обсуждается проблема согласованного выбора методов кодирования и модуляции. Вводится новый параметр, измеряющий выигрыш при использовании кодирования в канале. Эта не претендующая на математическую строгость глава призвана сыграть важную роль связующего звена между теорией кодов и ее практическими применениями.

Хочется отметить, что теория информации сейчас находится в процессе развития. Поэтому ее достижения и тенденции за время, прошедшее после выхода в свет данной книги, не могли быть в ней отражены. К вопросам, не включенным в книгу, относятся, в частности, коды для многоисточниковых, широковещательных и многосторонних каналов, коды, исправляющие дефекты и ошибки, и коды, повышающие скрытность передачи. В настоящее время с этими достижениями можно ознакомиться лишь по журнальным и обзорным статьям.

При переводе и редактировании были исправлены некоторые опечатки, имеющие место в японском издании. Часть из них была любезно указана нам авторами, которым приносим глубокую благодарность.

С. И. Гельфанд, Б. С. Цыбаков

Предисловие авторов

К настоящему времени по теории кодирования вышли следующие монографии: книга Питерсона [1] и ее расширенный вариант — монография Питерсона и Уэлдона [2], оригинальная книга по алгебраической теории кодирования Берлекэмпа [3], книга Ван-Линта, систематизирующая алгебраическую теорию кодирования [4], прекрасное введение в теорию кодирования Лина [5] и большой труд Миякавы, Ивадари и Имаи [6]. Однако уже после выхода в свет этих книг Гоппа, Юстесен и др. получили ряд новых важных результатов.

В теории кодирования можно выделить следующие три раз дела: теорию алгебраических кодов, теорию сверточных колов и теорию кодов, используемых в арифметических устройствах. Все эти разделы тесно связаны друг с другом, но в то же время характеризуются собственным подходом к проблеме кодирования. В данной книге этим разделам посвящены соответственно главы 1—4; 5, 6; 8, 9. Каждый раздел, как правило, начинается введением основных понятий и заканчивается изложением сравнительно новых результатов. Авторы не претендуют на исчерпывающее изложение всего материала теории кодирования, скорее, они преследуют цель рассмотреть все наиболее важные моменты в развитии методов теории.

В гл. 7 подробно исследуются различные вопросы, связанные с применением теории кодирования. При первом знакомстве с теорией кодирования затруднения, как правило, возникают там, где используются понятия и результаты теории конечных полей. Поэтому в эту книгу было решено включить главу, в которой кратко рассматриваются основные понятия и результаты теория конечных полей, используемые в теории кодирования. Для понимания содержания книги достаточно знакомства с университетским курсом математики.

Разд. 1.1-1.4 гл. 1, а также гл. 3, 4 написаны Касами, гл. 2 — Токура, разд. 1.5 гл. 1 и гл. 5-7 - Ивадари, гл. 8 и 9 — Инатаки. Главы 1—4, 5—7 и 8, 9 можно читать почти независимо. Кроме того, читатели, знакомые с конечными полями, могут пропустить гл. 2 и приступить к чтению последующих глав, обращаясь к гл. 2 лишь по мере необходимости.

В гл. 1 вводятся основные понятия теории кодирования, в частности понятия, связанные с блоковыми кодами, определяется ряд границ, характеризующих предельные характеристики

блоковых кодов; в разд. 1.5 методом Галлагера доказана теорема кодирования Шеннона, которая в свое время послужила отправной точкой теории кодирования.

В гл. 2 рассматриваются группы, кольца, поля, векторные пространства, многочлены и другие понятия и результаты теории конечных полей в том объеме, который необходим для чтения статей по теории кодирования. Многие результаты теории кодирования формулируются в виде задач или утверждений.

В гл. 3 рассматриваются свойства линейных кодов и методы их кодирования и декодирования, свойства циклических кодов, являющихся подклассом линейных кодов, а также методы задания таких кодов. При этом подчеркивается значение алгебраической теории кодирования, которая изучает классы кодов с определенной алгебраической структурой и использует эту структуру для детального описания свойств кодов и построения для них эффективных алгоритмов кодирования и декодирования.

Алгебраическая теория кодирования содержит много результатов, которые заслуживают подробного рассмотрения, и поэтому выбрать материал для данной книги было довольно трудно. В гл. 4 основной акцент был сделан на пояснение различных методов теории кодирования, в соответствии с чем и отбирался материал для этой главы. В эту главу включены наиболее детально исследованные к настоящему времени БЧХ-коды и методы их декодирования, важные с практической точки зрения методы мажоритарного декодирования, играющие важную роль в теории многочлены Матсона — Соломона, полиномиальные коды, содержащие в качестве своих подкодов БЧХ-коды, некоторые классы кодов, допускающих мажоритарное декодирование, их двойственные коды, каскадные коды, строящиеся на основе нескольких кодов с меньшими значениями параметров, каскадные коды Юстесена, представляющие собой первый класс кодов, свойства которых не ухудшаются в области больших значений параметров. Она содержит также интенсивно исследуемые в настоящее время коды Гоппы (вообще говоря, не являющиеся циклическими), включающие как подкласс БЧХ-коды, методы декодирования кодов Гоппы и несколько отличающиеся от кодов, перечисленных выше, коды, исправляющие пачки ошибок. К сожалению, в этой книге не удалось рассмотреть квадратично-вычетные коды [2,3], нелинейные коды [6], обстоятельные работы, посвященные исследованию

структуры весов [3,4], проблему синхронизации [2] и некоторые другие важные вопросы.

Читателям, которые впервые хотели бы ознакомиться с основами теории блоковых кодов, рекомендуется изучить следующие разделы: 1.1-1.3, 1.4.1, помеченные знаком разделы гл. 2, 3.1-3.3, 3.5-3.7, 4.1, 4.2.1, 4.3, 4.8.

Гл. 5 и 6 посвящены сверточным кодам. Рассматриваемые в начале гл. 5 коды, которые допускают пороговое декодирование, имеют простые алгоритмы декодирования и могут быть легко реализованы, что очень важно с практической точки зрения. Методы построения и декодирования таких кодов главным образом являются алгебраическими и основаны на теории автоматов. Особое внимание в этой главе уделяется возможности практической реализации декодирования. Простое декодирование допускают рассматриваемые здесь коды, исправляющие независимые ошибки, коды, исправляющие пачки ошибок, диффузные коды, исправляющие независимые ошибки и пачки ошибок, равномерные коды, похожие на блоковые коды, образованные последовательностями максимальной длины.

При последовательном декодировании, которое рассматривается в гл. 6, число операций изменяется в зависимости от уровня шума, действующего в канале. Благодаря этому последовательное декодирование по своим характеристикам приближается к декодированию по максимуму правдоподобия и широко используется в реальных системах космической связи. Алгебраические методы для анализа этого метода декодирования не подходят. С помощью вероятностных методов для последовательного декодирования выводятся различные границы, в частности верхние и нижние границы для распределения выполняемых декодером операций, вероятности переполнения буфера, вероятности ошибки при декодировании и др. Анализ последовательного декодирования оказывается весьма сложным. Кроме алгоритмов последовательного декодирования, в этой главе рассматривается также алгоритм декодирования Витерби, который представляет собой алгоритм декодирования по максимуму правдоподобия. Сравнение сверточных кодов с блоковыми кодами показывает, что первые при декодировании с помощью алгоритма Витерби имеют лучшие характеристики; это один из важных выводов теории кодирования. Кроме того, в этой главе рассматривается гибридный метод декодирования, представляющий собой объединение последовательного и алгебраического декодирования, а также исследуется структура расстояний сверточных кодов.

В гл. 7 сначала описываются основные компоненты, входящие в состав кодирующих и декодирующих устройств, а также схемы кодирующих и декодирующих устройств для некоторых

кодов. Вторая часть этой главы посвящена проблемам, связанным с применением теории кодирования. Для развития теории кодирования использовались в основном методы современной алгебры и различные методы получения оценок; из-за сложности этих методов существуют трудности в понимании связи теории с теми реальными задачами, которые она призвана решать. Чтобы преодолеть эти трудности, в гл. 7 исследуется адекватность математических моделей их реальным прообразам и исследуются границы применимости теории кодирования. Основными объектами применения теории кодирования являются системы связи и вычислительные машины. В этой главе введено понятие выигрыша при применении кодирования в системе связи, дано несколько примеров систем связи с кодированием и показана целесообразность введения этого понятия. В разделах, посвященных применениям теории кодирования в вычислительных машинах, рассмотрены коды, исправляющие ошибки оператора при вводе информации в машину, а также коды, допускающие быстрое декодирование.

Тем, кто хочет ознакомиться лишь с основами сверточных кодов, рекомендуем прочитать разделы 5.1-5.8, 6.1 и 6.2. Читатели, которые интересуются лишь применениями теории кодирования, могут читать гл. 7 независимо.

В гл. 8 и 9 рассматриваются коды, предназначенные для обнаружения и исправления арифметических ошибок, возникающих в арифметических устройствах, в частности AN-коды. Кодовыми словами -кодов являются двоичные представления целых чисел, кратных числу А. Эти коды отличаются от всех кодов, рассматривавшихся до гл. 8. Поскольку для изложения теории таких кодов требуются дополнительные сведения о свойствах целых чисел и их двоичных представлений, то в начале гл. 8 приводятся основные понятия и результаты теории целых чисел, используемые в дальнейшем. Далее в гл. 8 дается определение -кода, описываются особенности ошибок, возникающих при выполнении арифметических операций, в частности при сложении и вычитании чисел, вводится арифметическое расстояние, играющее в теории арифметических кодов ту же роль, что и расстояние Хэмминга в теории алгебраических кодов, описывается несколько классов кодов, исправляющих одиночные и кратные ошибки, и исследуются их свойства.

Гл. 9 посвящена циклическим -кодам. Как и алгебраические циклические коды, циклические -коды обладают рядом достоинств и особых свойств. С помощью разложения целых чисел на простые множители и приведенной системы вычетов по ее подгруппе циклические ЛЛ-коды можно разложить на строго циклические коды и таким образом исследовать их структуру. Кроме того, это разложение указывает на систематический

метод построения циклических -кодов и позволяет оценить распределение весов кодовых слов. В конце главы кратко рассмотрены -коды, исправляющие пачки ошибок, арифметические коды с несколькими модулями, -ичные -коды и проведено сравнение -кодов и алгебраических кодов.

В заключение нам хочется поблагодарить С. Адзуми за составление табл. А. 1 и А. 2 приложения и внесение исправлений в гл. 1—4.

Авторы

Литература

(см. скан)