Проектирование собственного кода, исправляющего ошибки

Введение

Задачей системы кодирования устойчивой к помехам считается защита информационных данных от случайных ошибок и помех при передаче и хранении данных. Система кодирования, устойчивая к помехам, даёт возможность ликвидации ошибок при обмене данными, а также ошибок, возникающих при их хранении. При передаче информации посредством каналов связи есть вероятность возникновения ошибок из-за различных помех. Это может стать причиной частичной потери информации. Если не использовать помехоустойчивую систему кодирования, то будет невозможно передавать большие объёмы информации, так как в любой системе передачи данных и их хранения есть вероятность возникновения ошибок.

Статья: Проектирование собственного кода, исправляющего ошибки

Найди решение своей задачи среди 1 000 000 ответов

Найти решение задачи

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

1. Выполняется запрос повторной информационной передачи. То есть с помощью кода, устойчивого к помехам, выполняется только обнаружение ошибок, а при появлении ошибки идёт запрос повторной передачи пакета данных.
2. Осуществляется непосредственное исправление ошибочных данных. То есть, помехоустойчивый код декодируется, и в процессе декодирования устраняются обнаруженные ошибки.
3. Гибридный вариант, объединяющий вышеназванные варианты. При нахождении ошибки выполняется операция по её исправлению, но если ошибку исправить не удалось, то запрашивается повторная передача данных.

Проектирование собственного кода, исправляющего ошибки

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

Все методы помехоустойчивых кодов обладают некоторым обязательным набором параметров:

1. Скорость кода $R$, которая является характеристикой доли данных, обладающих полезной информацией в передаваемом сообщении. Она определяется следующим выражением: $R = k / n = k / m + k$, где:

   • $n$ это общее количество знаков в кодированном сообщении.
   • $m$ это количество символов, подлежащих проверке.
   • $k$ это количество информационных символов.

   Значения $n$ и $k$ часто задаются вместе с наименованием кода, чтобы имелась возможность его однозначной идентификации.

2. Значение кратности выявления ошибок. А именно количество ошибочных знаков, которое код может выявить.

3. Значение кратности скорректированных ошибок. А именно количество ошибочных знаков, которые код может исправить (эта величина обозначается знаком t).

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

1 0 1 0 0 1 0 0 | 0

Если число единиц является чётным, то нужно прибавить единицу:

1 1 0 1 0 1 0 0 | 1

Во время приёма сообщения выполняется анализ бита чётности, и если принятый бит не совпадает с расчётным значением бита чётности, то выполняется фиксация ошибки.

Классификация кодов, способных исправлять ошибки

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

1. Непрерывная система кодирования. Операция вычисления кодов и их расшифровки выполняется непрерывно. Свёрточное кодирование является разновидностью непрерывного кодирования. На кодирующий модуль подаётся код одного знака, а выходным сигналом является набор знаковых кодов, то есть всем входным знакам приводится в соответствие комплект некоторого числа выходных знаков, так как прибавлены коды избытка.
2. Блочная система кодирования. Операция определения кодов и их расшифровки осуществляется по отдельным блокам. Блочный код является более простым, поскольку полный текст сообщения необходимо разбить на набор блоков и далее выполнить последовательное кодирование каждого блока.

По используемому набору символов системы кодирования, способные исправлять ошибки, подразделяются на следующие виды:

1. Двоичная система кодирования. Применяется бинарная система счисления.
2. Символьное кодирование. Применяется переформатирование начального двоичного кодового набора в разные символы.

При этом, системы блочного кодирования можно разделить на следующие виды:

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

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

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