Мажоритарный метод защиты от ошибок

Широкому
применению кодов, исправляющих любые
соче­тания
ошибок кратности t
и
менее, способствовала возможность
мажоритарного декодирования, основанного
на принципе голо­сования,
т. е. принятия решения «по большинству
голосов» [3,
4]. Использование мажоритарного
декодирования для цикли­ческих
кодов, особенно кодов БЧХ, позволяет
значительно уп­ростить
реализацию декодера.

В
основе мажоритарного декодирования
двоичных цикли­ческих
кодов лежит то, что для каждого кодового
символа c_i
можно
составить S
контрольных
проверок на четность вида

Если
при этом элемент с_i
не
входит в правую часть ни одного из
соотношений (7.1),
а любой элемент c_ij≠с_i
входит
только в
одно соотношение, то такие проверки
называют разделенны­ми
или ортогональными. К разделенным
проверкам (7.1)
до­бавляют
тривиальную проверку с_j=c_i,
что
позволяет для оп­ределения
элемента с_i
использовать S
+ 1 проверочных соот­ношений.
Отсюда следует, что для циклического
кода, исправ­ляющего
ошибки кратности t
и
менее, количество S
контроль­ных
соотношений (7.1)
с разделенными проверками не должно
быть
меньше 2t.

Тогда,
с учетом тривиальной проверки, будем
иметь S+1≥d_min=2t+1.Из
этого, а также из свойств ортогональных
проверок
следует, что ошибки в t
кодовых
символах могут при­вести
к неправильному определению значения
c_i
не
более чем в t
проверках.
Именно последнее обстоятельство и
позволяет для определения значения
символа с_i
применить
мажоритар­ный
принцип.

Наряду
с разделенными проверками существует
мажори­тарное
декодирование с квазиразделенными
проверками и с λ-связанными проверками
[3].

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

Система
λ-связанных
проверочных соотношений вида (7.1),
определяющих
символ с_i,
характеризуются
тем, что любой другой
символ с_j≠c_i
, входит
не более чем в λ
проверок,
но существует
хотя бы один символ c_i,
который
входит точно в λ
проверок.

На
практике более широкое применение
находит мажори­тарное декодирование
с разделенными проверками.

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

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

Второе
достоинство мажоритарного декодирования
заключа­ется
в том, что система проверочных соотношений
для символа с_i;
при сдвиге содержимого регистра переходит
в систему прове­рок
для очередного символа комбинации с_i+1
. Эта особенность позволяет
осуществить процедуру последовательного
(один за другим)
мажоритарного декодирования всех
символов комби­нации
циклического кода.

Наконец,
существенным достоинством мажоритарного
деко­дирования
является также и то, что кроме всех
ошибок кратности
t≤S/2
могут
исправляться и некоторые ошибки более
вы­сокой
кратности.

Приведем
пример мажоритарного декодирования
цикличе­ского
кода (7, 3) с разделенными проверками и с
образующим полиномом
Р
(х) = (1+
x)(1+x+
х³).
Этот
код имеет мини­мальное
кодовое расстояние d_min
= 4. Очевидно, что такой код может исправлять
однократные ошибки и обнаруживать все
двухкратные
ошибки.

Образующая
матрица G
систематического
циклического ко­да
(п,
к) =
(7, 3) с указанным выше образующим полиномом
Р
(х) =
1 + x²
+ x³+x’⁴
имеет вид

Проверочная
матрица Н
образуется
из единичной матрицы размерности
(п —
к) и
транспонированной матрицы остатков
R^T,
т. е.

Так
как циклический код является нулевым
пространством по
отношению к проверочной матрице, то
для любой разрешен­ной
кодовой комбинации (с₀
c₁
с₂
с₃
с₄
с₅
с₆)
справедливо
ра­венство

Таким
образом, умножив вектор-строку (с₀
c₁
с₂
… с₆)
на
транспонированную
проверочную матрицу (7.3), получим
сле­дующие
уравнения:

c₃+c₄+c₆=0. (7.4)

Взяв
первое из уравнений системы (7.4), а
также сложив по
модулю два первое и третье, первое,
второе и четвертое уравнения
получим следующую систему разделенных
проверок для
мажоритарного определения элемента
с₀:

Как
видно из системы (7.5),
любой элемент с_i≠c₀
входит только
в одну из трех проверок, что позволяет
правильно оп­ределить
значение с₀
по
большинству при любой однократной
ошибке.

