Лабораторная работа. Исследование процессов кодирования и декодирования при передаче дискретных сообщений кодами Хэмминга. Скачать бесплатно

ОТЧЕТ
ПО ЛАБОРАТОРНОЙ РАБОТЕ
по дисциплине «Информационные технологии»
Исследование процессов кодирования и декодирования при передаче дискретных сообщений кодами Хэмминга.
2012
 

Реферат

Отчет по лабораторной работе 11 с., 1 часть, 6 источников. КОД ХЭММИНГА, КОДИРОВАНИЕ, ДЕКОДИРОВАНИЕ, ДИСКРЕТНОЕ СООБЩЕНИЕ, СИНДРОМ ОШИБКИ.
КЛЮЧЕВЫЕ СЛОВА.
Предметом исследования лабораторной работы являются процессы кодирования и декодирования при передаче дискретных сообщений кодами Хэмминга
Цель работы – изучение способов задания, оценки конкретных свойств, принципа построения и работы кодирующих и декодирующих устройств кодов Хэмминга.
Порядок выполнения задания:
1 Построить порождающую матрицу кода.
2 Построить проверочные матрицы кода.
3 Сформировать системы проверочных и синдромных уравнений.
4 Сформировать кодовое слово исследуемого кода, ввести одиночную ошибку.
5 Показать на примере, что код не гарантирует обнаружение тройных ошибок.
6 Произвести первичное декодирование принятого сообщения, закодированного кодом Хэмминга.
По итогам работы были сделаны выводы об особенностях кодирования методом Хэмминга.
 

Содержание

Введение    4
Результаты выполнения    6
1    Определяем длину информационного i и длину проверочного к последовательного кода и формируем код Хэмминга    6
1    Порождающая матрица    6
2    Проверочная матрица    6
3    Проверочные уравнения    7
4    Декодирование    8
Заключение    10
Список использованных источников    11

Введение

Коды Хэмминга — наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов (представлены Хэммингом в 1950 г.) Построены они применительно к двоичной системе счисления.
Данные коды обладают кодовым расстоянием dmin=3 и поэтому способны исправлять только одну или обнаружить две ошибки. Число разрешенных кодовых комбинаций для кодов с d=3 равно N ≤ 2n•(1+n)-1. Для кодов Хэмминга выбрано предельное значение разрешенных кодовых комбинаций N = 2n•(1+n)-1, а число информационных разрядов k определяется как
k = log[ 2n•(1+n)-1 ] = n - log(n + 1).
Данное уравнение имеет целочисленные решения k = 0,1,4,11,26,…., которые и определяют соответствующие коды Хэмминга.
Алгоритм кодирования может быть представлен следующим образом. Все номера позиций кода нумеруются в двоичной системе счисления, начиная с единицы p-разрядным двоичным числом: p = [ log(n) ], где [ ] - ближайшее большее целое, n - число разрядов кода cncn-1 ...cj...c1. Проверочные разряды размещаются в позициях кода, кратных целой степени двойки 20,21,… и т.д.: cj = bj , j = 2i, i = 0,1,…,(r-1), где r - число проверочных разрядов. Значение cj проверочного разряда определяется как сумма по mod2 тех разрядов кода, в номере которых двоичный разряд с i-ым весом равен единице.
Алгоритм декодирования может быть представлен следующим образом. Вычисляется значение синдрома ошибки: Eош = || hrhr-1 ...hi...h1 ||. Значение i-го разряда синдрома определяется как сумма по mod2 тех разрядов принятого кода, включая проверочные, в номере которых вес двоичного разряда совпадает с весом разряда синдрома. Например, для r = 3:
 
