Помехоустойчивое кодирование

Построение помехоустойчивых кодов связано с добавлением к кодовой комбинации исходного кода (первичного кода) дополнительных контрольных символов. Если длина исходных кодовых комбинаций равна k, а количество добавляемых контрольных символов равна r, то кодирующее отображение имеет вид:

Г: A^k ® B^k+r.

Если алфавиты A и B равны и n = k + r, то получаем следующее кодирующее отображение, определяющее (n, k) код:

Г: A^k ® Aⁿ.

Коэффициент избыточности (n, k) кода можно вычислить, используя выражение:

К_и = 1 - k / n.

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

Линейными m-ичными кодами называют k-мерные подпространств n-мерного пространства V. Среди линейных кодов особую роль играют групповые коды для которых m=2 (двоичные коды).

Пусть алфавит A состоит из двух символов A = {0, 1} и a₁ = (a₁₁,a₁₂,…,a_1i,…,a_1k) и a₂ = (a₂₁,a₂₂,…,a_2i,…,a_2k) - кодовые комбинации, принадлежащие A^k , a₁,a₂ Î A^k . Кодовое расстояние между кодовыми комбинациями a₁ и a₂ определяется выражением:

_k

d =  (a_1i Å a_2i),

ⁱ⁼¹

где через Å обозначена операция сложения по модулю два.

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

e = (e₁, e₂,…, e_i,…, e_k), e Î A^k , A ={0, 1}.

Кратностью ошибки называют величину равную:

_k

t =  e_i

ⁱ⁼¹

Искажение сообщения, вызванное ошибкой e, e = (e₁,e₂,…,e_i,…,e_k) в канале передачи данных, определятся отображением:

f_e: Aⁿ ® Aⁿ ,

где a =(a₁, a₂, … , a_n), b =(b₁, b₂, … , b_n), b = f_e(a) b_i = a_i Å e_i, i = 1, n.

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

_{k k}

 a_i =  b_i.

^{i=1 i=1}

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

Эффективность кодов с обнаружением ошибок характеризуется коэффициентом обнаружения ошибок K_об, определяемый выражением:

K_об = N_s / N_,

где N_s - количество обнаруженных ошибочных кодовых комбинаций,

N_ - количество кодовых комбинаций переданных с ошибками:

_k

N__

ⁱ⁼¹

где количество кодовывых комбинаций при передачи которых возникли ошибки i-ой кратности. 

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

K_ис = N_c / N_,

где N_c - количество кодовых комбинаций с обнаруженными и исправленными ошибками.

9.1. Коды с обнаружением ошибок

9.1.1. Код проверки на четность

В коде проверки на четность относится к коду (k, 1). К кодовой комбинации добавляется один контрольный разряд a_k+1, определяемый выражением:

a_k+1 = a₁ Å a₂ Å … Å a_k.

Этот код позволяет обнаруживать ошибки с нечетной кратностью.

9.1.2. Код с постоянным весом

Код содержит постоянное количество единиц. Количество кодовых комбинаций длины n с k единицами определяется числом сочетаний из n по k:

N = C^k_n ⁼ n! /( k!(n - k)!) ^.

Применение кода с постоянным весом не позволяет обнаружить ошибки смещения.

9.1.3. Корреляционный код

Кодовое отображение корреляционного кода имеет вид:

Г: A ® A² и задается таблицей 9.1.

Таблица 9.1.

Символы входного алфавита	Кодовые комбинации
0	01
1	10

Применение корреляционного кода позволяет обнаружить ошибку, если встречаются запрещенные кодовые комбинации 00 или 11. Код позволяет обнаружить ошибку с кратностью равной единице. Коэффициент избыточности кода равна 0.5.