Границы избыточности

Для построения любого избыточного помехоустойчивого кода необходимо решить задачу нахождения минимального значения избыточных элементов k или минимальной избыточности R. Постановка задачи: для заданного числа рабочих комбинаций M (или числа информационных элементов m) и заданного числа r обнаруживаемых ошибок типа трансформации, числа s исправляемых из них из них и числа e исправляемых ошибок стирания найти минимальное число избыточных элементов k. Задание величин s, r и e эквивалентно заданию минимального кодового расстояния d_min.

Точное решение этой задачи не найдено, однако предложены граничные оценки величины k_min. Наиболее известно и часто используема граница, предложенная Хеммингом.

Пусть требуется построить код, содержащий M рабочих кодовых комбинаций, которые позволили бы исправлять все ошибки трансформации кратности. Хемминг рассматривал двоичные коды, поэтому M = 2^m, d_min ≥ 2s + 1.

Введем в код k избыточных элементов. Имеем n = m + k элементов в кодовой комбинации.

Если код должен исправлять все ошибки кратности s, то число различных векторов ошибок E определяется числом сочетаний из n по m:

Каждый из векторов может исказить любую рабочую комбинацию . В результате будет получено ME искаженных комбинаций.

Так как по построению кода в нем существует количество нерабочих комбинаций N_НЕРАБ = 2ⁿ – 2^m, то для принципиальной возможности исправления всех ошибок кратности s необходимо выполнить условия

Полученное выражение называется границей Хемминга

Подставляя n = m + k, из (10) получаем выражение содержит одно неизвестное k, которое обычно находят методом подбора.

Используя информационный подход, можно получить другую оценку k:

В ходе этих рассуждений предполагалось, что вероятность появления вектора ошибки одинакова для ошибок любой кратности, что не соответствует действительности. Завышенная величина k позволяет упростить расчеты при определении информации по Хартли, а также избежать катастрофических последствий.