При проверке информации после ее приема возможны три случая:
•    Отсутствие ошибок - корректирующее число равно нулю, общая четность суммы единиц кодовой комбинации правильна.
•    Одиночная ошибка - контроль общей четности кодовой комбинации обнаруживает ошибку, корректирующее число указывает номер искаженного разряда (если корректирующее число равно нулю - ошибка произошла в разряде общей четности).
•    Двойная ошибка - корректирующее число не равно нулю, контроль общей четности кодовой комбинации не обнаруживает ошибки.
Целью работы являлось проведение кодирования и декодирования сообщения кодами Хэмминга.
Результаты выполнения
1    Определяем длину информационного i и длину проверочного к последовательного кода и формируем код Хэмминга
Нам дана длина кода – n. Информационные и проверочные биты определим из соотношения:       
2к > i+k    (1)
Т.к. длина кода n=7, а длину информационного кода возьмем равную i=4, то согласно соотношению (1) количество проверочных бит k=n-i, k=3:  
23 > 4+3.
Код (7,4,3).
Формируем код Хэмминга: k1 k2 i3 k4 i5 i6 i7  (проверочные биты стоят на местах: 20, 21, 22, 23 и т.д.):
1. xxx1
2. xx1x
3. xx11    xxx1            k1 = i3   i5  i7             
4. x1xx    xx1x                 k2 = i3   i6  i7 
5. x1x1    x1xx            k4 = i5   i6  i7
6. x11x
7. x111

1    Порождающая матрица

Кодом Хэмминга называется (n,k)-код, проверочная матрица которого имеет i = n-k строк и 2i-1 столбцов, причем столбцами являются все различные ненулевые последовательности. Столбец Р – проверка на четность.
Строим порождающую матрицу кода, которая состоит из единичной матрицы Ii, содержащей информационные биты и прямоугольной матрицы Ki,k, составленной из проверочных битов:
 

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

Проверочная матрица имеет вид H(n,i)=|Ki,kT, Ii|; где Ii - единичная матрица;
Ki,kT - прямоугольная матрица в транспонированном виде матрицы Ki,k из порождающей матрицы. Проверочная матрица любого кода Хэмминга всегда содержит минимум три линейно зависимых столбца.
В нашем случае H(7,3)=|K4,3T, I4|:
 
Отсюда получаем проверочную матрицу вида:
 

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

Сформируем кодовое слово исследуемого кода, введем одиночную ошибку и покажем ее исправление путем вычисления синдрома.
Произведение любого кодового слова G на транспонированную проверочную матрицу дает нулевой вектор размерности (n-i):   Gi•Hn,iT =[00...]
Возьмем любой код из порождающей матрицы G, умножим на HT и проверим на наличие ошибки:
 
Как видно из полученного результата,  ошибки нет.
Произведение некоторого кодового слова Gi', т.е. с ошибкой, на транспонированную проверочную матрицу называется синдромом и обозначается Si:
Gi'•H(n, k)T= Si.
Пусть переданное кодовое слово G= 1000111, а принятое слово - G'= 1000110.  Синдром, соответствующий принятому слову будет равен S=G'•H(8,4)T=[001]. Вычисленный синдром указывает на ошибку. Покажем это:
 
Код Хэмминга позволяет выявить только одну ошибку. Пусть передано кодовое слово 1000111. Сделаем три ошибки и получим код 1011110. Проверим его:
 
Как видно из полученного результата, проверяемый код содержит ошибку.

4    Декодирование

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

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

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

Заключение

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

Список использованных источников

1.    Блейхут Р. Теория и практика кодов, контролирующих ошибки. Пер. с англ. М.: Мир, 1986, 576 с.
2.    Кларк Д., Кейн Д. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. М.: Радио и Связь,1987, 300 с.
3.    Коды Хэмминга // Netwiki (http://iu5.bmstu.ru/netwiki/index.php Коды_Хэмминга)
4.    Никитин Г.И. Эффективные коды: Метод. указ., ЛИАП, Л., 1987, 28 с.
5.    Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976, 600c.
6.    Семенов Ю.А. Алгоритмы телекоммуникационных сетей. Часть 1. Алгоритмы и протоколы каналов и сетей передачи данных. - БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2007


Скачать одним архивом (бесплатно):




Использование материалов сайта с целью размещения на сторонних ресурсах ЗАПРЕЩЕНО


Не подходит работа? Нет материала? Не знаешь как сделать? Воспользуйся работой на заказ!

/td