ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА

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

В ряде случаев эта сложность связана с тем, что число операций (или, что одно и то же, объем памяти), которое требуется выполнить при декодировании, экспоненциально увеличивается с ростом Этот недостаток характерен для метода декодирования любых случайных кодов (в том числе и групповых). Другие методы декодирования требуют выполнения весьма сложных, с трудом поддающихся автоматизации вычислений, последовательность которых определяется громоздкой логической схемой. Этим недостатком обладает алгоритм Питерсона для декодирования кодов Боуза — Чоудхури.

Именно поэтому в последнее время внимание многих исследователей обращено на разработку методов декодирования, допускающих автоматизацию с помощью реально осуществимого (по объему и быстродействию) оборудования. Таким образом, задача построения оптимальных и близких к ним кодов вытесняется задачей построения кодов с простым алгоритмом декодирования, обеспечивающих вместе с тем достаточно хорошее использование избыточности.

Одним из наиболее перспективных в этом отношении является весьма интенсивно развиваемое направление, известное в литературе по теории кодирования как последовательное декодирование.

Разработанное впервые Возенкрафтом и Рейффеном и усовершенствованное в дальнейшем другими авторами последовательное декодирование является асимптотически оптимальным (в смысле Шеннона), причем число операций, необходимое в среднем для декодирования одного символа, пропорционально величине Однако алгоритм последовательного декодирования (а значит, и требуемая для его реализации аппаратура) все еще остается довольно сложным. Это заставляет искать новые, более простые методы декодирования. Исследованию одного из таких методов, по-видимому, предельно простого, посвящается предлагаемая читателю книга Месси. В ней описываются коды (главным образом непрерывные), для которых существуют так называемые разделенные или ортогональные проверки.

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

при условии, что

а равенство имеет место только тогда, когда Это значит, что любой символ входит не более чем в одно из сиотношений (1), называемых разделенными или ортогональными проверками, а символ а, не входит в правую часть ни одной из этих проверок.

Добавим к разделенным проверкам (1) тривиальное соотношение

и при декодировании будем определять символ а, из уравнений (1) и (2), в правую часть которых

подставляются принятые кодовые символы (некоторые из них искажены помехами). Из свойств ортогональных проверок следует, что искажение кодовых символов может привести к искажению результатов не более чем проверок.

Таким образом, при наличии ошибок среди символов, участвующих в декодировании символа символ а; будет правильно определен не менее чем в случаях. Последнее соображение позволяет при декодировании символа применить мажоритарный принцип, т. е. определять а; «по большинству голосов». Это обеспечивает правильное декодирование символа во всех случаях, когда

