Блоковые коды

Общие принципы использования избыточности. На вход двоичного кодирующего устройства поступает k символов. На выходе ему соответствует n (n > k) символов. Всего может быть 2 ^k входных (разрешенных) и 2 ⁿ выходных последовательностей, 2 ⁿ – 2 ^k являются запрещенными комбинациями.

Искажение информации в процессе передачи сводится к тому, что некоторые символы заменяются другими – неверными. Всего существуют 2 ⁿ × 2 ^k возможных вариантов, из них:

– 2 ^k случаев безошибочной передачи;

– 2 ^k (2 ^k – 1) случаев перехода в другие разрешенные комбинации (необнаруживаемые ошибки);

– 2 ^k (2 ⁿ – 2 ^k) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены.

Вероятность обнаружения ошибки: .

Исправление ошибок. При получении запрещенной комбинации считают, что передавалась разрешенная комбинация A_i. Ошибка будет исправлена, если полученная комбинация действительно образовалась из A_i, т.е. в 2 ⁿ – 2 ^k случаях.

Большинство разработанных кодов предназначено для корректирования взаимно независимых ошибок определенной кратности и пачек ошибок. Степень отличия любых двух кодовых комбинаций назовем кодовым расстоянием d (число единиц в сумме по модулю 2).

При декодировании принятая комбинация отождествляется с той разрешенной, которая находится от нее на наименьшем кодовом расстоянии (метод максимального правдоподобия).

При d = 1 все кодовые комбинации являются разрешенными (при n = 3 подходят: 000, 001, 010 и т.д.). Если d = 2, ни одна из разрешенных комбинаций при одиночной ошибке не переходит в другую разрешенную. В общем случае при необходимости обнаруживать ошибки кратностью до r включительно, минимальное расстояние между разрешенными кодовыми комбинациями должно быть по крайней мере на единицу больше r. Для исправления одиночной ошибки каждой разрешенной комбинации необходимо сопоставить подмножество запрещенных кодовых комбинаций. Чтобы эти подмножества не пересекались, расстояние должно быть не менее 3. При n = 3 за разрешенные комбинации можно принять 000 или 111. Тогда (для 000) запрещенные комбинации 001, 010, 100 образуются в результате однократной ошибки.

Для разрешенной комбинации 111 запрещенные – 110, 011, 101.

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

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