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

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

(кликните для просмотра скана)

(кликните для просмотра скана)

7.3.1. Задача теории кодирования

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

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

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

Фиг. 7.29. Модель системы связи.

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

7.3.2. Стоимость и надежность

Рассмотрим взаимосвязь между стоимостью и надежностью систем, использующих помехоустойчивое кодирование. На фиг. 7.30 показана связь между стоимостью и пропускной способностью различных систем связи. Как видно из фиг. 7.30, стоимость одного канала зависит от того, является ли система связи коаксиальной, микроволновой, системой миллиметрового диапазона и т. д., и снижается по мере роста суммарной пропускной способности системы связи. Что касается каждой конкретной системы, то ее стоимость возрастает из года в год только из-за повышения расходов на оплату обслуживающего персонала.

Фиг. 7.30. Стоимость линий связи.

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

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

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

7.3.3. Применение в вычислительных системах

Остановимся здесь на применении теории кодирования в вычислительных системах. Первым кодом, исправляющим ошибки, который стал применяться в вычислительных машинах, был разработанный еще на заре теории кодирования в 1950 г. код Хэмминга. Как указывалось ранее, этот код был разработан специально для применения в вычислительных машинах. Код Хэмминга стал применяться в вычислительных машинах не сразу, и это объясняется тем, что после появления кода Хэмминга постоянно совершенствовались сами запоминающие элементы; сначала использовались электронные лампы, далее появились параметроны, полупроводниковые элементы и наконец интегральные схемы. При этом надежность запоминающих элементов постоянно и быстро росла. Первой вычислительной машиной, в которой использовался код "Хэмминга, была вычислительная машина IBM 7030, а в Японии — машина DIPS фирмы Japan Telephone and Telegraph Public. Однако если первая была построена спустя 10 лет после появления кода Хэмминга, то вторая — спустя 20 лет. До этого времени в вычислительных машинах использовался лишь простейший способ повышения надежности, а именно проверка на четность (или на нечетность).

В последние годы различнее достаточно сложные коды, исправляющие большое число ошибок, начали применяться как в самих вычислительных машинах, так и в их периферийном оборудовании, в частности в накопителях на магнитной ленте. По мере развития вычислительной техники коды, исправляющие ошибки, будут играть все большую роль в повышении надежности вычислительных систем. Согласно Чену [2], для этого имеются следующие предпосылки:

I. При повышении скорости вычислений и плотности монтажа уменьшается отношение сигнал/шум.

II. Целесообразность использования с экономической точки зрения несовершенных элементов, в частности больших интегральных схем.

III. По мере увеличения числа вычислительных машин, использующих каналы связи, т. е. по мере расширения сетей вычислительных машин, возрастает объем информации, передаваемой в режиме «on line».

Указанные выше закономерности связаны между собой. Так, например, существует хорошо известный закон Гроша [3], устанавливающий связь между стоимостью и скоростью обработки информации в вычислительных машинах. Согласно этому закону, стоимость вычислений пропорциональна корню квадратному из скорости вычислений. Так, например, для снижения стоимости вычислений в 10 раз скорость вычислений должна быть увеличена в 100 раз. Однако если повышается скорость вычислений, то уменьшаются отношение сигнал/шум и, естественно, надежность. В этом случае обычно возникает необходимость вновь повысить надежность путем введения избыточности, которая существенно не повлияла бы на стоимость системы в целом. Еще одно обстоятельство, связанное с предпосылкой II, на которое следует обратить внимание, — это то, что в качестве оперативной памяти современных вычислительных машин начали использоваться полупроводниковые запоминающие устройства, стоимость которых, как указывалось, быстро снижается.

Для сравнения надежности полупроводниковых запоминающих устройств и запоминающих устройств на магнитных элементах рассмотрим, например, ЗУ средней емкости, состоящие из накопителей и периферийного оборудования. В ЗУ на магнитных элементах доля отказов из-за неисправности накопителя составляет 10—40%, а доля отказов из-за неисправности периферийных схем — от 60 до 90%. В то же время в полупроводниковых ЗУ доля отказов из-за неисправности накопителя достигает 70—95% и лишь 5—30% составляют отказы периферийного оборудования [4]. Таким образом, при использовании полупроводниковых ЗУ в качестве оперативной памяти возникает необходимость повышения надежности последней. Главным образом именно в связи с этим в настоящее время обсуждаются различные способы повышения надежности оперативной памяти с помощью кодов, исправляющих ошибки. Конечно, введение избыточности приводит к повышению стоимости памяти периферийного оборудования, но если учесть, что это повышение позволяет резко понизить стоимость накопителей, то в целом стоимость вычислений понижается. С точки зрения возможности понижения стоимости вычислений применение кодов, исправляющих ошибки, в вычислительных машинах также представляется целесообразным.

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

также «самокорректирующиеся» схемы, изучаемые в теории автоматов, а также так называемые арифметические коды, описываемые в последующих двух главах и используемые в некоторых арифметических устройствах, в частности в сумматорах. Что касается кодов, исправляющих ошибки, то они в общем случае применяются в системах, про которые достаточно знать лишь то, что в них информация вводится и выводится. При этом исследуемая система часто оказывается сложнее, чем изображенный на фиг. 7.29 канал связи. В действительности, как показано на фиг. 7.31, любую систему можно рассматривать как некий «черный ящик» и, сравнивая входы с выходами, найти распределение ошибок. Зная это распределение, из всех известных кодов можно выбрать тот, который исправляет наиболее часто возникающие конфигурации ошибок; кроме того, можно построить новый код специально для данного распределения ошибок. Например, в процессе общения оператора с вычислительной машиной при выполнении ручных операций возникает большое число ошибок, связанных с перестановкой соседних символов.

Фиг. 7.31. Система связи с каналом, рассматриваемым как «черный ящик»

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

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