Разработка методов мажоритарного декоди-рования с улучшенными вероятностно-временными характеристиками

Содержание

Введение 3
1. Повышение эффективности использования каналов передачи данных (повышение вероятностно-временных характеристик декодирования) 6
2. Помехоустойчивое кодирование информации 14
3. Циклические коды 18
3.1. Задание циклических кодов 18
3.2. Коды с постоянной четностью единиц 21
3.3. Помехоустойчивость циклических кодов 22
4. Мажоритарное декодирование циклических кодов 25
5. Мажоритарное декодирование кодов с повторением 30
5.1. Адаптивное мажоритарное декодирование кодов с повторением 30
5.2. Расширение области адаптивного мажоритарного декодирования кодов с повторением 35
5.3. Мажоритарное декодирование избыточных (n, к) -кодов с повторением 39
5.4. Поэтапная обработка кодов с повторением 42
Заключение 49
Литература 50

...

Введение 3
1. Повышение эффективности использования каналов передачи данных (повышение вероятностно-временных характеристик декодирования) 6
2. Помехоустойчивое кодирование информации 14
3. Циклические коды 18
3.1. Задание циклических кодов 18
3.2. Коды с постоянной четностью единиц 21
3.3. Помехоустойчивость циклических кодов 22
4. Мажоритарное декодирование циклических кодов 25
5. Мажоритарное декодирование кодов с повторением 30
5.1. Адаптивное мажоритарное декодирование кодов с повторением 30
5.2. Расширение области адаптивного мажоритарного декодирования кодов с повторением 35
5.3. Мажоритарное декодирование избыточных (n, к) -кодов с повторением 39
5.4. Поэтапная обработка кодов с повторением 42
Заключение 49
Литература 50

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

а кратность исправляемых ошибок
(20)
Характеристики (19) и (20) позволяют определить достоверность информации первого и второго этапов обработки по методике (п.3.3).
Таким образом, можно отметить, что наряду с разра­ботанными процедурами обнаружения и исправления оши­бок циклические коды хорошо совместимы с процедурой поэтапного принятия решений, что повышает эффективность их использования при передаче информации в информационных системах.
5. Мажоритарное декодирование кодов с повторением
5.1. Адаптивное мажоритарное декодирование кодов с повторением
Представляет интерес разработка мажоритарных кодирующих устройств, имеющих возможность перестраиваться в зависимости от качества каналов связи и вместе с тем сохраняющих простоту технической реализации. Рассмотрим некоторые из наиболее перспективных направлений построения такого типа устройств. [5, 57]
Определение метода. В соответствии с этим методом запоминают 1-ю посылку, сравнивают его со следующей и дополнительно запоминают позиции несовпадающих эле­ментов. При приеме каждого последующего повторения производят его сравнение и выявляют несовпадения с пре­дыдущим результатом, на место которого записывают сов­падающие элементы принимаемого повторения, те несов­падающие элементы, которые соответствуют хранимым в данный момент несовпадениям, а остальные элементы при­нимаемого повторения перед записью инвертируют. Кроме
Рис. 4.
того, при приеме нечетно­го повторения логически складывают выявленные и хранимые несовпадения, на место которых записы­вают результат логическо­го сложения. При приеме четного повторения выпол­няют операцию логическо­го умножения для выяв­ленных и хранимых несов­падений, на месте которых записывают результат логического перемножения. На рис. 4 изображен граф, соответствующий дан­ному методу, где показано
— состояние одноименных элементов памяти; — «1» и «0» четного и нечетного повторений.
Начальное состояние памяти устанавливается после приема первой пары элементов
Ориентированный граф (стрелка) определяет переход системы из одного состояния в другое в зависимости от вида последующих принимаемых элементов.
Рассмотрим действие метода на примере мажоритарного анализа кода с тремя и пятью посылками. Для наглядности предполагаем, что имеют место искажения и поэтому посыл­ки 1,2, 3-я не совпадают:
Запоминают 1-ю посылку. Сравнивают 2-ю и 1-ю посылки и запоминают 2-ю посылку на месте 1-й.
Позиции несовпадений
запоминают дополнительно. Таким образом, используют 2 n элементов памяти, где n – число элементов в одной посылке (в примере n = 6). Третью посылку сравнивают со второй. Совпадающие элементы 3-й посылки без изменений записывают на место 2-й посылки:
Аналогично записывают несовпадающие элементы 3-й посылки, которым соответствуют ранее запомненные несовпадения, а именно 4-й и 5-й элементы
Остальные несовпадающие элементы 3-й посылки перед записью инвертируют, следовательно, 3-й элемент
Таким образом, вместо второй посылки окажется записан результат мажоритарной обработки «два из трех»
(21)
Несовпадения 2-й 3-й посылок
Логически складывают с хранимыми несовпадениями
(22)
А результат логического сложения (22) записывают на место ранее хранимых несовпадений.
Таким образом, к концу приема 3-й посылки в n элементах памяти хранится результат мажоритарной обработки и в n-элементах памяти – несовпадения (22).
Если к концу приема 3-й посылки оценка состояния канала связи указывает на необходимость продолжения приема посылки и декодирования по критерию «три из пяти», то осуществляют прием 4-й и 5-й посылок
Четвертую посылку сравнивают с результатом мажоритарной обработки (21) и выявляют несовпадения
(23)
На место результата (21) записывают совпадающие элементы 4-й посылки, т.е. 2-й и 6-й:
(24)
и несовпадающие элементы, которым соответствуют хранимые несовпадения (6,3), т.е. 3, 4 и 5-й элементы:
(25)
Остальные элементы 4-й посылки перед записью инвертируют, поэтому 1-й элемент
(26)
Таким образом, из (24), (25) и (26) формируется промежуточный результат

