Программа для исследования помехоустойчивости линейного аддитивного блочного кода заданного вида синдромным методом

Программа для исследования помехоустойчивости линейного аддитивного блочного кода заданного вида синдромным методом

 

Студент группы 1B0

Крючков А.В.

Руководитель

Доцент кафедры СРС

В.А. Кологривов

 

 

Реферат

Пояснительная записка содержит: листов ____, источников 4, приложений 1, рисунков 1.

ИЗБЫТОЧНОСТЬ, ПОМЕХОУСТОЙЧИВОСТЬ, ЛИНЕЙНЫЙ КОД, БИНАРНАЯ МАТРИЦА, ПОРОЖДАЮЩАЯ МАТРИЦА, ПРОВЕРОЧНАЯ МАТРИЦА, СИНДРОМ ОШИБКИ, КОДИРОВАНИЕ, ДЕКОДИРОВАНИЕ, ВЕКТОР ОШИБОК, СУММИРОВАНИЕ ПО МОДУЛЮ 2, SCILAB

Работа посвящена закреплению навыков работы на персональном компьютере в средах Windows, SciLab и принципам аддитивного алгебраического кодирования и декодирования. Изучению основных элементов теории построения помехоустойчивости линейных блочных аддитивных алгебраических кодов и реализации одного из алгоритмов кодирования и декодирования.

Работа выполнена в среде SciLab. Результатом проделанной работы является реализация программного кода для исследования помехоустойчивости блочного аддитивного кода заданного вида.

Пояснительная записка выполнена в текстовом редакторе Microsoft Word 2010.

Содержание

1. Введение

2. Общие сведения о системе scilab

2.1 Возможности SciLab

3. Основы помехоустойчивого кодирования

3.1 Основные положения

3.2 Основные принципы

3.3 Линейные блочные коды

3.4 Порождающая и проверочная матрица

3.4.1 Порождающая матрица

3.4.2 Проверочная матрица

4. Синдромный метод

4.1 Синдром и обнаружение ошибки линейным блочным кодом

4.2 Синдромное декодирование линейных блочных кодов

5. Описание программы

5.1 Главная программа Kursovaya2. sci

5.2 Функция umn_bin_mat

6. Интерпретация результатов

7. Заключение

Список использованных источников

Приложения

Введение

 

Информация - это знания, это деньги, это возможность управления людьми, это власть. Невозможно переоценить роль и значение информации в современном обществе. Реализовать же заложенные в информации возможности можно обеспечив ее правильное использование или, говоря образно, движение. Для обеспечения этого “движения" человечеством созданы многообразные средства, регламентирующие и обеспечивающие возможность связи внутри общества. Виды этой связи чрезвычайно обширны, но, касаясь технической стороны вопроса и рассматривая связь как передачу информации на расстояние.

Рассмотрим принципы защиты от ошибок информации возникающих при ее передачи по каналам связи одним из известных способом.

Блоковые коды и методы их декодирования [1]:

·   Коды Хемминга

·   Коды Рида - Соломона

·   Мажоритарно декодируемые коды

·   Синдромный метод

·   Маркерный метод

В работе предлагается подробно рассмотреть принципы построения линейных блочных аддитивных алгебраических кодов и принципы их декодирования маркерным методом.

блочный код синдромный метод

Общие сведения о системе scilab

 

SciLab - пакет прикладных математических программ, предоставляющий мощное открытое окружение для инженерных (технических) и научных расчётов [2].

 

Возможности SciLab

 

Возможности SciLab содержит множество математических функций, и есть возможность добавления новых, написанных на различных языках (C, C++, Fortran …).

В системе доступно множество инструментов:

·   2D и 3D графики, анимация

·   Линейная алгебра, разреженные матрицы

·   Полиномиальные и рациональные функции

·   Интерполяция, аппроксимация

·   Симуляция: решение ОДУ и ДУ

·   Дифференциальные и не дифференциальные оптимизации

·   Обработка сигналов

·   Параллельная работа

·   Статистика

·   Работа с КА

SciLab имеет схожий с MATLAB язык программирования. В состав пакета входит утилита, позволяющая конвертировать документы Matlab в SciLab.

SciLab позволяет работать с элементарными и большим числом специальных функций (Бесселя, Неймана, интегральные функции). Также имеет мощные средства работы с матрицами, полиномами (в том числе и символьно), производить численные вычисления (например, численное интегрирование) и решение задач линейной алгебры, оптимизации и симуляции, мощные статистические функции, а также средство для построения и работы с графиками.

Основные положения

 

Задача кодера источника - представить подлежащие передаче данные в максимально компактной и, по возможности, неискаженной форме.

