51359

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

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

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

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

Русский

2014-02-10

46.8 KB

39 чел.

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

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

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

Отчёт

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

Вывод

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


 

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

51388. Построить решение, включающее в себя три проекта, которые содержат: проект DLL(библиотеку классов), консольный проект и Windows-проект 205.17 KB
  Построить Решение включающее в себя три проекта которые содержат: проект DLLбиблиотеку классов консольный проект и Windowsпроект. Построим аналог класса Mth и поместим этот класс в проект DLLбиблиотеку классов что позволит повторно использовать его присоединяя при необходимости к различным проектам. Все три проекта будут находиться в одном Решении. Создание проектов: 1 Создание DLL проекта типа Библиотека классовClss Librry Запустить VS со стартовой страницы перейти к созданию проекта и в качестве типа проекта указать...
51391. Подсчитать количество точек, пробелов и символов «b» в потоке данных 17.77 KB
  Алгоритм Начало Обьявление переменных ch=0 pt=0 sp=0 bi=0 Вывод списка команд Getchr=EOF вывод подсказки на экран printf vvedide chislo n; while ch=getchr=EOF до тех пор пока ch не равно EOF выполнять цикл ifch.
51393. Прямые измерения активного электрического сопротивления.(Измерения омметром, мультиметром и мостом) 1.4 MB
  Цель работы Получение навыков измерения активного электрического сопротивления далее сопротивления. Ознакомление с методами измерения активного сопротивления. Сведения необходимые для выполнения работы Перед выполнением работы повторите вопросы обработки и представления результата прямых и косвенных измерений и ознакомьтесь со следующими вопросами: Измерение электрического сопротивления постоянному току методами непосредственной оценки и сравнения с мерой.
51394. Измерение постоянного напряжения методом компенсации 978 KB
  Измерение постоянного напряжения методом компенсации Получение сведений о погрешностях измерения напряжения компенсационным методом. Устройство принцип действия и основные характеристики делителя постоянного напряжения. Компенсаторы потенциометры постоянного тока предназначены для измерения методом сравнения с мерой ЭДС напряжения и величин функционально с ними связанных.