Ранее хранимые несовпадения (22) логически перемножают с выявленными несовпадениями (23):
(27)
и результат (27) записывают на место несовпадений (22).
Таким образом, и на этом этапе оказываются задействованными только 2n элементов памяти.
Продолжают прием 5-й посылки, сравнивают ее с промежуточным результатом (26) и выявляют несовпадения:
(28)
Совпадающие 2, 3, 6-й элементы 5-й посылки записывают на место промежуточного результата (26) без изменения
Аналогично записывают несовпадающие элементы, которым соответствуют хранимые несовпадения (27), т.е. 4 и 5-й элементы:
(29)
Остальные элементы 5-й посылки перед записью получают 1-й элемент
(30)
В результате из (28), (29) и (30) формируется результат мажоритарной обработки «три из пяти»
который записывается на место промежуточного результата (26). Вероятностные характеристики метода « из » имеют следующий вид:
5.2. Расширение области адаптивного мажоритарного декодирования кодов с повторением
При снижении качества канала связи в течение длительного времени оказывается целесообразным введение дополнительной избыточности путем увеличения числа передач кодов с повторением, с последующей мажоритарной обработкой. При этом возможна поэтапная обработка принимаемых посылок без потери промежуточных результатов [5, 60].
Определение метода. В соответствии с этим методом подсчитывают число единиц в одноименных элементах посылок, где — 2,3,..., М, и полученное число для каждого из элементов в виде цифрового кода последовательно записывают. При приеме очередной посылки упомянутые цифровые коды последовательно и синхронно считывают. Корректируют, увеличивая на единицу те числа , которым соответствуют единичные элементы очередной посылки, при условии, что , и вновь после­довательно перезаписывают. При этом результат мажо­ритарной обработки образуют каждый раз в момент при­ема нечетных посылок по правилу: если — фор­мируют информационную единицу, а если — фор­мируют нуль.
Рассмотрим действие способа на примере мажоритарного декодирования кодов с повторением, где = 2,3,..., 7, т.е. М = 7. Как было отмечено, для записи циф­ровых кодов необходимо элементов памяти. Если = 5, то в частном случае можно использовать три пятиразряд­ных регистра сдвига. Для наглядности предположим, что имеют место искажения и поэтому посылки, приведенные в табл. 1, не совпадают:
Таблица 1
Номер посылки
Номер разрядов посылок
1
2
3
4
5
1
1
1
1
1
2
1
1
1
3
1
1
1
1
4
1
5
1
1
1
6
1
1
1
7
1
1
1
8
1
1
1
9
1
1
1
10
1
11
1
1
1
12
1
1
1
13
1
Память представим в виде трех регистров сдвига Р1, Р2 и РЗ, где i-й столбец предназначен для записи цифро­вого кода, соответствующего числу единиц в i-х элемен­тах принятых комбинаций.
Так, для пяти комбинаций из табл. 1 цифровые коды в памяти будут следующие:
т.е. для первого элемента принято 3 единицы, для второго — 4, для третьего — 2 и т.д. Рассмотрим действие способа. Для приведенных в табл. 1 данных.
Принимают первую посылку, подсчитывают число единиц и цифровые коды записывают в регистры сдвига со стороны 5-х разрядов, продвигая их с каждым новым принимаемым элементом влево. Таким образом к концу приема 1-й посылки содержимое регистров будет следующее:
Регистр
1
2
3
4
5
Регистр
1
2
3
4
5
P1
1
1
20
P1
1
1
1
1
20
P2
1
1
1
1
21
P2
21
P3
1
22
P3
22
т.е. в регистре Р1 запишется 1-я посылка, Принимают 2-ю посылку и одновременно последовательно и синхронно считывают цифровые коды (см. п. 5.1) начиная с первых разрядов регистров. Цифровые разряды регистров (см. п. 5.1) корректируют и увеличивают на единицу для тех элементов, для которых в данный момент принимают единицу, т.е для 2, 3, 5-го элементов, и новый результат опять перезаписывают, (так как в данный момент все ). По окончании приема 2-й посылки в регистрах будем иметь цифровые коды:
(31)
Так (трехкратное повторение), то и и результат мажоритарной обработки будет:
Этот же результат можно получить повторно, считывая цифровые коды (31) из регистров и применяя к ним известное правило. При необходимости осуществляют прием очередных посылок.
После приема 4-й посылки цифровые коды в регистре будут
- а после приема 5-й посылки:
Так как в этом случае = 3 (пятикратное повто­рение), то
и .
и результат мажоритарной обработки будет
Аналогично осуществляется прием и обработка оче­редных посылок и после окончания приема 10-й посылки в регистрах будет следующие цифровые коды:
Так как = М = 7, то при приеме 11-й посылки остается без изменения (не корректируется) и в регистры перезапишутся цифровые коды
В этом случае = 6, и .
Поэтому результат мажоритарной обработки будет
При приеме 12-й посылки , и следовательно не корректируются. В ре­гистры перезапишутся цифровые коды:
Те же цифровые коды и по той же причине не коррек­тируют при приеме 13-й посылки. Поэтому в регистры перезапишутся цифровые коды
В этом случае = М = 7, и результат мажоритарной обработки будет:
Реализация известных способов для рассмотренных методов потребовала бы 12 элементов памяти, т.е. сложность этого устройства оказалась бы в четыре раза большей. Чрезмерная сложность и ограничивала до настоящего времени применение указанных устройств в адаптивных системах связи.
5.3. Мажоритарное декодирование избыточных (n, к) -кодов с повторением
Данный метод относится к комбинированным методам защиты информации от ошибок, в которых сочетаются исправление части ошибок посредством мажоритарной об­работки (2m — 1) повторений с последующей проверкой полученного результата на наличие или отсутствие ошибок по контрольным проверкам избыточного (n, k) - кода.
Вероятностные характеристики метода. Если используется трехкратное повторение комби­наций избыточного (n, k)-кода, для которого — кратность гарантийно обнаруживаемых ошибок, то после мажоритар­ной обработки будем иметь
.
Вероятность необнаружения ошибок в этом случае
(32)
или
(33)
где (32) — приближенное выражение.
Потери информации при этом оцениваются по формуле
. (34)
В тех случаях, когда мажоритарной обработке подвер­гается (2m — 1) повторений, может быть получено из следующего приближенного выражения:
. (35)
Рис. 5
Характеристики метода для канала с группирующи­мися ошибками. Из рис. 5 следует, что к необнаружива­емым ошибкам относятся ошибки, содержащие t(t = 0,1 ...,) искажений типа единицы, j(j= 0,1,2,..., -t) искаже­ний типа двойки при t + j< и i искажений типа тройки (i = +1-j, +2-j,..., n-t-j). Отметим, что ; в этом случае число необнаруживаемых ошибок определенной кратности
а общее число ошибок данной кратности —
Предполагая все ошибки равновероятными и зная суммарную вероятность этих ошибок P[(t + 2j + 3i), Зn], можно определить вероятность необнаруженных ошибок рассматриваемой кратности
Суммируя по всем значениям t, j и i, получим выражение для определения полной вероятности необнаружения ошибок:
(36)
где
- коэффициент, учитывающий обнаружение ошибок более высокой кратности, чем .
В определенных случаях можно уменьшить вероятность необнаруженных ошибок соответствующим выбором верх­него предела для переменных t и j, если независимо от результата контрольных проверок избыточного кода бра­ковать информацию в случаях, когда число несовпадений (искажения типа единицы и двойки) в одноименных эле­ментах превысит некоторый порог . Не все составляющие выражения (36) имеют одина­ковый вес. Некоторые из них убывают очень быстро. Это позволяет использовать приближенную формулу: