Общие понятия

Обнаружение и исправление ошибок

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

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

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

В общем случае для обнаружения t ошибок минимальное кодовое расстояние

d₀ = t + 1.

Минимальное кодовое расстояние, необходимое для одновременного обнаружения t и исправления s ошибок,

d₀ = t + s + 1.,

Для кодов, только исправляющих s ошибок,

d₀ = 2s + 1.

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

Для обнаружения и исправления одиночной ошибки соотношение между числом информационных разрядив k и числом корректирующих разрядов r должно удовлетворять следующим условиям:

,

,

при этом подразумевается, что общая длина кодовой комбинации

n = k + ρ

Для практических расчетов при определении числа контрольных разрядов кодов с минимальным кодовым расстоянием d₀ = 3 удобно пользоваться выражениями

ρ₁₍₂₎ = [ log₂ ( n + 1 ) ],

если известна длина полной кодовой комбинации n, и

ρ ₁₍₂₎ = [log₂ { ( k + 1 ) + [ log₂ ( k + 1) ] } ],

если при расчетах удобнее исходить из заданного числа информационных символов k .

Для кодов, обнаруживающих все трехкратные ошибки (d₀ = 4),

ρ ₁₍₃₎ ³ 1 + log₂ ( n + 1 ),

или

ρ ₁₍₃₎ ³ 1 + log₂ [ ( k + 1 ) + log₂ ( k + 1 ) ].

Для кодов длиной в n символов, исправляющих одну или две ошибки (d₀ = 5),

ρ ₂ ³ log₂ (C_n² + C_n¹ + 1).

Для практических расчетов можно пользоваться выражением:

.

Для кодов, исправляющих 3 ошибки (d₀ = 7),

.