51359

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

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

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

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

Русский

2014-02-10

46.8 KB

36 чел.

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

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

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

Отчёт

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

Вывод

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


 

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

34767. Научное познание и его специфические признаки. Методы научного познания 46 KB
  Методы научного познания. Так в зависимости от роли и места в процессе научного познания можно выделить методы формальные и содержательные эмпирические и теоретические методы исследования и изложения и т. Выделяют также качественные и количественные методы методы непосредственного и опосредованного познания оригинальные и производные и т. В этом плане все методы научного познания по степени общности и сфере действия могут быть разделены на пять основных групп: Философские методы среди которых наиболее древними являются диалектический и...
34768. Здоровье как ценность, философия здоровья человека 28.5 KB
  В большинстве стран был принят целый ряд юридических документов государственных масштабов по экологическому контролю за деятельностью промышленных и других предприятий по охране окружающей среды и здоровья человека. сформировался культ здоровья и здорового образа жизни как поощряемого и престижного способа существования. Культ здоровья и здорового образа жизни является жизненно важным делом лишь для очень небольшого количества людей в основном энтузиастов.
34769. Проблема жизни и смерти в духовном опыте человека. Философия о смысле жизни, смерти и бессмертии. Право на смерть 67.5 KB
  Философия о смысле жизни смерти и бессмертии. В чем смысл жизни Постановка проблемы В жизни каждого нормального человека рано или поздно наступит момент когда он задается вопросом о конечности своего индивидуального существования. Наличием такого знания в духовном опыте человека в значительной степени и объясняется острота с которой перед ним встает вопрос о смысле и цели жизни.
34770. Понятие истины. Объективность истины. Принципы: корреспонденции, когеренции и прагматизма. Гносеологическая, логическая и онтологическая формы истины 42.5 KB
  Объективность истины. Гносеологическая логическая и онтологическая формы истины. Абсолютные истины складываются на основе относительных.
34771. Истина как процесс. Диалектика абсолютной и относительной истины 39.5 KB
  Диалектика абсолютной и относительной истины. Конвенциональная концепция истины считает истинное знание или его логические основания результатом конвенции соглашения. Разброс мнений достаточно велик однако наибольшим авторитетом и самым широким распространением пользовалась и пользуется классическая концепция истины берущая свое начало от Аристотеля и сводящаяся к корреспонденции соответствию знания объекту. Классическая концепция истины хорошо согласуется с исходным гносеологическим тезисом диалектикоматериалистической философии о том...
34772. Истина, ложь, заблуждение. Конкретность истины. Ложь «во спасение». Проблема врачебных ошибок 41.5 KB
  Конкретность истины.В философии понятие истины совпадает с комплексом базовых концепций позволяющих различить достоверное и недостоверное знание по степени его принципиальной возможности согласовываться с действительностью по его самостоятельной противоречивости непротиворечивости а также в рамках разведения полезности и бесполезности эффективности и неэффективности. категория истины обладает двойственной характеристикой. уклонение от истины принимаемое нами за истинное суждение; основывается всегда на неверности по существу самих...
34773. Практика как критерий истины. Абсолютность и относительность практики как критерия истины 43 KB
  Абсолютность и относительность практики как критерия истины К сожалению фактически все попытки решить проблему критерия истины не увенчались успехом. следует выделить две особенности практики как критерия истины: 1. Это достигается в процессе материального воплощения мышления в человеческой практики. С его помощью невозможно доказать немедленно непосредственно истинность или ложность тех или иных научных теорий которые выходят за пределы возможностей самой практики обусловленной историческим отрезком времени.
34774. Практика как специфический способ отношения человека к миру. Формы практической деятельности. Специфика медицинской практики 34 KB
  Формы практической деятельности. Интегративные функции практики по отношению к другим формам жизнедеятельности В сфере реального отношения людей к миру к природе к обществу к другим людям формируются исходные стимулы развитии всех форм человеческой культуры. Создаваемые в культуре и в материальном производстве и в регуляции отношений между людьми в обществе и наконец в сфере науки искусства философии способы деятельности возникают но сути своей как ответ па определенные проблемы и задачи связанные с воспроизводством...
34775. Глобальные проблемы современности. Философский анализ и решение. Альтернативы будущего 42.5 KB
  Остановим внимание на названных и в первую очередь на экологической проблеме в силу тех причин что все происходящее на планете Земля с участием человека или без него протекает и в природе. Геосфера поверхность Земли как необитаемая так и пригодная для жизни человека. Ноосфера ноо разум область разумной деятельности человека онрделяемая в конечном счете уровнем человеческого интеллекта и объемом перерабатываемой его мозгом информации. С целью их разгадки все сферы взаимоотношений природы и человека были условно разделены на...