- •Федеральное агенство по образованию
- •Помехоустойчивые коды в радиотехнике и связи
- •Введение
- •Глава 1. Помехоустойчивые коды
- •1.2. Коды, обнаруживающие ошибки
- •1.2.1. Двоичный безызбыточный код
- •1.2.2. Код с защитой по паритету (четности, нечетности)
- •1.2.3. Код с простым повторением
- •1.2.4. Код с повторением и инверсией
- •1.2.5. Код на одно сочетание
- •1.3. Коды, исправляющие ошибки
- •1.3.1. Общие правила построения блочных кодов
- •1.3.2. Правила построения кода Хэмминга
- •1.3.3. Правила построения кода Рида-Маллера
- •1.3.4. Основные понятия о свойствах многочленов и полях Галуа
- •1.3.5. Правила построения примитивных кодов бчх
- •1.3.6. Правила построения кода Голея
- •1.3.7. Правила построения кода Рида-Соломона
- •1.3.8. Правила построения кода Вайнера-Эша
- •1.3.9. Правила построение кода Ивадаре
- •1.4. Кодирование и декодирование кодов
- •1.4.1. Методы кодирования и декодирования циклических кодов
- •1.4.2. Методы кодирования и декодирования линейных кодов
- •1.4.3. Методы кодирования и декодирования свёрточных кодов
- •1.5. Описание инструментальной системы для построения помехоустойчивых кодов
- •1.5.1. Установка инструментальной среды на пэвм
- •1.5.2. Интерфейс инструментальной среды
- •1.6. Методика построения кодов в инструментальной среде «Помехоустойчивые коды»
- •1.6.1. Код Хэмминга
- •1.6.2. Код Рида-Маллера
- •1.6.3. Код бчх
- •1.6.4. Код Голея
- •1.6.5. Код Рида-Соломона
- •1.6.6. Код Вайнера-Эша
- •1.6.7. Код Ивадаре
- •1.7. Вычисление характеристик кодов
- •1.7.1. Вычисление энергетической эффективности кода
- •1.7.2. Вычисление корреляционных функций кода
- •1.8. Построение кодирующих и декодирующих схем
- •1.9. Задание к лабораторной работе «Построение и расчет параметров помехоустойчивых кодов»
- •1.10. Контрольные вопросы к главе 1
- •Глава 2. Коды для линий связи
- •2.1. Особенности линейных кодов
- •2.2. Параметры и характеристики линейных кодов
- •Правила построения линейных
- •Биполярный код с замещением трех нулей (в3zs)
- •2.3.6. Парноизбирательный троичный код (пит, pst)
- •2.3.7. Код с инверсией токовых посылок (cmi)
- •2.3.12. Код dmi
- •2.3.13. Код h
- •2.3.14. Код isdn
- •2.3.15. Квазитроичный разностный код (prkk)
- •2.4. Правила построения линейных алфавитных кодов
- •2.4.1. Код 4b3t
- •2.4.2. Код fomot
- •2.4.3. Код ms43
- •2.5. Правила построения многоуровневых кодов (мур)
- •2.6. Описание программы Code
- •2.7. Задание к лабораторной работе «Построение и расчет параметров кодов для линий связи»
- •2.8. Контрольные вопросы к главе 2
- •Глава 3. Псевдослучайные последовательности
- •3.1. М-последовательности
- •3.2. Задание к лабораторной работе «Построение и расчет характеристик псевдослучайных сигналов»
- •3.3. Контрольные вопросы к главе 3
- •Библиографический список
- •Помехоустойчивые коды в радиотехнике и связи
- •Помехоустойчивые коды в радиотехнике и связи
1.4.2. Методы кодирования и декодирования линейных кодов
Правила кодирования линейного кода задает проверочная матрица.
Пусть матрица H определена следующим образом:
, (1.33)
Матрица состоит из двух частей: информационнойи проверочной. Каждая изстрок матрицы определяет правило формирования соответствующего проверочного элемента. Так, единицы, расположенные на местах, соответствующих информационным элементам в первой строке, указывают на то, какие информационные элементы должны участвовать в получении первого проверочного элемента. Например, из первой строки следует.
Структурная схема кодирующего устройства, задаваемого проверочной матрицей , приведена на рис.1.9.
Рис.1.9 |
Рис.1.10 |
Алгоритм декодирования включает в себя вычисление и анализ синдрома . Если R(x)=0, то принятое кодовое слово считается неискаженным. Если R(x), то приемник отвергает принятое кодовое слово.
Структурная схема декодера, определенного проверочной матрицей (1.33), представлена на рис.1.10.
1.4.3. Методы кодирования и декодирования свёрточных кодов
При сверточном кодировании поток данных разбивается на блоки длины k0, которые называют кадрами информационных символов. Кадры информационных символов кодируются кадрами кодового слова длины n0 каждый. Причем кодирование каждого кадра информационных символов в отдельный кадр кодового слова производится с учетом предыдущих т кадров информационных символов.
Структура кодера определяется длиной регистра, числом сумматоров и связями каждого сумматора с регистром. Связи выражают двоичным числом (или порождающим полиномом). Единицы в разрядах числа указывают на наличие связей соответствующих отводов регистра с сумматором.
Например, приведенная на рис.1.11 схема кодера соответствует сверточному коду, определенному порождающими полиномами =(111), =(101).
Рис.1.11
Способ представления связи между входными и выходными последовательностями называется решетчатой диаграммой (рис.1.12). Для решетчатой диаграммы характерны следующие утверждения:
состоит из узлов и ребер (ветвей);
число ребер, исходящих из узла, равно основанию кода;
число узлов - ;
выходные символы записываются над ветвями;
надписи около узлов характеризуют логическое состояние кодирующего устройства;
каждой информационной последовательности символов соответствует определенный путь на диаграмме;
процесс кодирования заключается в выборе одного из путей диаграммы.
Рис.1.12
Декодирование сверточных кодов осуществляется одним из трех методов: c вычислением проверочной последовательности, по принципу максимума правдоподобия или методом Витерби.
С вычислением проверочной последовательности. На приемной стороне из принятых информационных символов формируют проверочные по тому же закону, что и на передающей стороне, которые затем сравнивают с принимаемыми проверочными символами. Закон формирования проверочных символов выбирается таким образом, чтобы по структуре проверочной последовательности можно было определить искаженные символы. Метод применим только для систематических сверточных кодов.
Декодирование по принципу максимума правдоподобия сводится к задаче отождествления принятой последовательности с одной из возможных. Решение принимается в пользу той последовательности, которая в меньшем числе позиций отличается от принятой. Метод применим для любого сверточного кода, но не реализуем при больших значенияхk из-за необходимости перебора возможных кодовых последовательностей.
При декодировании методом Витерби из всех путей на решетчатой диаграмме выбирается путь, которому соответствует кодовая последовательность, отличающаяся от принятой в меньшем числе символов (весе - ).
Пример. Пусть последовательность на выходе кодера (рис.1.11) имеет вид 00 00 00 00 00 … , а принятая последовательность - 10 00 10 00 00… . Работу декодера иллюстрируют диаграммы (рис.1.13,а-в), где числа в узлах характеризуют минимальный вес пути на -м такте.
а)
|
б) |
в) | |
Рис.1.13 |
На третьем такте работы декодера (рис.1.13а) общее число путей равно 8. Декодер сравнивает метрики для пар путей, ведущих в каждый узел, и из каждой пары оставляет путь с меньшим весом:
Расчет веса пути для первого узла | ||
Расчет веса пути для второго узла |
Таким образом, для первого узла на диаграмме выбирается путь с весом (рис.1.13а), для второго узла – путь с весоми т.д. На четвертом такте работы (рис.1.13б) для первого узла на диаграмме выбирается путь с весом, для второго узла – путь с весоми т.д. Процесс сравнения веса пар путей, ведущих в каждый узел, повторяется на каждом такте.
Глубина (число тактов), на которой происходит слияние путей, является случайной величиной, зависящей от ошибок в принятой последовательности, и заранее не может быть вычислена. Поэтому при практической реализации декодера устанавливают некоторую фиксированную глубину декодирования. В примере на 10-м такте первые восемь ветвей всех «выживших» путей совпадают (рис.1.13в). В этот момент согласно алгоритму Витерби, принимается решение о принятых символах.