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

Помехоустойчивые коды. Классы кодов и их характеристики.

Принципы построения помехоустойчивых кодов.

Проблема повышения достоверности обусловлена несоответствием между требованиями, предъявляемыми при передаче данных и качеством реальных каналов связи. В сетях передачи данных АСУ требуется обеспечить вероятность ошибочного приема комбинации первичного кода не выше 106...109. При использовании реальных каналов связи (вероятность искажения бита не более 

102...103) и простого (безизбыточного) кода, указанная вероятность не превышает 5*103.

Решение задачи повышения достоверности осуществляется в настоящее время в двух направлениях:

  совершенствование каналообразующей аппаратуры;

 использование специальных процедур, основанных на использовании

помехоустойчивых (корректирующих) кодов.

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

Применение корректирующих кодов, как правило, связано с разбиением сообщений на блоки из k элементов, называемых k элементными комбинациями.

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

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

Пусть zi произвольная n элементная двоичная комбинация, общее количество различных комбинаций длины n равно 2n. Если из множества Z = {zi | i = 1...2n } выбрать по некоторому правилу Nk < 2n комбинаций, то полученное множество V = {vi | i= 1...Nk}, V Ì Z будет корректирующим кодом.

Комбинации vi называются кодовыми или разрешенными комбинациями, а комбинации zi V запрещенными комбинациями.

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

Задача кодирования это задача получения kэлементного блока из принятых комбинаций множества Z при одновременном обнаружении или исправлении ошибок.

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

 обнаружения ошибок;

 исправления ошибок;

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

 Ввод-вывод

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

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

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

Основные параметры корректирующих кодов. Комбинация А = (а 0, а1, а2,..., аn1), где аi элементы, значения которых равны 0 или 1, характеризуются весом

  n1 W = S ai, т.е. числом единиц в ней. i=0.

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

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


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