КОДЫ КОРРЕКТИРУЮЩИЕ

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

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

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

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

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

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

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

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

К. к. для симметричного канала наиболее исследованы. Теория этих кодов широко использует алгебр, структуры (группы, кольца, поля, векторные пространства и др.). Для кодов, корректирующих независимые ошибки, важную роль играет понятие кодового расстояния. Расстояние между любой парой двоичных кодовых слов определяется соотношением: где хэмминговым расстоянием, операция сложения по модулю 2. Кодовое расстояние является наименьшим хэмминговым расстоянием между кодовыми словами. Кодовое расстояние определяет корректирующие возможности кода по отношению к независимым ошибкам в соответствии со следующим основным свойством: для того, чтобы код обнаруживал все комбинации из s ошибок и исправлял все комбинации из t ошибок, необходимо и достаточно, чтобы кодовое расстояние было равно .

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

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

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

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

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

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

Среди всех известных циклических кодов для канала с независимыми ошибками наилучшими по своим корректирующим свойствам являются коды Боуза — Чоудхури—Хоквингэма (БЧХ). Эти коды могут быть построены в широком диапазоне кодовых длин и кодовых расстояний. Для любых целых значений существует код БЧХ длины с кодовым расстоянием и содержащий не более чем проверочных символов. Коды БЧХ задаются обычно корнями порождающего многочлена, являющимися последовательными степенями примитивного элемента а поля Известны и др. конструкции кодов БЧХ, в частности, порождаемые и непримитивными элементами поля Коды БЧХ по своей избыточности при заданном кодовом расстоянии довольно экономичны и близки к теоретическому пределу. Код Хэмминга и ряд др. К. к. могут рассматриваться, как частные случаи кодов БЧХ. Др. важным классом циклических кодов являются коды для каналов с пакетами (пачками) ошибок. Наиболее известными кодами этого класса являются коды Файра, определяемые порождающими полиномами вида , где неприводимый полином степени т. Они пригодны для широкого диапазона длин кодов и длин корректируемых пачек ошибок.

К числу кодов, исправляющих пачки ошибок, относятся также коды Эйбрамсона и коды Меласа. Широкими возможностями для коррекции пачек ошибок обладают также коды Рида — Соломона и коды БЧХ. Спец. класс К. к. образуют коды, локализующие ошибки. Эти коды являются промежуточными между кодами, исправляющими ошибки и кодами, обнаруживающими ошибки, т. к. позволяют установить местоположение ошибки с точностью до подблока, т. е. нескольких кодовых позиций кодового слова. Такие коды можно построить на базе известных циклических кодов. Коды, локализующие ошибки, представляют интерес для систем передачи с переспросом, использующим обратный канал, для задач помехоустойчивого кодирования многоблочных структур автоматов и др.

Наряду с К. к. для симметричных каналов большой интерес представляют также коды для асимметричных каналов. Учет асимметрии ошибок реальных каналов передачи и обработки информации во многих случаях позволяет получить более простые конструкции К. к. либо уменьшить необходимую избыточность при заданной корректирующей способности кода. Большинство конструкций К. к. для асимметричного канала основано на весовых представлениях кодовых слов, при которых каждая кодовая позиция взвешена некоторым постоянным весом, а проверочные соотношения являются некоторыми функциями веса кодовых слов. В основу обнаружения асимметричных ошибок при этом положен принцип изменения веса. Наиболее известными кодами этого типа являются коды постоянного веса (коды с постоянным числом единиц), находящие широкие применения в технике связи, преобразующих устр-вах, а также для кодирования десятичных цифр в ЦВМ (коды «2 из 5», «3 из 7»).

Коды для асимметричных каналов обнаруживают произвольные сочетания асимметричных ошибок, однако относятся к числу неразделимых кодов. Аналогом их среди разделимых кодов являются коды Бергера — Фреймана. Известны коды, корректирующие асимметричные ошибки и обладающие меньшей избыточностью, чем аналогичные коды для симметричных каналов: коды Кима — Фреймана и Варшамова — Тененгольца, корректирующие однократные асимметричные ошибки, код Тененгольца, корректирующий двойные асимметричные ошибки, коды, корректирующие пачки асимметричных ошибок. Известны также конструкции кодов, корректирующих асимметричные ошибки в многоканальных системах, использующихся при проектировании внеш. запоминающих устр-в ЦВМ и многоканальных систем передачи информации.

В системах обработки информации находят применение К. к., получившие название арифметических. К таким кодам наряду с требованиями коррекции ошибок предъявляются также требования удобства выполнения арифм. операций над кодовыми словами (см. Операции над числами). Для оценки корректирующей способности арифм. кодов используют отличные от хэмминговских понятия ошибки и кодового расстояния. Арифм. вес числа N определяется при этом как минимальное число слагаемых в представлении числа в виде где . Арифм. расстояние между числами и — арифм. вес разности и равно кратности ошибки, переводящей число в Тдкое определение расстояния достаточно хорошо отражает специфику ошибок, которые могут возникнуть при выполнении арифм. операций (типа сложения), в т. ч. возможное размножение ошибок по цепи переноса. При оценке корректирующей способности кодов к независимым арифм. ошибкам арифм. расстояние является полным аналогом расстояния Хэмминга. Наиболее широкий класс арифм. кодов образуют -коды, в которых кодируемое число N представляется

произведением его на специально подобранный множитель А.

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

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

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

Лит.: Варшамов Р.Р. Математические методы повышения надежности в реальных системах связи. «Известия АН СССР. Техническая кибернетика», 1964, № 4; Акушский И. Я., Юдицкий Д. И. Машинная арифметика в остаточных классах. М., 1968 [библиогр. с. 430—433]; Дадаев Ю. Г. Арифметические коды, исправляющие ошибки. М., 1969 [библиогр. с. 161—164]; Питерсон У. Коды, исправляющие ошибки. Пер. с англ. М., 1964 [библиогр. с. 309—316]. О. М. Рякин.