Связь между корректирующей способностью кода и длиной кода

Обычная последовательность выбора кода следующая:

• — исходя из мощности М первичного алфавита, определяется количество информационных разрядов к;
• — задается возможная кратность ошибок Г, подлежащих обнаружению и исправлению;
• — определяется количество дополнительных проверочных разрядов г, которые вместе с информационными определят длину кода п.

Пусть известна мощность первичного ал&авита М. Необходимое количество информационных битов

Пусть необходимо исправить ошибки кратности от 1 до t. Число возможных однократных ошибок в коле длиной п равно С=п, число двукратных ошибок равно число возможных t-кратных ошибок равно

Общее число ошибок

Эти Е ошибок могут проявиться в каждой из 2^к возможных входных последовательностей. Полное число ошибочных комбинаций, подлежащих исправлению, равно Е? 2^к. Код длиной п обеспечивает исправление не более 2^п — 2^к комбинаций, так как существует именно столько запрещенных комбинаций. Следовательно, необходимое условие для возможности исправления ошибок можно записать в виде

Отсюда получим

Обозначив буквой г число проверочных символов и учитывая, что г = пк, приходим к виду.

Учитывая, что , можно записать.

или

Это так называемая граница Р. Хемминга (или условие Хемминга), которая связывает число проверочных разрядов г и значность кода п.

Ричард Уэсли Хемминг (1915 —1998) — американский математик, работавший в области компьютерных наук и телекоммуникаций. Его научные достижения включают коды Хемминга, окно Хемминга, числа Хемминга, расстояние Хемминга. Р. Хемминг — один из участников «Манхеттенского проекта» (разработка ядерного оружия США), где он занимался программированием одного из первых компьютеров. Позднее Хемминг работал вместе с К. Шенноном в корпорации Bell Laboratories. Основатель и президент Ассоциации компьютерной техники, профессор.

В частном случае, когда требуется исправить однократные ошибки, имеем зависимость

Оценить количество проверочных символов и избыточность кода можно по табл. 4.3, построенной по указанной зависимости (4.5).

Таблица 4.3

Соотношение контрольных и информационных символов для кода, исправляющего однократные ошибки.

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

Сравните с аналогичной табл. 4.4 для помехоустойчивого кода, исправляющего двукратные ошибки.

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

Таблица 4.4

Соотношение контрольных и информационных символов для кода, исправляющего двукратные ошибки.

8 Выполняется ли неравенство Хемминга в задаче о разведчиках? Ответ: да, но только для двукратных ошибок. Если же требуется исправлять и однократные, и двукратные ошибки, то г > log₂(l + 8 + 28) = 6.