При передаче информации по каналу связи с помехами в принятых данных могут возникать ошибки. При большом числе ошибок полученной информацией пользоваться нельзя.

Возможность использования кодирования для уменьшения числа ошибок в канале была теоретически показана К. Шенноном в 1948 году в его работе “Математическая теория связи”. В ней было сделано утверждение, что если скорость создания источником сообщений (производительность источника) не превосходит некоторой величины, называемой пропускной способностью канала, то при соответствующем кодировании и декодировании можно свести вероятность ошибки в канале к нулю. [3].

Вскоре, однако, стало ясно. Что фактическое ограничение на скорость передачи устанавливаются не пропускной способностью канала, а сложностью схем кодирования и декодирования. Поэтому усилия разработчиков и исследователей в последние десятилетия были направлены на поиски эффективных кодов. Создание практически реализуемых схем кодирования и декодирования, которые по своим характеристикам приближались бы к предсказанным теоретически.

Основные принципы

 

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

Первое - использование избыточности. Закодированные последовательности всегда содержат дополнительные, или избыточные, символы.

Количество символов в кодовой последовательности y всегда больше, чем необходимо для однозначного представления любого сообщения  из алфавита.

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

Существует два больших класса корректирующих кодов - блочные и сверточные. Определяющее различие между этими кодами состоит в отсутствии и наличии памяти кодера.

Кодер для блочных кодов делит непрерывную информационную последовательность x на блоки - сообщений длиной k символов.

Кодер канала преобразует блоки - сообщений x в более длинные двоичные последовательности y, состоящих из n символов и называемые кодовыми словами. Символы (n - k),добавляемые к каждому блоку - сообщению кодером, называются избыточными. Они не несут никакой дополнительной информации, и их функция состоит в обеспечении возможности обнаруживать (или исправлять) ошибки, возникающие в процессе передачи [3].

Для оценки потенциальных способностей кода можно воспользоваться пределом Хэмминга

 (3.1)

 

где  - число сочетаний из n по j.

Заметим, что неравенство определяет минимальное необходимое число избыточных бит (нижнюю границу) для исправления всех комбинаций ошибок вплоть до t - битовых. Иначе можно сказать, что неравенство определяет верхнюю границу возможностей, когда в коррекции t - битовых ошибок как функцию числа бит чётности n - k.

Как мы ранее показали, k - разрядным двоичным словом можно представить  возможных значений из алфавита источника. Им соответствует  кодовых слов на выходе кодера.

Такое множество  кодовых слов называется блочным кодом.

Термин “ без памяти ” означает, что каждый блок из n символов зависит только от соответствующего информационного блока из k символов и не зависит от других блоков.

Линейные блочные коды

 

Для блочного кода с кодовыми словами длиной в n символов, если он только не обладает специальной структурой, аппарат кодирования и декодирования является очень сложным. Поэтому ограничим свое рассмотрение лишь кодами, которые могут быть реализованы на практике

Одним из условий реализуемости блочных кодов является условие линейности.

Кодовые символы в аддитивных блочных кодах в алгебраическом смысле образуют линейную аддитивную группу относительно операции суммированию по модулю 2.

Работая с двоичными кодами, мы постоянно будем сталкиваться с элементами двоичной арифметики, поэтому определим основные понятия.

Возьмем простейшее поле, состоящее из двух элементов - нуля " 0 " и единицы " 1 ". Определим для него операции сложения и умножения по модулю 2:

 

 

Желательным качеством линейных блочных кодов является систематичность.

Аддитивный код имеет вид изображённый на рисунке 3.1, то есть содержит неизменную информационною часть длиной k символов и избыточную длиной n - k символов.

 

Рисунок 3.1

 

Блочный код, обладающий свойством линейности и систематичности, называется линейным блочным систематичным кодом ( n, k ) - кодом.

Порождающая матрица

Взаимосвязь входных и выходных состояний кодера, удобно отобразить системой линейных алгебраических уравнений с использованием операции суммирования по модулю 2

 

, (3.2)

 

где  - биты входного информационного символа;

 - биты выходного символа кодера.

Матрицу коэффициентов системы определяющих уравнений кодера обозначим как .

Транспонированная матрица коэффициентов системы известна как порождающая или генерирующая матрица аддитивного алгебраического кодера [4].

 

 (3.3)

 

где  - единичный блок размерностью k × k;

 - проверочный блок.

Линейный блочный систематический (n, k) - код полностью определяется матрицей G размером k × n с двоичными матричными элементами. При этом каждое кодовое слово является линейной комбинацией строк матрицы G, а каждая линейная комбинация строк G - кодовым словом

Алгоритм кодирования с использованием порождающей или генерирующей матрицы запишется

 ( 3.4)

 

