11. Что такое минимальное расстояние кода? Как упрощается процедура отыскания минимального расстояния для линейного кода?

Минимальное расстояние кода С, определяемое как минимальное расстояние Хэмминга между двумя различными векторами кода С. Для произвольно выбранного минимального расстояния кода, заданного нечетным числом d, число информационных символов равно L N - d 1 и любая конфигурация ( d - 1) / 2 ( N - L) / 2 ошибок может быть исправлена. Если представить каждую букву кодового слова т двоичными символами, то получим двоичный код с Lm информационными символами. Верхняя граница минимального расстояния кода указывает тот теоретический предел, который не может быть превзойден заданным классом кодов по его кодирующей способности, если параметры п и k кода заданы. Наименьшее значение из набора dt для М-кодовых слов называется минимальным расстоянием кода и обозначается ofmin. Поскольку хеммингово расстояние является мерой различия между парами кодовых слов, оно, разумеется, имеет отношение к коэффициенту корреляции между соответствующими парами сигналов, генерируемыми кодовыми словами.

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

Пусть U = (U₀, U₁, U₂, ...U_n-1) - двоичная последовательность длиной  n.

Число единиц (ненулевых компонент) в этой последовательности называется весом Хемминга  вектора U  и  обозначается   w(U).

Коды Хэмминга являются самоконтролирующимися кодами, то есть кодами, позволяющими автоматически обнаруживать ошибки при передаче данных. Для их построения достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру этого разряда так, чтобы общее количество единиц в изображении любого числа было, например, четным. Одиночная ошибка в каком-либо разряде передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок.

При этом невозможно узнать, в каком именно разряде произошла ошибка, и, следовательно, нет возможности исправить её. Остаются незамеченными также ошибки, возникающие одновременно в двух, в четырёх или вообще в четном количестве разрядов. Впрочем, двойные, а тем более четырёхкратные ошибки полагаются маловероятными.

13. Что такое декодирование по максимуму правдоподобия и по минимуму Хемминговского расстояния? Когда эти правила совпадают?

Декодирование по максимуму правдоподобия. Для сверточных кодов разработаны алгоритмы синдромного, последовательного декодирования и декодирования по максимуму правдоподобия (алгоритм Витерби). Алгоритм Витерби является рекуррентной процедурой, направленной на поиск пути по кодовой решетке, ближайшего к принимаемой последовательности. Как уже указывалось, декодирование по минимуму расстояния является оптимальным в канале с независимыми ошибками. Основные операции алгоритма поясним при декодировании кода. Пусть для простоты передается нулевое кодовое слово, а в канале произошла трехкратная ошибка, так что принятая последовательность имеет вид 10 10 00 00 10 00 ... 00 ... Результаты поиска ближайшего пути после приема 14 элементарных блоков показаны на рис. 5.12.

На правой части рисунка видны четыре пути, ведущие в каждый узел решетки. Рядом проставлены расстояния (меры расходимости) этих путей от принятой последовательности на отрезке из 14 блоков. Мера верхнего пути значительно меньше мер нижних. Поэтому можно предположить, что верхний путь наиболее вероятен. Однако декодер Витерби, не зная следующих фрагментов принимаемой последовательности, вынужден запомнить все четыре пути на время приема   элементарных блоков. Число   называется шириной окна декодирования. Понятно, что для уменьшения ошибки декодирования следует выбирать   достаточно большим, в несколько раз превышающим длину блока, что, естественно, усложняет декодер. В данном случае  .

Левая часть рисунка демонстрирует возможную ситуацию неисправляемой ошибки. Существует два пути с одинаковыми мерами расходимости. Декодер может разрешить эту неопределенность двумя способами. Отметить этот участок как недостоверный или принять одно из двух решений: информационная последовательность равна 00000... или 10100.... Очевидно, расширение окна декодирования не позволяет исправить такую ошибку. Ее исправление возможно при использовании кода с большей корректирующей способностью.

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

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

2. Полученные меры расходимости ребер суммируются с расстоянием путей, которые они продолжают.

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

В результате этих операций к каждому узлу нового столбца вновь ведет один путь.

Минимум Хемминговского расстояния.

Расстояние Хемминга d(c,y) между последовательностями с и у это количество позиций, в которых с и у различаются.

Метод декодирования С по минимуму расстояния Хэмминга (МРХ) состоит в отображении y в такое слово Cc.i, для которого расстояние Хэмминга )y,cid( имеет минимальное значение. Каждая выходная последовательность y при этом будет отображаться в ближайшее по Хэммингу кодовое слово из С. Рее области будут строиться следующим образом:

Yi={y:d(c(i), y) > (d(c(i), y) для любого j не равного i.

Поэтому в таком канале минимизация расстояния Хемминга максимизирует функцию правдоподобия и следовательно, два метода декодирования МП и МРХ совпадают.