51359

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

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

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

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

Русский

2014-02-10

46.8 KB

35 чел.

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

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

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

Отчёт

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

Вывод

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


 

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

48072. Наукова комунікація як складова фахової діяльності. Українська термінологія у професійному спілкуванні 323 KB
  Особливості наукового тексту і професійного наукового викладу думки. Науковий стиль української мови має свої особливості. Загальні ознаки наукового стилю поняттєвість. Термін та його ознаки. термінологія як система...
48073. Матеріалознавство та технологія матеріалів 1.4 MB
  Кристалізація металів. Механічні властивості металів та методи їх визначення Мета: Ознайомити студентів з основними поняттями конструкційних матеріалів: будовою та властивостями металів роллю вітчизняних та зарубіжних вчених у розвитку матеріалознавства з основними механічними властивостями металів і сплавів та методами їх випробування. Кристалічна будова металів будова і властивості реальних кристалів. Плавлення металів.
48074. Народознавство 1.1 MB
  Релігія в житті українського народу. Звичаї та обряди українського народу. Ретромандрівка в глибину століть допоможе зрозуміти духовність і менталітет нашого народу віковічно творений як образне бачення українською людиною світу землі та життя на ній. Українське народознавство як навчальний предмет Відродження України неможливе без пробудження національної свідомості українського народу насамперед молоді.
48075. Электротехника 5.26 MB
  Определение связи между токами напряжениями параметрами заданной цепи и теми величинами которые определяют работу рассматриваемой установки например: к. Принцип работы и общие свойства важнейших электротехнических устройств и элементов электрической цепи. Задачи синтеза заключаются в разработке методов такого выбора схемы соединения элементов цепи и такого подбора параметров этих элементов чтобы полученная цепь обладала заданными характеристиками. По наличию данных элементов различают соответственно активные и пассивные цепи.
48076. НЕГЛАСНІ СЛІДЧІ (РОЗШУКОВІ) ДІЇ. КУРС ЛЕКЦІЙ 722 KB
  Підстави проведення негласних слідчих розшукових дій. Засоби що використовуються під час проведення негласних розшукових дій Лекція 3. Негласні слідчі розшукові дії законодавець визначив як різновид слідчих розшукових дій відомості про факт та методи проведення яких не підлягають розголошенню за винятком випадків передбачених Кримінальним процесуальним кодексом України ч. Подано базові нетаємні положення що стосуються організації та тактики проведення негласних слідчих розшукових дій вивчення яких відповідає вимогам підготовки...
48077. ГРОШІ ТА КРЕДИТ. КОНСПЕКТ ЛЕКЦІЙ 971 KB
  Сутність і функції грошей. Походження грошей. Види грошей. Функції грошей. Характеристика і структура грошового обороту
48078. Культура наукової мови 542 KB
  Наукова мовна культура основа професійної діяльності дослідника Наукова мова як комунікативний феномен Поняття культура наукової мови.Етапи становлення й дослідження наукової мови Роль науки в житті суспільства за останні десятиліття надзвичайно зросла. Дається взнаки і домінування в міжнародному науковому просторі англійської мови як глобальної мови науки.
48079. Облікова політика підприємства 2.96 MB
  Якщо такі умови визначити неможливо амортизація нараховується за прямолінійним методом ПсБО 9 Запаси Одиниця обліку запасів найменування; однорідна група вид Методи оцінки вибуття запасів ідентифікованої собівартості відповідної одиниці запасів; середньозваженої собівартості; собівартості перших за часом надходження запасів ФІФО; нормативних витрат; ціни продажу Застосовується підприємствами роздрібної торгівлі та громадського харчування Метод обліку транспортнозаготівельних витрат шляхом прямого...
48080. Общая биология. Конспект лекций 728.5 KB
  Методы изучения наследственности человека Генеалогический метод ЛЕКЦИЯ Воздействие человека на биосферу Круглые черви паразиты человека Аскарида ЛЕКЦИЯ Клещи обитатели жилища человека