- •Тема 7. Коды Рида- Соломона (рс)
- •7.1. Определение и основные свойства
- •Пример 7.1
- •Пример 7.2
- •7.1.1. Расширенные рс-коды
- •Пример 7.3
- •7.1.2. Укороченные рс-коды
- •7.1.3. Отображение рс-кодов над gf(2m) на двоичные коды
- •7.1.4. Способы кодирования и декодирования рс-кодов
- •1. Многочлен локаторов ошибок:
- •2.Синдромный многочлен
- •3. Многочлен значений ошибок
- •7.2. Быстрое декодирование кодов бчх
- •7.2.1. Ключевое уравнение
- •7.2.2. Решение ключевого уравнения
- •7.2.3. Примеры решения ключевого уравнения
- •7.3.Кодирование на основе решения ключевого уравнения
- •7.4.Задачи
- •Тема 8. Непрерывные коды
- •8.1. Сверточное кодирование
- •8.2. Представление сверточного кодера
- •8.2.1. Представление связи
- •8.2.1.1. Реакция кодера на импульсное возмущение
- •8.2.1.2. Полиномиальное представление
- •8.2.2. Представление состояния и диаграмма состояний
- •8.2.3. Древовидные диаграммы
- •8.2.4. Решетчатая диаграмма
- •8.3. Формулировка задачи сверточного декодирования
- •8.3.1. Алгоритм сверточного декодирования Витерби
- •8.3.2. Пример сверточного декодирования Витерби
- •8.3.2.1. Процедура сложения, сравнения и выбора
- •8.3.2.2. Вид процедуры сложения, сравнения и выбора на решетке
- •8.3.3. Память путей и синхронизация
- •8.4. Свойства сверточных кодов
- •8.4.1. Пространственные характеристики сверточных кодов
- •8.4.1.1. Возможности сверточного кода в коррекции ошибок
- •8.4.2. Систематические и несистематические сверточные коды
- •8.4.3. Распространение катастрофических ошибок в сверточных кодах
- •8.4.4. Границы рабочих характеристик сверточных кодов
- •8.4.5. Эффективность кодирования
- •8.4.6. Наиболее известные сверточные коды
- •8.5. Задачи
- •Тема 9. Некоторые специальные классы кодов. Составные коды
- •9.1. Коды для исправления пачек ошибок
- •9.2. Коды на основе последовательностей максимальной длины
- •9.3. Коды для асимметричных каналов
- •9.3.1. Коды с постоянным весом
- •9.3.2. Коды Бергера
- •9.4 Каскадные коды
- •9.4.1. Принципы построения каскадных кодов
- •9.4.2. Режимы использования каскадных кодов
- •9.4.3. Построение двоичных каскадных кодов на основе кодов Рида–Соломона и Боуза–Чоудхури–Хоквингема
- •Пример 9.2.
- •Пример 9.3.
- •9.5. Задачи
- •Тема 10. Цикловая синхронизация
- •Назначение и классификация способов цикловой синхронизации
- •10.2. Способ установки фазы приемного распределителя путем сдвига.
- •10.3. Способ мгновенной установки фазы
- •10.3.1. Маркерный способ цикловой синхронизации на основе синхронизирующих кодовых последовательностей
- •10.4 . Способ выделения сигнала фазового запуска по зачетному отрезку
- •Тема 11. Системные методы защиты от ошибок без обратной связи
- •11.1. Классификация и основные характеристики систем повышения достоверности
- •11.1.1. Теоретические основы системных методов защиты от ошибок
- •11.1.2. Классификация системных методов защиты от ошибок
- •11.1.3 .Основные параметры и характеристики систем повышения достоверности
- •11.2. Методы повышения достоверности в однонаправленных системах
- •11.2.1.Однонаправленные системы с многократным повторением сообщений
- •11.2.2.Однонаправленные системы с исправляющим ошибки кодом
- •11.2.3.Однонаправленные системы с исправлением стираний
- •11.3. Задачи
- •Тема 12. Системные методы защиты от ошибок с обратной связью
- •12.1. Системы повышения достоверности с решающей обратной связью с непрерывной последовательной передачей сообщений и блокировкой (рос-пПбл).Общие положения
- •12.2. Описание работы системы рос-пПбл
- •12.3. Режим переспроса
- •12.4. Расчет параметров системы рос-пПбл Относительная скорость передачи
- •Расчет вероятности ошибок на выходе системы
- •Расчет времени доведения сообщений
- •Расчет емкости накопителя-повторителя
- •12.5. Рекомендации по выбору оптимального кода Расчет оптимальных характеристик помехоустойчивого кода
- •Охарактеризуем поток ошибок, пропущенных в приемник сообщений средней вероятностью ошибки на бит, равной и показателем группирования ошибок.
- •12.6. Выбор порождающего многочлена
- •12.7. Задачи
- •Тема 1. Основные понятия и определения в области пдс…………………………………..…...2
- •Тема 2. Системные характеристики систем передачи дискретных сообщений………………..11
- •Тема 3. Основные характеристики уровня дискретного канала пдс……………………...……21
- •Тема 4. Устройство синхронизации по элементам (усп)……………………………………….50
- •Тема 5. Линейные (n,k)-коды…….…………………………………………………………………..54
- •Тема 6. Двоичные циклические (n,k) – коды…………………………………………………… 105
- •Тема 7. Коды Рида- Соломона (рс)…………………………………………..…………………..165
- •7.1. Определение и основные свойства………………….…………………….……………...165
- •7.1.3. Отображение рс-кодов над gf(2m) на двоичные коды……………………………….170
- •Тема 8. Непрерывные коды……………………………………………...……………………….185
- •Тема 9. Некоторые специальные классы кодов. Составные коды………………………………210
- •9.4.1. Принципы построения каскадных кодов……………………………………………………………215
- •9.4.2. Режимы использования каскадных кодов…………………………………………………………..218
- •9.4.3. Построение двоичных каскадных кодов на основе кодов Рида–Соломона и Боуза–Чоудхури–Хоквингема………………..………………………………………………..…………………………………219
- •Тема10. Цикловая синхронизация……………………………...…………………………………………222
- •Тема 11. Системные методы защиты от ошибок без обратной связи………………………………..…234
- •Тема 12. Системные методы защиты от ошибок с обратной связью…..…………………….…...244
7.2.2. Решение ключевого уравнения
а). Алгоритм Питерсона.
У. Питерсон [1] представил ключевое уравнение в матричной форме:
Таким образом, задача определения коэффициентов многочлена локаторов ошибок сводится к прямому решению системы v линейных уравнений с v неизвестными.
Известно, что, если существует наибольший общий делитель d(x) двух многочленов а(х) и b(х), то существуют многочлены f(x) и g(x) такие, что справедливо: a(x)f{x)+b(x)g(x)=d(x).
Многочлен d(x) может быть найден по алгоритму Евклида, который состоит в последовательном делении с остатком а(х) на b(х), затем b(х) на первый остаток r1(х), затем r1(х) на второй остаток r2(х) и т.д.
При декодировании кодов БЧХ интересуются не конечным результатом алгоритма Евклида, а промежуточными результатами, которые можно представить в виде: a(x)f(x)+b(x)g(x)=r(x).
У. Сугияма и его соавторы [3] использовали этот результат для решения ключевого уравнения следующим образом: b(x)g(x)= ri(x) (mod a(x)), полагая,
а(х)=х2t, b(x)=S(x), gl(x)=Λi(x), ri(x)=Ωi(x).
При этом используется свойство алгоритма Евклида:
deg[gi(x)]+deg[ri-l(x)]=deg[a(x)].
Если а(х)=х2t, то deg[Λi(x)]+deg[Ωi-l(x))=2t,
deg[Λi(x)]+deg[Ωi(x))<2t.
При появлении v≤t ошибок имеем: deg[Ω(x)]< deg[Λ (x)] ≤t.
Существует единственный с точностью до постоянного множителя (элемента поля) многочлен Λ(х) степени ≤ t, удовлетворяющий уравнению:
Ωi(x) =S(x) Λi(x) (mod x2t),
если deg[Ωi-1(x)]≥ t при deg[Λi(x)]≤ t
и deg[Ωi(x)]< t при deg[Λi+1,(x)] > t.
Поэтому промежуточные результаты на I-ом шаге дают единственное интересующее нас решение ключевого уравнения.
Таким образом, для решения ключевого уравнения следует применять алгоритм Евклида до тех пор, пока не будет выполнено условие
deg[Ωi(x)]< t.
Итак, алгоритм Евклида решения ключевого уравнения по методу У. Сугиямы и др. сводится к следующему:
1. Применить алгоритм Евклида к а(х)=х2t и b(x)=S(x).
2. Использовать начальные условия:
Λ-1(х)=0,
Λ0(х)=1,
Ω-1(x)=x2t,
Ω0(x)=S(x).
3. Остановиться, если deg[Ωi(x)]< t.
4. Положить Λ(х)= Λi(x) и Ω(x)= Ωi(x).
При вычислении значений Λi(x) и Ωi(x) следует использовать свойство алгоритма Евклида: каждое из значений Λi(x) и Ωi(x) получается из двух предшествующих значений по следующей общей формуле:
Ei(x)=Ei-2(x)+qi(х)Ei-1(x) , где .
В квадратных скобках записано частное от деления указанных многочленов т,е. многочлен степени 0 и более.
в) Алгоритм Берлекемпа-Месси.
На рис.7.1 представлен доработанный алгоритм, позволяющий кроме А(х) получать также и многочлен значений ошибок и Ω(x).
Этот алгоритм был предложен Э. Берлекемпом и Дж. Месси[4] как итеративный процесс построения минимального линейного регистра сдвига с обратной связью, аналогичного схеме решения разностных уравнений, генерирующего все компоненты синдромного многочлена S(x) no υ первым.
Целью алгоритма является нахождение коэффициентов многочлена локаторов ошибок Λ(х), значение которых определяет вид обратных связей регистра.
г) Алгоритм Форни
Д. Форни (см. раздел 7.1) получил выражение для вычисления значения ошибки, если известны многочлены значения ошибок Ω(x) и локаторов ошибок:
,
где Хl-1- корень многочлена Λ(х), обратный локатору ошибки Хl, Λ′(Х ) –производная от много члена Λ(х).