Концепция организации сетей

Декодирование помехоустойчивых кодов.

Рассмотрим основные принципы декодирования блочных и непрерывных кодов, используемых в режиме исправления и обнаружения ошибок. Наиболее распространенным способом исправления ошибок блочным кодом является декодирование по максимуму правдоподобия. Способ декодирования по максимуму правдоподобия основан на следующем очевидном положении: вероятность искажения кодовой комбинации уменьшается с ростом кратности ошибок, т.е. P(i, n) > P(i+1, n). Поэтому представляется естественным отождествлять принятую комбинацию с кодовой комбинацией, отстоящей от нее на наименьшее расстояние.

Процедура исправления ошибок реализуется в следующей последовательности:

1) Вычисляется расстояние Хэмминга d между принятой комбинацией z и всеми разрешенными комбинациями (vi | i =1...2k).

2) Принятая комбинация Z отождествляется с кодовой комбинацией, для которой справедливо d = min di.

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

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

 способ порогового декодирования;

 способ последовательного декодирования;

 способ декодирования по максимуму правдоподобия.

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

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

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

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

Количество линий, входящих в состав шины, принято называть разрядностью (шириной) этой шины. Ширина адресной шины, например, определяет максимальный размер оперативной памяти, которая может быть установлена в вычислительной системе. Ширина шины данных определяет максимальный объем информации, которая за один раз может быть получена или передана по этой шине.

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

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

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

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

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


Беспроводные сети