51359

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

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

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

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

Русский

2014-02-10

46.8 KB

31 чел.

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

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

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

Отчёт

по лабораторной работе № 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. Результат выполнения программы

Вывод

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


 

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

41554. ИНВЕСТИЦИОННЫЙ ПРОЕКТ 472.5 KB
  Инвестиционный проект это план программа хозяйственного мероприятия или предпринимательского проекта реализация которых требует привлечения инвестиций. Структура затрат на реализацию проекта а также доходов получаемых в результате инвестиций традиционно отлична для каждой из выделенных стадий. Определение целей и класса инвестиций 1. Метод расчета рентабельности инвестиций 2.
41555. СУЩНОСТЬ ИННОВАЦИОННЫХ ПРОЦЕССОВ И КЛАССИФИКАЦИОННЫЕ ПОДХОДЫ К ИХ ГРУППИРОВКЕ 308 KB
  Изменения в организации производства и его материальнотехническом обеспечении. Речь может идти также о качественных или количественных изменениях как с положительными так и с отрицательными социальноэкономическими последствиями. Большинство западных авторов обычно подчеркивают необходимость практической реализации изменения. Это могут быть количественные или качественные изменения которые касаются той или иной сферы деятельности предприятия.
41556. ИНВЕСТИЦИОННЫЙ ПРОЦЕСС И МИССИЯ КОМПАНИИ 63.5 KB
  Среди обширного спектра факторов влияющих на выбор миссии компании есть чрезвычайно важный с точки зрения долгосрочной перспективы безкризисного существования фирмы это фактор адекватности инвестирования выдвинутым критериям. Акцент на исследовании этого вопроса делается по двум основным причинам: определяющей роли которая принадлежит инвестиционному процессу в выборе линии поведения фирмы особенно на долгосрочном горизонте ее роста и инноваций продукта. Принятие решений в этой области...
41557. ИНВЕСТИЦИИ: ПОНЯТИЕ, КЛАССИФИКАЦИЯ. РОЛЬ ИНВЕСТИЦИЙ 151.5 KB
  Одной из важнейших сфер деятельности любой фирмы являются инвестиционные операции. Оба типа инвестиций имеют большое значение для сохранения жизнеспособности фирмы и ее развития. Их целью является прежде всего создание условий для снижения затрат фирмы за счет замены оборудования обучения персонала или перемещения производственных мощностей в регионы с более выгодными условиями производства; инвестиции в расширение производства. Логика зависимости между типом инвестиций и уровнем их риска очевидна: она определяется степенью...
41558. ИННОВАЦИОННАЯ ПОЛИТИКА 187 KB
  Как и практически всякая иная политика она неодинакова в разных странах хотя и подчинена одной и той же цели: стимулированию инновационной активности и развитию научнотехнического потенциала. Место и роль инновационной политики в структуре государственного регулирования экономики определяются особенностями инновационного процесса как объекта управления. В практической направленности инновационной идеи и состоит ее притягательная сила для капиталистических компаний. Так к числу внутренних побудительных мотивов инновационной активности можно...
41559. ГОСУДАРСТВЕННЫЕ ЦЕННЫЕ БУМАГИ 168.63 KB
  Хотя по своей экономической сути все виды ГЦБ есть долговые ценные бумаги на практике каждая самостоятельная ГЦБ получает свое собственное название позволяющее отличать ее от других видов облигации. ГЦБ как правило занимают ведущее место на рынке облигаций где их доля доходит до 50 а значит и на всем рынке ценных бумаг поскольку на последнем преобладают облигации. В структуре ГЦБ наибольший удельный вес имеют среднесрочные и долгосрочные облигации но по отдельным странам имеется значительный разброс показателей характеризующих место...
41560. Вторичные ценные бумаги 142.54 KB
  Привлекательные качества АDR для инвесторов состоят в: покупке ценных бумаг с более высоким уровнем доходности чем акции национальных компаний; минимизации рисков по сравнению с прямой покупкой иностранных акций; возможности выхода на рынок другой страны при отсутствии достаточных знаний иностранных фондовых рынков их особенностей и традиций налогообложения и т. Упрощенно торговлю в США акциями российского эмитента через АDR можно представить следующим образом. Американский инвестор пожелавший купить АDR делает заказ на покупку...
41561. СРОЧНЫЕ КОНТРАКТЫ 341.76 KB
  В последнем случае класс производных инструментов включает не только срочные контракты но и любые другие новые инструменты рынка такие как вторичные ценные бумаги в их потенциально бесконечном многообразии комбинации ценных бумаг со срочными контрактами и т.1 Основные различия между ценными бумагами и срочными контрактами как производными инструментами Признак Ценная бумага Срочный контракт как производный инструмент Вид капитала Представитель действительного капитала Фиктивный капитал Движимое имущество собственность Представитель...
41562. ВИДЫ ПРОФЕССИОНАЛЬНОЙ ДЕЯТЕЛЬНОСТИ НА РЫНКЕ ЦЕННЫХ БУМАГ 166 KB
  Третья группа участников рынка ценных бумаг представлена профессиональными участниками к которым согласно Федеральному закону â€œО рынке ценных бумаг†следует отнести юридических лиц в том числе и кредитные организации а также граждан физических лиц зарегистрированных в качестве предпринимателей и специализирующихся на оказании услуг всем участникам фондового рынка. Понятие профессионального участника рынка ценных бумаг в Российской Федерации по мере его развития и создания...