Напомним
свойство циклических кодов, заключающееся
в том,
что если вектор (с_о
c₁
c₂
с_з
c₄
c₅
c₆)
соответствует
разре­шенной
комбинации неукороченного циклического
(п,
k)
-кода,
то
ее циклический сдвиг влево, т. е. (с₁
с₂
с₃
с₄,
с₅
с₆
с₀),
также
является
разрешенной кодовой комбинацией, для
которой си­стема
разделенных проверок (7.5) превратится
в систему для определения
уже элемента с₁,
т.
е.

Таким
образом, мажоритарный элемент, определяющий
лю­бой
элемент кода с_i
и позволяющий исправлять однократные
ошибки,
является одним и тем же.

Рис.
7.1. Функциональная схема мажоритарного
декодирования цикличе­ского
кода с образующим многочленом Р(х)
= 1
+ х²
+ х³
+ х⁴

Добавив
систему разделенных проверок (7.5)
тривиальной проверкой
c₀=c₀,
получим
систему, позволяющую не только исправлять
любую однократную ошибку «по большинству»,
но и
обнаруживать любую двухкратную ошибку.
Например, если ошибки
возникли в элементах c₄
и
с₅,
то при
мажоритарном де­кодировании
значение элемента с₀
будет определено в соответ­ствии
с уравнениями (7.5) правильно, а при
определении зна­чения
элемента с₁
по
уравнениям (7.6) и тривиальной проверке
c₁=c₁
возникнет
неопределенность, так как два значения
c₁
будут
правильными, а два—нет. При такой
ситуации мажоритарный
декодер будет формировать сигнал
обнаружения оши­бок
кратностью больше единицы.

Функциональная
схема декодера, соответствующего
рассмот­ренному
примеру, показана на рис. 7.1. Из описанного
выше ал­горитма следует, что при
поступлении на вход декодера комби­нации
в течение п
тактов
ключ находится в положении 1, а в течение
следующих п
тактов,
пока осуществляется считывание
комбинации,
ключ находится в положении 2.

ЗАКЛЮЧЕНИЕ

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

КОНТРОЛЬНЫЕ
ВОПРОСЫ

1. Дайте определение
   группы, кольца, поля.

2. Перечислите
   и кратко охарактеризуйте основные
   свойства полей Га-

   луа.

3. Охарактеризуйте
   основные действия над многочленами в
   поле двоичных
   чисел и общие принципы их реализации.

4. Назовите основные
   свойства циклических кодов.

5. Каким требованиям
   должен удовлетворять образующий
   многочлен?

6. Сформулируйте
   понятия «систематический» и
   «несистематический» цик­лический
   код.

7. Запишите
   в полиноминальном представлении
   выражения в общем ви­де
   для комбинации систематического и
   несистематического циклических ко­дов.

8. Дайте
   определение образующей и проверочной
   матриц. В чем отли­чие
   образующих матриц систематического
   и несистематического цикличе­ского
   кода?

9. Охарактеризуйте
   кратко процедуру исправления однократной
   ошибки

   циклическим
   кодом. Сравните с декодированием
   укороченным циклическим

   кодом.

1. Назовите
   основные особенности циклических
   кодов Файра. Каково

   соответствие
   между длиной кодовой комбинации и
   выбранным образующим

   многочленом?

2. Каково
   соответствие между корректирующими
   свойствами кодов БЧХ

   и
   степенью образующего многочлена?

3. Назовите и кратко
   охарактеризуйте основные этапы
   алгебраического

   декодирования
   циклических кодов БЧХ с исправлением
   ошибок.

1. Дайте
   содержательное определение
   циклических кодов Рида—Соло­мона.

2. Сравните
   процедуры декодирования кодами БЧХ
   и Рида—Соломона,

   их
   различие и сходство при исправлении
   ошибок.

3. Раскройте
   возможности использования кодов
   Рида—Соломона для исправления
   стираний.

4. Охарактеризуйте
   основные принципы мажоритарного
   декодирования

   циклических кодов.

Л И Т Е Р А Т У Р А

1. Питерсон
   У., Уэлдон
   Э.
   Коды, исправляющие ошибки/Пер.
   с

   англ.
   —М.:
   Мир, 1976.— 594 с.

2. К
   л а р к Д ж., К е й н Д ж. Кодирование
   с исправлением ошибок в

   системах
   цифровой связи/ Пер. с англ. — М.: Радио
   и связь, 1987.— 391 с.

3. К
   о л е с н и к В. Д., Мирончиков
   Е. Т. Декодирование цикличе­ских
   кодов.
   —
   М.:
   Связь,
   1968.— 251 с.

