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

Вывод

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


 

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

66680. Жизнь и научная деятельность Натальи Ивановны Базилевич 136.45 KB
  Существует такое неофициальное, но очень почетное в профессиональных кругах звание - рыцарь науки. Его удостаиваются те, кто беззаветно служил избранному делу, посвятив свою жизнь исследованиям и добившиеся в этом деле выдающихся результатов. Бесспорно, таким рыцарем науки была Наталья Ивановна Базилевич.
66681. РАБОТА СО СПИСКАМИ ИЛИ БД 3.74 MB
  Excel может работать как с простыми и небольшими по размерам, так и с более сложными и занимающими большой объём дискового пространства базами данных (БД). В Excel БД это просто список, состоящий из одного или более столбцов.
66682. НАУКА І ТЕХНІКА ХУІІ-ХІХ СТОЛІТЬ 41.3 KB
  Розвиток матеріального виробництва стає тісно пов'язаний з досягненнями науки і використанням її результатів у практичному житті людей. На форми останніх впливали і особливості мануфактурного виробництва і наукова революція і зміни що виявлялись у самій техніці.
66683. Василий Васильевич Докучаев 123 KB
  Василий Васильевич родился 1 марта 1846 года и прожил 57 плодотворнейших лет, став родоначальником нашей науки, человеком, чье имя, пожалуй, в первую очередь приходит в голову, когда говоришь о почве и о почвоведении, ну да об этом несколько позже.
66684. Векторная графика 278.91 KB
  В зависимости от видов компьютерной графики под этим термином понимаются как и пиксели или спрайты в растровой графике так и векторные объекты такие как круг квадрат линия кривая и т. Для дальнейшего рассмотрения проблемы постройки объектов с помощью векторной графики...
66685. Времена года как тема искусства и музыки 87.63 KB
  Четыре времени года венецианского композитора Антонио Вивальди первые четыре из двенадцати скрипичных концертов его восьмого опуса одни из самых знаменитых его произведений и одни из известнейших музыкальных произведений в стиле барокко.
66686. Виды сетевых атак 206 KB
  Типичными угрозами в среде Интернета являются: Сбой в работе одной из компонент сети. Сбой изза ошибок при проектировании или ошибок оборудования или программ может привести к отказу в обслуживании или компрометации безопасности изза неправильного функционирования одной из компонент сети.
66688. Компьютерный вирус 64 KB
  Однако большинство специалистов сходятся на мысли что компьютерные вирусы как таковые впервые появились в 1986 году хотя исторически возникновение вирусов тесно связано с идеей создания самовоспроизводящихся программ. Одним из пионеров среди компьютерных вирусов считается вирус...