Математическая энциклопедия - код с исправлением ошибок

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

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

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

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

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

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

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