Emporio Armani мужские    часы

Emporio Armani мужские часы

Гуманитарные науки

У нас студенты зарабатывают деньги

 Дипломы, работы на заказ, недорого

Дипломы, работы на заказ, недорого

 Cкачать    курсовую

Cкачать курсовую

 Контрольные работы

Контрольные работы

 Репетиторы онлайн по английскому

Репетиторы онлайн по английскому

Приглашаем к сотрудничеству преподователей

Приглашаем к сотрудничеству преподователей

Готовые шпаргалки, шпоры

Готовые шпаргалки, шпоры

Отчет по практике

Отчет по практике

Приглашаем авторов для работы

Авторам заработок

Решение задач по математике

Закажите реферат

Закажите реферат

Курсовой расчет по сопромату Профилактическое обслуживание ПК Электротехника Контрольная по математике Эпоха становления русской живописи

Эффективная организация обмена информации

Методика построения помехоустойчивых кодов. Информационный предел избыточности

Кодирование с помощью которого можно устранять ошибки обусловленные наличием шума в канале называется помехоустойчивым. Коды способные исправлять и обнаруживать ошибки называется помехоустойчивым кодом. К сожалению основная теорема кодирования Шеннона не конструктивна, она не указывает способ построения конкретного оптимального помехоустойчивого кода, обеспечивающего предельное согласование сигнала с каналом, существование которого доказывает. Вместе с тем обосновав принципиальную возможность построения помехоустойчивых кодов, обеспечивающих идеальную передачу. Теория Шеннона мобилизовала усилия ученых на разработку конкретных кодов. В результате в настоящее время теория помехоустойчивого кодирования превратилась в самостоятельную науку в развитии которой достигнуты большие успехи.
Рассмотрим основополагающие принципы заложенные в основу построения помехоустойчивых кодов. Как следует из доказательства основной теоремы Шеннона неприменимым свойством помехоустойчивых кодов является наличие избыточности. При этом необходима не просто любая избыточность, а специфическая, определяемая свойствами канала и правилом построения кода. И позволяющая с минимальными затратами повысить вероятность передачи. В ситуации когда источник сообщений обладает собственной существенной избыточностью, которая в принципе тоже в определенной степени повышает достоверность передачи информации, но не так эффектно как это возможно. Поступают следующим образом: сначала с помощью эффективного кодирования до минимума уменьшают избыточность источника сообщений, а затем в процессе помехоустойчивого кодирования вносят в передаваемый сигнал избыточность, позволяющую простыми средствами поднять верность. Таким образом эффективное кодирование может сочетаться с помехоустойчивым.
Помехоустойчивые коды можно подразделить на два больших класса блочные и непрерывные. В случае блочных кодов, при кодировании, каждому дискретному сообщению ставится в соответствие отдельный блок кодовых символов называемого кодовой комбинацией. Непрерывные коды образуют последовательность символов неразделяемых на кодовые комбинации.
[an error occurred while processing this directive]
Рассмотрим принцип построения помехоустойчивых блочных кодов. Избыточность обуславливающая корректирующие свойства равномерного блочного кода обычно вводится за счет выполнения неравенства mn M (2.29), где m-основание кода т.е. объем алфавита используемых кодовых символов, n-длина или количество разрядов кодовой комбинации, М-количество сообщений подлежащих кодированию. Выполнение этого неравенства означает, что для передачи знаков сообщения используют лишь часть М возможных кодовых комбинаций. Используемые кодовые комбинации называют разрешенными. Неиспользуемые mn -M комбинации являются запрещенными. На вход канала подаются только разрешенные комбинации. Если вследствие помех один или несколько символов приняты ошибочно, то на выходе канала появляется запрещенная комбинация, что и говорит о наличии ошибки. Для того, чтобы обеспечить выполнение (2.29) необходимо выбирать n  K , где К-минимальное целое, удовлетворяющее неравенству mKM (2.30). Число К обычно называют количеством информационных разрядов кодовой комбинации, поскольку именно столько разрядов должна содержать комбинация кода с основанием m, чтобы число разных кодовых комбинаций было не меньше числа сообщений М подлежащих передаче. R=n-K разрядов кодовой комбинации необходимых для передачи полезной информации называются проверочными. Количество их и определяет избыточность помехоустойчивого кода. При использовании помехоустойчивого кода возможно декодирование с обнаружением и исправлением ошибок. В первом случае на основе анализа принятой комбинации выясняется, является ли она разрешенной или запрещенной. После этого запрещенная комбинация либо отбрасывается, либо уточняется путем посылки запроса на повторение переданной информации. Во втором случае при приеме запрещенной комбинации определенным способом выявляются и исправляются содержащиеся в ней ошибки. Максимальные числа ошибок в кодовой комбинации q и S которые могут быть обнаружены (q) или исправлены (S) с помощью данного кода называются соответственно обнаруживающей или исправляющей способностью кода. В значении q и S определяются величиной dmin минимальным кодовым расстоянием между ближайшими разрешенными комбинациями. Под кодовым расстоянием понимают количество неодинаковых разрядов в кодовых комбинациях. Величина dmin в помехоустойчивом коде зависит от соотношения n и К т.е. от числа r проверочных разрядов кода.
Рассмотрим информационный (т.е. базирующий на идеях Теории Информации) подход позволяющий оценить необходимую минимальную избыточность, выраженную в количестве проверочных разрядов rmin блочного помехоустойчивого кода длиной n с заданной исправляющей способностью S. Пусть имеется код с основанием m и с исправляющей способностью S. И используется декодирование с исправлением ошибок. На приеме при использовании такого кода возможно две ситуации: правильный прием сообщения и неправильный. Осуществление с вероятностью PH. Неправильный прием может произойти в том случае, когда из-за превышения числом ошибок пришедшей из канала кодовой комбинации значение S она может превратиться в одну из других разрешенных кодовых комбинаций. В свою очередь правильный прием осуществляется либо в том случае, когда в принимаемой комбинации отсутствуют ошибки (обозначим вероятность такого сообщения Р0), либо Nправ в случаях когда в принятой комбинации присутствуют ошибки которые могут быть исправлены рассмотренным кодом. Вероятности таких случаев обозначим через Pj j=1  Nправ. Для решения поставленной задачи определим минимальное количество информации, которой может быть описана совокупность событий, включающая появление одной из конкретных ошибок и отсутствие ошибок или появление некорректных ошибок. Зная эту величину и максимальное количество информации которое может содержать один проверочный символ кода можно определить минимальное число проверочных символов.
Количество информации необходимо для описания указанных событий (2.31) (в случае отсутствия ошибки учтем включением нуля в предел суммирования). Максимальное количество информации которое может содержать символ кода с основанием m в соответствии с (1.6) равно log2m. Следовательно число проверочных разрядов в комбинации кода не может быть меньше, чем (2.32). Определенную таким образом величину rmin называют информационным пределом избыточности. Найдем значение rmin для двоичного канала с независимыми ошибками. В таком канале появление предыдущей ошибки не влечет за собой появление последующей. В этой ситуации число R(i) ошибок кратности i в кодовой комбинации длиной n равно числу сочетаний .

