Порядок выполнения работы

Лабораторная работа №1

Исследование процессов кодирования и декодирования

при передаче дискретных сообщений кодами Хэмминга

Цель работы: изучение способов задания, оценки конкретных свойств, принципа построения и работы кодирующих и декодирующих устройств кодов Хэмминга.

Порядок выполнения работы

Составить проверочную матрицу систематического кода Хэмминга (7,4), используя следующие принципы её построения:

- матрица должна состоять из различных столбцов;

- последние столбцы матрицы образуют единичную подматрицу ..

Здесь и далее используются следующие обозначения:

-длина кодового слова (суммарное количество информационных и проверочных бит для одного блока передаваемой информации).

-длина информационного слова (количество информационных бит для одного блока передаваемой информации).

-количество проверочных бит .

Размер проверочной матрицы будет . Столбцы проверочной матрицы содержат 3 бита. Для краткости они могут быть представлены в восмиричной системе цифрами 1, 2, 3, 4, 5, 6,7.

Учитывая, что столбцы единичной диагональной матрицы являются двоичными числами - степенями 2-х: 4=2²,2=2¹, 1=2⁰ и одинаковы для всех вариантов задания, требуется определить 4 первые столбца, которые, в свою очередь, образуют ряд оставшихся двоичных трёхбитовых чисел: 3,5,6 и 7. Количество вариантов чередования столбцов равно количеству возможных перестановок, то есть . Все эти возможные перестановки сведены в таблицу с вариантами задания.

Вариант	1-4 столбцы проверочной матрицы (подматрица )
	3,5,6,7
	3,5,7,6
	3,6,7,5
	3,6,5,7
	3,7,5,6
	3,7,6,5
	5,3,6,7
	5,3,7,6
	5,6,3,7
	5,6,7,3
	5,7,3,6
	5,7,6,3
	6,3,5,7
	6,3,7,5
	6,5,3,7
	6,5,7,3
	6,7,3,5
	6,7,5,3
	7,3,5,6
	7,3,6,5
	7,5,3,6
	7,5,6,3
	7,6,3,5
	7,6,5,3

Для получения четырёх первых столбцов проверочной матрицы необходимо преобразовать в двоичную форму четыре восьмиричных числа из вышеприведённой таблицы. Добавив к ним три последних столбца, получим проверочную матрицу для кода Хэмминга со следующими параметрами:

Длина кодового слова, равная количеству столбцов n=7.

Количество проверочных бит равное количеству строк r=3.

Длина информационного блока k=4.

По проверочной матрицы ,составленной из двух подматриц, строится образующая . Для этого потребуется транспонировать подматрицу и добавить к ней слева единичную матрицу.

По полученным матрицам формирeтся система проверочных и синдромных уравнений.

На основе проверочных и синдромных уравнений строятся схемы кодирующего и декодирующего устройств.

Пример Пусть задана образующая матрица

Построить систему проверочных и синдромных уравнений и построить схемы кодирующего и декодирующего устройств.

Проверочные уравнения служат для вычисления проверочных символов согласно формуле:

Раскрыв содержание матричной операции, получим уравнения для символов кодового слова.

Последние 3 уравнения вычисляют проверочные символы и называются проверочными.

По ним строится блок –схема кодера:

Синдромные уравнения строятся по матричному алгоритму декодирования

Определим проверочную матрицу через образующую

Раскрыв матричную операцию для бит синдрома, получим:

В матричном виде это уравнение представлено формулой

,где

- синдром ошибки;

- транспонированная проверочная матрица.

По синдромному уравнению можно построить схему декодера:

На схеме блок «таблица синдромов» – это запоминающее устройство, определяющее по синдрому (он задаётся как адрес) вектор ошибки (последовательность бит, в которой единица располагается на том месте, на котором располагается ошибочный бит в кодовом слове). Например, для ошибки во втором бите кодового слова вектор ошибки представляется кодом . На схеме для краткости предусматривается исправление ошибок только в информационной части кодового слова (в трёх первых битах ).В сокращённом виде вектор для ошибки во втором бите имеет вид: .

Произвести кодирование сообщения кодом Хэмминга, сформировав кодируемое сообщение в виде двух блоков по варианту в таблице 2.Каждый информационный блок содержит 4 бита.

Для передачи кодируются 2 блока

Таблица2

Для каждого блока вычисляется кодовое слово: сначала на бумаге путём умножения строки на матрицу, а затем на компьютере с помощью программы Labor1.exe в подкаталоге «Labor1» каталога «Лаб1 ПК». 4 файла с расширениями *.dll и *.bpl, которые должны быть в каталоге Labor1, необходимы как вспомогательные. Проверить правильность вычислений «вручную» порезультатам компьютерного расчёта.

Составить таблицу синдромов путём задания векторов ошибок в 1 – 7-м битах кодового слова (e=1000000, e=0100000 - e=0000001) и вычислением синдромов по формуле .

В первое из вычисленных кодовых слов внести ошибку, инвертировав один из битов. Второе кодовое слово оставить без изменений.

Произвести декодирование принятого кодового слова, закодированного кодом Хэмминга. Для этого надо вычислить синдром на бумаге по приведённой формуле и затем на компьютере для полученных выше кодовых слов (первое с внесённой ошибкой, второе - без ошибок). Программа Labor1.exe размещена лабораторном компьютере.

Убедиться, что при отсутствии ошибок в кодовом слове значение синдрома s=0.

Определить положение ошибочного бита в первом кодовом слове по вектору ошибки из таблицы синдромов.

Содержание отчета

1. Наименование и цель работы.

2. Исходные данные для выполнения работы.

3. Результаты выполнения работы:

Проверочная матрица

Образующая матрица

Транспонированная проверочная матрица

Проверочные уравнения

Схема кодера

Синдромные уравнения

Схема декодера

Результаты кодирования по формуле

Результаты кодирования на компьютере

Таблица синдромов

Результаты декодирования по формуле

Результаты декодирования на компьютере

Выводы

.

Не нашли, что искали? Воспользуйтесь поиском по сайту: