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

Вывод

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


 

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

34336. Области применения серной кислоты и технико-экономические показатели ее производства 32.5 KB
  Области применения серной кислоты и техникоэкономические показатели ее производства. Производство серной кислоты одной из самых сильных и дешевых кислот имеет важное народнохозяйственное значение обусловленное ее широким применением в различных отраслях промышленности. Контактным способом получают около 90 от общего объема производства кислоты так как при этом обеспечивается высокая концентрация и чистота продукта. В качестве сырья для производства серной кислоты применяются элементарная сера и серный колчедан; кроме того широко...
34337. Производство аммиака и азотной кислоты 35 KB
  Производство аммиака и азотной кислоты В соответствии с принципом ЛеШателье при повышении давления и уменьшении температуры равновесие этой реакции смещается в сторону образования аммиака. Основным агрегатом установки для производства аммиака служит колонна синтеза Производство азотной кислоты: Азотная кислота одна из важнейших минеральных кислот. Такая смесь кипит без изменения концентрации кислоты. Современное производство азотной кислоты основано на процессах окисления аммиака и последующей переработке оксидов азота.
34338. Пр-во азотных мин.удобрений и их классификация 30.5 KB
  Прво азотных мин. Большинство азотных удобрений получают нейтрализацией кислот щёлочами.глубину потери 225; поглощается по типу обменной адсорбции Карбамид мочевина 2NH3CO2=NH2COONH4= =CONH22H2O 2000C; 20 МПа 466 Лучшее удобрение для внекорневой подкормки растений Аммиачная селитра NH3HNO3=NH4NO3Q 3435 Закисляет почву гигроскопична слеживается взрывоопасна Сульфат аммония 2NH3H2SO4=NH42SO4Q 20521 Эффективен под орошаемые культуры рис хлопчатник Среди азотных удобрений самая большая массовая доля азота в...
34339. Фосфорная кислота 24 KB
  Н3РО4 безводная фосф кислота представляет собой бесцветное вещество плавящиеся при температуре 42. Однако на практике имеют дело с жидкой Н3РО4 что объясняется склонностью Н3РО4 к переохлаждению при темп 121С При небольшом переохлаждении она представляет собой густую сиропоподобную жидкость плотностью 188 г см^3 При нагревании водные растворы ортофосф кислоты теряют воду образуя пирафосфорная а затем метофосф кислота. Безводная ортофосф кислота очень агрессивна.
34340. Особенности производства калийных удобрений 29 KB
  Выделение хлористого калия из сильвинитовых руд может быть основано на различии механических физических или химических свойств составляющих компонентов. Переработка сильвинитов для получения хлористого калия по галургическому методу основана на физикохимических особенностях системы NCl КС1 Н2О. Эта особенность системы NCl КС1 Н2О используется для производства хлористого калия из сильвинитов по галургическому методу. Рационально построенная схема производства хлористого калия из сильвинита должна учитывать следующие технологические...
34341. Фосфорные минеральные удобрения 24 KB
  Фосфорные минеральные удобрения Фосф. К фосфорным удобрениям относятся простой и двойной суперфосфат принадлежащие к классу водорастворимых удобрений и комплексные удобрения. Фосфор вносят в почву и с помощью сложного удобрения аммофоса. Фосфорные удобрения получают как физическими так и химическими методами.
34342. Технология производства и экономическая эффективность выпуска и использования пластмасс 30.5 KB
  Технология производства и экономическая эффективность выпуска и использования пластмасс. Изделия из пластмасс наиболее часто получают методами горячего прессования литья под давлением экструзии выдувания обработки резанием. Прессование применяется главным образом для переработки термореактивных пластмасс. термореактивная смола переводится в плавкое состояние при котором и происходит вторая стадия процесса формование; затем происходит реакция поликонденсации и пластмасса отверждается становясь неплавкой и нерастворимой.
34343. Сырьевые материалы и основы производства резины 28 KB
  Резину изготавливают с помощью вулканизации. В результате вулканизации каучук превращается в прочную эластичную упругую массу резину. В результате вулканизации молекулы каучука сливаются между собой дисульфидными мостиками в одну трехмерную макромолекулу. Большую роль играют так называемые ускорители вулканизации органические соединения содержащие серу или азот меркаптобензтиазол дифенилгуанидин и др.
34344. Основные свойства и назначения природных и искусственных строительных материалов 21 KB
  Основные свойства и назначения природных и искусственных строительных материалов. Основные свойства строительных материалов можно разделить на несколько групп. К 1ой группе относятся физические свойства материалов: плотность и пористость. Ко 2й свойства характеризующие устойчивость материала к воздействию воды и низких температур: водопоглощение влажность влагоотдача гигроскопичность водопроницаемость водо морозостойкость.