Разработка методов мажоритарного декодирования с улучшенными вероятностно-временными характеристиками (стр. 1 из 9)
Дипломная работа
«Разработка методов мажоритарного декодирования с улучшенными вероятностно-временными характеристиками»
Проблема обеспечения безошибочности (достоверности) передачи информации в сетях имеет очень важное значение. Если при передаче обычной телеграммы возникает в тексте ошибка или при разговоре по телефону слышен треск, то в большинстве случаев ошибки и искажения легко обнаруживаются по смыслу. Но при передаче данных одна ошибка (искажение одного бита) на тысячу переданных сигналов может серьезно отразиться на качестве информации.
Существует множество методов обеспечения достоверности передачи информации (методов защиты от ошибок), отличающихся по используемым для их реализации средствам, по затратам времени на их применение на передающем и приемном пунктах, по затратам дополнительного времени на передачу фиксированного объема данных (оно обусловлено изменением объема трафика пользователя при реализации данного метода), по степени обеспечения достоверности передачи информации. Практическое воплощение методов состоит из двух частей – программной и аппаратной. Соотношение между ними может быть самым различным, вплоть до почти полного отсутствия одной из частей.
Выделяют две основные причины возникновения ошибок при передаче информации в сетях:
• сбои в какой-то части оборудования сети или возникновение неблагоприятных объективных событий в сети (например, коллизий при использовании метода случайного доступа в сеть). Как правило, система передачи данных готова к такого рода проявлениям и устраняетих с помощью планово предусмотренных средств;
• помехи, вызванные внешними источниками и атмосферными явлениями. Помехи – это электрические возмущения, возникающие в самой аппаратуре или попадающие в нее извне. Наиболее распространенными являются флуктуационные (случайные) помехи. Они представляют собой последовательность импульсов, имеющих случайную амплитуду и следующих друг за другом через различные промежутки времени. Примерами таких помех могут быть атмосферные и индустриальные помехи, которые обычно проявляются в виде одиночных импульсов малой длительности и большой амплитуды. Возможны и сосредоточенные помехи в виде синусоидальных колебаний. К ним относятся сигналы от посторонних радиостанций, излучения генераторов высокой частоты. Встречаются и смешанные помехи. В приемнике помехи могут настолько ослабить информационный сигнал, что он либо вообще не будет обнаружен, либо искажен так, что «единица» может перейти в «нуль» и наоборот.
Трудности борьбы с помехами заключаются в беспорядочности, нерегулярности и в структурном сходстве помех с информационными сигналами. Поэтому защита информации от ошибок и вредного влияния помех имеет большое практическое значение и является одной из серьезных проблем современной теории и техники связи.
Среди многочисленных методов защиты от ошибок выделяются три группы методов: групповые методы, помехоустойчивое кодирование и методы защиты от ошибок в системах передачи с обратной связью.
Из групповых методов получили широкое применение мажоритарный метод, реализующий принцип Вердана, и метод передачи информационными блоками с количественной характеристикой блока.
Суть мажоритарного метода, давно и широко используемого, состоит в следующем. Каждое сообщение ограниченной длины передается несколько раз, чаще всего три раза. Принимаемые сообщения запоминаются, а потом производится их поразрядное сравнение. Суждение о правильности передачи выносится по совпадению большинства из принятой информации методом «два из трех».
Работа Хэмминга явилась катализатором цепной реакции выдвижения новых идей в области декодирования, которая началась с 1954 года. Американский ученый И.С. Рид был первым, кто использовал мажоритарное декодирование кодов Рида – Маллера. При мажоритарном декодировании для каждого информационного символа формируется нечетное число оценок путем сложения по модулю 2 определенных комбинаций символов принятого кода. Решение об истинном значении принятого символа принимается по мажоритарному принципу – если большее количество оценок равно 1, то принимается именно такое решение. В 1963 году Дж.Л. Месси [13, 25] установил общие принципы построения и декодирования подобных кодов. Достоинством мажоритарно декодируемых кодов является чрезвычайная простота и быстродействие алгоритмов декодирования. Однако класс таких кодов весьма мал, и эти коды слабее других. Значительный вклад в создание теории построения мажоритарно декодируемых кодов внесли в 1965 году советские ученые В.Д. Колесник и Е.Т. Мирончиков. [7, 35]
Использование методов передачи, основанных на применении мажоритарного декодирования двоичных последовательностей, направлено на решение ряда задач, которые можно свести к улучшению характеристик каналов передачи данных и к созданию новых методов кодирования.
1. Повышение эффективности использования каналов передачи данных (повышение вероятностно-временных характеристик декодирования)
Изложение мажоритарного метода декодирования будет неполным без рассмотрения вопросов технической реализации, анализа и синтеза алгоритмов передачи данных, а также сопоставления с известными методами по основным характеристикам, описывающим эффективность каналов передачи данных.
Рассматривая задачу повышения эффективности использования каналов передачи данных, можно выделить три важнейшие проблемы:
1. Проблему обеспечения требуемой верности Ртр, принятой и выдаваемой потребителю после декодирования информации. При этом будем понимать, что вероятность ошибки Рош в такой информации не должна превышать при работе по любому из используемых каналов наперед заданной величины Ртр. Обычно задачу обеспечения требуемой верности принятой информации определяют как «повышение верности», т.е. как снижение вероятности Рош относительно вероятности ошибки в используемом дискретном канале, описываемой вероятностью искажения символа Р0. Для этой цели используют коды с обнаружением ошибок, с помощью которых выявляют и бракуют кодовые последовательности с ошибками, а также коды с исправлением t и менее ошибок. В случае обнаружения ошибок величина Рош определяется вероятностью того, что используемый код не бракует искаженную кодовую последовательность (не обнаруживает ошибку) при работе по данному каналу или классу каналов связи. Вопрос о гарантии требуемой величины Ртр сводится к анализу обнаруживающей способности используемого кода в рассматриваемом классе каналов связи и к методам выбора типа и параметров (синтезу) кода, обеспечивающего Ртр в любом из используемых каналов связи.
Широко используемые для исправления ошибок двоичные и q-ичные алгебраические коды с кодовым расстоянием d исправляют все векторы ошибок с весом не более t=(d-1)/2. С вероятностью 
, где P (i, n) – вероятность возникновений ровно i ошибок в кодовом блоке длиной п, такой код выдает потребителю информацию без ошибок. При числе ошибочных символов S>t может происходить либо отказ от декодирования, когда декодер выдает с вероятностью Рст сигнал о необходимости стирания кодового блока, либо имеет место декодирование с ошибкой, после чего искаженная информация с числом искаженных символов S'≶S выдается потребителю с вероятностью Рош.
Если считать, что код не исправляет ошибок кратности S>t, то Рст+Рош=Р2 = 
. В этом случае проблема обеспечения требуемой верности передачи состоит из решения следующих задач:
а) определения значений вероятностей Рош и Рст для конкретного кода и различных характерных интервалов кратности ошибки от t+1 до d и выше;
б) оценки свойств дискретного канала путем описания его параметров, простейшими из которых являются значения P (i, n);
в) разработки в алгоритме декодирования надежного механизма выявления ситуации неисправляемых ошибок и выхода в отказ от декодирования.
Рисунок 1 – иллюстрирует отличие задачи обеспечения требуемой верности (кривая 1) от задачи повышения верности (кривая 2). При повышении верности обеспечивается Рош<Ртр только при Р0<Ргр. При обеспечении требуемой верности любое качество канала (вплоть до его обрыва) не увеличивает вероятность Рош выше Ртр, сводя все случаи невозможности правильного декодирования блока к отказу от декодирования, сохраняя способность выдачи потребителю информации при улучшении состояния канала, при. котором методы приема и обеспечения требуемых вероятностно-временных характеристик обмена информации (проблема 2) приводят к успешному декодированию и выдаче информации потребителю. Для такого канала полная группа событий содержит следующие события:
· правильный прием кодового блока, который не был искажен требуемой в канале или в котором правильно исправлена ошибка с вероятностью Рп.пр;
· произошла ошибка декодирования и кодовый блок с ошибкой выдан потребителю с вероятностью Рош;
· произошел отказ от декодирования с вероятностью Ротк.
Отнеся число исходов каждого события к числу переданных блоков, имеем Рп.пр+Рош+Ротк=1. Учитывая, что информация выдается потребителю в первых двух случаях, вероятность приема Рпр=Рп.пр+Рош.
Рис. 1. Сопоставление задач повышения и обеспечения требуемой верности передачи
Для любого кода, обеспечивающего требуемую верность, можно рассматривать две области: область приема и область отказа. В области приема вероятность ошибки равна нулю. Для кодов с обнаружением ошибки это случай, когда кодовый блок не искажен с вероятностью Р (0, п), а для кодов с исправлением ошибок – это возникновение не более t ошибок. При этом Рош=0; Рпр=Рп.пр; Ротк=0. В области отказа (при кратности ошибки, превышающей t) Рп.пр=0; Рпр=Рош; Ротк=1-Рош. Отметим что для каждой из этих областей понятие финальной вероятности ошибки Рош.ф как отношения числа блоков с ошибкой декодирования к числу принятых блоков является бессмысленным. Действительно, по определению, в области приема Рош.ф=0. В области отказа прием блока возможен только при ошибочном его декодировании, поэтому Рош.ф=1, причем для любого кода, независимо от его избыточности и того, какую часть ошибок он обнаруживает или исправляет.