4. К
   а
   сам
   и
   Т.. То кур
   а Н.,
   Ив а дари
   Е., Инагаки
   Я. Теория

   кодирования/
   Пер. с япон.
   —
   М.:
   Мир,
   1978.— 576 с.

5. Р
   и д И. С, Соломон
   Г. Полиноминальные коды над
   некоторыми

   конечными
   полями//Кибернетический сборник.
   — М.— 1963. — Вып . 7.—

   С. 74—79.

6. Берлекэмп
   Э.
   Теория и практика кодов, исправляющих
   ошибки/

   Пер.
   с англ. — М.: Мир, 1971. —478 с.

7. Питерсон
   У.
   Коды, исправляющие ошибки/Пер. с
   англ. — М.:

   Мир,
   1964.— 338 с.

8. Курош А. Г. Курс
   высшей алгебры. — М.: Наука, 1975. — 431 с.

9. Гантмахер
   Ф.
   Р. Теория матриц. — М.: Наука, 1967.—
   575 с.

СОДЕРЖАНИЕ

Предисловие 1

Из групповых
методов
получили широкое применение:

• мажоритарный
  метод;

• метод передачи
  информационными блоками с количественной
  характеристикой блока.

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

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

Вопросы по теме

Для самооценки по
теме 6 ответить на вопросы:

1. Основные причины
   возникновения ошибок.

2. Методы защиты от
   ошибок и средства их реализации.

3. Помехоустойчивое
   кодирование в системах телекоммуникации.

4. Основные показатели
   корректирующих кодов.

5. Системы передачи
   с обратной связью: разновидности,
   особенности применения.

6. Системы с решающей
   обратной связью.

7. Системы с
   информационной обратной связью.

8. Групповые методы
   защиты от ошибок.

5

Соседние файлы в папке Лекции Вссит

• #
• #
• #
• #
• #
• #
• #
• #
• #

Данный метод относится к комбинированным методам защиты информации от ошибок, в которых сочетаются исправление части ошибок посредством мажоритарной обработки (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) имеют одинаковый вес. Некоторые из них убывают очень быстро. Это позволяет использовать приближенную формулу:

(37)

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

Поэтапная обработка кодов с повторением

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

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

а оперативность управления как

, (38)

где V — скорость модуляции. Следовательно, имеет место высокая оперативность и низкая достоверность, поскольку для повышения достоверности не используется вся вводимая избыточность.

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

причем << .

Однако оперативность управления резко снижается и характеризуется выражением

т.е.

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

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

Рис. 6.

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

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

Достоверность информации может быть вычислена по формуле

Потери информации характеризуются выражением

При может быть использовано приближенное выражение

Минимальное время доведения информации до получателя характеризуется выражением (38).

На рис. 6 приведена зависимость для при условии, что .

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

Достоверность, надежность доведения информации и оперативность управления могут быть вычислены по следующим формулам:

Сравнительный анализ показывает, что

< и < .

На рис. 6.6 приведена зависимость из которой видно, что при

,

а при , .

Критическое значение длины кодовой комбинации может быть вычислено по формуле

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

Достоверность, надежность доведения информации и оперативность управления вычисляются по следующим формулам:

;

Сравнительный анализ показывает, что

, а

На рис. 6 приведены зависимости, из которых видно, что при

; при ; при ; а при .

Критические значения длины кодовой комбинации и могут быть определены по следующим формулам:

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

Достоверность, надежность доведения информации и оперативность управления вычисляются по следующим формулам:

Сравнительный анализ показывает, что

;

Однако достоверность предварительного решения четвертого алгоритма выше, чем третьего. Проще оказывается и аппаратурная реализация четвертого алгоритма.

На рис. 6 приведена зависимость , из (которой можно сделать вывод, что для всех значений ). При

;

;

;

;

;

.

Критические значения длины кодовой комбинации можно вычислить по формулам:

;

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

На первом этапе выбираются характеристики обнаруживающего ошибки кода ( и ) для кодирования одного повторения сообщения.

Вычисляются основные параметры с использованием приведенных формул и строятся графические зависимости . Для заданных характеристик канала связи и различных значений .

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

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

При может быть выбран четвертый алгоритм при условии что , как обладающий большей достоверностью, или второй алгоритм при и .

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

Сравнительная оценка различных алгоритмов поэтапного декодирования избыточных (, ) — кодов с повторением позволила определить области их предпочтительного использования и разработать методику выбора требуемого алгоритма.