Лабораторная работа 10
Исследование работы кодирующих устройств
систематических кодов
Цель и содержание:
Углубить знания, по основам построения порождающей матрицы систематических кодов. Исследовать корректирующие свойства помехоустойчивых систематических блочных кодов.Теоретическое обоснование
Построить порождающую и проверочную матрицы для систематического кода длиной n = 15, исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации М43 = 0101011. Провести декодирование полученной избыточной кодовой комбинации. Провести исследования корректирующей способности кода для однократных и двукратных ошибок, используя проверочную матрицу.
Решение.
Наиболее широкий класс корректирующих кодов - это систематические коды. Для них сложение по модулю два двух разрешенных кодовых кодограмм дает разрешенную кодовую кодограмму. В теории кодирования широко используется матричное представление кодов. Все разрешенные кодовые кодограммы (n, k) кода можно получить, располагая k исходными кодовыми кодограммами. Комбинации должны удовлетворять условиям:
В число этих кодограмм не должна входить нулевой. Кодовое расстояние между двумя любыми парами больше либо равно d(min). Каждая исходная комбинация должна содержать количество единиц больше либо равно d(min), т. е. вес ее должен быть равным либо превышать d(min). Все исходные кодовые кодограммы должны быть линейно независимы (ни одна из них не должна представлять сумму других исходных кодограмм)Исходную кодограмму можно получить из матрицы, которая содержит k строк и n столбцов.
k первых столбцов являются информационными ; ρ последних столбцов являются проверочными символами;
Матрица P(n, k) является порождающей (образующей). Данную матрицу можно представить в виде двух матриц:
- информационной (размером k x k);
- проверочной.
Для построения порождающей матрицы информационную матрицу удобно представить в виде единичной матрицы (единицы по диагонали). Проверочная матрица должна строиться с соблюдением следующих условий:
Количество единиц должно быть не меньше равно d(min) - 1. Сумма по модулю два любых двух комбинаций (строк) должна содержать не менее d(min) - 2 единиц.Проверочные символы образуются за счет линейных операций над информационными символами. Для каждой кодовой комбинации должно быть построено ρ независимых сумм по модулю два. Весьма удобно проверочные суммы составлять с помощью проверочной матрицы согласно алгоритма:
В начале строится проверочная часть порождающей матрицы. Затем снизу дописывается единичная матрица.Произведение порождающей матрицы на проверочную матрицу равно нулю.
P(n, k)* H*(ρ) = 0
Совокупность комбинаций линейного кода - есть множество разрешенных последовательностей Bi для которых произведение Bi* H*(ρ) = 0, где Bi - матрица строка.
Алгоритм определения проверочных символов следующий:
Позиции, занимаемые в первом столбце должны участвовать в формировании первого проверочного символа. Единицы во втором столбце участвуют в формировании второго проверочного символа. Алгоритм продолжается для всех с столбцов матрицы. В результате получается с проверочных уравнений, позволяющих определить значения проверочных символов в кодограмме.При построении порождающей матрицы воспользуемся основными правилами, согласно которым порождающая матрица имеет вид
Проверочная матрица получается из исходной Р(15,7) и имеет вид
2. Покажем процесс получения разрешенной кодовой комбинации для исходной М43 = 0101011 с использованием порождающей матрицы.
В43=М43*Р(15,7)=1*010000010101010+1*000100010011001+1*00001010100101 + 1*000000111000011 = 0101011 01010101
Проведем процедуру декодирования помехоустойчивого кода (15,7) с использованием проверочной матрицы. Для обнаружения ошибки необходимо определить синдром ошибки. Если данный синдром равен нулю, то полученная кодовая комбинация является разрешенной, в противном случае – произошла ошибка. Для вычисления синдрома необходимо перемножить полученную кодовую комбинацию на проверочную матрицу.
Si = H(15,7) * B43= 10101010 + 10011001 + 10100101 + 11000011 + 01000000 + + 00010000 + 00000100 + 00000001 = 0000 0000
Полученный нулевой синдром свидетельствует о том, что принятая комбинация является разрешенной.
Пусть в 3 разряде (а3) принятой кодовой комбинации произошла ошибка. Тогда кодограмма представляется следующим образом
В43* = 0 1 1 1 0 1 1 0 1 0 1 0 10 1
Определим синдром ошибки
Si = H(15,7) * B43* = 10101010 + 11001100 + 10011001 + 10100101 + 11000011 + + 01000000 + 00010000 + 00000100 + 00000001 = 1100 1100
Полученнй синдром отличен от нуля. Следовательно, принятая кодовая комбинация не является разрешенной. Для определения местоположения ошибки обращаемся к проверочной матрице. Данный синдром соответствует третьей строке проверочной матрицы, что позволяет сделать вывод – ошибка произошла в третьем разряде. Тогда вектор ошибка
Е = 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
Для корректировки результата необходимо к принятой кодовой комбинации прибавить по модулю 2 вектор ошибки. Результатом будет.
В43* = 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1
Е = 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
В43 = 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1
Пусть произошла двукратная ошибка в а4 и а7. Тогда принятая комбинация имеет вид В43*= 0100010 01010101. Определим синдром ошибки.
Si = H(15,7) * B43*= 10101010 + 10100101 + 01000000 + 00010000 + 00000100 + + 00000001 = 0101 1010
Синдром отличен от нуля. Однако данная комбинация отсутствует в проверочной матрице. Это позволяет сделать вывод о том, что полученная кодовая комбинация содержит ошибку, кратность которой больше 1. Для определения местоположения ошибки необходимо произвести попарное суммирование по модулю 2 строк проверочной матрицы. Сумма четвертой и седьмой строк равна синдрому ошибки. Следовательно, ошибочными являются 4 и 7 разряды кодовой комбинации В43*, а вектор ошибки имеет вид
Е = 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0.
Для получения истинной кодовой комбинации необходимо произвести суммирование по модулю 2 искаженной кодограммы с вектором ошибки.
В43* = 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1
Е = 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0
.В43 = 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1
Проведенные исследования корректирующих способностей кода (15,7) показали, что данный систематический код позволяет исправлять как однократные, так и двукратные ошибки.
Аппаратура и материалы
Компьютерный класс общего назначения с конфигурацией ПК не хуже рекомендованной для ОС Windows 7. Операционная система Windows 7.Методика и порядок выполнения работы
Изучить теоретический материал работы. Провести исследование корректирующих способностей помехоустойчивых систематических кодов.Варианты задания
Построить порождающую и проверочную матрицы систематического кода (15, 6), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок. Построить порождающую и проверочную матрицы систематического кода (16, 7), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок. Построить порождающую и проверочную матрицы систематического кода (11, 2), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок. Построить порождающую и проверочную матрицы систематического кода (11, 3), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок. Построить порождающую и проверочную матрицы систематического кода (16, 8), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок. Построить порождающую и проверочную матрицы систематического кода (13, 5), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок. Построить порождающую и проверочную матрицы систематического кода (14, 6), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок. Построить порождающую и проверочную матрицы систематического кода (14, 5), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок. Построить порождающую и проверочную матрицы систематического кода (12, 3), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок. Построить порождающую и проверочную матрицы систематического кода (12, 4), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок. Построить порождающую и проверочную матрицы систематического кода (17, 8), исправляющего двукратные ошибки. Показать процесс образования разрешенной кодовой комбинации. Провести исследования корректирующих способностей кода – исправление однократных и двукратных ошибок. Показать процесс обнаружения трехкратных ошибок.Содержание отчета и его форма
Отчет по лабораторной работе, оформленный письменно, должен содержать процесс исследования корректирующих способностей помехоустойчивых кодов по своему варианту и ответы на контрольные вопросы.
Вопросы для защиты работы
Помехоустойчивые коды и их классификация Корректирующие способности кодов Минимальное кодовое расстояние и его связь с dmin Алгоритм построения порождающей матрицы. Алгоритм построения проверочной матрицы Алгоритм построения проверочных уравнений