Лабораторная работа №1
Исследование циклических кодов
Цель работы
Ознакомление с методами построения циклических корректирующих кодов. Экспериментальное исследование обнаруживающей и исправляющей способности циклических кодов (15,11) и (23,12).
Предварительная подготовка
2.1 Ознакомиться с описанием работы, изучить по указанной ниже литературе и ответить на следующие вопросы:
2.1.1. В чем заключается назначение блока “кодек” в обобщенной структурной схеме системы связи?
2.1.2. Перечислите некоторые практические приложения теории помехоустойчивого кодирования.
2.1.3. Поясните отличие режимов (обнаружение или исправление ошибок) и типов кодов, используемых в системах связи и хранения данных.
2.1.4. Приведите основные понятия теории помехоустойчивого кодирования. Поясните их сущность.
2.1.5. В чем заключается сущность энергетического выигрыша от кодирования (ЭВК)?
2.1.6. Дайте определение поля Галуа.
2.1.7. В чем заключаются свойства группы?
2.1.8. Найдите сумму двух элементов двоичного поля Галуа: α=101, β=011.
2.1.9. Запишите таблицы сложения для целых положительных чисел по модулю чисел 4, 8.
2.1.10. Запишите таблицы умножения для целых положительных чисел по модулю чисел 4, 8.
2.1.11. Какие коды называются линейными?
2.1.12. Что такое синдром ошибки, как он определяется математически (и в процессе декодирования)?
2.1.13. Поясните принцип умножения многочленов на примере: a (x)=1+ x+x 3и b (x)=1+ x 5.
2.1.14. Какой код называется циклическим? Что такое производящий многочлен циклического кода и как он определяется?
2.1.15. Запишите производящий многочлен g (x)= x 11+ x 9+ x 7+ x 6+ x 5+ x +1 в двоичной и восьмеричной форме.
2.1.16. Нарисуйте структурную схему кодера циклического кода (23,12).
2.1.17. Что такое укороченный циклический код? Его свойства.
2.1.18. Запишите все укороченные коды циклического кода (7,4).
2.2 Рассчитайте вероятность ошибки в кодовом слове на входе и выходе декодера для исследуемых кодов, если вероятность ошибки в канале с независимыми ошибками равна p (указана в таблице 1).
Таблица 1
| № бригады | ||||||||||||
| P | 0,1 | 0,09 | 0,08 | 0,07 | 0,06 | 0,05 | 0,04 | 0,03 | 0,02 | 0,01 | 0,05 | 0,025 |
2.3 Для подготовки к работе рекомендуется следующая литература:
- А.А.Макаров, В.П.Прибылов. Помехоустойчивое кодирование в системах телекоммуникаций: Учеб. пособ., 2004.
- А.А.Макаров. Методы повышения помехоустойчивости систем связи: Учеб. пособ., 1991.
- А.А.Макаров, Л.А.Чиненков. Основы теории помехоустойчивости систем связи: Учеб. пособ., 1997.
- А.А.Макаров, В.И.Ковязин. Автоматизация проектирования систем передачи данных: Учебное пособие, 1987.
Краткая теория
Декодер Меггита представляет собой синдромный декодер, исправляющий одиночные ошибки, в памяти которого с целью упрощения хранится только один синдром ошибки S15(x)=x3+1 (соответствует последовательности ошибки e15(x)=x14), синдромы остальных одиночных ошибок циклически сдвигаются в регистре синдрома до совпадения с S15(x); число тактов сдвига i (i=0,1,2...14) плюс единица равно номеру искаженного кодового элемента.Структурная схема декодера показана на рисунке 1.
Рисунок 1- Декодер Меггита циклического кода (15,11)
Декодер работает следующим образом. Кодовое слово (с ошибками или без них) в виде последовательности из 15 двоичных символов поступает в буферный регистр и одновременно в регистр синдрома, где производится деление этого слова на производящий многочлен кода g(x)=x4+x+1 в результате чего вычисляется синдром ошибки Sj(x): S0j,S1j, S2j, S3j - символы синдрома. Ошибка обнаруживается, если хотя бы один символ синдрома не равен нулю. Исправление ошибок производится в следующих 15 тактах. Если Sj(x)=S15(x), то ошибка в первом символе кодового слова, который находится в 15- ой ячейке буферного регистра. Тогда на первом такте схема {И} выдаёт единицу и в сумматоре по mod 2 на выходе буферного регистра корректируется первый символ кодового слова. Если ошибка в другом символе, то производится циклический сдвиг синдрома Sj(x) в регистре синдрома по цепи обратной связи с учетом того, что вход декодера в цикле исправления ошибок отключен. На каждом i-ом такте проверяется равенство Sj+i(x)=S15(x) и в благоприятном случае на выходе схемы {И} появляется импульс коррекции ошибки, инвертирующий символ на выходе буферного регистра.
На рисунке 2 приведена структурная схема декодера Касами-Рудольфа.
Рисунок 2 -Декодер Кассами-Рудольфа для циклического кода Голея (23,12)
В данном декодере используется не оптимальный перестановочный метод декодирования, в котором с целью упрощения процедуры поиска ошибки используются циклические сдвиги синдромов ошибок и их сравнение с "покрывающими" синдромами (алгоритм Касами-Рудольфа). Для кода Голея (23,12): g(x)=x11+x9+x7+x6+x5+x+1 множество ошибок, вес (кратность) которых не превышает трёх, покрывается тремя последовательностями ошибок e1(x)=0, e17(x)=x16, e18(x)=x17, имеющих синдромы: S1(x)=0; S17(x)=x8+x7+x4+x3+x+1; S18(x)=x9+x8+x5+x4+x2+x. Декодер отслеживает синдром ошибок, отличающийся от S1(x) не более, чем в трёх позициях, а также синдромы ошибок, отличающиеся от S17(x) и S18(x) не более, чем в двух позициях.
Декодирование производится в течение двух циклов.
В первом цикле в течение 23 тактов производится запись принятого кодового слова в буферный регистр (п1=0) и вычисление синдрома ошибки в синдромном регистре (п2=0).
Во втором цикле (п1=1) из 23 тактов производится поиск и исправление ошибок путем циклического сдвига синдрома ошибки и его сравнения с покрывающими синдромами в анализаторе синдрома. Одновременно циклически сдвигается кодовое слово в буферном регистре. Позиции ошибок обнаруживаются при удовлетворении какого-либо из неравенств в анализаторе синдрома; на выходе соответствующей схемы анализатора появляется сигнал, по которому выход синдромного регистра подключается (п2=1) к сумматору в цепи циклического сдвига буферного регистра для исправления ошибок. Если срабатывает вторая или третья схемы анализатора, то дополнительно исправляются ошибки в 17-ой или 18-ой ячейках буферного регистра в соответствии с номером покрывающего синдрома; одновременно производится стирание этого синдрома в синдромном регистре. После 23-го такта производится проверка состояния синдромного регистра и, если остаток не превышает двух единиц, его содержимое используется для коррекции состояний первых 11 ячеек буферного регистра. На этом декодирование заканчивается и на выход выдаются информационные символы, расположенные в первых 11 ячейках буферного регистра; одновременно на вход может подаваться новое кодовое слово (п1=0).
Лабораторное задание
4.1 Ознакомиться с рабочим местом и особенностями экспериментального исследования корректирующих кодов на ЭВМ.
4.2 Определить экспериментально кодовое расстояние исследуемых кодов и способность кодов с различной избыточностью (для заданных производящих полиномов g1(х) и g2(х)) обнаруживать и исправлять ошибки.
код 1 – (n,k)=(23,12); производящий полином g1(x)=x11+x10+x6+x5+x4+x2+1;
код 2 – (n,k)=(15,11); производящий полином g2(x)=x4+ x+1.
4.3 Исследовать и сравнить результаты декодирования кодовых слов с ошибками различной кратности.
Порядок выполнения работы
5.1 Определить величину кодового расстояния для каждого из двух исследуемых кодов (n, k)=(23,12) и (n, k)=(15,11). Для этого необходимо для каждого из исследуемых кодов найти максимальную (гарантируемую) кратность исправляемых ошибок tисп, последовательно увеличивая число ошибок в кодовых словах, формируемых на экране (факт исправления ошибки данной кратности определяется визуально путем сравнения кодовых слов на входе кодера и выходе декодера). Кодовое расстояние d определяется по известному соотношению, связывающему его с максимальной кратностью исправляемых ошибок. По полученной величине кодового расстояния определить ожидаемую кратность гарантированно обнаруживаемых ошибок tобн.
5.2 Исследовать результаты декодирования кодовых слов с ошибками различной кратности (с учетом tобн и tисп предыдущего пункта). Получить несколько вариантов декодирования кодовых слов с последовательностями ошибок е(х) различной кратности и конфигурации для случаев: а) обнаруживаемых ошибок кратности tош<tобн и tош>tобн; б) необнаруживаемых ошибок в том числе кратности tош=tобн+1.
5.3 Сравнить обнаруживающую и исправляющую способность кодов по полученным результатам.
Примечание: Результаты исследований по пункту 5.2 необходимо записывать в файл или выводить на принтер для отчета.
Содержание отчёта
Отчет должен содержать:
- структурные схемы декодеров;
- структурные схемы алгоритмов, имитирующих работу декодеров;
- результаты оценки кодового расстояния для обоих кодов;
- результаты исследования помехоустойчивости кодов;
- сравнительный анализ помехоустойчивости кодов;
- выводы.
Вопросы к защите
7.1. Для кодов (15,11) и (23,12) определите скорость кода и избыточность c учетом того, что кодовое расстояние этих кодов равно d =3 и 7, соответственно. Определите вероятность ошибочного декодирования, если вероятность ошибки равна: а) p =10 -3; б) p =10 -4; в) p =10 -5.
7.2. Поясните сущность группового линейного кода.
7.3. Построить групповой двоичный код, исправляющий одиночные ошибки t и=1, длина кодового слова n =9 (см. пример 2.17).
7.4. Нарисуйте структурную схему циклического кодера, если производящий многочлен кода (31,26) g(x)=458 (в восьмеричной форме).
7.5. Что такое и какой вид имеют производящая и проверочная матрицы линейных кодов? Как построить производящую и проверочную матрицы кода по производящему многочлену?
7.6. Определите проверочные символы кодового слова циклического кода (23,12), если информационное слово имеет вид: Ii (x)=000001101001; Ii+ 1(x)=000000000001; Ii+ 2(x)=000000000000; Ii+ 3(x)=111111111111.
7.7. Назовите методы декодирования циклических кодов. Поясните сущность этих методов.
7.8. Какие методы декодирования циклических кодов являются оптимальными? Запишите критерий оптимальности.
7.9. Нарисуйте и поясните структурную схему синдромно-матричного декодера. В чем состоят проблемы его практической реализации?
7.10. В чем отличие декодера Меггитта от обычного синдромного декодера с табличным поиском?
7.11. Найдите какой символ входного кодового слова содержит ошибку, если декодер Меггита (рисунок 3.4) вычислил синдром ошибки вида: Si (x)=1101, Si+ 1(x)=1001, Si+ 1(x)=0001, Si+ 1(x)=0101, Si+ 1(x)=1111.
7.12. Найдите синдром ошибки, если на вход декодера Меггита подаётся кодовое слово вида: Ai (x)=0010100, Ai+ 1(x)=1110100, Ai+ 2(x)=1101001, Ai+ 3(x)=1001000.
7.13. В чем отличие декодера Касами-Рудольфа от обычного синдромного декодера?
7.14. Нарисуйте и поясните структурную схему мажоритарного декодера.
7.15. Какой вид имеет система разделённых проверок?
7.16. Нарисуйте и поясните структурную схему порогового декодера.