Повышение эффективности использования каналов передачи данных (повышение вероятностно-временных характеристик декодирования)

Введение

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

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

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

• сбои в какой-то части оборудования сети или возникновение неблагоприятных объективных событий в сети (например, коллизий при использовании метода случайного доступа в сеть). Как правило, система передачи данных готова к такого рода проявлениям и устраняетих с помощью планово предусмотренных средств;

• помехи, вызванные внешними источниками и атмосферными явлениями. Помехи – это электрические возмущения, возникающие в самой аппаратуре или попадающие в нее извне. Наиболее распространенными являются флуктуационные (случайные) помехи. Они представляют собой последовательность импульсов, имеющих случайную амплитуду и следующих друг за другом через различные промежутки времени. Примерами таких помех могут быть атмосферные и индустриальные помехи, которые обычно проявляются в виде одиночных импульсов малой длительности и большой амплитуды. Возможны и сосредоточенные помехи в виде синусоидальных колебаний. К ним относятся сигналы от посторонних радиостанций, излучения генераторов высокой частоты. Встречаются и смешанные помехи. В приемнике помехи могут настолько ослабить информационный сигнал, что он либо вообще не будет обнаружен, либо искажен так, что «единица» может перейти в «нуль» и наоборот.

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

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

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

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

Работа Хэмминга явилась катализатором цепной реакции выдвижения новых идей в области декодирования, которая началась с 1954 года. Американский ученый И.С. Рид был первым, кто использовал мажоритарное декодирование кодов Рида – Маллера. При мажоритарном декодировании для каждого информационного символа формируется нечетное число оценок путем сложения по модулю 2 определенных комбинаций символов принятого кода. Решение об истинном значении принятого символа принимается по мажоритарному принципу – если большее количество оценок равно 1, то принимается именно такое решение. В 1963 году Дж.Л. Месси [13, 25] установил общие принципы построения и декодирования подобных кодов. Достоинством мажоритарно декодируемых кодов является чрезвычайная простота и быстродействие алгоритмов декодирования. Однако класс таких кодов весьма мал, и эти коды слабее других. Значительный вклад в создание теории построения мажоритарно декодируемых кодов внесли в 1965 году советские ученые В.Д. Колесник и Е.Т. Мирончиков. [7, 35]

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

Повышение эффективности использования каналов передачи данных (повышение вероятностно-временных характеристик декодирования)

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

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

1. Проблему обеспечения требуемой верности Р_тр, принятой и выдаваемой потребителю после декодирования информации. При этом будем понимать, что вероятность ошибки Р_ош в такой информации не должна превышать при работе по любому из используемых каналов наперед заданной величины Р_тр. Обычно задачу обеспечения требуемой верности принятой информации определяют как «повышение верности», т.е. как снижение вероятности Р_ош относительно вероятности ошибки в используемом дискретном канале, описываемой вероятностью искажения символа Р₀. Для этой цели используют коды с обнаружением ошибок, с помощью которых выявляют и бракуют кодовые последовательности с ошибками, а также коды с исправлением t и менее ошибок. В случае обнаружения ошибок величина Р_ош определяется вероятностью того, что используемый код не бракует искаженную кодовую последовательность (не обнаруживает ошибку) при работе по данному каналу или классу каналов связи. Вопрос о гарантии требуемой величины Р_тр сводится к анализу обнаруживающей способности используемого кода в рассматриваемом классе каналов связи и к методам выбора типа и параметров (синтезу) кода, обеспечивающего Р_тр в любом из используемых каналов связи.

Широко используемые для исправления ошибок двоичные и q-ичные алгебраические коды с кодовым расстоянием d исправляют все векторы ошибок с весом не более t=(d-1)/2. С вероятностью , где P (i, n) – вероятность возникновений ровно i ошибок в кодовом блоке длиной п, такой код выдает потребителю информацию без ошибок. При числе ошибочных символов S>t может происходить либо отказ от декодирования, когда декодер выдает с вероятностью Р_ст сигнал о необходимости стирания кодового блока, либо имеет место декодирование с ошибкой, после чего искаженная информация с числом искаженных символов S'≶S выдается потребителю с вероятностью Р_ош.

