Широкому
применению кодов, исправляющих любые
сочетания
ошибок кратности t
и
менее, способствовала возможность
мажоритарного декодирования, основанного
на принципе голосования,
т. е. принятия решения «по большинству
голосов» [3,
4]. Использование мажоритарного
декодирования для циклических
кодов, особенно кодов БЧХ, позволяет
значительно упростить
реализацию декодера.
В
основе мажоритарного декодирования
двоичных циклических
кодов лежит то, что для каждого кодового
символа ci
можно
составить S
контрольных
проверок на четность вида
Если
при этом элемент сi
не
входит в правую часть ни одного из
соотношений (7.1),
а любой элемент cij≠сi
входит
только в
одно соотношение, то такие проверки
называют разделенными
или ортогональными. К разделенным
проверкам (7.1)
добавляют
тривиальную проверку сj=ci,
что
позволяет для определения
элемента сi
использовать S
+ 1 проверочных соотношений.
Отсюда следует, что для циклического
кода, исправляющего
ошибки кратности t
и
менее, количество S
контрольных
соотношений (7.1)
с разделенными проверками не должно
быть
меньше 2t.
Тогда,
с учетом тривиальной проверки, будем
иметь S+1≥dmin=2t+1.Из
этого, а также из свойств ортогональных
проверок
следует, что ошибки в t
кодовых
символах могут привести
к неправильному определению значения
ci
не
более чем в t
проверках.
Именно последнее обстоятельство и
позволяет для определения значения
символа сi
применить
мажоритарный
принцип.
Наряду
с разделенными проверками существует
мажоритарное
декодирование с квазиразделенными
проверками и с λ-связанными проверками
[3].
Система
квазиразделенных проверок отличается
от системы разделенных
проверок тем, что в каждую проверку
входит одна и та же линейная комбинация
символов, тогда как любой другой
символ ci,
не
входящий в эту комбинацию, входит только
в одну из проверок.
Система
λ-связанных
проверочных соотношений вида (7.1),
определяющих
символ сi,
характеризуются
тем, что любой другой
символ сj≠ci
, входит
не более чем в λ
проверок,
но существует
хотя бы один символ ci,
который
входит точно в λ
проверок.
На
практике более широкое применение
находит мажоритарное декодирование
с разделенными проверками.
Не
проводя подробный анализ эффективности
того или иного
метода мажоритарного декодирования
циклических кодов, укажем лишь некоторые
его достоинства.
Первое
из них заключается в сравнительно
простой технической
реализации мажоритарного декодирования.
Схема декодера
двоичного циклического кода содержит
мажоритарный элемент,
регистр сдвига и сумматоры по модулю
два.
Второе
достоинство мажоритарного декодирования
заключается
в том, что система проверочных соотношений
для символа сi;
при сдвиге содержимого регистра переходит
в систему проверок
для очередного символа комбинации сi+1
. Эта особенность позволяет
осуществить процедуру последовательного
(один за другим)
мажоритарного декодирования всех
символов комбинации
циклического кода.
Наконец,
существенным достоинством мажоритарного
декодирования
является также и то, что кроме всех
ошибок кратности
t≤S/2
могут
исправляться и некоторые ошибки более
высокой
кратности.
Приведем
пример мажоритарного декодирования
циклического
кода (7, 3) с разделенными проверками и с
образующим полиномом
Р
(х) = (1+
x)(1+x+
х3).
Этот
код имеет минимальное
кодовое расстояние dmin
= 4. Очевидно, что такой код может исправлять
однократные ошибки и обнаруживать все
двухкратные
ошибки.
Образующая
матрица G
систематического
циклического кода
(п,
к) =
(7, 3) с указанным выше образующим полиномом
Р
(х) =
1 + x2
+ x3+x’4
имеет вид
Проверочная
матрица Н
образуется
из единичной матрицы размерности
(п —
к) и
транспонированной матрицы остатков
RT,
т. е.
Так
как циклический код является нулевым
пространством по
отношению к проверочной матрице, то
для любой разрешенной
кодовой комбинации (с0
c1
с2
с3
с4
с5
с6)
справедливо
равенство
Таким
образом, умножив вектор-строку (с0
c1
с2
… с6)
на
транспонированную
проверочную матрицу (7.3), получим
следующие
уравнения:
c3+c4+c6=0. (7.4)
Взяв
первое из уравнений системы (7.4), а
также сложив по
модулю два первое и третье, первое,
второе и четвертое уравнения
получим следующую систему разделенных
проверок для
мажоритарного определения элемента
с0:
Как
видно из системы (7.5),
любой элемент сi≠c0
входит только
в одну из трех проверок, что позволяет
правильно определить
значение с0
по
большинству при любой однократной
ошибке.
Напомним
свойство циклических кодов, заключающееся
в том,
что если вектор (со
c1
c2
сз
c4
c5
c6)
соответствует
разрешенной
комбинации неукороченного циклического
(п,
k)
-кода,
то
ее циклический сдвиг влево, т. е. (с1
с2
с3
с4,
с5
с6
с0),
также
является
разрешенной кодовой комбинацией, для
которой система
разделенных проверок (7.5) превратится
в систему для определения
уже элемента с1,
т.
е.
Таким
образом, мажоритарный элемент, определяющий
любой
элемент кода сi
и позволяющий исправлять однократные
ошибки,
является одним и тем же.
Рис.
7.1. Функциональная схема мажоритарного
декодирования циклического
кода с образующим многочленом Р(х)
= 1
+ х2
+ х3
+ х4
Добавив
систему разделенных проверок (7.5)
тривиальной проверкой
c0=c0,
получим
систему, позволяющую не только исправлять
любую однократную ошибку «по большинству»,
но и
обнаруживать любую двухкратную ошибку.
Например, если ошибки
возникли в элементах c4
и
с5,
то при
мажоритарном декодировании
значение элемента с0
будет определено в соответствии
с уравнениями (7.5) правильно, а при
определении значения
элемента с1
по
уравнениям (7.6) и тривиальной проверке
c1=c1
возникнет
неопределенность, так как два значения
c1
будут
правильными, а два—нет. При такой
ситуации мажоритарный
декодер будет формировать сигнал
обнаружения ошибок
кратностью больше единицы.
Функциональная
схема декодера, соответствующего
рассмотренному
примеру, показана на рис. 7.1. Из описанного
выше алгоритма следует, что при
поступлении на вход декодера комбинации
в течение п
тактов
ключ находится в положении 1, а в течение
следующих п
тактов,
пока осуществляется считывание
комбинации,
ключ находится в положении 2.
ЗАКЛЮЧЕНИЕ
В
настоящем учебном пособии рассмотрены
основы циклических
кодов, а также наиболее широко применяемые
коды для борьбы с ошибками.
Конечно,
ввиду ограниченного объема пособия
в нем не нашли отражения все варианты
построения циклических
кодов, не отражены такие вопросы, как
программная реализация
циклических кодов, оценка эффективности
применения
корректирующих кодов в системах передачи
данных с учетом
распределения ошибок в реальных
дискретных каналах, каскадные
коды, в состав которых входят циклические
коды. Вместе
с тем, изучив основы циклических кодов,
будущие инженеры автоматической
электросвязи смогут самостоятельно
разобраться
с указанными выше вопросами.
КОНТРОЛЬНЫЕ
ВОПРОСЫ
-
Дайте определение
группы, кольца, поля. -
Перечислите
и кратко охарактеризуйте основные
свойства полей Га-луа.
-
Охарактеризуйте
основные действия над многочленами в
поле двоичных
чисел и общие принципы их реализации. -
Назовите основные
свойства циклических кодов. -
Каким требованиям
должен удовлетворять образующий
многочлен? -
Сформулируйте
понятия «систематический» и
«несистематический» циклический
код. -
Запишите
в полиноминальном представлении
выражения в общем виде
для комбинации систематического и
несистематического циклических кодов. -
Дайте
определение образующей и проверочной
матриц. В чем отличие
образующих матриц систематического
и несистематического циклического
кода? -
Охарактеризуйте
кратко процедуру исправления однократной
ошибкициклическим
кодом. Сравните с декодированием
укороченным циклическимкодом.
-
Назовите
основные особенности циклических
кодов Файра. Каковосоответствие
между длиной кодовой комбинации и
выбранным образующиммногочленом?
-
Каково
соответствие между корректирующими
свойствами кодов БЧХи
степенью образующего многочлена? -
Назовите и кратко
охарактеризуйте основные этапы
алгебраическогодекодирования
циклических кодов БЧХ с исправлением
ошибок.
-
Дайте
содержательное определение
циклических кодов Рида—Соломона. -
Сравните
процедуры декодирования кодами БЧХ
и Рида—Соломона,их
различие и сходство при исправлении
ошибок. -
Раскройте
возможности использования кодов
Рида—Соломона для исправления
стираний. -
Охарактеризуйте
основные принципы мажоритарного
декодированияциклических кодов.
Л И Т Е Р А Т У Р А
-
Питерсон
У., Уэлдон
Э.
Коды, исправляющие ошибки/Пер.
сангл.
—М.:
Мир, 1976.— 594 с. -
К
л а р к Д ж., К е й н Д ж. Кодирование
с исправлением ошибок всистемах
цифровой связи/ Пер. с англ. — М.: Радио
и связь, 1987.— 391 с. -
К
о л е с н и к В. Д., Мирончиков
Е. Т. Декодирование циклических
кодов.
—
М.:
Связь,
1968.— 251 с. -
К
а
сам
и
Т.. То кур
а Н.,
Ив а дари
Е., Инагаки
Я. Теориякодирования/
Пер. с япон.
—
М.:
Мир,
1978.— 576 с. -
Р
и д И. С, Соломон
Г. Полиноминальные коды над
некоторымиконечными
полями//Кибернетический сборник.
— М.— 1963. — Вып . 7.—С. 74—79.
-
Берлекэмп
Э.
Теория и практика кодов, исправляющих
ошибки/Пер.
с англ. — М.: Мир, 1971. —478 с. -
Питерсон
У.
Коды, исправляющие ошибки/Пер. с
англ. — М.:Мир,
1964.— 338 с. -
Курош А. Г. Курс
высшей алгебры. — М.: Наука, 1975. — 431 с. -
Гантмахер
Ф.
Р. Теория матриц. — М.: Наука, 1967.—
575 с.
СОДЕРЖАНИЕ
Предисловие 1
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
|
|
Макеты страниц
Мажоритарное декодирование — это метод декодирования, который сравнительно прост в реализации. Если желательно иметь чрезвычайно быстрые декодеры, то нужно обратиться к мажоритарным декодерам. К сожалению, они могут декодировать чрезвычайно малый класс кодов, и эти коды, как правило, слабее других. Следовательно, для практики мажоритарное декодирование имеет второстепенное значение. Несмотря на это, некоторые практические требования могут быть удовлетворены только в его рамках. Кроме того, эти коды интересны с теоретической точки зрения и открывают новые возможности теории кодов, контролирующих ошибки.
Большинство известных кодов, которые могут быть декодированы мажоритарным методом, — это циклические коды или расширенные циклические коды. Для этих кодов мажоритарные декодеры всегда могут быть реализованы как декодеры Меггитта и отличаются особенно простой древовидной логикой для проверки синдрома. Поэтому с прагматической точки зрения мажоритарно декодируемые коды можно определить как те циклические коды, для которых декодер Меггитта может рассматриваться как стандартный. Однако путь нахождения этих кодов весьма сложен и запутан.
13.1. ДЕКОДИРОВАНИЕ МАЖОРИТАРНЫМ МЕТОДОМ
В кодах Рида-Маллера, изучавшихся в § 3.6, декодирование каждого информационного символа производилось путем нахождения большинства голосов в множестве проверочных равенств-. Существуют и другие коды, которые могут быть декодированы мажоритарно. В ретроспективе история таких кодов обычн прослеживается до кодов Рида-Маллера.
Напомним, что любой линейный 
-код над 
имеет проверочную матрицу 
а кодовые слова удовлетворяют
равенсхву 
Если ограничиться рассмотрением 
строки матрицы 
то получаегся проверочное равенство
Взяв любую линейную комбинацию строк 
можно образовать повое проверочное равенство. Всего таким путем можно образовать 
проверочных равенств. Искусство мажоритарного декодирования и состоит в выборе хорошего подмножества этих проверок (при условии, что оно существует).
В этом и следующем параграфе мы займемся построением мажоритарных декодеров. В дальнейших параграфах мы изучим построение кодов, допускающих мажоритарное декодирование.
Определение 13.1.1. Множество проверочных равенств называется согласующимся в 
координате, если компонента 
входит в каждое проверочное равенство этого множества и каждая компонента 
входит не более чем в одно проверочное равенство этого множества.
Как будет показано в приведенной ниже теореме, мажоритарный декодер оценивает по большинству голосов в проверочных равенствах. Априори не известно, произошла или нет ошибка в 
принятом бите, и равная нулю величина ошибки — это один из кандидатов при таком голосовании. Если число 
проверочных равенств четно, то при одинаковом числе голосов предпочтение отдается решению об отсутствии ошибок. Если 
нечетко и число ошибок меньше 
то правильное решение всегда принимается большинством голосов.
Теорема 13.1.2. Если множество 
проверочных равенств согласуется в 
координате и если о принятом слове произошло не более 
ошибок, то компонента оценивается правильно.
Доказательство состоит в описании процедуры исправления. Так как компонента 
входит в каждое проверочное равенство этой совокупности, 
не равно нулю. Положим
Деление на 
гарантирует, что коэффициент при в сумме равен единице. Поскольку существует 
равенств, то 
по меньшей мере для половины значений 
не более 
других 
отличны от нуля, и каждое из этих 
входит в множество проверочных равенств не более одного раза. Следовательно, не менее 
всех 
равны 
если ей, равно нулю, и более 
всех 
равны 
если 
отлично от пуля. Поэтому 
находится мажоритарным решением по 
Следствие 13.1.3. Если для каждой координаты существует 
проверочных равенств, которые согласуются в этой координате, то код может исправлять 
ошибок.
Доказательство следует непосредственно. 
Если 
четно, то 
является целым числом и код можег исправлять 
ошибок. Отсюда следует, что минимальное расстояние кода не меньше 
Прямое доказательство этого факта, включая случай нечетных 
дается в приведенной ниже теореме. Естественно назвать 
расстоянием, реализуемым при мажоритарном декодировании; оно иногда обозначается через 
Истинное минимальное расстояние может быть больше.
Теорема 13.1.4. Если для каждой координаты линейного кода существует 
проверочных равенств, которые согласуются в этой координате, то минимальное расстояние кода не меньше 
Доказательство. Выберем любое ненулевое кодовое слово и любую координату к, в которой находится ненулевой символ. В координате 
согласуются 
проверочных равенств. Каждое из них включает ненулевую компоненту 
и поэтому должно включать хотя бы одну другую ненулевую компоненту, поскольку в правых частях всех проверочных равенств стоят нули. Следовательно, существует не менее 
других ненулевых компонент. 
Следствие 13.1.5. Если для неко порой координаты циклического кода существует 
проверочных равенств, которые согласуются в этой координате, то минимальное расстояние кода не меньше 
Доказательство. Каждый циклический сдвиг кодового слова в циклическом коде образует другое кодовое слово того же кода; поэтому множество 
проверочных равенств для одной координаты можно использовать для того, чтобы выписать множество проверочных равенств для любой другой координаты. 
Теорема 13.1.6. Пусть 
— минимальное расстояние кода, дуального коду над 
Тогда мажоритарный декодер для 
может исправить не более 
ошибок.
Доказательство. Линейные комбинации строк матрицы 
образуют кодовые слова в дуальном коде. Рассмотрим множество 
проверочных равенств, согласующихся в первой координате. Каждое равенство содержит не менее 
пенулевых компонент среди оставшихся 
координат и каждая из оставшихся 
координат не равна нулю по крайней мере в одном из 
равенств.
Следовательно, 
и мажоритарный декодер может исправлять 
ошибок.
Итак, при мажоритарном декодировании нельзя декодировать на радиусе упаковки кода, если не выполняется неравенство
Это условие необходимо, но не достаточно. Для большинства представляющих практический интерес кодов это условие не выполняется.
Мажоритарный декодер довольно прост, но, вообще говоря, применим лишь к кодам с плохими характеристиками. Поэтому мы введем нечто более сложное, а именно 
-шаговый мажоритарный декодер.
Двухшаговый мажоритарный декодер использует мажоритарное решение для локализации ошибки в множестве компонент, а не в конкретной компоненте. Затем для нахождения ошибки уже в этом множестве вновь используется мажоритарное решение. 
-шаговый мажоритарный декодер использует мажоритарную логику на 
уровнях. На каждом уровне декодер исходит из того, что ошибка уже локализована в некотором множестве компонент, и, используя мажоритарное решение, локализует ошибку в подмножестве этих компонент.
Определение 13.1.7. Множество проверочных соотношений называется согласующимся в множестве координат 
если существует множество коэффициентов 
такое, что сумма 
входит в каждое проверочное равенство данного множества и каждая компонента 
при 
входит не более чем в одно проверочное равенство множества.
Естественно, 
-шаговый мажоритарный декодер может исправлять больше ошибок, чем одношаговый мажоритарный декодер, но, вообще говоря, все еще не позволяет достичь радиуса упаковки кода, как показывает следующая теорема.
Теорема 13.1.8. Пусть 
минимальное расстояние кода, дуального коду над 
Тогда 
-шаговый мажоритарный декодер для 
может исправлять не более 
ошибок.
Доказательство. Чтобы исправлять 
ошибок, прежде всего необходимо составить 
проверочных равенств, согласующихся в некотором множестве В, содержащем 
координат. Каждое такое равенство соответствует линейной комбинации строк матрицы 
и эти линейные комбинации представляют собой кодовые слова дуального кода 
Пусть число ненулевых компонент в 
проверочном равенстве, не считая компонент,
координаты которых принадлежат В, равно 
Эти равенства соответствуют кодовым словам дуального кода, и поэтому
Суммируя эти 
соотношений, получаем
Так как каждая компонента, координата которой не принадлежит множеству В, может быть ненулевой не более чем в одном проверочном равенстве, то
Исключая 
получаем
Теперь необходимо вывести второе условие. Разность двух кодовых слов дуального кода также представляет собой кодовое слово, у которого в 
позициях стоят нули. Отсюда следует, что при 
Существует 
таких равенств, и каждое а, входит в 
из них. Складывая все такие равенства, имеем 
Наконец, исключим 
используя это равенство и полученное ранее. Это дает
Так как мажоритарный декодер может исправлять 
ошибок, отсюда следует утверждение теоремы.
Из этой теоремы, в частности, следует, что 
-код Голея не может быть декодирован мажоритарным методом.
Оглавление
- ОТ РЕДАКТОРА ПЕРЕВОДА
- ПРЕДИСЛОВИЕ
- ГЛАВА 1. ВВЕДЕНИЕ
- 1.1. ДИСКРЕТНЫЙ КАНАЛ, СВЯЗИ
- 1.2. ИСТОРИЯ КОДИРОВАНИЯ, КОНТРОЛИРУЮЩЕГО ОШИБКИ
- 1.3. ПРИЛОЖЕНИЯ
- 1.4. ОСНОВНЫЕ ПОНЯТИЯ
- 1.5. ПРОСТЕЙШИЕ КОДЫ
- ГЛАВА 2. ВВЕДЕНИЕ В АЛГЕБРУ
- 2.1. 2-ПОЛЕ И 6-10-ПОЛЕ
- 2.2. ГРУППЫ
- 2.3. КОЛЬЦА
- 2.4. ПОЛЯ
- 2.5. ВЕКТОРНЫЕ ПРОСТРАНСТВА
- 2.6. ЛИНЕЙНАЯ АЛГЕБРА
- ГЛАВА 3. ЛИНЕЙНЫЕ БЛОКОВЫЕ КОДЫ
- 3.1. СТРУКТУРА ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ
- 3.2. МАТРИЧНОЕ ОПИСАНИЕ ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ
- 3.3. СТАНДАРТНОЕ РАСПОЛОЖЕНИЕ
- 3.4. КОДЫ ХЭММИНГА
- 3.5. СОВЕРШЕННЫЕ И КВАЗИСОВЕРШЕННЫЕ КОДЫ
- 3.6. ПРОСТЫЕ ПРЕОБРАЗОВАНИЯ ЛИНЕЙНОГО КОДА
- 3.7. КОДЫ РИДА—МАЛЛЕРА
- ГЛАВА 4. АРИФМЕТИКА ПОЛЕЙ ГАЛУА
- 4.2. КОНЕЧНЫЕ ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ
- 4.3. КОЛЬЦА МНОГОЧЛЕНОВ
- 4.4. КОНЕЧНЫЕ ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦАХ МНОГОЧЛЕНОВ
- 4.5. ПРИМИТИВНЫЕ ЭЛЕМЕНТЫ
- 4.6. СТРУКТУРА КОНЕЧНОГО ПОЛЯ
- ГЛАВА 5. ЦИКЛИЧЕСКИЕ КОДЫ
- 5.2. ПОЛИНОМИАЛЬНОЕ ОПИСАНИЕ ЦИКЛИЧЕСКИХ КОДОВ
- 5.3. МИНИМАЛЬНЫЕ МНОГОЧЛЕНЫ И СОПРЯЖЕНИЯ
- 5.4. МАТРИЧНОЕ ОПИСАНИЕ ЦИКЛИЧЕСКИХ КОДОВ
- 5.5. КОДЫ ХЭММИНГА КАК ЦИКЛИЧЕСКИЕ КОДЫ
- 5.6. ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ДВЕ ОШИБКИ
- 5.7. ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ПАКЕТЫ ОШИБОК
- 5.8. ДВОИЧНЫЙ КОД ГОЛЕЯ
- 5.9. КВАДРАТИЧНО-ВЫЧЕТНЫЕ КОДЫ
- ГЛАВА 6. СХЕМНАЯ РЕАЛИЗАЦИЯ ЦИКЛИЧЕСКОГО КОДИРОВАНИЯ
- 6.1. ЛОГИЧЕСКИЕ ЦЕПИ ДЛЯ АРИФМЕТИКИ КОНЕЧНОГО ПОЛЯ
- 6.2. ЦИФРОВЫЕ ФИЛЬТРЫ
- 6.3. КОДЕРЫ И ДЕКОДЕРЫ НА РЕГИСТРАХ СДВИГА
- 6.4. ДЕКОДЕР МЕГГИТТА
- 6.5. ВЫЛАВЛИВАНИЕ ОШИБОК
- 6.6. УКОРОЧЕННЫЕ ЦИКЛИЧЕСКИЕ КОДЫ
- 6.7. ДЕКОДЕР МЕГГИТТА ДЛЯ. КОДА ГОЛЕЯ
- ГЛАВА 7. КОДЫ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА
- 7.2. ДЕКОДЕР ПИТЕРСОНА ГОРЕНСТЕЙНА—ЦИРЛЕРА
- 7.3. КОДЫ РИДА СОЛОМОНА
- 7.4. СИНТЕЗ АВТОРЕГРЕССИОННЫХ ФИЛЬТРОВ
- 7.5. БЫСТРОЕ ДЕКОДИРОВАНИЕ КОДОВ БЧХ
- 7.6. ДЕКОДИРОВАНИЕ ДВОИЧНЫХ КОДОВ БЧХ
- 7.7. ДЕКОДИРОВАНИЕ С ПОМОЩЬЮ АЛГОРИТМА ЕВКЛИДА
- 7.8. КАСКАДНЫЕ (ГНЕЗДОВЫЕ) КОДЫ
- 7.9. КОДЫ ЮСТЕСЕНА
- ГЛАВА 8. КОДЫ, ОСНОВАННЫЕ НА СПЕКТРАЛЬНЫХ МЕТОДАХ
- 8.2. ОГРАНИЧЕНИЯ СОПРЯЖЕННОСТИ И ИДЕМПОТЕНТЫ
- 8.3. СПЕКТРАЛЬНОЕ ОПИСАНИЕ ЦИКЛИЧЕСКИХ КОДОВ
- 8.4. РАСШИРЕННЫЕ КОДЫ РИДА-СОЛОМОНА
- 8.5. РАСШИРЕННЫЕ КОДЫ БЧХ
- 8.6. АЛЬТЕРНАНТНЫЕ КОДЫ
- 8.7. ХАРАКТЕРИСТИКИ АЛЬТЕРНАНТНЫХ КОДОВ
- 8.8. КОДЫ ГОППЫ
- 8.9. КОДЫ ПРЕПАРАТЫ
- ГЛАВА 9. АЛГОРИТМЫ, ОСНОВАННЫЕ НА СПЕКТРАЛЬНЫХ МЕТОДАХ
- 9.2. ИСПРАВЛЕНИЕ СТИРАНИЙ И ОШИБОК
- 9.3. ДЕКОДИРОВАНИЕ РАСШИРЕННЫХ КОДОВ РИДА—СОЛОМОНА
- 9.4. ДЕКОДИРОВАНИЕ РАСШИРЕННЫХ КОДОВ БЧХ
- 9.5. ДЕКОДИРОВАНИЕ ВО ВРЕМЕННОЙ ОБЛАСТИ
- 9.6. ДЕКОДИРОВАНИЕ ЗА ГРАНИЦЕЙ БЧХ
- 9.7. ДЕКОДИРОВАНИЕ АЛЬТЕРНАНТНЫХ КОДОВ
- 9.8. ВЫЧИСЛЕНИЕ ПРЕОБРАЗОВАНИЙ В КОНЕЧНЫХ ПОЛЯХ
- ГЛАВА 10. МНОГОМЕРНЫЕ СПЕКТРАЛЬНЫЕ МЕТОДЫ
- 10.1. КОДЫ-ПРОИЗВЕДЕНИЯ
- 10.2. КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ
- 10.3. ДЕКОДИРОВАНИЕ КОДА-ПРОИЗВЕДЕНИЯ
- 10.4. МНОГОМЕРНЫЕ СПЕКТРЫ
- 10.5. БЫСТРЫЕ КОДЫ БЧХ
- 10.6. ДЕКОДИРОВАНИЕ МНОГОМЕРНЫХ КОДОВ
- 10.7. ДЛИННЫЕ КОДЫ НАД МАЛЫМИ ПОЛЯМИ
- ГЛАВА 11. БЫСТРЫЕ АЛГОРИТМЫ
- 11.1. ЛИНЕЙНАЯ СВЕРТКА И ЦИКЛИЧЕСКАЯ СВЕРТКА
- 11.2. БЫСТРЫЕ АЛГОРИТМЫ СВЕРТКИ
- 11.3. БЫСТРЫЕ ПРЕОБРАЗОВАНИЯ ФУРЬЕ
- 11.4. АЛГОРИТМЫ АГАРВАЛА—КУЛИ ВЫЧИСЛЕНИЯ СВЕРТОК
- 11.5. АЛГОРИТМ ВИНОГРАДА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
- 11.6. УСКОРЕННЫЙ АЛГОРИТМ БЕРЛЕКЭМПА—МЕССИ
- 11.7. РЕКУРРЕНТНЫЙ АЛГОРИТМ БЕРЛЕКЭМПА—МЕССИ
- 11.8. УСКОРЕННОЕ ДЕКОДИРОВАНИЕ КОДОВ БЧХ
- 11.9. СВЕРТКА В СУРРОГАТНЫХ ПОЛЯХ
- ГЛАВА 12. СВЕРТОЧНЫЕ КОДЫ
- 12.2. ОПИСАНИЕ СВЕРТОЧНЫХ КОДОВ С ПОМОЩЬЮ МНОГОЧЛЕНОВ
- 12.3. ИСПРАВЛЕНИЕ ОШИБОК И ПОНЯТИЯ РАССТОЯНИЯ
- 12.4. МАТРИЧНОЕ ОПИСАНИЕ СВЕРТОЧНЫХ КОДОВ
- 12.5. НЕКОТОРЫЕ ПРОСТЫЕ СВЕРТОЧНЫЕ КОДЫ
- 12.6. АЛГОРИТМЫ СИНДРОМНОГО ДЕКОДИРОВАНИЯ
- 12.7. ОБЕРТОЧНЫЕ КОДЫ ДЛЯ ИСПРАВЛЕНИЯ ПАКЕТОВ ОШИБОК
- 12.8. АЛГОРИТМ ДЕКОДИРОВАНИЯ ВИТЕРБИ
- 12.9. АЛГОРИТМЫ ПОИСКА ПО РЕШЕТКЕ
- ГЛАВА 13. КОДЫ И АЛГОРИТМЫ ДЛЯ ДЕКОДИРОВАНИЯ МАЖОРИТАРНЫМ МЕТОДОМ
- 13.1. ДЕКОДИРОВАНИЕ МАЖОРИТАРНЫМ МЕТОДОМ
- 13.2. СХЕМЫ МАЖОРИТАРНОГО ДЕКОДИРОВАНИЯ
- 13.3. АФФИННЫЕ ПЕРЕСТАНОВКИ ДЛЯ ЦИКЛИЧЕСКИХ КОДОВ
- 13.4. ЦИКЛИЧЕСКИЕ КОДЫ, ОСНОВАННЫЕ НА ПЕРЕСТАНОВКАХ
- 13.5. СВЕРТОЧНЫЕ КОДЫ С МАЖОРИТАРНЫМ ДЕКОДИРОВАНИЕМ
- 13.6. ОБОБЩЕННЫЕ КОДЫ РИДА—МАЛЛЕРА
- 13.7. ЕВКЛИДОВО-ГЕОМЕТРИЧЕСКИЕ КОДЫ
- 13.8. ПРОЕКТИВНО-ГЕОМЕТРИЧЕСКИЕ КОДЫ
- ГЛАВА 14. КОМПОЗИЦИЯ И ХАРАКТЕРИСТИКИ КОНТРОЛИРУЮЩИХ ОШИБКИ КОДОВ
- 14.2. ВЕРОЯТНОСТИ ОШИБОЧНОГО ДЕКОДИРОВАНИЯ И НЕУДАЧНОГО ДЕКОДИРОВАНИЯ
- 14.3. РАСПРЕДЕЛЕНИЕ ВЕСОВ СВЕРТОЧНЫХ КОДОВ
- 14.4. ГРАНИЦЫ МИНИМАЛЬНОГО РАССТОЯНИЯ ДЛЯ БЛОКОВЫХ КОДОВ
- 14.5. ГРАНИЦЫ МИНИМАЛЬНОГО РАССТОЯНИЯ ДЛЯ СВЕРТОЧНЫХ КОДОВ
- ГЛАВА 15. ЭФФЕКТИВНАЯ ПЕРЕДАЧА СИГНАЛОВ ПО ЗАШУМЛЕННЫМ КАНАЛАМ
- 15.1. ОГРАНИЧЕННЫЙ ПО ПОЛОСЕ ГАУССОВСКИЙ КАНАЛ
- 15.2. ЭНЕРГИЯ НА БИТ И ЧАСТОТА ОШИБОК НА БИТ
- 15.3. МЯГКОЕ ДЕКОДИРОВАНИЕ БЛОКОВЫХ КОДОВ
- 15.4. МЯГКОЕ ДЕКОДИРОВАНИЕ СВЕРТОЧНЫХ КОДОВ
- 15.5. ПОСЛЕДОВАТЕЛЬНОЕ ДЕКОДИРОВАНИЕ
- ЛИТЕРАТУРА
Защита от ошибок в сетях.
Проблема обеспечения безошибочности (достоверности) передачи информации в сетях имеет очень большое значение. Практическое воплощение методов состоит из двух частей — программной и аппаратной.
Выделяют две основные причины возникновения ошибок при передаче информации в сетях:
• сбои в какой-то части оборудования сети или возникновение неблагоприятных объективных событий в сети (например, коллизий при использовании метода случайного доступа в сеть). Как правило, система передачи данных готова к такого рода проявлениям и устраняет их с помощью предусмотренных планом средств;
• помехи, вызванные внешними источниками и атмосферными явлениями.
Помехи — это электрические возмущения, возникающие в самой аппаратуре или попадающие в нее извне.
Среди многочисленных методов защиты от ошибок выделяются три группы методов: групповые методы, помехоустойчивое кодирование и методы защиты от ошибок в системах передачи с обратной связью.
Из групповых методов получили широкое применение мажоритарный метод.
Рекомендация для Вас — 13. Математическая модель изменения уровня жидкости.
Суть мажоритарного метода, давно и широко используемого в телеграфии, состоит в следующем. Каждое сообщение ограниченной длины передается несколько раз, чаще всего три раза. Принимаемые сообщения запоминаются, а потом производится их поразрядное сравнение. Суждение о правильности передачи выносится по совпадению большинства из принятой информации методом «два из трех».
Другой групповой метод, также не требующий перекодирования информации, предполагает передачу данных блоками с количественной характеристикой блока. Такими характеристиками могут быть: число единиц или нулей в блоке, контрольная сумма передаваемых символов в блоке, остаток от деления контрольной суммы на постоянную величину и др.
Помехоустойчивое (избыточное) кодирование, предполагающее разработку и использование корректирующих (помехоустойчивых) кодов, применяется не только в ТКС, но и в ЭВМ для защиты от ошибок при передаче информации между устройствами машины. Оно позволяет получить более высокие качественные показатели работы систем связи. Его основное назначение заключается в обеспечении малой вероятности искажений передаваемой информации, несмотря на присутствие помех или сбоев в работе сети.
Системы передачи с обратной связью делятся на системы с решающей обратной связью и системы с информационной обратной связью.
Особенностью систем с решающей обратной связью (систем с перезапросом) является то, что решение о необходимости повторной передачи информации (сообщения, пакета) принимает приемник. Здесь обязательно применяется помехоустойчивое кодирование, с помощью которого на приемной станции осуществляется проверка принимаемой информации.
В системах с информационной обратной связью передача информации осуществляется без помехоустойчивого кодирования. Приемник, приняв информацию по прямому каналу и зафиксировав ее в своей памяти, передает ее в полном объеме по каналу обратной связи передатчику, где переданная и возвращенная информация сравниваются. При совпадении передатчик посылает приемнику сигнал подтверждения, в противном случае происходит повторная передача всей информации. Таким образом, здесь решение о необходимости повторной передачи принимает передатчик.