Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Результат поиска
Наименование:
Диплом Пути и методы повышения эффективности использования каналов передачи данных (повышение вероятностно-временных характеристик декодирования). Помехоустойчивое кодирование информации. Задание циклических кодов. Мажоритарное декодирование циклических кодов.
Информация:
Тип работы: Диплом.
Предмет: Схемотехника.
Добавлен: 24.02.2010.
Год: 2010.
Уникальность по antiplagiat.ru: < 30%
Описание (план):
53
Дипломная работа «Разработка методов мажоритарного декодирования с улучшенными вероятностно-временны и характеристиками»
Введение
Проблема обеспечения безошибочности (достоверности) передачи информации в сетях имеет очень важное значение. Если при передаче обычной телеграммы возникает в тексте ошибка или при разговоре по телефону слышен треск, то в большинстве случаев ошибки и искажения легко обнаруживаются по смыслу. Но при передаче данных одна ошибка (искажение одного бита) на тысячу переданных сигналов может серьезно отразиться на качестве информации.
Существует множество методов обеспечения достоверности передачи информации (методов защиты от ошибок), отличающихся по используемым для их реализации средствам, по затратам времени на их применение на передающем и приемном пунктах, по затратам дополнительного времени на передачу фиксированного объема данных (оно обусловлено изменением объема трафика пользователя при реализации данного метода), по степени обеспечения достоверности передачи информации. Практическое воплощение методов состоит из двух частей - программной и аппаратной. Соотношение между ними может быть самым различным, вплоть до почти полного отсутствия одной из частей.
Выделяют две основные причины возникновения ошибок при передаче информации в сетях:
* сбои в какой-то части оборудования сети или возникновение неблагоприятных объективных событий в сети (например, коллизий при использовании метода случайного доступа в сеть). Как правило, система передачи данных готова к такого рода проявлениям и устраняетих с помощью планово предусмотренных средств;
* помехи, вызванные внешними источниками и атмосферными явлениями. Помехи - это электрические возмущения, возникающие в самой аппаратуре или попадающие в нее извне. Наиболее распространенными являются флуктуационные (случайные) помехи. Они представляют собой последовательность импульсов, имеющих случайную амплитуду и следующих друг за другом через различные промежутки времени. Примерами таких помех могут быть атмосферные и индустриальные помехи, которые обычно проявляются в виде одиночных импульсов малой длительности и большой амплитуды. Возможны и сосредоточенные помехи в виде синусоидальных колебаний. К ним относятся сигналы от посторонних радиостанций, излучения генераторов высокой частоты. Встречаются и смешанные помехи. В приемнике помехи могут настолько ослабить информационный сигнал, что он либо вообще не будет обнаружен, либо искажен так, что «единица» может перейти в «нуль» и наоборот.
Трудности борьбы с помехами заключаются в беспорядочности, нерегулярности и в структурном сходстве помех с информационными сигналами. Поэтому защита информации от ошибок и вредного влияния помех имеет большое практическое значение и является одной из серьезных проблем современной теории и техники связи.
Среди многочисленных методов защиты от ошибок выделяются три группы методов: групповые методы, помехоустойчивое кодирование и методы защиты от ошибок в системах передачи с обратной связью.
Из групповых методов получили широкое применение мажоритарный метод, реализующий принцип Вердана, и метод передачи информационными блоками с количественной характеристикой блока.
Суть мажоритарного метода, давно и широко используемого, состоит в следующем. Каждое сообщение ограниченной длины передается несколько раз, чаще всего три раза. Принимаемые сообщения запоминаются, а потом производится их поразрядное сравнение. Суждение о правильности передачи выносится по совпадению большинства из принятой информации методом «два из трех».
Работа Хэмминга явилась катализатором цепной реакции выдвижения новых идей в области декодирования, которая началась с 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, причем для любого кода, независимо от его избыточности и того, какую часть ошибок он обнаруживает или исправляет.
2. Проблему обеспечения высоких вероятностно-временны характеристик обмена информацией или проблему помехоустойчивости. Эта проблема дополняет и делает одновременно более сложным решение первой проблемы, так как если не требовать высоких вероятностно-временны характеристик обмена, то для решений первой проблемы можно вообще ничего не принимать и стирать все принятые кодовые блоки.
В качестве вероятностно-временны характеристик (ВВХ) будем в первую очередь рассматривать две главные характеристики:
а) относительную скорость передачи информации по каналам с обратной связью R=(k/n) (1-Рст), где п, k - параметры используемого (п, k) - кода; Рст - вероятность стирания очередного кодового блока из-за обнаружения в нем неисправляемых соответствующим кодом ошибок или из-за особенностей используемого алгоритма обратной связи;
б) вероятность доведения сообщения заданного объема V в определенных условиях за время T-Рдов(V, Т). Эта характеристика предполагает доведение сообщения с заданной вероятностью Ртр и может использоваться в первую очередь в симплексных каналах, а также в дуплексных каналах, используемых для темповой передачи информации, или передачи в реальном масштабе времени.
3. Проблему сложности реализации устройств, осуществляющих наиболее трудоемкую обработку дискретной информации, к которой можно отнести кодирование и декодирование помехоустойчивых кодов, в том числе при использовании параллельных каналов или многократной передачи одного и того же сообщения. К этой же проблеме следует отнести задачу унификации аппаратуры передачи данных, имея при этом в виду создание таких методов помехоустойчивого кодирования и передачи информации и реализующей их аппаратуры, которые могли бы путем изменения перестраиваемых параметров аппаратуры обеспечивать работу по дуплексным и симплексным каналам, с исправлением и обнаружением ошибок помехоустойчивыми кодами, использование широкого набора типов дискретных каналов с различной интенсивностью и распределением потоков ошибок. При этом очень важно, чтобы замена дискретного канала требовала минимальных сведений о его качестве и потоках ошибок в канале. В самом лучшем случае сведений о потоке ошибок не требуется вообще, а решения о годности используемого канала вырабатываются на основе критериев, заложенных в алгоритме передачи информации (алгоритме декодирования) кода и связанных с невозможностью выполнения требуемых значений приведенных выше основных ВВХ.
Рассмотрим свойства наиболее широко применяемых на практике помехоустойчивых кодов с точки зрения поставленных выше проблем.
Обнаружение ошибок с помощью блоковых (п, k) - кодов характеризуется меньшей чем исправление ошибок двоичными кодами, зависимостью вероятности необнаруженной ошибки Рош от свойств исходного дискретного канала. Такие коды, имеющие кодовое расстояние d, по определению кода обнаруживают все ошибки веса t<d с числом необнаруженных ошибок, равным числу ненулевых кодовых слов 2k-1. Для наиболее конструктивных из этого класса циклических кодов известно и широко употребляется обнаружение ошибок за счет деления полинома, отображающего кодовую последовательность, на фиксированный порождающий полином кода g(X) степени п.
То есть среди известных кодов при аппаратной реализации циклические коды с обнаружением ошибок в наибольшей степени решают первую и третью проблемы. Известны попытки использовать такие коды в симплексных каналах в режиме многократной передачи кодового блока, кодированного циклическим кодом, а также мажоритарной обработкой одноименных двоичных символов различных блоков.
Однако нельзя строго утверждать, что блоковые коды с обнаружением ошибок обеспечивают Ртр в произвольном канале. На практике для оценки вероятности необнаруженной ошибки блоковыми кодами [11, 38] пользуются двумя основными выражениями:
Рош ? P (?1, n)*2-(n-k), (1)
Рош ? P (?d, n)*2-(n-k)(2)
Обе эти оценки приемлемы для инженерных расчетов для относительно хороших каналов и кодов с достаточно большим числом избыточных символов r = n-k, но каждая обладает недостатками, связанными с невозможностью учета свойств конкретных кодов с их спектрами весов. Формула (1) правильно отражает число векторов необнаруженной ошибки и их долю от всех 2n векторов длины п, но не учитывает того обстоятельства, что все ошибки кратности от 1 до d-1 и от п-d+1 до п такими кодами всегда обнаруживаются.
Формула (2), напротив, учитывает частично последнее обстоятельство для ошибки кратности до d-1 включительно, но дает заведомо оптимистический результат, так как предполагает, что число необнаруженных ошибок менее 2k-1, что неверно. Действительно, формула (2) предполагает отбрасывание из 2n векторов ошибки тех векторов, вес которых менее d и учитывает только (2-(n-k)) - ю долю остальных векторов, что меньше 2k-1.
Помехоустойчивые коды для обеспечения требуемой верности передаваемой информации имеют в настоящее время весьма широкую сферу применения. Развитие и широкое использование сетей ЭВМ, информационно-вычисли ельных сетей (ИВС), глобальных информационных сетей требуют разработки эффективных методов передачи и защиты дискретной информации от ошибок в каналах связи. Стремление упорядочить процедуры взаимодействия абонентов в ИВС явилось причиной создания Международной организацией стандартов (МОС) так называемой эталонной модели взаимодействия открытых систем (ЭМВОС). Иерархическое разделение функций обработки передаваемой информации привело к использованию понятия уровня, выполняющего определенную логическую функцию. Совокупность правил (процедур) взаимодействующих объектов ИВС одноименных уровней называют протоколом. Рекомендованная в ЭМВОС совокупность протоколов содержит семь следующих уровней: физический, уровень канала ПД или звена данных, сетевой, транспортный, сеансовый, представительный и прикладной. Причем уровень канала ПД имеет всегда, а транспортный и прикладной уровни, как правило, средства контроля верности принимаемой информации с помощью помехоустойчивого кода, допускающего простую программную реализацию в ЭВМ.
При обмене информацией в сетях ЭВМ, использующих на ребрах сети различные по физической природе и качеству канала связи, методы защиты от ошибок должны обеспечивать требуемую верность циркулирующих данных при работе по любому из каналов связи. Подобные требования предъявляются к каналам ПД, используемым в системах телемеханики и телеуправления, в АСУ различного типа. Наиболее сложной является задача обеспечения требуемой верности при работе по каналам низкого качества, когда вероятность искажения двоичного символа P0>10-2, и в каналах без обратной связи при использовании кодов с исправлением ошибок.
По указанным выше причинам представляется актуальной проблема создания методов защитыот ошибок для каналов ПД и других протокольных уровней, основанных на применении кодов, обеспечивающих заданную вероятность ошибки при использовании произвольных дискретных каналовсвязи с обеспечением высоких ВВХ обмена при простой реализации алгоритмов кодирования и декодирования.
Более сильная постановка задачи состоит в построении таких каналов ПД, в которых контролируется достигаемая верность и потребителю информации предоставляется возможность оперативно менять требования по гарантированной верности, принимая сообщение с нужной верностью и отказываясь от тех сообщений, верность которых не удовлетворяет потребителя информации.
2. Помехоустойчивое кодирование информации
Кодирование в широком смысле слова можно определить как процедуру взаимно однозначного отображения сообщений в сигналы, иными словами, преобразования сообщения в код. Декодированием называется обратный процесс. Таблица соответствия между совокупностью используемых сообщений и кодовыми комбинациями, которые их отображают, называется первичным кодом. В этом случае кодовая комбинация содержит k элементов. Кодовая комбинация избыточного кода содержит n элементов, где n > k.
Способность кода обнаруживать и исправлять ошибки обусловлена наличием избыточных элементов в кодовой комбинации r = n - k.
В этом случае общее число возможных кодовых комбинаций будет
, число разрешенных комбинаций , а запрещенных .
Искажение информации в процессе передачи сводится к тому, что некоторые из переданных элементов заменяются другими - неверными. При этом для систематических кодов из случаев передачи возможно случаев перехода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам, и случаев перехода в неразрешенные комбинации, которые могут быть обнаружены [5, 65]. Следовательно, часть опознанных ошибок от общего числа возможных случаев передачи составит
.
Например, при использовании одного избыточного элемента (r = 1) часть опознанных ошибок составляет
.
Для того чтобы искаженная кодовая комбинация была опознана с наименьшей ошибкой, необходимо чтобы остальные запрещенных комбинаций были разбиты на непересекающихся множеств , причем кодовые комбинации, принадлежащие , должны в наибольшей степени быть похожими на i-ю разрешенную комбинацию и должны быть приписаны ей.
Процедура опознания искаженной кодовой комбинации в этом случае будет состоять в ее сравнении со всеми кодовыми комбинациями. Когда произойдет совпадение с одной из комбинаций, принадлежащих , осуществится отождествление искаженной комбинации с i-й разрешенной, т.е. исправление ошибки. Ошибка будет исправлена в случаях из всех возможных. Отношение числа исправляемых кодом ошибочных кодовых комбинаций к числу обнаруживаемых ошибочных комбинаций равно [5, 67]:
.
Степень отличия любых двух кодовых комбинаций характеризуется расстоянием между ними в смысле Хэмминга, называемым кодовым расстоянием. Оно выражается числом элементов, в которых комбинации отличаются одна от другой, и обозначается через d. Минимальное количество элементов, в которых все комбинации кода отличаются друг от друга, называется минимальным кодовым расстоянием d0. Минимальное кодовое расстояние - параметр, определяющий помехоустойчивость избыточного кода. В общем случае для обнаружения всех ошибок до -кратных включительно минимальное кодовое расстояние
. (3)
Минимальное кодовое расстояние, необходимое для одновременного обнаружения и исправления ошибок:
, (4)
где t - число исправляемых ошибок.
Для кодов, только исправляющих ошибки:
(5)
Соотношения (3), (4) и (5) определяют лишь кратность гарантийно обнаруживаемых и исправляемых ошибок. Обычно коды обнаруживают и исправляют часть ошибок и более высокой кратности.
К наиболее употребляемым избыточным кодам можно отнести блоковые и непрерывные коды.
Блоковые коды характеризуются тем, что исходная непрерывная информационная последовательность разделяется на отдельные части, каждая из которых кодируется отдельно и независимо от других частей, образуя раз решенные слова избыточного кода.
Равномерные блоковые коды характеризуются одинаковой длиной разрешенных кодовых слов, в отличие от неравномерных кодов.
В непрерывных кодах исходная информационная последовательность не разделяется на части, а кодируется непрерывно, причем избыточные элементы формируются на определенных позициях между информационными. Равномерные блоковые коды подразделяются на линейные и нелинейные.
Линейные коды образуют наиболее обширный подкласс кодов и определяются тем, что сумма по модулю для двух и более разрешенных комбинаций кода дает комбинацию этого же кода.
Нелинейные коды не обладают этим свойством. Примером нелинейных кодов является код с постоянным весом, применяемый в телеграфии. В некоторых случаях линейные коды называют групповыми, что обусловлено математическим описанием подмножества разрешенных кодовых слов длины n как подгруппы в группе всех слов длины n. Линейный код, в котором информационные и проверочные элементы разделены и расположены на строго определенных позициях, называется систематическим, в отличие от несистематических кодов, в которых нельзя в явном виде выделить информационные и проверочные элементы. Систематические коды получили наибольшее распространение. Систематические коды, как правило, обозначаются (n, k) - кодами и включают: коды с проверкой на четность, коды Хэмминга, циклические коды, коды с повторением, итеративные коды, каскадные, коды Рида-Малера, дециклические коды и много других [3, 32].
В информационных системах для передачи коротких команд управления нашли наибольшее применение циклические коды; для обнаружения ошибок при встроенном контроле аппаратуры обработки - коды с одной проверкой на четность; при хранении информации - коды с повторением; при непрерывной передаче больших массивов измерительных данных - сверточные коды. Для повышения эффективности обработки избыточных кодов развиваются различные квазиоптимальные методы декодирования, использующие дополнительную информацию о ненадежных элементах передаваемых данных.
3. Циклические коды
3.1 Задание циклических кодов
Наиболее распространенным подклассом линейных кодов являются циклические коды. Это обусловлено относительно простым построением кодера и декодера, обнаруживающего ошибки, при достаточно высоких корректирующих способностях кода. Эти коды позволяют преодолеть некоторые трудности, связанные с технической реализацией, свойственные линейным кодам. В информационной системе циклические коды предпочтительны для передачи сообщений небольшой длины, например, команд управления объектами.
Алгебраическая структура циклических кодов впервые была исследована Боузом, Чоудхури и Хоквингемом, поэтому они известны как БЧХ-коды. Эти коды характеризуются следующими свойствами [7, 110]: длиной кодовых последовательностей
(6)
где т = 1,2,3,…;
числом проверочных элементов, не превышающим величины , т.е.
(7)
способностью обнаруживать все пакеты ошибок длины
(8)
циклическим сдвигом разрешенной комбинации кода, приводящим к образованию разрешенной комбинации; этого же кода.
Возможно задание циклических БЧХ-кодов при помощи порождающих или проверочных матриц аналогично общим правилам, построения линейных кодов. Однако воспользуемся более простыми инженерными методиками, базирующимися на алгебраических понятиях. В этом случае более удобной является запись кодовых комбинаций в виде полинома переменной х:
Коэффициенты aiпредставляют собой цифры данной системы счисления. В двоичной системе счисления коэффициенты могут принимать одно из двух значений 0 или 1. Так, двоичное четырехразрядное число 1001 может быть записано в виде полинома
Это выражение устанавливает однозначное соответствие между двумя формами записи кодовых комбинаций.
Циклические коды образуются умножением каждой комбинации - элементного безызбыточного кода, выраженной в виде многочлена G (х), на образующий полином Р (х) степени (п - k). При этом умножение производится по обычным правилам с приведением подобных членов по модулю два [6, 98]. Следовательно, в случае отсутствия ошибок любая разрешенная кодовая комбинация циклического кода должна разделиться на образующий полином Р (х) без остатка. Появление остатка от деления указывает на наличие ошибок в кодовой комбинации. При этом гарантийно обнаруживаются ошибки, определяемые выражениями (7) и (8).
Кроме того, обнаруживается большая часты ошибок более высокой кратности.
Широкое применение нашел другой метод, который в отношении степени избыточности и помехоустойчивости приводит к построению эквивалентного циклического кода. В соответствии с этим методом каждая кодовая комбинация первичного кода G (х) умножается на одночлен X n - k. Это эквивалентно приписыванию справа к комбинации G (х), записанной в двоичной форме, (п - k) нулей. Произведение G(х) x n - k делится на образующий полином Р (х) степени (п - k):
(9)
где Q (х) - частное от деления такой же степени, как и G (х); R (х) - остаток.
Так как частное Q (х) имеет такую же степень, как и кодовая комбинация G (х), то, следовательно, Q (х) является кодовой комбинацией этого же простого k-элементного кода.
Умножая обе части равенства на Р (х) получим:
(10)
Здесь знак минус заменен знаком плюс, так как сложение и вычитание по модулю два - операции эквивалентные.
Из полученного равенства видно, что кодовая комбинация циклического кода может быть получена двумя эквивалентными методами, причем второй метод приводит к построению систематического циклического кода, в котором информационные и проверочные элементы разделены. А так как информационные элементы непосредственно принимаются из канала связи, то эффект размножения ошибок в информационной части кодовой комбинации будет отсутствовать.
3.2 Коды с постоянной четностью единиц
Наименьшей избыточностью обладают циклические (k + 1, k) - коды, имеющие один проверочный элемент и получившие название кодов с постоянной четностью единиц. Построение этих кодов осуществляется при помощи образующего полинома
методами, изложенными в п. 4.1. При этом разрешенные кодовые слова циклического (k + 1, k) - кода во всех случаях содержат четное число единиц. Докажем это свойство, используя метод построения циклических кодов, основанный на умножении комбинаций G (х) на образующий полином
Р (х) = х + 1.
Так как образующий полином Р (х) является двучленом, то произведение G (х) Р (х) независимо от числа членов первого сомножителя
G(х) всегда будет содержать четное число членов.
Доказанное свойство определяет метод построения кодов с постоянной четностью единиц, наиболее пригодный для технической реализации и приводящий к получению кодовых комбинаций систематического кода.
Коды с постоянной четностью единиц позволяют обнаружить любые ошибки нечетной кратности, т.е. для этих; кодов = 1,3,5,…, l, где l = k для нечетных значений k и l = k + 1 для четных значений k.
3.3 Помехоустойчивость циклических кодов
Циклические коды можно использовать в следующих режимах: для исправления ошибок; для обнаружения ошибок; для исправления и обнаружения ошибок.
Достоверность передаваемой информации. Наиболее предпочтительным является использование циклических кодов в режиме обнаружения ошибок, так как при этом достигается наибольшая достоверность передаваемой информации, определяемая вероятностью необнаруженных ошибок:
(11)
где - вероятность ошибок кратности, большей чем ; - кратность гарантийно обнаруживаемых циклическим кодом ошибок;- коэффициент, учитывающий долю необнаруживаемых ошибок более высокой кратности, чем .
C учетом выражения (11) получим
(12)
При пР0 1, ограничиваясь первым членом суммы, получим приближенное выражение, пригодное для инженерных расчетов:
(13)
При передаче информации в канале связи с группирующимися ошибками, определяя , и подставляя в (11), получим приближенное выражение
(14)
Для точных расчетов вероятность должна определяться из выражения (3).
Использование циклических кодов для исправления ошибок приводит к снижению достоверности передаваемой информации, которая может быть определена по формулам (12), (13) и (14), если исключить коэффициент и вместо параметра подставить параметр t, который определяет кратность гарантийно исправляемых циклическим кодом ошибок и связан с соотношением
. (15)
Режим одновременного исправления и обнаружения ошибок по достигаемой достоверности занимает промежуточное положение между рассмотренными режимами. Вероятность необнаружения ошибок в этом случае может быть вычислена по формулам (11) - (13), если параметр уменьшить на величину t.
В режиме исправления ошибок достоверность снижается по сравнению с режимом обнаружения ошибок. Это позволяет сделать вывод, что наиболее рациональными следует считать такие системы передачи дискретной информации, в которых циклические коды используются для обнаружения ошибок.
В некоторых случаях, когда используются каналы связи достаточно низкого качества, находит применение режим одновременного исправления и обнаружения ошибок. Это позволяет уменьшить потери информации и увеличить относительную скорость передачи.
Потери информации. Потери информации имеют место в том случае, когда возникает ошибка, необнаруживаемая циклическим кодом, поэтому для режима обнаружения ошибок можно записать, что
(16)
где Рош - вероятность появления любой ошибки в кодовой комбинации. Так как в реальных системах Рн.о.<Рош, то можно положить, что
(17)
В режиме одновременного исправления и обнаружения ошибок исправляются ошибки до t - кратных включительно. Поэтому потери будут обусловлены абсолютным большинством ошибок, кратность которых превышает t, т.е.
, (18)
где- вероятность появления i-кратных ошибок.
4. Мажоритарное декодирование циклических кодов
Декодирование циклических мажоритарных кодов с повторением. При декодировании циклических кодов, допускающих мажоритарную обработку, процесс декодирования может быть осуществлен только после приема всей комбинации циклического (п, k) - кода. Для кодов с повторением мажоритарная обработка заканчивается после приема всех повторений комбинации. Использование для помехоустойчивого кодирования сообщений одновременно циклических мажоритарных кодов и метода многократных повторений позволяет обеспечить требуемые характеристики по достоверности и надежности передачи информации при использовании каналов связи низкого качества.
На рис. 2 изображена функциональная схема декодирующего устройства для циклических мажоритарных кодов с повторением. Устройство содержит регистр сдвига 1, сумматоры по модулю два 2, распределитель 3, счетчики мажоритарных проверок 4 - 1, 4-2,…, 4 - k, блок запоминания 5, блок, сравнения 6 и дешифратор 7.
Регистр сдвига установлен для записи п элементов одной кодовой комбинации циклического (п, k) - кода и перезаписи комбинации по цепи обратной связи при формировании результатов мажоритарных проверок.
Сумматоры по модулю два 2 предназначены для вычисления мажоритарных проверок путем суммирования импульсов с различных ячеек регистра сдвига 1 с целью получения серии импульсов, из которых затем по большинству определяется значение информационного элемента. Входы сумматоров подключены к ячейкам регистра сдвига в соответствии с системой мажоритарных проверок для конкретного циклического кода.
Рис. 2
Распределитель 3 служит для направления результатов мажоритарных проверок с выходов сумматоров в счетчик того информационного элемента, которому соответствуют эти проверки.
Счетчики мажоритарных проверок 4-1, 4-2,…. 4-k используются для подсчета результатов мажоритарных проверок. Они выполнены по схеме с несколькими порогами срабатывания. Каждый порог определяется числом принятых кодовых комбинаций, по результатам мажоритарных проверок которых вычисляются информационные элементы. В общем случае число счетчиков равняется числу информационных элементов k в исходной кодовой комбинации. Если l - число мажоритарных проверок для одного информационного элемента за одно повторение, то минимальный порог определится величиной 0,5l (l - четное) или 0,5 (l+ 1). где l - нечетное. За m повторений порог определится величиной 0,5 lm или 0,5 (1m + 1). За все N повторений порог определится величиной 0,5 lm или 0,5 (lm + 1). Так, для циклического (7,3) - кода с трехкратным повторением l = 4, минимальный порог за одно повторение равен двум, порог за два повторения равен четырем и порог за все повторения равен 6.
Рис. 3
При этом счетчик мажоритарных проверок для одного информационного элемента (рис. 3) будет состоять из трех двоичных разрядов и значе и т.д.................