Если считать, что код не исправляет ошибок кратности S>t, то Р_ст+Р_ош=Р₂ = . В этом случае проблема обеспечения требуемой верности передачи состоит из решения следующих задач:

а) определения значений вероятностей Р_ош и Р_ст для конкретного кода и различных характерных интервалов кратности ошибки от t+1 до d и выше;

б) оценки свойств дискретного канала путем описания его параметров, простейшими из которых являются значения P (i, n);

в) разработки в алгоритме декодирования надежного механизма выявления ситуации неисправляемых ошибок и выхода в отказ от декодирования.

Рисунок 1 – иллюстрирует отличие задачи обеспечения требуемой верности (кривая 1) от задачи повышения верности (кривая 2). При повышении верности обеспечивается Р_ош<Р_тр только при Р₀<Р_гр. При обеспечении требуемой верности любое качество канала (вплоть до его обрыва) не увеличивает вероятность Р_ош выше Р_тр, сводя все случаи невозможности правильного декодирования блока к отказу от декодирования, сохраняя способность выдачи потребителю информации при улучшении состояния канала, при. котором методы приема и обеспечения требуемых вероятностно-временных характеристик обмена информации (проблема 2) приводят к успешному декодированию и выдаче информации потребителю. Для такого канала полная группа событий содержит следующие события:

· правильный прием кодового блока, который не был искажен требуемой в канале или в котором правильно исправлена ошибка с вероятностью Р_п.пр;

· произошла ошибка декодирования и кодовый блок с ошибкой выдан потребителю с вероятностью Р_ош;

· произошел отказ от декодирования с вероятностью Р_отк.

Отнеся число исходов каждого события к числу переданных блоков, имеем Р_п.пр+Р_ош+Р_отк=1. Учитывая, что информация выдается потребителю в первых двух случаях, вероятность приема Р_пр=Р_п.пр+Р_ош.

Рис. 1. Сопоставление задач повышения и обеспечения требуемой верности передачи

Для любого кода, обеспечивающего требуемую верность, можно рассматривать две области: область приема и область отказа. В области приема вероятность ошибки равна нулю. Для кодов с обнаружением ошибки это случай, когда кодовый блок не искажен с вероятностью Р (0, п), а для кодов с исправлением ошибок – это возникновение не более t ошибок. При этом Р_ош=0; Р_пр=Р_п.пр; Р_отк=0. В области отказа (при кратности ошибки, превышающей t) Р_п.пр=0; Р_пр=Р_ош; Р_отк=1-Р_ош. Отметим что для каждой из этих областей понятие финальной вероятности ошибки Р_ош.ф как отношения числа блоков с ошибкой декодирования к числу принятых блоков является бессмысленным. Действительно, по определению, в области приема Р_ош.ф=0. В области отказа прием блока возможен только при ошибочном его декодировании, поэтому Р_ош.ф=1, причем для любого кода, независимо от его избыточности и того, какую часть ошибок он обнаруживает или исправляет.

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

В качестве вероятностно-временных характеристик (ВВХ) будем в первую очередь рассматривать две главные характеристики:

а) относительную скорость передачи информации по каналам с обратной связью R=(k/n) (1-Р_ст), где п, k – параметры используемого (п, k) – кода; Р_ст – вероятность стирания очередного кодового блока из-за обнаружения в нем неисправляемых соответствующим кодом ошибок или из-за особенностей используемого алгоритма обратной связи;

б) вероятность доведения сообщения заданного объема V в определенных условиях за время T-Р_дов(V, Т). Эта характеристика предполагает доведение сообщения с заданной вероятностью Р_тр и может использоваться в первую очередь в симплексных каналах, а также в дуплексных каналах, используемых для темповой передачи информации, или передачи в реальном масштабе времени.

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

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

