23. Коды исправляющие ошибки

Существует множество кодов, исправляющих ошибки в двоичном коде. Это очень полезно, потому что множество информации портиться при хранении или передачи информации. Одним из примеров данных кодов можно привести «код Хемминга»(Подробно о нём уже написал другой автор http://habrahabr.ru/post/140611/). Они добавляют к бинарному тексту дополнительные, кодовые биты, при помощи которых мы сможем исправить полученные ошибки.

Каждый такой код имеет две характеристики – k и n. Такой код называется (n,k)-кодом. Здесь “n” обозначает общее количество символов в блоке закодированного текста, а “k” – число значимых символов.

Например, простейшим кодом является код с повторениями. В этом коде к каждому символу двоичного кода добавляется по n-1 кодовых битов, которые дублируют, значимый символ и в последствие мы сможем исправить ошибку. Например (3,1)-код дописывает к каждому символу в двоичной системе два таких же и при зашумлении, если меняется один символ из блока, то остаётся 2 одинаковых и по ним мы возвращаем исходный символ.

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

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

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