51359

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

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

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

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

Русский

2014-02-10

46.8 KB

37 чел.

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

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

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

Отчёт

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

Вывод

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


 

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

31153. Что такое стереотип 20 KB
  Стереотип- устойчивое представление о каких-л. объектах, свойствах той или иной соц. группы. (пример: свои – чужие. Чужие – любые другие, не входящие в твою группу)
31154. Каковы свойства стереотипа 20 KB
  Пример: свои чужие. Чужие любые другие не входящие в твою группу Свойства С: Стереотипы неиндивидуальны это групповое явление.
31155. Что такое слухи и как они связаны с феноменом массы 21.5 KB
  Свойства слухов: 1Высокая степень обобщенности; 2привязка ко времени и среде своего возникновения. 3наличие свежей новости; 4неофициальность; 5Слух сохраняет свою связь со всеми перечисленными типами соц сообщений; 6однократная воспроизводимость Второй раз одному и тому же лицу слух не пересказывается; 7подвергается дальнейшей трансляции. Слушающий впоследствии становясь говорящим передает этот слух новому слушающему.
31156. Каковы информационные предпосылки распространения слухов 23 KB
  Наиболее активными распространителями слухов явл люди формальная деятть кот играет в организации далеко не первую роль но кот хотят показать свою значимость и влияние.Чувство солидарности кот выражается в стремлении помочь коллегам друзьям знакомым предупредить их и дать возможность самим или совместно подготовиться к встрече с неприятным событием.Побуждение других к поддержке себя и своей позиции подталкивание к групповым действиям кот распространитель слуха не решается совершить сам в одиночку.
31157. Каковы психологические предпосылки распространения слухов 21.5 KB
  Чувство солидарности человека распространяющего слух.Слух как стремление человека найти союзников.Личная неприязнь злоба на определенного человека. Такой мотив побуждает человека распространять негативные слухи о своем недруге .
31158. Каковы разновидности слухов? Приведите примеры различных видов 23 KB
  Такие слухи не создаются целенаправленно возникают спонтанно.По эмоциональной характеристике: 1Слухжелание такой слух обычно выдает желаемое за действительное. Этот слух люди сами того не осознавая ждут и поэтому с легкостью ему верят.
31159. Что такое внушение 24 KB
  Непосредств словесного воздействие эмоц насыщенным, повелительным тоном. Словесная формула: прямая речь, обращенная к объекту воздействия. В ней выражается требуемое поведение либо состояние, кот должно наступать сразу же после высказанных слов.
31160. Расскажите о приемах внушения 24.5 KB
  вызвать через преподносимый образ понятие лозунг идею ассоциацию с чемлибо или кемлибо имеющим в глазах объекта бесспорный престиж ценность чтобы сделать содержание воздействия приемлемым. Заключается в цитировании высказываний личности кот уважает или наоборот ненавидит объект воздействия. Этот способ заключается в побуждении объекта воздействия принять содержащуюся в инфе идею суждение оценку мнение на том основании что якобы большинство представителей данной соц группы или воинского подразделения разделяют ее.
31161. Что такое внушаемость и каковы условия ее повышения 22.5 KB
  Условия повышающие внушсть: 1пребывание в большой группе людей. 3псих состояние внушаемого внуш легче осущ когда индивид наход в расслабленном состоянии или в сост психич возбуждения. 4Воздействие на органы чувств: Внушающие цвета: красный приводит к возбуждению фиол и синий подавляет.