Обнаружение ошибок с помощью блоковых (п, k) – кодов характеризуется меньшей чем исправление ошибок двоичными кодами, зависимостью вероятности необнаруженной ошибки Р_ош от свойств исходного дискретного канала. Такие коды, имеющие кодовое расстояние d, по определению кода обнаруживают все ошибки веса t<d с числом необнаруженных ошибок, равным числу ненулевых кодовых слов 2^k-1. Для наиболее конструктивных из этого класса циклических кодов известно и широко употребляется обнаружение ошибок за счет деления полинома, отображающего кодовую последовательность, на фиксированный порождающий полином кода g(X) степени п.

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

Однако нельзя строго утверждать, что блоковые коды с обнаружением ошибок обеспечивают Р_тр в произвольном канале. На практике для оценки вероятности необнаруженной ошибки блоковыми кодами [11, 38] пользуются двумя основными выражениями:

Р_ош ≈ P (≥1, n)•2^-(n-k),                                     (1)

Р_ош ≈ P (≥d, n)•2^-(n-k)                                      (2)

Обе эти оценки приемлемы для инженерных расчетов для относительно хороших каналов и кодов с достаточно большим числом избыточных символов r = n-k, но каждая обладает недостатками, связанными с невозможностью учета свойств конкретных кодов с их спектрами весов. Формула (1) правильно отражает число векторов необнаруженной ошибки и их долю от всех 2ⁿ векторов длины п, но не учитывает того обстоятельства, что все ошибки кратности от 1 до d-1 и от п-d+1 до п такими кодами всегда обнаруживаются.

Формула (2), напротив, учитывает частично последнее обстоятельство для ошибки кратности до d-1 включительно, но дает заведомо оптимистический результат, так как предполагает, что число необнаруженных ошибок менее 2^k-1, что неверно. Действительно, формула (2) предполагает отбрасывание из 2ⁿ векторов ошибки тех векторов, вес которых менее d и учитывает только (2^-(n-k)) – ю долю остальных векторов, что меньше 2^k-1.

Помехоустойчивые коды для обеспечения требуемой верности передаваемой информации имеют в настоящее время весьма широкую сферу применения. Развитие и широкое использование сетей ЭВМ, информационно-вычислительных сетей (ИВС), глобальных информационных сетей требуют разработки эффективных методов передачи и защиты дискретной информации от ошибок в каналах связи. Стремление упорядочить процедуры взаимодействия абонентов в ИВС явилось причиной создания Международной организацией стандартов (МОС) так называемой эталонной модели взаимодействия открытых систем (ЭМВОС). Иерархическое разделение функций обработки передаваемой информации привело к использованию понятия уровня, выполняющего определенную логическую функцию. Совокупность правил (процедур) взаимодействующих объектов ИВС одноименных уровней называют протоколом. Рекомендованная в ЭМВОС совокупность протоколов содержит семь следующих уровней: физический, уровень канала ПД или звена данных, сетевой, транспортный, сеансовый, представительный и прикладной. Причем уровень канала ПД имеет всегда, а транспортный и прикладной уровни, как правило, средства контроля верности принимаемой информации с помощью помехоустойчивого кода, допускающего простую программную реализацию в ЭВМ.

При обмене информацией в сетях ЭВМ, использующих на ребрах сети различные по физической природе и качеству канала связи, методы защиты от ошибок должны обеспечивать требуемую верность циркулирующих данных при работе по любому из каналов связи. Подобные требования предъявляются к каналам ПД, используемым в системах телемеханики и телеуправления, в АСУ различного типа. Наиболее сложной является задача обеспечения требуемой верности при работе по каналам низкого качества, когда вероятность искажения двоичного символа P₀>10^-2, и в каналах без обратной связи при использовании кодов с исправлением ошибок.

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

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