где x - входной (информационный) символ вектор - строка размерностью k;

G - порождающая матрица размерностью k × n;

y - выходной (кодовый) символ вектор - строка размерностью n.

Здесь при умножении входного вектора x на порождающую матрицу G также используется операция суммирования по модулю 2.

Проверочная матрица

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

 

, (3.5)

 

где  - проверочный блок размерностью (n - k) × k;

 - единичный блок размерностью (n - k) × (n - k).

Ортогональность порождающей и проверочной матриц определяется соотношением

 ( 3.6)

Синдромный метод

 

Описание программы

 

Интерпретация результатов

 

Пусть даны

 

, ,

 

Далее с помощью функции по формуле (3.4) получаем массив кодовых-символов

 

.

 

После чего находим массив вектор-строк синдромов ошибок по формуле (4.1) для случая без ошибочной передачи

 

.

 

Для случая ошибок в первых битах, тогда синдром ошибок примет вид

 

.

 

Для случая ошибок во вторых битах, тогда синдром ошибки примет вид

 

.

 

Для случая ошибок в третьих битах, тогда синдром ошибок примет вид

 

.

 

Сформируем матрицу однократных ошибок с 1-го по 7-ые биты и найдем синдром векторов ошибок

 

.

Заключение

 

В результате проделанной работе были изучены основные возможности системы SciLab. Рассмотрен синдромный метод помехоустойчивого кодирования. Приведённый пример подтверждает работоспособность программы. Также получены дополнительные знания для работы с текстовым редактором Microsoft Word и изучены вузовские стандарты по оформлению курсовой работы. Система научных и инженерных расчетов SciLab может использоваться для различных видов научной и учебной деятельности.

Приложения

 

Приложение А

Листинг главной программы для исследования помехоустойчивости линейного аддитивного блочного кода заданного вида синдромным методом

// Курсовая работа Крючкова А.В. студента 1 курса

// ТУСУРа РТФ кафедра СРС весенний семестр 2011г

// Программа разработана в среде SciLab-5.3.0

// Программа для исследования помехоустойчивости линейного аддитивного

// блочного кода заданного вида синдромным методом

// Рассмотрим код вида (7,3)

// Имя файла - Kursovaya2. sci

clc; clear; format ('v',25); mode (0);

function c = umn _ bin _ mat (a, b);

// Умножения бинарных матриц по модулю2+

// Входные данные:

// a,b - сопряжённые по размерностям бинарные матрицы

// Выходные данные:

// с-бинарная матрица, полученная путём умножения матриц a,b по модулю 2+

[n,k1] =size (a);

[k2,m] =size (b);=zeros (n,m);i=1: n;j=1: m; k=1: k1;

// Нахождение значение (i; j) элемента матрицы "c"

// при помощи операции сложения по модулю 2+(i,j) =bool2s (~isequal (c (i,j), (a (i,k) *b (k,j))));

end;;;

endfunction;

printf ('\n Программа для исследования помехоустойчивости линейного аддитивного блочного кода');('\n заданного вида синдромным методом\n Рассмотрим код вида (7,3) \n\n');(' Массив входных символов кодера \n');= [0,0,1;

0,1,0;

,1,1;

,0,0;

,0,1;

,1,0;

,1,1]

printf ('\n Матрица коэффицентов системы определяющих уравнений кодера \n');= [1,0,0;

0,1,0;

,0,1;

,1,1;

,0,1;

,1,0;

,1,1]

printf ('\n Генерирующая матрица кодера \n');=Gt'; // Транспонируем матрицу Gt('\n Кодирование. \n Массив кодовых символов* (на выходе кодера) \n');

y=umn_bin_mat (x,G);

y('\n*-где каждому входному символу соответствует один единственный кодовый символ');('\n\n Проверочная матрица H (из условия её ортогональности порождающей матрице G) \n');= [0,1,1,1;

1,0,1,1;

,1,0,1;

,0,0,0;

,1,0,0;

,0,1,0;

,0,0,1]

printf ('\n Декодирование. \n На вход декодера поступают принятые кодовые символы \n');('\n на выходе декодера имеем массив вектор-строк синдромов ошибок \n');(' Случай без ошибочной передачи \n');

s=umn_bin_mat (y,Ht)('\n Пусть с ошибкой приняты первые биты кодовых символов \n');= [1,0,1,1,1,0,1;

1,1,0,1,0,1,1;

,1,1,0,1,1,0;

,0,0,0,1,1,1;

,0,1,1,0,1,0;

,1,0,1,1,0,0;

,1,1,0,0,0,1]

printf ('\n Тогда синдром ошибки будит иметь вид \n')

s1=umn_bin_mat (r1,Ht)

printf ('\n Пусть с ошибкой приняты вторые биты кодовых символов \n');=      [0,1,1,1,1,0,1;

0,0,0,1,0,1,1;

,0,1,0,1,1,0;

,1,0,0,1,1,1;

,1,1,1,0,1,0;

,0,0,1,1,0,0;

,0,1,0,0,0,1]

printf ('\n Тогда синдром ошибки будит иметь вид \n')

s2=umn_bin_mat (r2,Ht)

printf ('\n Пусть с ошибкой приняты третьи биты кодовых символов \n');=      [0,0,0,1,1,0,1;

0,1,1,1,0,1,1;

,1,0,0,1,1,0;

,0,1,0,1,1,1;

,0,0,1,0,1,0;

,1,1,1,1,0,0;

,1,0,0,0,0,1]

printf ('\n Тогда синдром ошибки будит иметь вид \n')

s3=umn_bin_mat (r3,Ht)

printf ('\n Сформируем матрицу однократных ошибок с 1-го по 7-ые биты \n');(' и найдём синдромы векторов ошибок\n')= [1,0,0,0,0,0,0;

0,1,0,0,0,0,0;

,0,1,0,0,0,0;

,0,0,1,0,0,0;

,0,0,0,1,0,0;

,0,0,0,0,1,0;

,0,0,0,0,0,1]

printf ('\n Тогда синдром ошибки будит иметь вид \n')

se=umn_bin_mat (re,Ht)

printf ('\n\n Программа закончила работу. ');

Программа для исследования помехоустойчивости линейного аддитивного блочного кода заданного вида синдромным методом

 

Студент группы 1B0

Крючков А.В.

Руководитель

Доцент кафедры СРС

В.А. Кологривов

 

 

Реферат

Пояснительная записка содержит: листов ____, источников 4, приложений 1, рисунков 1.

ИЗБЫТОЧНОСТЬ, ПОМЕХОУСТОЙЧИВОСТЬ, ЛИНЕЙНЫЙ КОД, БИНАРНАЯ МАТРИЦА, ПОРОЖДАЮЩАЯ МАТРИЦА, ПРОВЕРОЧНАЯ МАТРИЦА, СИНДРОМ ОШИБКИ, КОДИРОВАНИЕ, ДЕКОДИРОВАНИЕ, ВЕКТОР ОШИБОК, СУММИРОВАНИЕ ПО МОДУЛЮ 2, SCILAB

Работа посвящена закреплению навыков работы на персональном компьютере в средах Windows, SciLab и принципам аддитивного алгебраического кодирования и декодирования. Изучению основных элементов теории построения помехоустойчивости линейных блочных аддитивных алгебраических кодов и реализации одного из алгоритмов кодирования и декодирования.

Работа выполнена в среде SciLab. Результатом проделанной работы является реализация программного кода для исследования помехоустойчивости блочного аддитивного кода заданного вида.

Пояснительная записка выполнена в текстовом редакторе Microsoft Word 2010.

Содержание

1. Введение

2. Общие сведения о системе scilab

2.1 Возможности SciLab

3. Основы помехоустойчивого кодирования

3.1 Основные положения

3.2 Основные принципы

3.3 Линейные блочные коды

3.4 Порождающая и проверочная матрица

3.4.1 Порождающая матрица

3.4.2 Проверочная матрица

4. Синдромный метод

4.1 Синдром и обнаружение ошибки линейным блочным кодом

4.2 Синдромное декодирование линейных блочных кодов

5. Описание программы

5.1 Главная программа Kursovaya2. sci

5.2 Функция umn_bin_mat

6. Интерпретация результатов

7. Заключение

Список использованных источников

Приложения

Введение

 

Информация - это знания, это деньги, это возможность управления людьми, это власть. Невозможно переоценить роль и значение информации в современном обществе. Реализовать же заложенные в информации возможности можно обеспечив ее правильное использование или, говоря образно, движение. Для обеспечения этого “движения" человечеством созданы многообразные средства, регламентирующие и обеспечивающие возможность связи внутри общества. Виды этой связи чрезвычайно обширны, но, касаясь технической стороны вопроса и рассматривая связь как передачу информации на расстояние.

Рассмотрим принципы защиты от ошибок информации возникающих при ее передачи по каналам связи одним из известных способом.

Блоковые коды и методы их декодирования [1]:

·   Коды Хемминга

·   Коды Рида - Соломона

·   Мажоритарно декодируемые коды

·   Синдромный метод

·   Маркерный метод

В работе предлагается подробно рассмотреть принципы построения линейных блочных аддитивных алгебраических кодов и принципы их декодирования маркерным методом.

блочный код синдромный метод