Циклический код. Исследование корректирующего кода
![]()
|
Исследование корректирующего кода Лабораторное задание Ознакомиться с интерфейсом программы и схемами кодера и декодера при (n,k)=(7,4). Задать исходную комбинацию на входе кодера циклического кода (7,4) и произвести кодирование. Затем в канале указать ошибки в любых битах получившейся в результате кодирования комбинации. Произвести декодирование получившейся комбинации с ошибкой, с помощью декодера и сравнить с исходной. Ознакомление с методами построения корректирующих кодов. Экспериментальное исследование обнаруживающей и исправляющей способности циклического кода.
Где 0100 111 – разрешенная комбинация, информационные элементы которой соответствуют вдесятичной счисления номеру бригады (лабораторной установки №4).
Порядок выполнения работы Изучить теоретические сведения к данной лабораторной работе, приведенные в пункте 3. Запустить программу, двойным кликом мыши по ярлыку с названием «Циклический код (7.4)». На экране появится окно с изображением кодера циклического кода (7,4) (Рисунок 3): Интерфейс программы в окне с кодером циклического кода (7;4): Исходная кодовая комбинация; Закодированная кодовая комбинация; Ячейки формирователя проверочных групп (ФПГ); Кнопка для начала кодирования (впоследствии становится кнопкой «Такт»); Кнопка для перехода в канал связи, чтобы внести ошибку. ![]() Рисунок 3 – Модель кодера циклического кода (7,4) 4.3 На входе кодера необходимо ввести свою исходную информационную кодовую комбинацию, после чего нажать на кнопку «Начать». ![]() Рисунок 4 – Модель кодера циклического кода (7,4) С помощью кнопки «такт» происходит выполнение следующего такта. Содержимое ячеек формирователя проверочной группы каждого такта и значение элемента на входе нужно свести в таблицу 2: Таблица 2
4.4 По истечению 7 тактов формируется закодированная кодовая комбинация, которую нужно записать в отчет. Затем программа выдает сообщение «Кодирование завершено!», следует нажать ОК и перейти к каналу с помощью кнопки «В канал». ![]() Рисунок 5 – Окно канала 4.5 В канале необходимо указать ошибку в битах закодированной кодовой комбинации (в любом бите на выбор студента), после чего необходимо нажать кнопку «Декодировать» для перехода к декодеру Меггита. 4.6 На рисунке 6 приведена схема декодера Меггита для циклического кода (7,4), по которой будет происходить декодирование кодовой комбинации с ошибкой. Бит с ошибкой выделен красным цветом. Для начала декодирования необходимо нажать кнопку «Начать». ![]() Рисунок 6 – Модель декодера Меггита Интерфейс программы в окне с декодером Меггита: Закодированная кодовая комбинация с ошибкой; Результат декодирования; Ячейки ФПГ; Ячейки регистра задержки (РЗ); Кнопка для начала декодирования (впоследствии становится кнопкой «Такт»); Группа кнопок для дальнейшего действия: Кнопка «Вернуться к кодеру» - если нужно задать другую исходную комбинацию и произвести её кодирование; Кнопка «Вернуться к каналу» - если необходимо задать ошибку в другом бите закодированной комбинации; Кнопка «Выход из программы» - если лабораторная работа выполнена, чтобы закрыть окно программы. 4.7 С помощью кнопки «такт» осуществляется переход к следующему такту. В вверху указывается действие текущего такта: 0 такт – «Начальное состояние…» 1-7 такт – «Идет загрузка в регистр…» 8-14 такт – «Процесс исправления ошибки…» 15-21 такт – «Выгрузка данных из регистра на выход…» После выполнения 21 такта на экране высвечивается сообщение «Процесс декодирования завершен!!!» (Рисунок 7). Необходимо нажать ОК и зафиксировать в отчете кодовую комбинацию на выходе и выделить в ней информационные элементы. ![]() Рисунок 7 – Модель декодера Меггита Содержимое ячеек формирователя проверочной группы каждого такта и значение элемента на входе при выполнении действий загрузки в регистр и процесса исправления ошибки нужно свести в таблицу 3: Таблица 3
4.8 После окончания выполнения лабораторной работы следует закрыть программу, затем выключить компьютер. Содержание отчёта Отчет должен содержать: цель работы; предварительный расчет; структурные схемы кодера и декодера Меггита; результаты кодирования и декодирования в виде таблиц 2 и 3; выводы. Основные теоретические положения Принципы помехоустойчивого (корректирующего) кодирования. Кодовое расстояние В теории помехоустойчивого кодирования важным является вопрос об использовании избыточности для корректирования возникающих при передаче ошибок. Здесь удобно рассмотреть блочные коды, в которых всегда имеется возможность выделить отдельные кодовые комбинации. Напомним, что для равномерных кодов число возможных комбинаций равно ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Различие между комбинациями равномерного кода принято характеризовать расстоянием, равным числу символов, которыми отличаются комбинации одна от другой. Расстояние ![]() ![]() ![]() Например: ![]() ![]() Для любого кода ![]() ![]() Введем коэффициенты, характеризующие обнаруживающую и исправляющую способность кодов ( ![]() ![]() ![]() ![]() ![]() ![]() Принцип направления ошибок следующий. Мы разбиваем все множество комбинаций на ряд непересекающихся подпространство по количеству разрешенных комбинаций. Все запрещенные комбинации находятся в соответственных подпространствах разрешенных комбинаций. Если передавалась комбинация ![]() ![]() ![]() ![]() ![]() ![]() ![]() Кратность ошибки – число искаженных элементов в одной комбинации. Если в комбинации ![]() ![]() Рисунок 1 Модели каналов а) с независимыми ошибками; б) с кратными ошибками (пакетирование) Для правильности выбора кода необходимо знать статистику ошибок в канале. Обнаруживающая и исправляющая способность кодов Для лучшего понимания сущности обнаружения и исправления ошибок воспользуемся пространственными представлениями. Для обнаружения ошибок все пространство кодовых слов подразделяется на два подпространства – разрешенных и запрещенных комбинаций (кодовых слов). ![]() Рисунок 2 Мханизм обнаружения ошибок Следует заметить, что если из-за воздействия помех одна разрешенная кодовая комбинация преобразуется в другую разрешенную кодовую комбинацию, то такая ошибка, хотя она и присутствует, обнаружена не будет. Для исправления ошибок все пространство кодовых слов разбивается на ![]() ![]() Рисунок 3 Механизм исправления ошибок В каждом подпространстве находится одна разрешенная комбинация (обозначена кружком «○») и некоторое количество запрещенных из общего количества ![]() ![]() Исправление ошибок производится в два этапа: 1. Определяется кодовое расстояние между пришедшей кодовой комбинацией и всеми разрешенными кодовыми комбинациями. 2. Решение принимается в пользу той разрешенной кодовой комбинции, для которой кодовое расстояние будет наименьшим (т.е. реализуется критерий идеального наблюдателя). Для получения некоторых количественных соотношений рассмотрим две комбинации ![]() ![]() ![]() Рисунок 4 Иллюстрация для определения кодовых расстояний при обнаружении и исправлении ошибок В общем случае некоторая пара разрешенных комбинаций ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Если ![]() ![]() ![]() Процедура исправления ошибок в процессе декодирования сводится к определению переданной комбинации по известной принятой. Расстояние между переданной разрешенной комбинацией и принятой запрещенной комбинацией ![]() ![]() ![]() ![]() где ![]() Т.к. обычно ![]() ![]() ![]() ![]() ![]() Минимальное значение ![]() Возможно также построение таких кодов, в которых часть ошибок исправляется, а часть только обнаруживается. Так, в соответствии с рис. 4, в, ошибки кратности ![]() ![]() ![]() ![]() ![]() Существуют двоичные системы связи, в которых решающее устройство выдает, кроме обычных символов 0 и 1, еще так называемый символ стирания θ. Этот символ соответствует приему сомнительных сигналов, когда затруднительно принять определенное решение в отношении того, какой из символов, 0 или 1, был передан. Принятый символ в этом случае стирается. Однако при использовании корректирующего кода возможно восстановление стертых символов. Если в кодовой комбинации число символов ![]() ![]() ![]() а остальные символы приняты без ошибок, то такая комбинация полностью восстанавливается. Корректирующая способность кода возрастает с увеличением ![]() ![]() ![]() ![]() что, в свою очередь, требует избыточного числа символов ![]() ![]() ![]() При независимых ошибках вероятность определенного сочетания ![]() ![]() ![]() Отсюда полная вероятность ошибки кратности ![]() ![]() Используя (7), можно записать формулу, определяющую вероятность отсутствия ошибок в кодовой комбинации, т.е. вероятность правильного приема: ![]() и вероятность правильного корректирования ошибок: ![]() Здесь суммирование производится по всем значениям кратности ошибок ![]() ![]() Вероятность ![]() ![]() ![]() Циклические коды (систематический блочный код). Разрешенные комбинации циклического кода можно вычислить последовательно, применяя две операции: циклическую перестановку и суммирование по модулю 2. Циклическая перестановка менее трудоемкая, и это обстоятельство полезно использовать для упрощения процесса вычислений. Расширим производящий момент кода (7,4) до семи членов, применяя нулевые коэффициенты: ![]() ![]() Запишем первую комбинацию: ![]() Применив шесть раз операцию циклической перестановки, можно записать следующие шесть комбинаций. Дальнейшее применение перестановки теряет смысл (они будут приводить к повторению уже имеющихся). Просуммируем по модулю два любые две комбинации из уже имеющихся. Получим комбинацию, содержащую четыре единицы и три нуля. Следующие шесть комбинаций получаются в результате шестикратной циклической перестановки ее элементов. Чтобы получить пятнадцатую комбинацию, нужно найти среди ранее полученных четырнадцати любую пару взаимно противоположных и просуммировать их по модулю 2 ( ![]() Рассмотрим еще один способ нахождения разрешенных кодовых комбинаций, который широко применяется на практике. Пусть ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() где ![]() ![]() Если остаток от деления добавить к ![]() Пример: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Разрешенная кодовая комбинация имеет вид: ![]() ![]() В приемнике (декодере) принятая кодовая комбинация делится на производящий полином. При нулевом остатке комбинация принята верно, либо содержит необнаруженную ошибку; остаток от деления указывает, что комбинация принята с обнаруженной ошибкой. По виду остатка может быть определен искаженный элемент в информационной части принятой комбинации (формируется так называемый синдром). |