51359

Синдромное декодирование

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

Информатика, кибернетика и программирование

На основе кода с проверкой на четность можно построить высокоскоростной код позволяющий исправлять однократные ошибки где проверки на четность располагаются оптимальным образом – код Хэмминга. Так уравнения для формирования проверочных символов могут быть представлены в виде порождающей матрицы G а для проверок на четность в виде проверочной матрицы кода H. Ход работы В ходе данной лабораторной работы было реализовано консольное приложение которое выполняет следующие функции: 1строит порождающую и проверочную матрицы для кода...

Русский

2014-02-10

46.8 KB

26 чел.

Министерство образования Республики Беларусь

ПОЛОЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра вычислительных систем и сетей

Отчёт

по лабораторной работе № 2 по курсу «Теория кодирования»

«Синдромное декодирование»

Выполнила:                                                                             Кирсанова В.М.

    гр. 10-ИТ-3          

                                                                                              

          

Проверил:                                                                                        Богуш Р.П.

Полоцк. 2013

  1.  Цель работы

Изучение методов синдромного декодирования на примере кодов Хэмминга.

Теоретические сведения

Двоичное число, состоящее из 0 для каждой выполненной проверки на чётность и 1 для каждой невыполненной, называется синдромом.

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

Основная идея кодов Хемминга состоит в том, что синдром даёт фактическое положение ошибки в одной из n позиций кодового слова, причём нулевой синдром означает отсутствие ошибки. Поэтому количество проверочных бит r выбирается как наименьшее целое положительное число, такое, что двоичное представление n=k+r содержит r бит.

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

Ход работы

В ходе данной лабораторной работы было реализовано консольное приложение, которое выполняет следующие функции:

1)строит порождающую и проверочную матрицы для кода Хемминга;

2) строит порождающую и проверочную матрицы для треугольного кода;

3)кодирует сообщение с использованием порождающей матрицы;   

4)декодирует сообщение с использованием проверочной матрицы (вычисляет синдром);

5)демонстрирует разработанные процедуры кодирования и декодирования для кода Хемминга и треугольного кода;

Для хранения кодовых слов в программе используется  контейнер BitSet библиотеки STL. BitSet позволяет нам хранить битовые маски чисел, например типа int или long int, а также получать битовую маску целого числа, подсчитывать количество единичных разрядов, инвертировать значение выбранного разряда числа, выполнять побитовые операции XOR, AND и др.

Для построения проверочной матрицы для кода Хемминга реализована функция  MakeHemMatrixH(), которая по заданным размерам генерирует матрицу H. Матрица H для кода Хемминга содержит все десятичные числа из диапазона от 1 до 2r-1 в двоичном представлении. Функция MakeHemMatrixG() строит порождающую матрицу Хемминга на основе проверочной, а именно, столбцы с номером, являющимся степенью 2, содержат строки проверочной матрицы из которых выброшены элементы, расположенные в позициях с номером, являющимися степенью 2.

Для построения порождающей матрицы треугольного кода реализована функция MakeTrMatrixG(), которая по заданным размерам строит матрицу G. Проверочные символы получаются на основе уравнений проверок для треугольного кода. В качестве примера, для кода (10,6) уравнения имеют следующий вид: p1 = i1 + i2 + i3, p2 = i3 + i4 + i5, p3 = i2 + i5 + i6, p4 = i1 + i4 + i6, где p – проверочные символы, а i – информационные. Проверочная матрица для треугольного кода формируется на основании порождающей с помощью транспонирования столбцов проверок и добавлением единичной матрицы нужного размера. За формирования проверочной матрицы отвечает функция MakeTrMatrixH().

Функция кодирования Code() выполняет кодирование сообщения с помощью порождающей матрицы, при этом она является универсальной, т.к. в нее в качестве параметров передаются матрица, сообщение и нужные размеры. По такому же принципу организована и функция декодирования Decode(), которая вычисляет синдром сообщения.

Демонстрация разработанных процедур кодирования и декодирования осуществляется в функциях TestT() и TestH(). В функции TestH() показано вычисление синдромов для кода Хемминга для различных сообщений: верного (синдром равен 0) и ошибочных (синдром в десятичном представлении указывает позицию неверного разряда, в случае единичной ошибки). Функция TestT() демонстрирует вычисление синдрома для верного сообщения и для ошибочного сообщения, причем в первом случае синдром является нулевым, а во втором содержит ненулевые значения.


Пример работы программы для кода Хемминга (7,4):

Рис. 1. Результат выполнения программы

Вывод

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


 

А также другие работы, которые могут Вас заинтересовать

15369. Повышение эффективности производства подсолнечника на примере ООО Лосево 1.28 MB
  Основы экономики производства подсолнечника 5 Народнохозяйственное значение производства подсолнечника 5 Состояние и основные тенденции развития рынка 9 подсолнечника в России Краткая характеристика ООО Лосево
15370. Понятие и виды освобождения от наказания 191.5 KB
  Проявившиеся в последнее время тенденции широкого применения к лицам, впервые совершившим преступления не только небольшой, но и средней тяжести, института освобождения от наказания, нуждается в дальнейшем изучении с целью выявления необходимости последующего изменения уголовного закона и эффективности его применения
15371. Правовые основы доходов и расходов, финансирования 187 KB
  Термин «государственные доходы» употребляется в литературе и правовых актах в двояком значении. С одной стороны, этим термином обозначается определенная группа экономических распределительных отношений, а с другой – материальные носители этих отношений – финансовые ресурсы государства
15372. Принципы гражданского процессуального права 205 KB
  Данная курсовая работа состоит из: введения, в котором описываются задачи, цели, предмет и объект данного научного исследования; основной части, состоящей из трех глав. Первые две главы раскрывают непосредственно содержание принципов гражданского судопроизводства
15373. Психология мотивации человека 163.5 KB
  Введение Проблема мотивации и мотивов поведения в деятельности – одна из основных в психологии. Вряд ли найдется такая область психологии которая не затрагивала бы мотивационного процесса. В настоящее время мотивация как психическое явление трактуется поразному....
15374. Развитие толерантности в системе образования - как объективная потребность современного общества 225 KB
  Курсовая работа Тема: Развитие толерантности в системе образования как объективная потребность современного общества. Развитие толерантности является объективной потребностью современного общества. В услов
15375. Разработка целевого рынка витаминных препаратов 775 KB
  Целью данной работы является разработка целевого рынка витаминных препаратов для гипотетической фирмы на рынке Санкт-Петербурга. Для этого будет проведено маркетинговое исследование рынка витаминных препаратов
15376. Оценка бюджетной эффективности инновационного проекта 308.5 KB
  Введение Современный бизнес является инновационным. Развитие невозможно без инноваций а инновации в свою очередь – без инвестиций. Для финансирования инновационно-инвестиционных проектов используются разнообразные источники и механизмы в том числе и кредиты. Дл
15377. Роль Сбербанка в экономике страны 203.5 KB
  Введение В современном мире банки не только организуют денежный оборот и кредитные отношения но и выполняют огромное число разнообразных банковских операций необходимых для дальнейшего развития общества. Сберегательный банк это один из универсальных коммерчес