Корректирующие коды
ЭВМ воспринимают вводимую в них информацию в виде определенных символов. Обычно применяются двоичные символы: 0 и 1. Это обусловливается сравнительной простотой электронных элементов с двумя устойчивыми состояниями: ключевым режимом ламп и полупроводников, переключением состояний магнитных сердечников с прямоугольной петлей гистерезиса и т. д.
Кодирование информации состоит в представлении чисел и слов соответствующими им комбинациями символов.
Совокупность всех комбинаций из определенного количества символов, которые избраны для представления информации, называют кодом. Каждую такую комбинацию символов будем называть кодовой комбинацией. Общее количество кодовых комбинаций может быть меньше или равно числу всевозможных комбинаций из заданного количества символов.
Приведем некоторые определения из теории кодирования.
Равномерный код – код, все комбинации которого содержат одинаковое количество символов.
Неравномерный код – код с различным количеством символов для различных комбинаций (например, азбука Морзе).
В компьютерах обычно используют равномерные коды.
Кодовое расстояние – число позиций, в которых коды не совпадают. Так, если A~ a1, a2, ..., an, B ~ b1, b2, ..., bn, то кодовое расстояние (W) вычисляется по формуле
Пример: A ~ 101110, B ~ 000110, то W(AÄB) = 2.
Минимальное кодовое расстояние
(d) – это минимальное расстояние между двумя любыми кодовыми комбинациями в заданном коде.
Для всех корректирующих кодов d > 1. Для обнаружения ошибки кратности t требуется, чтобы d = t + 1, а для ее исправления — d = 2t + 1. C увеличением значения d растет корректирующая способность кода, которая количественно может быть выражена как вероятность обнаружения или исправления ошибок различных типов.
В зависимости от назначения и возможностей помехозащищенных кодов различают коды самокорректирующиеся (позволяющие автоматически исправлять ошибки) и самоконтролирующиеся (позволяющие автоматически обнаруживать наиболее вероятные ошибки).
