Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования и науки РФ
Томский государственный университет систем управления и радиоэлектроники (ТУСУР)
Кафедра средств радиосвязи (СРС)
Пояснительная записка к курсовой работе по информатике
Программа для исследования помехоустойчивости линейного аддитивного блочного кода заданного вида синдромным методом
Студент группы 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. Введение
Информация - это знания, это деньги, это возможность управления людьми, это власть. Невозможно переоценить роль и значение информации в современном обществе. Реализовать же заложенные в информации возможности можно обеспечив ее правильное использование или, говоря образно, движение. Для обеспечения этого “движения" человечеством созданы многообразные средства, регламентирующие и обеспечивающие возможность связи внутри общества. Виды этой связи чрезвычайно обширны, но, касаясь технической стороны вопроса и рассматривая связь как передачу информации на расстояние.
Рассмотрим принципы защиты от ошибок информации возникающих при ее передачи по каналам связи одним из известных способом.
Блоковые коды и методы их декодирования [1]:
· Коды Хемминга
· Коды Рида - Соломона
· Мажоритарно декодируемые коды
· Синдромный метод
· Маркерный метод
В работе предлагается подробно рассмотреть принципы построения линейных блочных аддитивных алгебраических кодов и принципы их декодирования маркерным методом.
блочный код синдромный метод
SciLab - пакет прикладных математических программ, предоставляющий мощное открытое окружение для инженерных (технических) и научных расчётов [2].
Возможности 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)
Алгоритм декодирования с использованием проверочной матрицы сводиться к уравнению
, (4.1)
где r - принятый, возможно с ошибками, кодовый символ вектор-строка размерностью n;
s - синдром ошибки вектор-строка размерностью n - k.
При отсутствии ошибок приема, когда r = y, синдром ошибки представляет собой нулевой вектор. Наличие ошибки характеризуется не нулевым синдромом. При этом разным ошибкам соответствуют разные по значению синдромы, что позволяет опознавать и исправлять ошибку. Для двоичных кодов достаточно локализовать ошибку и сменить значение соответствующих битов на противоположные.
При передаче кодового слова x по каналу с шумом принятая последовательность будет иметь вид
. (4.2)
Некоторые сочетания ошибок, использую синдром, обнаружить невозможно. Например. Если переданное кодовое слово x под влиянием помех превратилось в другое кодовое слово этого же кода, тогда синдром будет равен нулю, декодер ошибки не обнаружит.
Рассмотрим, как можно использовать синдром принятого вектора не только для обнаружения, но и для исправления ошибок.
Пусть
, и
являются передаваемым кодовым словом, вектором ошибок и принятым вектором соответственно.
Тогда
(4.3)
и синдром
,
поскольку для любого кодового слова
(4.4)
Таким образом, синдром принятой последовательности r зависит только от ошибки, имеющий место в этой последовательности, и совершенно не зависит от переданного кодового слова.
Задача декодера, используя эту зависимость, определить элементы (координаты) вектора ошибок. Найдя вектор можно восстановить кодовое слово как
. (4.5)
Если место ошибки определенно, то устранить ее уже не представляет трудностей.
Функция Kursovaya2. sci является главной программой, содержащей в себе входные и выходные данные, стандартные функции и обращение к вспомогательным подпрограммам. Она отвечает за реализацию заданного алгоритма.
Работа: В программе заранее определены массив входных символов кодера и проверочную матрицу, а так же значение матрицы коэффициентов системы определяющих уравнений кодера, далее путём ее транспонирования получаем генерирующую матрицу кодера. Затем с помощью функции umn_bin_mat идёт кодирование входных символов и на выходе получаем массив кодовых символов. После чего с помощью той же функции umn_bin_mat но уже с использованием проверочной матрицы, получаем на выходе декодера массив вектор-строк синдромов ошибок для случая безошибочной передачи. Далее мы намеренно делаем ошибки в нескольких битах кодовых-символов, после чего находим для них синдромов. После чего формируем матрицу однократных ошибок с начального до конечного бита по главной диагонали и находим для них синдром ошибок.
Листинг главной программы смотри приложение А.
Заголовок: c=umn_bin_mat (a,b);
Входные параметры:
a, b - сопряжённые по размерностям бинарные матрицы.
Выходные параметры:
с - бинарная матрица, полученная путём умножения матриц a, b по модулю 2+
Назначение: Эта функция отвечает за формирования выходной матрицы путем перемножения входных матриц по модулю 2+.
Листинг подпрограммы функции umn_bin_mat. смотри приложение А.
Пусть даны
,,
Далее с помощью функции по формуле (3.4) получаем массив кодовых-символов
.
После чего находим массив вектор-строк синдромов ошибок по формуле (4.1) для случая без ошибочной передачи
.
Для случая ошибок в первых битах, тогда синдром ошибок примет вид
.
Для случая ошибок во вторых битах, тогда синдром ошибки примет вид
.
Для случая ошибок в третьих битах, тогда синдром ошибок примет вид
.
Сформируем матрицу однократных ошибок с 1-го по 7-ые биты и найдем синдром векторов ошибок
.
В результате проделанной работе были изучены основные возможности системы SciLab. Рассмотрен синдромный метод помехоустойчивого кодирования. Приведённый пример подтверждает работоспособность программы. Также получены дополнительные знания для работы с текстовым редактором Microsoft Word и изучены вузовские стандарты по оформлению курсовой работы. Система научных и инженерных расчетов SciLab может использоваться для различных видов научной и учебной деятельности.
1. Алексеев Е.Р. А47 Scilab: Решение инженерных и математических задач / Алексеев Е.Р., Чеснокова О.В., Рудченко Е.А. _ М.: ALT Linux; БИНОМ. Лаборатория знаний, 2008. - 260 с.: ил.; 8 с. цв. вклейки. (Библиотека ALT Linux).
2. Шульгин В.И. Основы теории передачи информации. Ч.1. Экономное кодирование. / В.И. Шульгин. - учебн. пособ. - Харьков: Нац. Аэрокосм. ун-т "Харьк. авиац. ин-т", 2003. - 196 с. (электр. версия).
. Шульгин В.И. Основы теории передачи информации. Ч.2. Помехоустойчивое кодирование/ В.И. Шульгин. - учебн. пособ. - Харьков: Нац. Аэрокосм. ун-т "Харьк. авиац. ин-т", 2003. - 87 с. (электр. версия).
. Кологривов В.А. Принцип аддитивного алгебраического кодирования и декодирования. / В.А. Кологривов. - учебн. - мет. пособ. - Томск: ТУСУР, 2010. - 102 с.
Приложение А
Листинг главной программы для исследования помехоустойчивости линейного аддитивного блочного кода заданного вида синдромным методом
// Курсовая работа Крючкова А.В. студента 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 Программа закончила работу. ');