(2.33).

Поскольку ошибки независимы вероятность P(i) возникновения в кодовой комбинации ошибки кратности i равна P(i)=Pi(1-P)n-i (2.34), где Р-вероятность ошибки в канале. Учитывая, что в данном случае Nпр=S выражение (2.31) можно записать в виде . Вторым слагаемым можно пренебречь поскольку, описываемая им функция не используется в процессе исправления ошибок. Поэтому с учетом (2.23 и 2.24) имеем (2.35). Рассмотрим частный случай когда возникновение конкретной ошибки любой кратности и отсутствие ошибок имеют равную вероятность, т.е. Pi(1-P)n-i=P1 при любом i. Величину Р1 определим из условия нормировки (2.36), отражающего тот факт, что вероятность появления ошибки какой-либо кратности, включения и нулевую равна единице. Из (2.36) имеем следовательно (2.37). Поскольку под двоичной, то есть m=2 c учетом (2.37 и 2.38) имеем . Найденное таким образом значение rmin совпадает с оценками полученными другим методами в частности с нижним пределом Хэмминга. Аналогичным образом могут быть найдены информационные пределы избыточности для других конфигураций ошибок в канале, например для пакетных ошибок, когда одиночные ошибки группируются в пакеты различной кратности. Полученные при этом результаты так же хорошо согласовывается с выводами полученными другими методами. Найденное таким образом значение rmin совпадает с оценками, полученными другими методами, в частности, с нижним пределом Хэмминга. Аналогичным образом могут быть найдены информационные пределы избыточности для других конфигураций ошибок в канале, например для пакетных ошибок, когда одиночные ошибки группируются в пакеты различной кратности. Получаемые при этом результаты также хорошо согласуются с выводами, полученными другими методами.