где р — вероятность ошибочного приема символа кодового слова; t— число
ошибок, гарантированно исправляемых линейным кодом Y{n, R).
При оптимальном декодировании в декодирующем устройстве необходимо
хранить список всех слов кода У(п, R) п последовательно сравнивать
принятую последовательность со всеми словами списка.
СТАНДАРТНАЯ РАССТАНОВКА. ДЕКОДИРОВАНИЕ ЛИНЕЙНЫХ
КОДОВ ПО СИНДРОМУ
Предположение, что множество 5 выходных последовательностей канала
является ^"-мерным векторным пространством над полем GF(q}, а множество
У(n, R) входных последовательностей (код) является подпространством раз-
мерности nR. существенно облегчает декодирование. В этом случае Y(n. Р)
является подгруппой аддитивной группы V^, и, следовательно. V,^ может быть
разложено на смежные классы по подгруппе Y(n, R}Vy". Пусть i/i, у
2
, •••, у'"—
псе элементы i{n,R} (кодовые слова), тогда все элементы множества V^
1
будут
представлены с помощью стандартного расположения [5]
y1=0 y2 … yM
e1 e1+y2….e1+yM
e2 e2+y2 ….e2+yM
es es+y2 … es+yM
(здесь через 0 обозначен единичный элемент группы Vq
n
}.
Каждая строка в (13) образующими элементами соответствующих
смежных классов. Если в качестве образующих 0, е
1
, е
2
, ..., е' взяты элементы
минимального веса в своем смежном классе, то любая последовательность g
из t'-ro столбца отличается от у в меньшем числе разрядов, чем. от любого
другого слова yi=V(n,R) i
≠
K. Если в смежном классе, содержащем ξ,
существует несколько элементов минимального веса, то найдется столько же
кодовых слов, отличающихся от ξ в одном и том же наименьшем числе
разрядов.
Для доказательства предположим, что ξ=y
i
+е, где е - элемент
минимального веса в своем смежном классе. Очевидно, d{y
i
. ξ)=w (<•) и
d(y
k
,
ξ
)=w(y
k
- y
i
-e). Если е— единственный элемент минимального веса, то
d{y
i
. ξ)<d(y
k
, ξ) для всех K
≠
i. Если таких элементов несколько (например,
w(y'+e)=w(e) , то d{y
i
. ξ)=
,)1(
1
1
−
==
−≤
∑
n
TI
i
i
n
ош
p
p
C
P
=d(y
k
, ξ) то при условии, что y
k
=y
j
-y
i
. Следовательно, для каждого
элемента y'+e минимального веса в смежном классе, содержащем e, найдется
слово y
k
=y
i
+y
i
, которое находится от у на расстоянии d(y
k
, i)=w(e).
Таким образом, для всех последовательностей ξ, входящих в 1-й столбец
стандартной расстановки, условная вероятность Р(ξ\у') максимальна. Если i
находится в смежном классе с несколькими элементами минимального веса,
то условная вероятность Р(ξ\у
i
)=Р(ξ\у
k
) и остается максимальной для всех У,
находящихся на одинаковом расстоянии от ;. Правило декодирования может
быть сформулировано следующим образом: найти выходную
последовательность канала ξ∈V
n
в (13} и считать, что была передана та
последовательность y'∈Y(n.R), которая находится в том же столбце, что и
ξ.
Очевидно, это правило совпадает с декодированием по максимуму
правдоподобия и, следовательно, является оптимальным.
Правило декодирования линейного кода можно сформулировать так: после
того. как выходная последовательность E; найдена в 113). определить
наиболее вероятный вектор ошибки e. отыскивая образующий элемент того
смежного класса, который содержит ^; переданную последовательность
найти из соотношения y=ξ—e.
Можно построить аналогичную процедуру декодирования, если
воспользоваться однозначным соответствием между смежными классами и
синдромами образующих элементов. Правило декодирования заключается в
следующем: вычислить синдром принятой последовательности
(13)
S=ξH
T
=eH
T
,
где e — образующий элемент смежного класса, содержащего ξ. По
найденному синдрому S найти e; определить у из соотношения у=ξ—e.
Такое декодирование также совпадает с декодированием по максимуму
правдоподобия и, следовательно, остается оптимальным. Первыми кодами с
подобной процедурой декодирования были коды Хемминга, исправляющие
одиночные ошибки.
Однако отыскание последовательности ошибок, когда число допустимых
ошибок больше одной, быстро усложняется и при достаточно длинных кодах
и большом количестве исправляемых ошибок становится практически
невозможным,