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

Вывод

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


 

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

85036. Формирование взаимоотношений со сверстниками противоположного пола 30.74 KB
  Формирование взаимоотношений со сверстниками противоположного пола Цель урока. Сформировать убеждение что каждый человек должен рассматривать вопросы взаимоотношений с лицами противоположного пола с позиций норм нравственности и обеспечения сохранения своего здоровья и здоровья окружающих. Обратить внимание учащихся на особое место которое начинают занимать в их жизни взаимоотношения со сверстниками противоположного пола. Интерес к вопросам пола и первая влюбленность у многих возникают очень рано часто задолго до наступления полового...
85037. Взаимоотношения подростка и общества. Правовая ответственность несовершеннолетних 30.94 KB
  Проанализировать основные причины правонарушений совершаемых в подростковом возрасте; разобрать с учащимися отдельные положения Уголовного кодекса РФ предусматривающие уголовную ответственность несовершеннолетних. Основные причины правонарушений совершаемых подростками. Эти знания позволят каждому избежать правонарушений которые совершаются случайно за компанию и не стать преступником. Изучение совершенных подростками правонарушений показывает что в большинстве случаев эти поступки явились следствием притязаний молодых людей на...
85038. Здоровый образ жизни и безопасность жизнедеятельности 31.03 KB
  Сформировать у учащихся целостное представление о том что здоровый образ жизни залог безопасности человека в повседневной жизни и в различных опасных и чрезвычайных ситуациях. Общие понятия о культуре безопасности жизнедеятельности. Уровень культуры безопасности жизнедеятельности как критерий определения уровня здоровья и безопасности. Подчеркнуть что общая культура населения нашей страны в области безопасности во многом не соответствует реальным условиям жизнедеятельности она отстает от стремительных темпов развития цивилизации.
85039. Первая медицинская помощь пострадавшим и ее значение 31.59 KB
  Познакомить учащихся с правилами оказания первой помощи и средствами которые могут быть использованы при этом. Сформировать у них убеждение в том что каждый человек должен владеть приемами в оказании первой медицинской помощи пострадавшим. Общие правила оказания первой медицинской помощи. Средства используемые при оказании первой медицинской помощи.
85040. Первая медицинская помощь при отравлениях аварийно химически опасными веществами (АХОВ) 25.42 KB
  Первая медицинская помощь при отравлениях аварийно химически опасными веществами АХОВ Цель урока. Познакомить учащихся с правилами оказания первой медицинской помощи при отравлении наиболее распространенными аварийно химически опасными веществами аммиаком и хлором. Если такой возможности нет повторить с учащимися какие химически опасные вещества относятся к АХОВ напомнить что наиболее распространенными АХОВ являются аммиак и хлор. Контрольные вопросы Какие вещества называются аварийно химически опасными Каковы признаки отравления...
85041. Первая медицинская помощь при травмах. Первая медицинская помощь при утоплении 27.1 KB
  Познакомить учащихся с правилами оказания первой медицинской помощи при переломах вывихах растяжениях и разрывах связок. Познакомить учащихся с правилами оказания первой медицинской помощи при утоплении. Объяснить правила оказания первой медицинской помощи при травмах: при переломах; при вывихах растяжениях и разрывах связок; при растяжении мышц и сухожилий. При этом подчеркнуть что объем мероприятий первой медицинской помощи зависит от тяжести состояния пострадавшего.
85042. Пожары в жилых и общественных зданиях, их причины и последствия 31.81 KB
  Дать учащимся представление о значении огня в жизнедеятельности человека о причинах возникновения пожаров и их возможных последствиях для безопасности человека. Изучаемые вопросы Значение огня в жизнедеятельности человека. Используя материалы курса истории обсудить с учащимися значение огня в жизнедеятельности человека на разных этапах развития общества. Благодаря использованию огня человек становился все меньше зависимым от природных условий существования.
85043. Профилактика пожаров в повседневной жизни и организация защиты населения. Права, обязанности и ответственность граждан в области пожарной безопасности 31.93 KB
  Права обязанности и ответственность граждан в области пожарной безопасности. Разъяснить учащимся значение профилактики пожаров; обсудить основные направления деятельности человека по обеспечению пожарной безопасности. Сформировать у учащихся чувство ответственного отношения к правилам пожарной безопасности к рекомендациям специалистов по правилам поведения для обеспечения личной безопасности во время пожара. Основные направления деятельности человека по обеспечению пожарной безопасности.
85044. Безопасное поведение на водоемах в различных условиях 33.55 KB
  Оказание помощи терпящим бедствие на воде. Закрепить знания правил безопасного поведения на воде во время купания во время водных походов в условиях аварийной ситуации возникшей во время водного пожара. Познакомить учащихся с основными способами оказания помощи терпящим бедствие на воде. Изучаемые вопросы Значение воды в жизнедеятельности человека безопасность на воде.