Для линейных кодов соотношения (1) являются линейными [над полем и техническое осуществление мажоритарного декодирования выполняется предельно просто. Схема, реализующая мажоритарное декодирование символа содержит мажоритарный элемент (т. е. устройство, осуществляющее выбор а, «по большинству голосов»), сумматоры и устройства умножения элементов поля причем для двоичных кодов устройства умножения ненужны.

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

Широкие перспективы перед мажоритарным декодированием открылись только тогда, когда была показана возможность его применения к некоторым классам блоковых циклических и сверточных непрерывных кодов. Для этих кодов при сдвиге (в случае блоковых кодов — циклическом) система ортогональных проверок для символа переходит в систему ортогональных проверок для символа Поэтому схема мажоритарного декодирования для одного символа может быть использована для последовательного декодирования (один за другим) всех символов кода.

Существенным достоинством мажоритарного декодирования является также и то, что, кроме всех ошибок кратности исправляется и некоторая часть ошибок более высокой кратности.

Кроме того, при незначительном изменении мажоритарного устройства можно часть корректирующей способности кода использовать для обнаружения (а не только для исправления) ошибок или наряду с ошибками исправлять также и стирания кодовых символов.

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

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

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

Одним из главных недостатков многих методов декодирования непрерывных кодов является эффект так называемого «размножения» ошибок. Автор уделяет ему достаточно внимания и указывает некоторые меры борьбы с этим недостатком.

Весьма важным и интересным является предложенное автором обобщение мажоритарного декодирования, при котором символ определяется не простым «голосованием», а «голосованием» с весом,

причем весовые множители зависят от статистики ошибок.

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

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

Две главы книги Месси посвящены описанию мажоритарного (или порогового) декодирования применительно к блоковым кодам. В отличие от непрерывных кодов, исследование которых отличается исключительной полнотой и содержит много интересных и важных результатов, блоковые коды исследованы в книге Месси значительно менее подробно. Однако и для блоковых кодов автор получил важные результаты.

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

Во-вторых, введенный автором процесс ортогонализации в L шагов представляет принципиальное обобщение метода мажоритарного декодирования применительно к блоковым кодам. Этот вопрос не нашел сколько-нибудь полного разрешения в книге Месси, но можно ожидать, что дальнейшие исследования в этом направлении существенно расширят класс блоковых кодов, к которым можно будет применить методы мажоритарного декодирования.

Месси не рассматривал методов построения блоковых кодов, допускающих мажоритарное декодирование. Единственные результаты в этом направлении получены в Советском Союзе В. Д. Колесником и Е. Т. Мирончиковым. Они изложены в диссертациях

авторов и их совместной статье «Некоторые циклические коды и схема декодирования по большинству проверок».

Предложенные достаточно общие методы построения блоковых циклических кодов, допускающих мажоритарное декодирование, использованы для построения большого числа конкретных кодов. Системы разделенных проверок для сумм некоторых символов, являющиеся основой ортогонализации в L шагов, также рассмотрены Мирончиковым и Колесником при совершенно ином подходе к решению задачи. Авторы указали некоторые способы построения кодов, для которых существуют такие системы проверок. Наконец, введенные ими «связанные» проверки совершенно не рассмотрены Месси.

Таким образом, книга Месси и работы Колесника и Мирончикова чрезвычайно удачно дополняют друг друга и в совокупности позволяют составить достаточно полное представление о современном состоянии и основной проблематике теории мажоритарного декодирования.

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

Э. Л. Блох

ПРЕДИСЛОВИЕ АВТОРА

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

Пороговое декодирование представляет собой метод исправления ошибок, особенно удобный для технической реализации. Для того чтобы подчеркнуть техническую точку зрения, мы уделяем значительное внимание вопросам создания простых логических схем, осуществляющих исправление ошибок. Мы надеемся, что эта книга будет стимулировать развитие других практических методов декодирования, обязательной чертой которых явится невысокая стоимость оборудования на передающем и приемном концах. (С удовлетворением отмечаем, что корпорация «Кодекс» уже изготовила кодирующее и декодирующее устройство, основанное на принципах порогового декодирования.)

Расположение материала позволяет облегчить переход от теории к практике. Идеи порогового декодирования сформулированы главным образом в гл. I. В гл. II описываются сверточные коды, а три

следующие главы посвящены специальным сверточным кодам для порогового декодирования, схемам декодирования и характеристикам декодирования. Гл. VI и VII посвящены приложению порогового декодирования к блоковым кодам.

От читателя не требуется никакой специальной подготовки: предполагается лишь общее знакомство с теорией вероятностей. Там, где используются алгебраические сведения (а их в книге немного), они всюду поясняются. Вообще, алгебраический подход используется только там, где он углубляет понимание рассматриваемых понятий; там же, где можно обойтись без алгебраических методов, используются другие средства: например, линейные коды трактуются на основе теории линейных уравнений, а не теории групп. Считается, что книга Питерсона «Коды, исправляющие ошибки» должна быть знакома любому серьезному работнику в области методов кодирования. К этой книге мы отсылаем читателя всякий раз, когда это оказывается полезным. Для дальнейшего чтения автор предложил бы книгу Фано «Передача информации», которая во всей полноте излагает развитие основ теории информации, и важную монографию Возенкрафта и Рейффена «Последовательное декодирование», в которой сверточные коды рассматриваются с иной точки зрения, чем принятая в нашей книге.

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

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

армией США, научно-исследовательским отделом ВВС и исследовательским отделом ВМФ.

Я также хочу выразить признательность за помощь, оказанную издательством и вычислительным центром Массачусетского технологического института и Ассоциацией национального научного фонда США (1959—1962).

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

Джеймс Л. Месси

Нотр-Дам, Индиана,

27 апреля 1963 г.