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

Элементы блокового К. с и. о. выбираются из нек-рого множества га-мерных векторов Lⁿ, снабженного метрикой l(,), а их окрестности ошибок задаются в виде шара с центром в элементе кода. Радиус этого шара определяет корректирующую способность блокового кода. Метрика l(,) зависит от характера ошибок, для исправления к-рых предназначен код. Дальнейшее изложение касается только блоковых К. с и. о. как наиболее распространенных.

Для того чтобы иметь возможность передать максимальное количество сообщений по каналу связи, необходимо использовать коды с, максимальным числом элементов при заданной корректирующей способности. Построение таких кодов является одной из основных задач теории К. с и. о. Эта задача достаточно далеко продвинута только для нек-рых рассматриваемых ниже конечных множеств Lⁿ. В то гке время как для приложений, так и для теории интересны коды на нек-рых бесконечных множествах, напр, на сфере в евклидовом пространстве Rⁿ.

При практическом использовании К. с и. о. возникают задачи отображения информации, предназначенной для передачи в множество элементов К. с и. о. и нахождения по принятому элементу х' переданного элемента кода х. Первая задача наз. задачей кодирования, вторая - задачей декодирования. Сложность кодирования и декодирования в значительной мере определяется свойствами используемого К. с и. <о. это="" обстоятельство="" приводит="" к="" изучению="" относительно="" узких="" классов="" кодов,="" как,="" например,="" рассматриваемых="" ниже="" двоичных="" линейных="">

Наиболее широко исследовались блоковые r-и чные коды в метрике Хемминга, ввиду того что они находят многочисленные применения, а методы их построения связаны с известными ранее математическими структурами. Элементами этих кодов являются нек-рые элементы множества В ⁿ_r, состоящего из всех векторов длины п, координаты к-рых принадлежат множеству из rэлементов. Расстоянием Хемминга d(x, у )между векторами х, у из В ⁿ_r наз. число их несовпадающих координат. Окрестность ошибок U_t(x)кратности t(t- целое) вектора хсостоит из всех векторов из В ⁿ_r, отличающихся от хне более чем в r координатах, т. е. Uf(x)- шар в метрике d(,) радиуса tс центром в точке х. В частности, U₁ (х). состоит из (r-1)n+1 векторов. Для произвольного множества функция наз. кодовым расстоянием r-ичного кода К. Код Кявляется К. си. о. кратности t, если При выполнении последнего неравенства каждая окрестность ошибок U_t(x), не пересекается ни с какой другой окрестностью ошибок кратности tвектора уиз К. Значительный прогресс в изучении r-ичных кодов получен для случая, когда г является степенью простого числа. В этом случае в качестве множества координат берут конечное поле GF(q)из qэлементов и используют алгебраические свойства этого понятия. Ниже предполагается, что координатами элементов множества являются элементы поля GF(q). Множество является линейным пространством над полем GF(q). Если векторы кода Кобразуют линейное подпространство пространства то код наз. линейным. Линейный код К может быть задан как своим базисом, так и базисом линейного пространства, двойственного к К. Последний способ более распространен. Матрица А, строками к-рой служат базисные векторы пространства, двойственного к К, наз. проверочной матрицей К. Для векторов справедливо соотношение: хА ^T=0, где А ^T- транспонированная матрица А. Далее п - длина кода, к- размерность линейного кода и d- кодовое расстояние. Код над наз. двоичным кодом.

Для оценки качества конкретных кодов изучают поведение функции m(n, d), равной максимальному числу векторов двоичного кода длины пс кодовым расстоянием d. Относительно хорошо функция т( п, d )изучена при больших d, и малых d,d=const, В первом случае величина т( п, d )не превосходит 2n при 2d=n и 2dl(2d-n) при 2d-n>0, а во втором - равна по порядку п ^-t2 ^п при d=2t+i. Если d=3, n=2^l-1, то т(n,3) = 2ⁿ/(n+1).

Код, на к-ром достигается последнее равенство, носит название двоичного кода Хемминга. Двоичный код Хемминга, корректирующий ошибки кратности t=l, обладает следующим свойством: шары радиуса t=l с центрами в точках кода не пересекаются и в то же время заполняют все множество Bⁿ₂. Подобные коды наз. совершенными. Известно, что, кроме кодов Хемминга, существует еще лишь конечное число нетривиальных двоичных совершенных кодов.

В случае изучают функцию (логарифмич. асимптотику m(n, d)), называемую скоростью передачи максимальным кодом с относительным кодовым расстоянием б. Для скорости i?(6) известны существенно различающиеся верхние и нижние оценки. Нижняя оценка (оценка Варшамова - Гилберта) имеет вид

где

и гарантирует существование кодов с указанными параметрами. Коды с параметрами, лежащими на границе (*), к настоящему времени (1978) могут быть построены только методом перебора. Существенно новые верхние оценки получены в [6], [7]. Весьма правдоподобна гипотеза, по к-рой R(d) = 1-H(d).

Далее рассматриваются конструктивные методы (т. е. методы, требующие для своей реализации относительно небольшого числа операций) построения К. с и. о. К важнейшим конструктивным кодам относятся: коды Рида - Соломона (PC-коды), коды Боуза - Чоудхури - Хоквингема (БЧХ-коды) и коды Рида - Маллера (РМ-коды). Перечисленные коды являются линейными. Отправной конструкцией для построения первых двух служит матрица А _r с элементами из GF(q):

где а -первообразный корень GF(q). Матрица А _r является проверочной матрицей PC-кода С _r над GF(q), к-рый имеет следующие параметры: n=q-1, k = q-r, d=r. Кодовое расстояние кода С _r является максимальным среди всех линейных кодов длины q-1 и

размерности q-r. Двоичный БЧХ-код Н _r состоит из всех векторов PC-кода С _г над GF(2^l), координаты к-рых принадлежат полю GF(2), т. е. H_r=C_r З B₂ⁿ. БЧХ-код Н _r при r=2t+l имеет следующие параметры: п=2^l- 1, Упомянутый выше код Хемминга совпадает с БЧХ-кодом Н ₃. Если t<2^[(l+1)/2]([x] - целая часть х), то размерность кода H_2t+1 равна п-lt. БЧХ-код является циклическим, т. е. обладает тем свойством, что вместе с вектором хсодержит все его циклнч. сдвиги. Число векторов БЧХ-кодов в случае r=const совпадает по порядку с мощностью наилучшего кода т( п, r).

Двоичный РМ-код определяется как множество двоичных векторов вида (f(a₁), f(a₂), ..., f(a_n)), где n=2^l, a₁, ..., a _п- всевозможные двоичные векторы длины lи f(x)пробегает множество всех функций алгебры логики, представимых в виде многочлена над GF(2)степени не выше г от lдвоичных переменных. РМ-код имеет следующие параметры: n=2^l, d=2^l-r

Скорость передачи R(К)двоичного кода Кдлины пс числом векторов топределяется как