Код С Исправлением Ошибок

Код, корректирующий ошибки,- множество сообщений, предназначенных для передачи по каналу связи с шумами, обладающее тем свойством, что окрестность ошибок каждого сообщения (т. е. совокупность искаженных вариантов этого сообщения) не пересекается с окрестностями ошибок других сообщений. Это свойство К. с и. о. позволяет правильно корректировать ошибки (т. е. правильно восстанавливать переданное сообщение) в тех (полученных на выходе канала) искаженных сообщениях, к-рые принадлежат своей окрестности ошибок. Элементы К. с и. о. используются при кодировании последовательностей информационных символов, вырабатываемых источником сообщений. Кодирование заключается в представлении информационной последовательности в специальной форме и введении в нее дополнительной информации ( избыточности). Избыточность обычно вводят путем добавления в сообщение тем или иным способом дополнительных символов. Напр., последовательность символов разбивается на блоки фиксированной длины к, а затем независимо один от другого блоки заменяются другими блоками большей длины п, к-рые являются элементами так наз. блокового К. с и. о. Известны [1] и другие способы введения избыточности и связанные с ними К. с и. о. Элементы блокового К. с и. о. выбираются из нек-рого множества га-мерных векторов Ln, снабженного метрикой l(,), а их окрестности ошибок задаются в виде шара с центром в элементе кода. Радиус этого шара определяет корректирующую способность блокового кода. Метрика l(,) зависит от характера ошибок, для исправления к-рых предназначен код. Дальнейшее изложение касается только блоковых К. с и. о. как наиболее распространенных. Для того чтобы иметь возможность передать максимальное количество сообщений по каналу связи, необходимо использовать коды с, максимальным числом элементов при заданной корректирующей способности. Построение таких кодов является одной из основных задач теории К. с и. о. Эта задача достаточно далеко продвинута только для нек-рых рассматриваемых ниже конечных множеств Ln. В то гке время как для приложений, так и для теории интересны коды на нек-рых бесконечных множествах, напр, на сфере в евклидовом пространстве Rn. При практическом использовании К. с и. о. возникают задачи отображения информации, предназначенной для передачи в множество элементов К. с и. о. и нахождения по принятому элементу х' переданного элемента кода х. Первая задача наз. задачей кодирования, вторая — задачей декодирования. Сложность кодирования и декодирования в значительной мере определяется свойствами используемого К. с и. Если К- линейный код, то R(K) = k/n. Скорость передачи перечисленных выше конструктивных кодов при 6 >0, стремится к 0. Известны конструктивные коды со скоростью передачи большей нуля при но меньшей скорости передачи кодов, существование к-рых устанавливает граница (*). При практическом использовании К. с и. о. кратности tдля коррекции ошибок канала связи необходимо устройство (декодер), к-рое по искаженному вектору указывает переданный кодовый вектор х. При этом предпочтительно использовать такие К. с и. о., для к-рых декодер имеет небольшую сложность. Под сложностью декодера двоичного кода Кс кодовым расстоянием 2t+1 понимается, напр., минимальное число функциональных элементов, к-рое необходимо для реализации булева оператора Малую сложность декодера имеют рассмотренные конструктивные коды. Кроме того, известны другие К. с и. о. со скоростью передачи, не стремящейся к 0 при d>0, и малой сложностью декодера. К таким кодам относятся, напр., каскадные коды и коды с малой плотностью проверок на четность. Каскадный код в простейшем случае представляет собой итерацию PC-кода над полем GF(2l )и двоичного кода длины п 1 размерности lс кодовым расстоянием d1. С помощью какого-либо линейного отображения устанавливается взаимно однозначное соответствие между элементами поля GF(2l). и векторами двоичного кода. Затем координаты PC-кода заменяются соответствующими векторами двоичного кода. В результате получается двоичный линейный каскадный код с параметрами n=n1(2l-1), k=l(2l-r). . Лучшие результаты достигаются, если для замены различных разрядов РС-кода использовать различные двоичные коды. Таким способом могут быть получены коды длины n, исправляющие с помощью декодера со сложностью, равной по порядку п log n, фиксированную долю от пошибок. Ансамбль двоичных кодов с малой плотностью проверок на четность определяется ансамблем проверочных матриц , состоящим из двоичных матриц нек-рого вида, размера к-рые содержат в каждом столбце и каждой строке соответственно lи h единиц, 4<l<h. При фиксированных lи hи типичный код длины пансамбля с помощью декодера со сложностью, по порядку равной пlog n, может исправлять фиксированную долю от пошибок. Скорость передачи как каскадных, так и кодов с малой плотностью проверок лежит ниже оценки (*). Достаточно широко исследовались коды на множествах В пq в метриках, отличных от метрики Хемминга. Направление и результаты этих исследований во многом сходны с соответствующими результатами для метрики Хемминга. В частности, рассматривались коды в метриках, связанных с синхронизационными ошибками, с ошибками в арифметич. устройствах ЭВМ (арифметические коды), с пачками ошибок, с несимметричными ошибками, с ошибками в непрерывном канале связи. Напр., в последнем случае множеством Ln является сфера единичного радиуса Sn в евклидовом пространстве Rn с центром в начале координат, а окрестностью ошибок Um(x),- поверхность, высекаемая из Sn-1 круговым конусом с полууглом j и с осью, проходящей через точки 0 и х. Следует также заметить, что коды в евклидовом пространстве Rn в несколько иной трактовке рассматривались, начиная с конца 19 в., в геометрии. Развитие теории К. си. о. стимулировалось работами К. Шеннона (С. Shannon) по теории информации, в к-рых была показана принципиальная возможность передачи по каналу связи с шумами информации со скоростью меньшей пропускной способности канала и произвольной малой ошибкой. Первоначально теория К. с и. о. удовлетворяла потребности техники связи в математических конструкциях, обеспечивающих надежную передачу информации при ограничениях на число и вид ошибок в сообщении. Затем результаты и методы теории К. с и. о. нашли применение в других областях. В частности, в математике этими методами удалось получить наилучшие (к 1978) оценки плотности укладки шаров в евклидовом пространстве, получить значительное продвижение при оценке сложности тупиковых дизъюнктивных форм для почти всех функций алгебры логики, построить нек-рые новые объекты в комбинаторике, построить самокорректирующиеся схемы из функциональных элементов и т. д. Лит.:[1]Питерсон У., Уэлдон Э., Коды, исправляющие ошибки, пер. с англ., 2 изд., М., 1976; [2] Берлекэмп Э., Алгебраическая теория кодирования, пер. с англ., М., 1971; [3] Дискретная математика к математические вопросы кибернетики, т. 1, М., 1974; [4] Блох Э. Л., Зяблов В. В., Обобщенные каскадные коды, М., 1976; [5] Колесник В. Д., МирончиковЕ. Т., Декодирование циклических кодов, М., 1968; [6] Сидельников В. М., "Пробл. передачи информ.", 1974, т. 10, в. 2, с. 43-51; [7] Левейштейн В. И., там же, с. 26-42; [8] Зяблов В. В., Пинскер М. С, "Пробл. передачи информ.", 1975, т. И, в. 1, с. 23-36. В. М. Сиделъников.